tags: `blog` `crypto`

Wiener's Attack を実装した

はじめに

RSA暗号運用でやってはいけない n のこと #ssmjp from sonickun

このスライドをみてそういえばWiener's Attack実装したこと無いなと思ったので勉強がてら実装してみました.
orisano/owiener

元論文はCryptanalysis of Short RSA Secret Exponentsで
理論についての説明は
http://elliptic-shiho.hatenablog.com/entry/2015/12/18/205804
が詳しいです.
ここでは実装について書いていこうと思います.

実装について

Wiener's Attackは連分数展開と連分数から近似分数を求める2つのパートからなります.
連分数展開に関してはユークリッドの互除法の過程で得られるので素直に実装します.
ユークリッドの互除法の計算量は

O (\log_{10} n)

def rational_to_contfrac(x: int, y: int) -> Iterator[int]:
    while y:
        a = x // y
        yield a
        x, y = y, x - a * y

連分数から近似分数を求めるパートがあるのですが,まず連分数から有理数を復元するところから説明します.
連分数を後ろから足して逆数求めることを繰り返していけば復元できます.

def contfrac_to_rational(contfrac: List[int]) -> Tuple[int, int]:
    from functools import reduce
    return reduce(
        lambda f,q: (q * f[0] + f[1], f[0]),
        reversed(contfrac),
        (1, 0),
    )

ちなみに上記のコードは使ってないのでrepositoryにはありません.
前から復元する場合は元論文の式6を用いるとできます.実際にはこちらを使います.

\begin{aligned} n_{0} & = & q_{0}, d_{0} & = & 1 \\ n_{1} & = & q_{0} q_{1} + 1, d_{1} & = & q_{1} \\ n_{i} & = & q_{i} n_{i - 1} + n_{i - 2}, d_{i} & = & q_{i} d_{i - 1} + d_{i - 2} for i = 2, 3, \dots, m \end{aligned}

式からもわかる様に前の2つの状態を持っていれば次の状態を作ることができます.
このままだと

i

が

0

と

1

の時条件分岐しないといけません.

- 1

と

- 2

の時を条件を満たす様に定義することで実装がシンプルになります.

\begin{aligned} n_{- 2} & = & 0, d_{- 2} & = & 1 \\ n_{- 1} & = & 1, d_{- 1} & = & 0 \\ n_{i} & = & q_{i} n_{i - 1} + n_{i - 2}, d_{i} & = & q_{i} d_{i - 1} + d_{i - 2} \end{aligned}

def contfrac_to_rational_iter(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]:
    n0, d0 = 0, 1
    n1, d1 = 1, 0
    for q in contfrac:
        n = q * n1 + n0
        d = q * d1 + d0
        yield n, d
        n0, d0 = n1, d1
        n1, d1 = n, d

計算量は

O (n)

になります.
用途を考えてgeneratorとして返しています.

近似分数を列挙するのですが元論文の3章のアルゴリズムを用います.
そんなに難しくないので読んでみることをおすすめします.
基本的には連分数を前の方だけ使って復元した値を近似分数とします.
愚直に実装すると以下の様になります.

def convergents_from_contfrac_naive(contfrac: List[int]) -> Iterator[Tuple[int, int]]:
    m = len(contfrac)
    for i in range(m):
        if i % 2 == 0:
            q = contfrac[:i+1]
            q[i] += 1
            yield contfrac_to_rational(q)
        else:
            q = contfrac[:i+1]
            yield contfrac_to_rational(q)

添字が偶数のときは最後の要素を1足した物を有理数に復元し,それを近似分数とします.
これは毎回contfrac_to_rationalを呼んでいて無駄です.
偶数のときの処理が面倒くさい様に見えるが,式を見てみると最後の要素に1を足すという処理は1つ前の結果を足すこと同様だと言うことがわかります.
つまり直前の結果だけ持っていれば良いです.

i = 0

のときは定義した

i = - 1

のときの結果を用います.

