公開鍵暗号 - RSA - Wiener's Attack

この記事では、RSA暗号への攻撃の中で恐らく最も有名であろうWiener's Attackについて取り上げる。多くは原論文を参考にしているが、証明の省略やアルゴリズムの一部改変等があるので、この記事を読んで氣になったのであればぜひとも原論文を読んで実際に実装してみて欲しい。

連分数

連分数とは、次の形で表される分数の一種である。

\[ \left. \cfrac{a_1}{q_1 + \cfrac{a_2}{q_2 + \cfrac{a_3}{\ddots\cfrac{}{q _ {m - 1} + \cfrac{a_m}{q_m}}}}}\right. = a_1/(q_1 + a_2/(q_2 + a_3/(\ldots/(q _ {m - 1} + a_m/q_m)))) \]

我々が興味があるのは、連分数の中でも \(a_i\)が全て1と等しいような連分数だ。扱いやすくするために、次のような表記を導入する。

\[ \langle q_0, q_1, \ldots, q_m \rangle = q_0 + 1/(q_1 + 1/(q_2 + 1/(\ \ldots/(q _ {m - 1} + 1/q_m)))) \]

例: \(\langle 0, 2, 1, 3 \rangle = 0 + 1/(2+1/(1+(1/3))) = \frac{4}{11}\)

有理数を連分数に展開することを連分数展開という。

fを連分数展開することはできた。では、\(\langle q_0, q_1, \ldots, q_m \rangle\)からfを復元することは可能だろうか? 先の式を見てもらえればわかるように、これは簡単だ。\(q_m\)から順に足して逆数を求めていくことを\(q_0\)まで繰り返せば良い。しかし、逆に\(q_0\)から順に求めていく方法はあるだろうか?\(n_i\)と\(d_i\)を次の式を満たすように定義する。

\[ \frac{n_i}{d_i} = \langle q_0, q_1, \ldots, q_m \rangle, \mbox{gcd}(n_i, d_i) = 1 \mbox{ for } i = 0, 1, \ldots, m \]

ここで、\(n_i, d_i\)はそれぞれ次のように表すことができる。

\[ \begin{align} n_0 &= q_0\\ n_1 &= q_0q_1 + 1\\ n_i &= q_i n _ {i-1} + n _ {i - 2}\ (\mathrm{for\ } i = 2, 3, \ldots, m.) \end{align} \]

\[ \begin{align} d_0 &= 1\\ d_1 &= q_1\\ d_i &= q_i d _ {i-1} + d _ {i - 2}\ (\mathrm{for\ } i = 2, 3, \ldots, m.) \end{align} \]

その上で、\(f = \frac{n_m}{d_m}\)とすることでfを復元することができる。

この時、面白いアルゴリズムが存在する。それは、ある数値fに対して\(f' = f(1-\delta)\)となるようなf'が存在し、\(\delta\)が十分小さい時に\(f'\)から\(f\)を求められるというもので、次のようにして計算される。なお、to_contfracは引数に与えられた数を連分数展開して\(\langle q_0, q_1, \ldots, q_m \rangle\)形式の配列で返す関数で、to_rationalは上で紹介した手法を用いて連分数から有理数へと変換する関数とする。

function reconstruct_f(f') {
  i ← 0
  q ← to_contfrac(f')
  while true {
    c ← to_rational(q[0], ..., q[i])
    if i is Even {
      if c Equals to_rational(q[0], q[1], ..., q[i-1], q[i]+1) {
        return c
      }
    } else if i is Odd {
      if c Equals to_rational(q[0], q[1], ..., q[i-1], q[i]) {
        return c
      }
    }
    i ← i + 1
  }
}

以上を踏まえて、Wiener's Attackを解説する。

Wiener's Attack

RSA公開鍵\( (e, n)\)と秘密鍵\(d\)があり、\(d\)が十分小さい時、公開鍵から\(d\)を復元することが出来る。

秘密鍵は次のように書くことが出来る。

\[ ed \equiv 1 \mod \phi(n) \]

これを書きなおして、

\[ ed = k\phi(n) + 1 \]

\(\phi(n) = (p-1)(q-1) = (n - p - q + 1)\)なので、

\[ \begin{align} ed &= k(n - p - q + 1) + 1\\ ed &= kn - kp - kq + k + 1\\ \frac{ed}{n} &= k(1-\delta) \ \ \ &\delta = \frac{p+q-1-\frac{1}{k}}{n}\\ \frac{e}{n} &= \frac{k}{d}(1-\delta) \end{align} \]

最後の式で出てきたk, dは\(\delta\)が十分に小さければ先ほど示したアルゴリズムによって求める事ができるので、dを求めることが出来る。*1素因数分解するのであれば先日の公開鍵暗号 RSA - Common Modulus Attack, 秘密鍵からの素因数分解 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいですで紹介した秘密鍵からの素因数分解手法を用いることでp, qを計算することが可能だ。

実装例

ここで、実装例であるpablocelayes/rsa-wiener-attackを見てみよう。ここでは、少しこれを変形したアルゴリズムが使用されている。該当部分はRSAwienerHacker.pyの以下の部分だ。

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

このアルゴリズムではfを求めるアルゴリズムを省き、総当りでk, dをチェックしていることに注意すれば、ほぼやっていることは同じだ。\(ed-1 \mod k\)が0になることは\(ed = k\phi(n)+1\)と同値であるため、この式で正しいdを選べているかどうかがわかる。その下にある式も展開すると、

\[ \begin{align} s &= n - \phi(n) + 1\\ &= pq - (pq - p - q + 1) + 1\\ &= p + q \end{align} \]

さらに、その下にある2次方程式

\[ \begin{align} x ^ 2 - sx + n &= 0\\ x ^ 2 - (p+q)x + pq &= 0\\ \end{align} \]

2次方程式は \((x-\alpha)(x-\beta) = x ^ 2 - (\alpha + \beta) x + \alpha\beta = 0\)のように表すことが出来るので、上の2次方程式の解は\(p, q\)である。よって、この2次方程式に整数解が2つ存在する時、正しくdを選択できたといえる。

参考文献/参考リンク

多少応用的だが、以下の論文も読むことをおすすめする。

*1:なお、原論文とは少し異なるアプローチをしていたり、値のチェックの省略がある。詳しくは原論文を参照。