RSA

公開鍵暗号 - RSA - Wiener's Attack - ₍₍ (ง ˘ω˘ )ว ⁾⁾
この記事では、RSA暗号への攻撃の中で恐らく最も有名であろうWiener's Attackについて取り上げる。多くは原論文を参考にしているが、証明の省略やアルゴリズムの一部改変等があるので、この記事を読んで氣になったのであればぜひとも原論文を読んで実際に実装してみて欲しい。 連分数 連分数とは、次の形で表される分数の一種である。 [ left. cf…
リンク
elliptic-shiho.hatenablog.com



₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです
読者になる

2015-12-18
公開鍵暗号 - RSA - Wiener's Attack
攻撃 公開鍵暗号

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

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

a1q1+a2q2+a3⋱qm−1+amqm=a1/(q1+a2/(q2+a3/(…/(qm−1+am/qm))))
我々が興味があるのは、連分数の中でも ai

が全て1と等しいような連分数だ。扱いやすくするために、次のような表記を導入する。

⟨q0,q1,…,qm⟩=q0+1/(q1+1/(q2+1/( …/(qm−1+1/qm))))
例: ⟨0,2,1,3⟩=0+1/(2+1/(1+(1/3)))=411

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

fを連分数展開することはできた。では、⟨q0,q1,…,qm⟩

からfを復元することは可能だろうか?先の式を見てもらえればわかるように、これは簡単だ。qmから順に足して逆数を求めていくことをq0まで繰り返せば良い。しかし、逆にq0から順に求めていく方法はあるだろうか?niとdi
を次の式を満たすように定義する。

nidi=⟨q0,q1,…,qm⟩,gcd(ni,di)=1 for i=0,1,…,m
ここで、ni,di

はそれぞれ次のように表すことができる。

=q0
=1
その上で、f=nmdm

とすることでfを復元することができる。

この時、面白いアルゴリズムが存在する。それは、ある数値fに対してf′=f(1−δ)

となるようなf'が存在し、δが十分小さい時にf′からfを求められるというもので、次のようにして計算される。なお、to_contfracは引数に与えられた数を連分数展開して⟨q0,q1,…,qm⟩
形式の配列で返す関数で、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≡1modϕ(n)
これを書きなおして、

ed=kϕ(n)+1
ϕ(n)=(p−1)(q−1)=(n−p−q+1)

なので、

=k(n−p−q+1)+1
最後の式で出てきたk, dはδ

が十分に小さければ先ほど示したアルゴリズムによって求める事ができるので、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−1modk

が0になることはed=kϕ(n)+1
と同値であるため、この式で正しいdを選べているかどうかがわかる。その下にある式も展開すると、

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

=0
2次方程式は (x−α)(x−β)=x2−(α+β)x+αβ=0

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