SECCON Beginners 2022 - Omni RSA writeup

writeup くらい書いておかないとなにもしていないような悲しい気持ちになるのでwriteupです

問題はこう

from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)

こういう問題をみたら、 $ed \equiv 1 \mod \phi$ をたてて、 $\phi$ を開いて $N, p, q, r$ で表したうえで $ed = 1 + k(N + \dots + 1)$ という形に剰余を開きたくなりますね。そのあと $N$ か $e$ で剰余を取り直す。

しかし今回の場合与えられている $s$ は $u \equiv d \mod (q-1)(r-1)$ の下位470bitなので愚直にそういうアプローチは取れずちょっと工夫が必要になりそうです。とにかく書いてみると、 $u = s + x*2^{470}$ として

$e(s + x*2^{470}) \equiv 1 \mod (q-1)(r-1)$

です。適当な整数 $k$ を持ち出してきて剰余を開き、ついでに $t = r \% q = r - q$ も与えられているので、 $r = q + t$ とおきなおすとこうです。

$e(s + x*2^{470}) = 1 + k(q-1)(q+t-1)$

一見これで $\mod q$ を取り直して $\beta = 0.25$ くらいでcoppersmith methodをすると $x$ が十分小さいので解けるように見えます。実際解けるっぽくて作問者writeupではそうなっていたんですが、私はパラメータの調整を雑にやった結果これでは解けないという誤った確信に至ったので別の方法をとりました。

ここで $\mod 2^{470}$ をとると下式のようになり、未知数は $k, q$ ですが、 $e \lt k$ で $e = 2003$ なので全探索すれば良さそうなので未知数は実質 $q$ だけです。

$es \equiv 1 + k(q-1)(q+t-1) \mod 2^{470}$

これをいきなり解くのは難しいので*1、更に簡単にして $\mod 2^m$ を考えます。

$es \equiv 1 + k(q-1)(q+t-1) \mod 2^m$

すると十分小さい $m$ の元では $q$ の下位bitの候補が全探索できます。まず $m=1$ で $q$ の最下位bitの候補を2通り探索し、続いて $m=2$ として下から2bit目の候補を探索します。候補数が $2^m$ 個に増えそうですが、 $q$ の下位bitと一致している場合は必ず等式が成り立つことを考えると、どこかのタイミングで上位bitの候補がなくなった場合は下位bitの選択がまちがっていたということなので捨ててよく、候補数はそんなに増えないことが期待できます*2。

というように $m$ を $1$ から $470$ 枝刈り全探索をやって残っていた候補はわずかなはずなので、そのなかで $n$ を割り切れるやつが $q$ です。というわけで $q$ が求められたので、 $r = q + t$ から $r$ を、 $n = pqr$ から $p$ を求めて素因数分解が完了したのでRSAは解けました。

エクスプロイトはこう！ 2冪で小さい方から枝刈り全探索というとTSG CTF 2019のOPQRXを思い出しますねとおもったけどこれは大きい方からだったか……

from Crypto.Util.number import inverse

t = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

qs = []

def dfs(sz, qbits, k):
    if sz == 470:
        qs.append(qbits)
        return

    if sz > 256 and qbits.bit_length() > 256:
        return

    q1 = qbits
    q2 = qbits | (1 << sz)

    a = e*s % 2**(sz+1) == (1 + k*(q1-1)*(q1+t-1)) % 2**(sz+1)
    b = e*s % 2**(sz+1) == (1 + k*(q2-1)*(q2+t-1)) % 2**(sz+1)
    if a:
        dfs(sz + 1, q1, k)
    if b:
        dfs(sz + 1, q2, k)

for k in range(1, e):
    dfs(0, 0, k)

for q in qs:
    if n % q != 0:
        continue
    r = q + t
    p = n // (q*r)
    phi = (p - 1) * (q - 1) * (r - 1)
    e = 2003
    d = inverse(e, phi)

    m = pow(cipher, d, n)
    print(bytes.fromhex(hex(m)[2:]))