Wiener's Attackを自力で実装してみた

## はじめに
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で実装した。また、有理数から連分数へ変換するユーティリティ関数も実装した。

```python3
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)$

この漸化式を利用し、連分数→有理数への変換を実装した。

```python
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)

```

テストをしてみたが、概ね正しいだろう。

```python
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$と展開できるとする。

> 1. $f$が見つかるまで、$i=0, 1, \ldots$に関してループする。
> 2. 漸化式を用いて、
> $i$が偶数の場合、$\langle q'_0, q'_1, \ldots, q'_i + 1 \rangle$
> $i$が奇数の場合、$\langle q'_0, q'_1, \ldots, q'_i \rangle$
> と等しい有理数を計算する。
> 3. 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)$を返す関数を実装した。

```python
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を素直に実装すればよい。

```python3
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

```python3
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) も見てみたが、自分の実装より高速な上に短く書かれていて、このようなコードを書きたいなと思った。

```python
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

```