RSAでe,dがわかっている時にNを素因数分解する

はじめに

はじめまして高校二年のもちもちと言います。
自分はセキュリティキャンプ全国大会'21の暗号のゼミの修了生で、またSECCON BEGINNERS(ctf4b)ではcrypto(暗号)の作問をしています。
ここではRSAの問題でたびたび見られる、e,dからNの素因数分解を試みる攻撃についての理論の話をしていきます。
全体的なモチベーションとしては$x^2=1\ mod\ N$つまり$x^2-1=(x-1)(x+1)\ mod\ n$の形を利用して、$x-1$がnの素因数で割り切れる確率って高そうだよね～って感じです。

ステップ1

$k=ed-1=2^st$とおく
※1
RSA暗号において$a^{ed}=a\ mod\ n$であることから、$a^{ed-1}=1\ mod\ n$、つまり$a^k=1\ mod\ n$が成り立つ。

ステップ2

$i=s,a=2$

ステップ3

$b=a^t\ mod\ n$ とする。もしbが1ならaを次の素数に更新し、ステップ3に戻る
※2
ほとんどの場合そのようなaはすぐに見つかる。なぜならNは無平方数、つまり各素因数が高々1乗のみで現れる数であるため、中国剰余定理により、Nと互いに素なaはこのステップで、Nの全ての素因数pに対して$a^t\ mod\ p = 1$となる場合にのみ拒否される。
中国の剰余定理は、一組の同時合同式が与えられたとき、その解が存在し、かつそれが一意であるならば、各合同式の法はすべて互いに素でなければならないという定理である。
つまり、Nが無平方数であるという事実は、Nを割り切る全ての素数pについて、それぞれが異なるmod pの環に属することを意味する。
ここで$a^t\ = 1\ mod\ p$ がaに対して成り立つとする。このとき、$a' = -a\ mod\ p$になるような$a'$を選んでやると、${a'}^t\ = (-1)^t=p - 1\mod\ p$となる。つまり、$mod\ p$で1となるものと$p-1$になるものは一対一に対応するため、ランダムに選ばれたaが$a^t\ mod\ p = 1$を満たす確率が最大でも1/2であることを意味する。
これが全てのpに対して独立に判定されるためこれが拒否される確率は十分に小さくなる。

ステップ4

$i \neq 1$ の時、$c=b^2\ mod\ n$とする。$c \neq 1$ の時$b=c,i-=1$を行い、ステップ4に戻る
※3
ステップ5に進むときには、$b\ mod\ N ≠ 1$かつ$b^2\ mod\ N = 1$が成り立つ

ステップ5

$b=N-1$の時、aを次の素数に更新し、ステップ3に戻る

ステップ6

$p=gcd(b-1,N),q=N/p$となる。
※4
$b^2\ mod\ N = 1$よりつまり$b \equiv ±1$である可能性が高く、またこれは$b-1$がNの素因数で割り切れる可能性が高い

実装

def factorize(N, e, d):
    from math import gcd
    import gmpy2

    k = d * e - 1
    t = k
    i = 0
    while t % 2 == 0:
        t //= 2
        i += 1
    fl = 1
    a = 2
    while True:
        b = pow(a, t, N)
        if b > 1 and fl:
            while True:
                if i != 1:
                    c = (b * b) % N
                    if c != 1:
                        b = c
                        i -= 1
                    else:
                        if b == N - 1:
                            fl = 0
                            break
                        else:
                            p = gcd(b - 1, N)
                            q = N // p
                            return p, q
                else:
                    fl = 0
                    break
        a = gmpy2.next_prime(a)
        fl = 1


e = 65537
N = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
p, q = factorize(N, e, d)

参考