def convergents_from_contfrac(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]:
    n_, d_ = 1, 0
    for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)):
        if i % 2 == 0:
            yield n + n_, d + d_
        else:
            yield n, d
        n_, d_ = n, d

これまで紹介して来たコードを組み合わせてattack関数を定義します.

def attack(e: int, n: int) -> Optional[int]:
    f_ = rational_to_contfrac(e, n)
    for k, dg in convergents_from_contfrac(f_):
        edg = e * dg
        phi = edg // k

        x = n - phi + 1
        if x % 2 == 0 and is_perfect_square((x // 2) ** 2 - n):
            g = edg - phi * k
            return dg // g
    return None

近似分数を総当りでdを特定します.
正しい有理数に復元できたかどうかの判定は元論文のとおりに実装しました.
平方数の判定は

O (l o g_{2} n)

程度でできるので,合計の計算量は

O (l o g_{2} n * l o g_{10} n)

になります.
比較的簡単にWiener's Attackを実装できました.
証明やどういう場合に使えるかについては元論文を読んで見てください.

おまけ

平方数の判定は2分探索を用いることで出来ますが,今回はgmpの実装を参考にしました.
平方数の

\mod 256

は

44

パターンしか無いのでまずそれで篩にかけます.
全体の

80 %

程度を瞬時に判定することが出来ます.
残りの

20 %

程度に対して

\mod 9, 5, 7, 13, 17

で同様のことを行います.
これにより全体の

96 %

に対して判定を行えます.
残りの

4 %

に対してニュートン法を用いて平方数判定を行います.

def is_perfect_square(n: int) -> bool:
    sq_mod256 = (1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0)
    if sq_mod256[n & 0xff] == 0:
        return False

    mt = (
        (9, (1,1,0,0,1,0,0,1,0)),
        (5, (1,1,0,0,1)),
        (7, (1,1,1,0,1,0,0)),
        (13, (1,1,0,1,1,0,0,0,0,1,1,0,1)),
        (17, (1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1))
    )
    a = n % (9 * 5 * 7 * 13 * 17)
    if any(t[a % m] == 0 for m, t in mt):
        return False

    return isqrt(n) ** 2 == n

整数のみを扱うニュートン法を用いました.
ニュートン法は初期値を決めないといけませんが平方根を求める場合は簡単にある程度良い初期値が与えられます.
適切に

n

を決定すると

S \approx α \cdot 2^{2 n}

は

0.5 \leq α < 2

になります.

n

は

S

の最上位bitが立ってる場所を2で割ると求めることが出来ます.

\sqrt{S} \approx \sqrt{α} 2^{n}

になるので初期値を

2^{n}

にすると正しい答えに近い地点にいるので収束が早くなります.

def isqrt(n: int) -> int:
    if n == 0:
        return 0

    x = 2 ** ((n.bit_length() + 1) // 2)
    while True:
        y = (x + n // x) // 2
        if y >= x:
            return x
        x = y

終わりに

Pythonなりにわかりやすく高速に実装できたかなと思います.
(JavaのBigIntegerを使って実装している例があったのですが読みづらくて辛かった)
実装してみて楽しかったので他の手法も論文を読みながら実装できるくらい頭良くなりたい.

参考文献

Cryptanalysis of Short RSA Secret Exponents:
https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf
公開鍵暗号 - RSA - Wiener's Attack - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです:
http://elliptic-shiho.hatenablog.com/entry/2015/12/18/205804
pablocelayes/rsa-wiener-attack:
https://github.com/pablocelayes/rsa-wiener-attack
wihoho/Wiener-s-Attack:
https://github.com/wihoho/Wiener-s-Attack
平方数かどうかを高速に判定する方法 - hnwの日記
http://d.hatena.ne.jp/hnw/20140503
Integer square root:
https://en.wikipedia.org/wiki/Integer_square_root
Methods of computing square roots:
https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Rough_estimation

tags: blog crypto