Wiener's Attackをやってみたい

はじめに

RSAに対する攻撃のひとつに、Wiener's Attackというものがあります。秘密鍵$d$が小さい場合に有効な攻撃で、公開鍵$(e,N)$から$d$を求められます。$e$と$d$は$ed \equiv 1 \pmod{\phi(N)}$という関係になるので、$e$が大きいときにWiener's Attackを考えてみるとよいかもしれません。

今回は、Wiener's AttackをPythonで実装し、CTFの問題をひとつだけ解いてみます。

※注意
・🐺が勉強としてやっているだけなので、参考程度に見てください。
・この記事は予告なく加筆・修正される場合があります

連分数と主近似分数

本題の前に、Wiener's Attackで必要な連分数と主近似分解を勉強しておきます。

連分数

次のような形の分数を有限正則連分数といい、$[a_0,a_1,a_2,\cdots,a_m]$と表すことにします。以降では、これを連分数と表記します。

$$a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\cdots + \frac{1}{a_m}}}}$$

有理数は連分数に変形でき、この操作を連分数展開といいます。分子と分母でユークリッド互除法をすることで、連分数展開ができます。

Pythonで書くとこんな感じです。

def continued_fraction(numerator, denominator):
    a = []
    while denominator != 0:
        a.append(numerator // denominator)
        numerator, denominator = denominator, numerator % denominator
    return a

主近似分数

ある有理数の連分数が$[a_0,a_1,a_2,\cdots,a_i,\cdots,a_m]$となるとき、この連分数展開を途中で止めた$[a_0,a_1,a_2,\cdots,a_i]$を主近似分数といいます。

主近似分数を$\frac{n_i}{d_i}$とすると、$n_i, d_i$はそれぞれ次のような漸化式で表せます。

$$\begin{aligned} n_0 &= a_{0}, d_{0}=1 \\ n_1 &= q_{0}q_{1}+1, d_{1}=q_{1} \\ n_i &= a_{i}n_{i-1}+n_{i-2}, d_{i}=a_{i}d_{i-1}+d_{i-2}\ (0 \le i \le m) \end{aligned}$$

Pythonで書くとこんな感じでしょうか。もっときれいに書けると思います。

def convergent(a):
    if len(a) == 1:
            return [a[0], 1]
    else:
        numerator = [a[0], a[0] * a[1] + 1]
        denominator = [1, a[1]]
        for ai in a[2:]:
            numerator[0], numerator[1] = numerator[1], ai * numerator[1] + numerator[0]
            denominator[0], denominator[1] = denominator[1], ai * denominator[1] + denominator[0]
        return [numerator[1], denominator[1]]

Wiener's Attack

Wiener's Attackの概要は、次のとおりです。証明や細かい部分は省略です。

$ed \equiv 1 \pmod{\phi(N)}$は、ある整数$k$を使って$ed=k\phi(N)+1$ ($k$は整数)と表せます。$\phi(N)=(p-1)(q-1)$なので、さらに変形して

$$\frac{e}{N}=\frac{k}{d}(1-\frac{p+q-1-\frac{1}{k}}{N})$$

とできますね。このとき、$\frac{k}{d}$は$\frac{e}{N}$の主近似分数となります。つまり、$\frac{e}{N}$の主近似分数を順に求めていくと、どこかの分母に$d$が出てくるということです。主近似分数を求めるには連分数展開をすればよかったので、$\frac{e}{N}$を連分数展開すれば$d$を求められます。
「$d$が十分に小さければ」についてですが、具体的には$d<\frac{1}{3}N^{\frac{1}{4}}$を満たせばよいようです。

$d$が求まれば、あとは復号するだけです。

Pythonで書くとこんな感じでしょうか。

def wieners_attack(e, n, ciphertext):
    a = continued_fraction(e, n)
    for i in range(1, len(a)):
        d = convergent(a[:i])[1]
        plaintext = pow(ciphertext, d, n)

Wiener's Attackをやってみる

picoCTFのDachshund Attacksという問題で、Wiener's Attackを試してみます。

What if d is too small? Connect with nc mercury.picoctf.net <port>.

サーバーに接続すると、以下が返ってきました。値は毎回ランダムだと思います。

Welcome to my RSA challenge!
e: 3846582932094138670737803938414796713679435711725169825618120939640784756281021057979867177337648475194149178180826281891186597855460221101473830844245495056223825784612496649386073390647133650789532627594972296466867552340022699080521464921132856671527228254340523458328461393677080171279088822105975506903
n: 70861126339548340474936494619069547448424050796813825952036436631153413936055258391649966432711723695888900938754493610447663393238312465839015505246321495831762104278977040349052253235242620371462847923499781205742904214331373434624452480835097664782698117019349993151498367979837258031362183332399991416733
c: 55469722241081357826973887676929862529368522341023811436532743070567838422833905386772399024818323692140894477722066663139078140159046999485248928742381395519929718645892977843383261578753034393923486085895187431756580218772832833603003578432969666897842341628709060787099421106901157283422281293916970628678

$e$が大きいので、Wiener's Attackをやってみます。

from Crypto.Util.number import long_to_bytes

def continued_fraction(numerator, denominator):
    a = []
    while denominator != 0:
        a.append(numerator // denominator)
        numerator, denominator = denominator, numerator % denominator
    return a

def convergent(a):
    if len(a) == 1:
            return [a[0], 1]
    else:
        numerator = [a[0], a[0] * a[1] + 1]
        denominator = [1, a[1]]
        for ai in a[2:]:
            numerator[0], numerator[1] = numerator[1], ai * numerator[1] + numerator[0]
            denominator[0], denominator[1] = denominator[1], ai * denominator[1] + denominator[0]
        return [numerator[1], denominator[1]]

def wieners_attack(e, n, ciphertext):
    a = continued_fraction(e, n)
    for i in range(1, len(a)):
        d = convergent(a[:i])[1]
        plaintext = long_to_bytes(pow(ciphertext, d, n))
        if plaintext[:7] == b"picoCTF":
            print(f"d: {d}\n{plaintext.decode()}")
            break

e = 3846582932094138670737803938414796713679435711725169825618120939640784756281021057979867177337648475194149178180826281891186597855460221101473830844245495056223825784612496649386073390647133650789532627594972296466867552340022699080521464921132856671527228254340523458328461393677080171279088822105975506903
n = 70861126339548340474936494619069547448424050796813825952036436631153413936055258391649966432711723695888900938754493610447663393238312465839015505246321495831762104278977040349052253235242620371462847923499781205742904214331373434624452480835097664782698117019349993151498367979837258031362183332399991416733
c = 55469722241081357826973887676929862529368522341023811436532743070567838422833905386772399024818323692140894477722066663139078140159046999485248928742381395519929718645892977843383261578753034393923486085895187431756580218772832833603003578432969666897842341628709060787099421106901157283422281293916970628678

wieners_attack(e, n, c)

できました。

d: 13921360718220634704255074513454607352469823139962751581799795989379408236775
picoCTF{proving_wiener_5086186}

平文（flag）が"picoCTF{xxx}"となるはずなので、これを利用して正しく復号できたかを確認するようにしました。ここはもっと上手くできそうですが、とりあえずはよいでしょう。

おわりに

今回は、Wiener's Attackを取り上げてみました。もう少し勉強して更新するかも。