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).