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}} \\ &= 2 + \frac{1}{1 + \frac{1}{\frac{5}{2}}} = 2 + \frac{1}{1 + \frac{1}{\frac{2\cdot 2 + 1}{2}}} \\ &= 2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{2}}} \\ &= [2, 1, 2, 2] \end{split} \end{equation*} このやり方から、分数を連分数に展開するには上のように分母と分子でユークリッド互除法をすればいいことが分かります。

主近似分数とは

実数\(\alpha\)を\(\alpha = [a_0, a_1, \cdots, a_n, \cdots]\)のように連分数展開したとします。ここで展開を途中で打ち切った値\([a_0, a_1 , \cdots, a_n]\)のことを主近似分数といいます。ここで攻撃の証明に必要な重要な定理を紹介します。

定理

\(\left| \alpha - \frac{p}{q} \right| < \frac{1}{2q^2}\)ならば、\(\frac{p}{q}\)は\(\alpha\)の主近似分数となる。

ここで\(p, q\)は既約分数です。この定理の証明にはまだ多くの議論を必要とするのでここではしませんm(_ _)m

Wiener's Attack

では目的の攻撃を説明していきます。

定理

\(N = pq\)かつ\(q < p < 2q\)とする。\(d < \frac{1}{3}N^{1/4}\)とすると、\(ed \equiv 1 \pmod{\varphi(N)}\)となる公開鍵\((e, N)\)から効率的に\(d\)を取り出せる。

証明

\(ed \equiv 1 \pmod{\varphi(N)}\)より\(ed - k\varphi(N) = 1\)となる\(k\)が存在します。よって、両辺を\(k\varphi(N)\)で割れば\[\left|\frac{e}{\varphi(N)} - \frac{k}{d} \right| = \frac{1}{d\varphi(N)}\]となります。また、\(\varphi(N) = (p - 1)(q - 1) = N - p - q + 1\)であることと、 \begin{equation*} \begin{split} p + q - 1 &< 2q + q - 1 \mbox{\(\quad [q < p < 2q\)より]}\\ &< 3q \\ &< 3\sqrt{N} \mbox{\(\quad [q^2 < N\)から \(q < \sqrt{N}\) となるため]} \\ \end{split} \end{equation*} より、\(|N - \varphi(N)| < 3\sqrt{N}\)となります。 \begin{equation*} \begin{split} \left| \frac{e}{N} - \frac{k}{d} \right| &= \left| \frac{ed - k\varphi(N) - kN + k\varphi(N)}{Nd} \right|\\ &= \left| \frac{1 - k(N - \varphi(N))}{Nd} \right| \\ &\leq \left| \frac{3k\sqrt{N}}{Nd} \right| \\ &= \frac{3k}{d\sqrt{N}} \end{split} \end{equation*} いま\(k\varphi(N) = ed - 1 < ed\)で\(e<\varphi(N)\)だから、仮定より\(k < d < \frac{1}{3}N^{1/4}\)であることを使うと、 \[\left| \frac{e}{N} - \frac{k}{d} \right| \leq \frac{1}{dN^{1/4}} < \frac{1}{2d^2}\]となります。前の定理よりこれで\(\frac{k}{d}\)が\(\frac{e}{N}\)の主近似分数であることが分かります。主近似分数は例で計算したようにユークリッド互除法と同じなので線形時間のアルゴリズムで計算できます。

Pythonによる計算

では実際にRSAの秘密鍵、公開鍵を作成してそれに対して攻撃をしてみたいと思います。素数として\(p = 110321, q = 101987\)とすると、\(N = pq = 11251307827\)、\(\varphi(N) = (p - 1)(q - 1) = 11251095520\)となります。 

>>> p = 110321
>>> q = 101987
>>> N = p*q
>>> N
11251307827
>>> (p - 1)*(q - 1)
11251095520
また、\(\frac{1}{3}N^{1/4} \approx 108.6\)なので、攻撃ができるように秘密鍵として\(d = 107\)とします。ではユークリッド互除法の関数を作って公開鍵\(e\)を生成します。 
def egcd(a, b):
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while b:
        q, r = a//b, a%b
        a, b = b, r
        a0, a1 = a1, a0 - q*a1
        b0, b1 = b1, b0 - q*b1
    gcd = a
    return gcd, a0, b0
スクリプトで以下のように実行すると 
>>> egcd(107, 11251095520)
(1, 1997858083, -19)
となり、公開鍵\(e = 1997858083\)を作ることができました。では次に主近似分数を作っていき、その中に秘密鍵\(d\)が現れることを確認します。 
def f(a, b):
    q, r = a//b, a%b
    a0, a1 = 1, q
    b0, b1 = 0, 1
    while r:
        a, b = b, r
        q, r = a//b, a%b
        a0, a1 = a1, a0 + q*a1
        b0, b1 = b1, b0 + q*b1
        print(b1)
この関数fは主近似分数の分母を表示していきます。スクリプトで\(e = 1997858083\)、\(N = 11251307827\)を入力すると以下のようになり、7行目に秘密鍵の107があることが分かると思います。 
>>> f(1997858083, 11251307827)
5
6
11
17
45
62
107
2737
5581
114357
119938
234295
354233
3776625
57003608
174787449
231781057
1101951677
11251307827

参考文献

Boneh, Dan (1999). Twenty Years of attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (2).

コメント

コメントを投稿

このブログの人気の投稿

RC4ストリーム暗号 in Python

はじめに 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] =
続きを読む

RSA暗号のしくみ

はじめに 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)\)
続きを読む