サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
ブラックフライデー
elliptic-shiho.hatenablog.com
はじめに この記事はセキュリティ・キャンプ全国大会 2023のLT大会で発表した以下のスライドを解説するものです. このときは5分程度しかなかったのでまともに解説できなかった. なんか色々書いていたら9000文字を越えてしまったので, 暇なときにつまみ読んでもらえればと思います. https://elliptic-shiho.github.io/slide/Playing_with_TPM.pdf この記事は少し砕けた形で書いてみようかと思いますが, 普段硬い文章ばかり書いているので読みづらいかもしれません. その点ご容赦ください. あとやたら長い. 前提としては「認証と認可の違い」「応用情報処理程度のPKIの知識」あたりがあるとわかりやすいと思います. TPMとは 皆さんTPM使ってますか? Windows 11へのアップグレード時にお世話になるあれです1. TPMという単語はTrust
この記事は CTF Advent Calendar 2016 - Adventar の22日目の記事です. 21日目の記事は@nolzeさんの どのCTFに出たらいいか分からない人のためのCTF年表 (2016年版) - A602 です. 多表式暗号の解読ではカシスキー・テストを用いた解読法がよく知られているが, 実はFriedman Testと呼ばれる一致指数(Index of coincidence)を用いた方法がこれとは別に存在し, (精度は劣るものの)カシスキー・テストよりも単純な計算で鍵長を推測することができる. この記事では, 一致指数を用いて多表式暗号を解読する手法をVigenere暗号に対して解説した後CTF(Capture the Flag)の暗号カテゴリの過去問題を実際に解いてみる. この記事では通して英語を平文にもつことを仮定するが, 他の言語でも同様に解読が可能であ
本記事では中国剰余定理(Chinese Reminder Theorem, CRT)1について解説する. 数学的な定義や意義について触れた後, 応用例としてRSA-CRT, Multi-Prime RSA, そしてPohlig-Hellman Attackについて述べる. 前提知識として, 簡単な初等整数論・群・環の言葉を知っていることが望ましい. 注: 本記事は2021/03/02に全面的に書き直された. レビューありがとうございます: @kimiyuki_u CRT 準備 まず, 本節でしばしば利用される定理である以下について述べる. Thm. 0. 任意の非零自然数$a, b$に対し, 整数$x, y$が存在して, $ax + by = \gcd(a, b)$をみたす. この定理における$(x, y)$は存在性を示すのみならず$(a, b)$から具体的に計算することが可能であり, そ
この記事では比較的新しい、かつ珍しい加法準同型性を持つPaillier暗号について解説する。 Paillier暗号とは、Pascal Paillierによって1999年に発明された公開鍵暗号で、素因数分解を安全性の根拠としている。この暗号は、メッセージ\(Enc(m_1), Enc(m_2)\)からそれらを足し合わせた暗号文を作ることができるという性質を持っている。これを加法準同型性といい、暗号の中でも非常に少ない(乗法準同型性は他にもRSA, Elgamal等に見られる)、珍しい暗号である。 鍵の生成 2つの大きな素数\(p, q\)をランダムに選択し、\(n = pq\)を計算する。 \(k\in\mathbb{Z} _ n\)をランダムに選び、\(g = (kn+1) \mod n ^ 2\)を計算する。 公開鍵を\( (n, g) \)、秘密鍵を\( (p, q) \)とする。 暗
RSAにはいくつもの攻撃手法が存在する。その中から、Common Modulus Attackと秘密鍵dからnを素因数分解することを取り上げる。 Common Modulus Attack RSAの教科書にも載るようなわかりやすく、簡単な攻撃で、次のように定義される。 RSA公開鍵\((n, e_1)\), \((n, e_2)\)と平文\(m\)、それぞれの公開鍵で暗号化した暗号文\(c_1, c_2\)があり、\(\mathrm{gcd}(e_1, e_2) = 1\)の時、\(n, e_1, e_2, c_1, c_2\)から平文\(m\)を導出することができる。 証明: \( \begin{align} c_1 &= m ^ {e_1} \mod n\\ c_2 &= m ^ {e_2} \mod n\\ \end{align} \) ここで、\(e_1s_1 + e_2s_2 =
Vigenere暗号は非常に強力な暗号だった。その強力さと汎用さから、いくつかの派生暗号が知られている。ここでは、その中から2つ取り出して書いてみようと思う。 Autokey暗号 Autokey暗号は、Vigenere暗号にストリーム暗号の要素を加えた暗号と言える。以下に暗号化/復号処理を示す。 暗号化 最初に、鍵を一つ決める。これは長さに特に制限は無い。ここではDJAUTOとする。 平文をここではAUTOKEY CIPHER IS VIGENEREという文字列にする。この時、次のようにして暗号化処理が行われる。 まずは普通にキーの長さと同じだけ暗号化する。DJAUTOは6文字なので、AUTOKEまでを暗号化してDDTIDSとなる。 次に、ここで暗号化した平文を鍵として再利用する。ここでは、AUTOKEを鍵として利用し、次のY CIPHEを暗号化する。暗号化された結果はB LIJASとなる
2018/10/22 全体的に問題があったので書き直した. 内容はほぼ変わっていない. 本記事では, 世界で最初に提案された公開鍵暗号であるRSA暗号の基礎事項について解説する. RSA暗号の動作原理について示した後, 簡単な攻撃手法の一覧を載せる. 公開鍵暗号 暗号理論, 特に現代暗号における暗号は「秘密鍵暗号(Secret-key Cipher)」, 「公開鍵暗号(Public-key Cipher)」の2種類に大分される. 秘密鍵暗号はよく知られている通り「秘密の鍵$k$を事前に共有しておき, その鍵を用いて暗号化・復号を行う暗号方式」である. これに対して公開鍵暗号は「暗号化に用いる鍵$k _ {enc}$, 復号に用いる鍵$k _ {dec}$が存在し, 暗号化・復号のそれぞれで異なる鍵を用いる暗号方式」と定義され, このうち$k _ {enc}$は一般に公開されることが多いこと
この記事は古典暗号の中でも複雑で解読しにくいとされている多表式換字式暗号であるVigenere暗号と、多くの場合に効果的な解読法であるカシスキー・テストを理解することを目標に書く。 Vigenere暗号 Vigenere暗号は頻度分析が発達し単一換字式暗号がある程度簡単に破られるようになってきた頃に発明された。名前は最終的な発明者であるBlaise de Vigenèreの名を取っている。(便宜上VigenèreではなくVigenereと書いているが、正しいのはVigenèreである。) 古典的な見方 この暗号は、多表式換字式暗号の形を取っている。そのため、同じ文字でも場所が違えば違う文字に暗号化される。 最初に、暗号鍵を決める。これはアルファベットであれば何でも良いが、安全性のためにはできるだけ長い方がよい。また、暗号鍵は平文の大きさに合わせて繰り返して使う。例えばCTFという暗号鍵を長
TL;DR セグメント木とは, ある半開区間の圏表現$\mathbb{I}$から何らかの圏$C$への関手$F$である. セグメント木の一点・多点更新クエリとは自然変換である. セグメント木という呼称はあくまで関手の計算グラフのとり方によるものであって, Sparse Table等の(列を計算するための)手法も, 基本的には統一した観点で見ることができる. はじめに 本記事は「高速計算可能な区間クエリとはどのようなものか」へと圏論的なモデルを与える. 特にセグメント木にフォーカスしているが, [2]における議論を前提とするならば, 本記事の内容はSparse Tableや累積和にも一般化可能であるはずである. ただしそれらに対しては未証明の部分が大きい. もともとは先日公開した論文[4]における議論から発展したものであるが, @convexineq氏によって計算機科学的視点からのセグメント木
このページを最初にブックマークしてみませんか？
『₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
