Wiener's attack 短い秘密鍵のRSA暗号への攻撃
はじめに ここでは短い秘密指数を持つ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}