暗号メモ

はじめに ここでは短い秘密指数を持つRSA暗号へのWienerの攻撃を紹介して、さらにPythonで実際に攻撃します。RSA暗号のべき乗剰余算は処理に時間がかかりますから、より高速な処理をする方法として鍵を小さくすることが考えられます。しかし、小さすぎると破られてしまうことがこの攻撃で分かります。しかもこの攻撃は公開鍵\((e, N)\)の情報だけで秘密鍵\(d\)を計算できる魅力的なものです。 攻撃の概要 RSA暗号の公開鍵\(e\)と秘密鍵\(d\)の間には\(ed \equiv 1 \pmod{\varphi(N)}\)という関係がありますから\(ed - k\varphi(N) = 1\)となる\(k\)が存在します。この攻撃は\(d\)が小さいとき(\(d<\frac{1}{3}N^{1/4}のとき\))に\(\frac{k}{d}\)が\(\frac{e}{N}\)の主近似分数になっているというものです。よって攻撃方法は\(\frac{e}{N}\)を連分数展開するだけです。 連分数とは 連分数とは以下のような形の分数をいいます。\[a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}\]これを\([a_0, a_1, a_2, \cdots]\)のように略記して書くことが多いです。では例として\(19/7\)という具体的な有理数をこの形に書き直してみたいと思います。19を7で割ると商と余りは2と5、すなわち\(19 = 7\cdot 2 + 5\)ですから以下のようになります。\[\frac{19}{7} = \frac{7\cdot 2 + 5}{7} = 2 + \frac{5}{7} = 2 + \frac{1}{\frac{7}{5}}\]以下このような計算を繰り返していきます。 \begin{equation*} \begin{split} 2 + \frac{1}{\frac{7}{5}} &= 2 + \frac{1}{\frac{5\cdot 1 + 2}{5}} = 2 + \frac{1}{1 + \frac{2}{5}

はじめに 高校の物理で\(\mbox{運動エネルギー} + \mbox{位置エネルギー} = \mbox{一定}\)というのを習ったと思います。ここでは保存力場でこの法則が成り立つことを証明したいと思います。 保存力場とは？ ベクトル場\(a\)に対して\(a = -\mathrm{grad}f\)を満たすスカラー場\(f\)が存在するとき、\(f\)をスカラーポテンシャル、\(a\)を保存力場といいます。 スカラー場とは 空間内の集合\(D\)の各点\(P\)において実数値\(f(P)\)が定まっているとき、\(f\)を\(D\)のスカラー場といいます。例えば、高さ、電位や密度などを決める関数はスカラー場と言えます。 ベクトル場とは 集合\(D\)の各点\(P\)においてベクトル\(a(P)\)が定まっているとき、\(a\)を\(D\)のベクトル場といいます。例えば、電場や磁場などがそう言えます。 \(\mathrm{grad}とは\) \(\mathrm{grad}f = (\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z})\) 例として、電場が保存力場であること（スカラーポテンシャル\(f\)を持つこと）を示しておきます。原点\(O\)に点電荷\(q\)を置いたとします。\(O\)を除いた領域\(D\)の点\(P\)に点電荷を置いたとき、この点電荷に働く電場\(E\)はクーロンの法則により \begin{equation*} \begin{split} E &= k\frac{q}{|\vec{OP}|^2}e \mbox{\(\quad\)[eは\(\vec{OP}\)方向の単位ベクトル]} \\ &= k\frac{q}{|\vec{OP}|^2}\frac{

はじめに RC4は1987年にRon Rivestによって作られました。1994年にアルゴリズムがリークされ、WEPやWPA（WI-FIで見たことありませんか？）で使われています。この暗号はとっても短いコードで書くことがでるので、誰でも簡単なRC4のおもちゃが作れると思います。ここでは、RC4をpythonで簡単に作ってみたいと思います。 RC4のしくみ RC4は2つのパートKSA(Key-scheduling algorithm)とPRGA(Pseudo-random generation algorithm)から構成されています。KSAはランダムな鍵(40～256bit)で\(S = [0, 1, ..., N - 1]\)を初期化し、PRGAはそのSを使って疑似乱数を生成します。この生成された疑似乱数と平文のxorを取っていくことで暗号化をします。以下に疑似コードを書いておきます。 KSA(K) Initialization: For i = 0 ... N - 1 swap S[i] = i j = 0 Scrambling: For i = 0 ... N - 1 j = j + S[i] + K[i mod l] Swap(S[i], S[j]) PRGA(S) Initialization: i = 0 j = 0 Generation loop: i = i + 1 j = j + S[i] Swap(S[i], S[j]) Output z = S[S[i] + S[j]] 上の疑似コードをPythonにしてRC4を作ります。 def KSA(key): l = len(key) S = list(range(256)) j = 0 for i in range(256): j = (j + S[i] + key[i % l]) % 256 S[i], S[j] =

はじめに Bloggerでの投稿練習にRSA暗号の仕組みを紹介してみたいと思います。 仕組み自体は簡単なのでググったら沢山でてきますが、実際は多くの攻撃があり素人が簡単に実装をできるものではありません。それに読み物としての記事が多くて素数の生成 はどうやるのか～など具体的に書いてなくて困ると思います。 その辺もどんな感じのアイデアを使ってるのか面白く書いてみたいと思いますので是非読んでみてください(^^)/ 仕組み まず、大きな素数（最近は2048bit）\(p, q\)を作り、\(N = pq\)とします。次に、\(\varphi(N)\)と互いに素な数\(e\)を作ります。\(ed \equiv 1 \pmod{\varphi(N)}\)となるように\(d\)を決めて\((e, N)\)を公開鍵、\((d, N)\)を秘密鍵とします。ここで\(\varphi\)はオイラーの\(\varphi\)関数で\(\varphi(N) = (p - 1)(q - 1)\)となります。 modの意味 \(a \bmod{b}\)は\(a\)を\(b\)で割った余りという意味です。 \(a \equiv b \pmod{N}\)は\(a\)を\(N\)で割った余りと\(b\)を\(N\)で割った余りが等しいという意味で、これは\(a - b = kN\)となる\(k\)があることと同じ意味です。 \(ed \equiv 1 \pmod{\varphi(N)}\)なら\(ed - k\varphi(N) = 1\)となるので、ユークリッド互除法で\(e\)から\(d\)を求めることができます。 オイラーの\(\varphi\)関数 \(\varphi(N) = \mbox{1からNまでで互いに素な数の個数}\)のことです。 例えば\(\varphi(8) = 4\)、\(\varphi(13) = 12\)となります。 \(p, q\)を素数とすると、\(\varphi(pq) = (p - 1)(q - 1)\)