LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@O-JuninBeginners Sec

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

Last updated at Posted at 2023-08-23

はじめに

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

  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)$を返す関数を実装した。

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
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?