はじめに
RSA暗号に対する攻撃の1つ「Wiener's Attack」の仕組みを勉強し、pythonで実装するまでの過程をアウトプット用に記事にしてみた。Wiener's Attackの論文 (https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf) は1989年に出ており、決して目新しい攻撃ではないが、
- 自分用のアウトプットとしての意味がある点
- Qiitaにはこのような記事があまり見られない点
から、少なくとも意味がないわけではないだろうと思い、書いてみた。ただし、あくまで個人的なアウトプットの域を出ないため、
- 本記事のコードや説明が間違っている可能性がある点
- コードの書き方が悪い可能性がある点
は、大目に見ていただきたい。
連分数の記法
文字の置き方を含め、極力元の論文と同じ記法を用いる。
Wiener's Attackは連分数を用いた攻撃であるため、連分数を記述するための記法を導入する。
$$
\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)\ldots)))
$$
latexで$q_m$の部分を記述するのが難しいので分数を/で表記したが、要するに
$$
\langle q_0, q_1, \ldots, q_m \rangle :=q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \ldots}}
$$
で、最後の部分が$\frac{1}{q_{m-1} + \frac{1}{q_m}}$ということである。
連分数のクラスをpythonで実装した。また、有理数から連分数へ変換するユーティリティ関数も実装した。
import math
from fractions import Fraction
class ContinuedFraction:
def __init__(self, q: list):
# m >= 1において、q_m >= 2を満たすため。
if len(q) != 1 and q[-1] == 1:
q = q[:-1]
q[-1] += 1
self._q = q
self._nest = len(q) - 1
@property
def q(self):
return self._q
@property
def nest(self):
return self._nest
def __str__(self):
output_list = ["<"]
for q_i in self.q:
output_list.append(str(q_i))
output_list.append(",")
output_list[-1] = ">"
return "".join(output_list)
def inv(f: Fraction):
return Fraction(f.denominator, f.numerator)
def fraction_to_continued(f: Fraction):
q_0 = math.floor(f)
q = [q_0]
previous_r_i = f - q_0
while previous_r_i != 0:
inv_previous_r_i = inv(previous_r_i)
q_i = math.floor(inv_previous_r_i)
previous_r_i = inv_previous_r_i - q_i
q.append(q_i)
return ContinuedFraction(q)
また、連分数から有理数への変換もしておきたい。一般に、連分数をi段目まで展開したときの表記を
$$
\frac{n_i}{d_i} = \langle q_0, q_1, \ldots, q_i \rangle, GCD(n_i, d_i) = 1
$$
としたとき、次の漸化式が知られている。
$ n_0 = q_0, d_0 = 1 $
$ n_1 = q_0q_1 + 1, d_1 = q_1 $
$ n_i = q_in_{i-1} + n{i-2}, d_i = q_id_{i-1} + d_{i-2} (i \ge 2)$
この漸化式を利用し、連分数→有理数への変換を実装した。
def continued_to_fraction(f: ContinuedFraction):
q = f.q
nest = f.nest
n_0 = q[0]
d_0 = 1
if nest == 0:
return Fraction(n_0, d_0)
n_1 = q[0] * q[1] + 1
d_1 = q[1]
if nest == 1:
return Fraction(n_1, d_1)
n_i_minus_2 = n_0
n_i_minus_1 = n_1
d_i_minus_2 = d_0
d_i_minus_1 = d_1
n_i = None
d_i = None
# nest=len(q) - 1であるため
for i in range(2, nest+1):
n_i = q[i]*n_i_minus_1 + n_i_minus_2
d_i = q[i]*d_i_minus_1 + d_i_minus_2
n_i_minus_2, n_i_minus_1 = n_i_minus_1, n_i
d_i_minus_2, d_i_minus_1 = d_i_minus_1, d_i
return Fraction(n_i, d_i)
テストをしてみたが、概ね正しいだろう。
f = Fraction(4, 11)
c = fraction_to_continued(f)
print(c)
print(continued_to_fraction(c))
<0,2,1,3>
4/11
Continued Fraction Algorithm
元論文で「Continued Fraction Algorithm」と称されている有用なアルゴリズムについて書く。アルゴリズムの主張は以下である。
Continued Fraction Algorithm
有理数$f$に対して、次のように$f'<=f$である$f'$を定める。
$f' = (1 - \delta)f$
ただし、$\delta \ge 0$で、$\delta$は十分に小さいとする。
このとき、未知である$f$の分母・分子を、既知の$f'$から高速に計算できる。
ここで、十分に小さい$\delta$は、不等式
$$ \delta < \frac{1}{\frac{3}{2}n_md_m} $$
で定められる。ただし、$f=\frac{n_m}{d_m}$である。
このアルゴリズムの手順は以下である。ただし、$f'=\langle q'_0, q'_1, \ldots \rangle$と展開できるとする。
- $f$が見つかるまで、$i=0, 1, \ldots$に関してループする。
- 漸化式を用いて、
$i$が偶数の場合、$\langle q'_0, q'_1, \ldots, q'_i + 1 \rangle$
$i$が奇数の場合、$\langle q'_0, q'_1, \ldots, q'_i \rangle$
と等しい有理数を計算する。- 2で生成した有理数がfと等しいか検証する。
RSA暗号への適用
RSA暗号で、$e$と$d$に関する合同式
$$
ed \equiv 1 \mod LCM(p-1, q-1)
$$
がある。
だいぶ端折ってしまうが、この式から変形すると次のようになる。詳しい式変形は元論文を参照。
$$
\frac{e}{pq} = \frac{k}{dg}(1-\delta)
$$
ただし、$k$、$g$は互いに素なある整数であり、
$$\delta=\frac{p+q-1-\frac{g}{k}}{pq}$$
である。
RSA暗号において、$e$と$pq(=N)$は公開鍵のため攻撃者に既知である。
Continued Fraction Algorithmの式と見比べると、$f'=\frac{e}{pq}$が既知で、$f=\frac{k}{dg}$が求めたいものであることから、この式にContinued Fraction Algorithmを適用することで、$k$、$dg$を求めることができる。
このアルゴリズムを実装する前に、計算して出た有理数が$f$と等しいかどうか検証する仕組みを実装する必要がある。よって、その検証について考える。
答えの検証
$e$、$d$の式を変形すると
$$
edg = k(p-1)(q-1) + g
$$
となる。ただし、$k$と$g$は先と同じもの。
アルゴリズムによって$k$、$dg$の値が出力されるが、それが正しいかどうかの検証をこの式から考える。
まず、$edg$は計算できる。値が正しければ$k$と$g$は互いに素より$edg$を$k$で割った余りは$g$となる。しかし、もし$edg$をkで割った余りが0ならば値は正しくないと判断できる。
また、$edg$を$k$で割った商が$(p-1)(q-1)$であるため、$(p-1)(q-1)$の予測が立てられる。
これまでの値より
$$
\frac{pq-(p-1)(q-1)+1}{2} = \frac{p+q}{2}
$$
が構成できるが、もしここで$\frac{p+q}{2}$の値が整数でなければ値は正しくない。
また、
$$
(\frac{p+q}{2})^2 - pq = (\frac{p-q}{2})^2
$$
より、$(\frac{p-q}{2})^2$の値の予測が立てられるが、もし$(\frac{p-q}{2})^2$の予測値が平方数であれば、$k$、$dg$の値が正しかったことになる。
以上より
$$
\frac{p+q}{2}, \frac{p-q}{2}
$$
の正しい値が判明するが、この2つの値より容易に$p, q$を構成することができる。
$p, q$が構成出来たらそれを返し、出来なければ$(-1, -1)$を返す関数を実装した。
def calc_p_q_orelse(k, dg, e, n):
if (e*dg) % k == 0:
return -1, -1
phi = e*dg // k
if (n - phi + 1) % 2 != 0:
return -1, -1
X = (n - phi + 1) // 2
Y2 = X*X - n
if Y2 < 0:
return -1, -1
Y = math.isqrt(Y2)
if Y*Y != Y2:
return -1, -1
return X+Y, X-Y
Wiener's Attackの実装
Continued Fraction Algorithmを素直に実装すればよい。
def wieners_attack(e, n):
f_prime = Fraction(e, n)
f_prime_continued = fraction_to_continued(f_prime)
for i in range(f_prime_continued.nest+1):
new_q = f_prime_continued.q[:i+1]
if i % 2 == 0:
new_q[-1] += 1
new_continued_fraction = ContinuedFraction(new_q)
new_fraction = continued_to_fraction(new_continued_fraction)
k = new_fraction.numerator
dg = new_fraction.denominator
p, q = calc_p_q_orelse(k, dg, e, n)
if p != -1 and q != -1:
return p, q
return -1, -1
実際に問題を解いてみる
ångstromCTF 2021 sosig
参考URL: https://zenn.dev/fiord/articles/49c843823f70d3b6e91b
from Crypto.Util.number import *
n = 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853
e = 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799
c = 13067887214770834859882729083096183414253591114054566867778732927981528109240197732278980637604409077279483576044261261729124748363294247239690562657430782584224122004420301931314936928578830644763492538873493641682521021685732927424356100927290745782276353158739656810783035098550906086848009045459212837777421406519491289258493280923664889713969077391608901130021239064013366080972266795084345524051559582852664261180284051680377362774381414766499086654799238570091955607718664190238379695293781279636807925927079984771290764386461437633167913864077783899895902667170959671987557815445816604741675326291681074212227
p, q = wieners_attack(e, n)
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(f"p: {p}")
print(f"q: {q}")
print(long_to_bytes(pow(c, d, n)).decode())
p: 128492410950654872001754818372751471227090063855833681574938088880503157691538748201946630518213794418274696316199318770451524663771258425569832321955651721320572306775923895573430031233522425368323141762665857788148189517919670087870657927204463889670604784945106039367955599815202555170174030185574626093699
q: 114793289992568105259243952247810662219227283817412230700343905680426540175503049211790228524234722231480483290184285517008546908588534934976456806645370618468232506120632142533312406493650231725291499768631732343302501728812874256317928494857305947135683846349816655828497281995629123361154466482144256790047
actf{d0ggy!!!111!1}
ちゃんと解けた。頑張って実装したので結構嬉しかったりする。
感想
論文を読む→実装するというプロセスを初めてまともに出来たので、達成感が大きかった。Wiener's Attackの論文が読みやすいのもあったと思う。
今後、CTFにおいてはCryptoに焦点を当てて勉強したいと考えているので、他の攻撃手法についてもこのように学んでいきたい。
全体のコード
コードの行数を数えてみたら、126行だった。自分はあまり実装が上手くないので、冗長な部分があるかもしれないが、わかりやすい実装を心掛けた。
この実装をした後に、他のひとの実装(https://github.com/orisano/owiener/blob/master/owiener.py) も見てみたが、自分の実装より高速な上に短く書かれていて、このようなコードを書きたいなと思った。
import math
from fractions import Fraction
# 連分数
class ContinuedFraction:
def __init__(self, q: list):
if len(q) != 1 and q[-1] == 1:
q = q[:-1]
q[-1] += 1
self._q = q
self._nest = len(q) - 1
@property
def q(self):
return self._q
@property
def nest(self):
return self._nest
def __str__(self):
output_list = ["<"]
for q_i in self.q:
output_list.append(str(q_i))
output_list.append(",")
output_list[-1] = ">"
return "".join(output_list)
def inv(f: Fraction):
return Fraction(f.denominator, f.numerator)
def fraction_to_continued(f: Fraction):
q_0 = math.floor(f)
q = [q_0]
previous_r_i = f - q_0
while previous_r_i != 0:
inv_previous_r_i = inv(previous_r_i)
q_i = math.floor(inv_previous_r_i)
previous_r_i = inv_previous_r_i - q_i
q.append(q_i)
return ContinuedFraction(q)
def continued_to_fraction(f: ContinuedFraction):
q = f.q
nest = f.nest
n_0 = q[0]
d_0 = 1
if nest == 0:
return Fraction(n_0, d_0)
n_1 = q[0] * q[1] + 1
d_1 = q[1]
if nest == 1:
return Fraction(n_1, d_1)
n_i_minus_2 = n_0
n_i_minus_1 = n_1
d_i_minus_2 = d_0
d_i_minus_1 = d_1
n_i = None
d_i = None
# nest=len(q) - 1であるため
for i in range(2, nest+1):
n_i = q[i]*n_i_minus_1 + n_i_minus_2
d_i = q[i]*d_i_minus_1 + d_i_minus_2
n_i_minus_2, n_i_minus_1 = n_i_minus_1, n_i
d_i_minus_2, d_i_minus_1 = d_i_minus_1, d_i
return Fraction(n_i, d_i)
def calc_p_q_orelse(k, dg, e, n):
if (e*dg) % k == 0:
return -1, -1
phi = e*dg // k
if (n - phi + 1) % 2 != 0:
return -1, -1
X = (n - phi + 1) // 2
Y2 = X*X - n
if Y2 < 0:
return -1, -1
Y = math.isqrt(Y2)
if Y*Y != Y2:
return -1, -1
return X+Y, X-Y
def wieners_attack(e, n):
f_prime = Fraction(e, n)
f_prime_continued = fraction_to_continued(f_prime)
for i in range(f_prime_continued.nest+1):
new_q = f_prime_continued.q[:i+1]
if i % 2 == 0:
new_q[-1] += 1
new_continued_fraction = ContinuedFraction(new_q)
new_fraction = continued_to_fraction(new_continued_fraction)
k = new_fraction.numerator
dg = new_fraction.denominator
p, q = calc_p_q_orelse(k, dg, e, n)
if p != -1 and q != -1:
return p, q
return -1, -1