TL;DR

  • Multi-Prime RSAの問題で$(q-1)(r-1)$を法とした$d$の下位bitと$r$を$q$で割ったものをくれる
  • $e$が比較的小さいことから、$ed -1 = k(q-1)(r-1)$となる$k$を総当りし、$q$で法をとると、$r$を$q$で割った余りが与えられているので、未知数が$d$だけになる
  • $d$の下位bitは十分な量分かっているのでCoppersmith's Attackで求められる
  • $r \approx q$であるから、$r$を$q$で割った際の法も小さく、これを総当りすれば求めた$d$とその時の$k$を利用して$q$が根である2次方程式が現れるのでこれを解いて素因数分解する

Prerequisite

  • Coppersmith's Attack

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)

3つの素数$p,q,r$でMulti-Prime RSAによる暗号化が行われており、それに加えてヒントパラメータが次のように与えられている。

  • rq: $r \bmod q$、以下では$r_q$とする
  • s: $d \bmod (q-1)(r-1)$の下位470bit

$ed \equiv 1 \mod (p-1)(q-1)(r-1)$が成り立つので当然$ed \equiv 1 \mod (q-1)(r-1)$が成り立つ。$(q-1)(r-1)$を法として考えているので$s$を使って次のような関係がある。

$$ e(d'\times 2^{470} + s) \equiv 1 \mod (q-1)(r-1) $$

ここで$d'$は、$d\equiv d'\times 2^{470} + s \mod (p-1)(q-1)$となるような高々42bit程度の数である。

ある整数$k$を用いて合同から等号に直すと次のようになる。

$$ e(d'\times 2^{470} + s) - 1 = k(qr - (q+r) + 1) $$

$k$については、$d' \times 2^{470} + s$がだいたい512bitで、$(qr - (q+r) + 1)$もだいたい512bitなので$e \approx k$としてよい。よって、$k$は2000程度の総当りで当てれば良い。

更に、 $r_q \equiv r \mod q$であり、どちらもgetPrime(256)で生成されているので$r = qc + r_q$と表した時に$c$は小さい整数であることが期待できる。よって、これは後に必要になったら総当たりすればいいので実質$r$は$q$の関数で表す事ができる。加えて、$q$で法をとると$c$は消えてくれる。

これを踏まえて両辺$q$で法をとると次のようになり、$k$を総当りするなら、次の式は未知数が$d'$だけになる。

$$ e(d'\times 2^{470} + s) - 1 \equiv -kr_q + k \mod q $$

$q$は$n$の約数なのでCoppersmith's Attackで$d'$を求められそうな予感がするし、実際試してみると求められる。$k$を総当りしながら求めたのでついでに$k$も求まっている。

元々考えていたのは次のような式であり、Coppersmith's Attackによって$d'$と$k$が判明した。。

$$ e(d'\times 2^{470} + s) - 1 = k(qr - (q+r) + 1) $$

既に上で説明したように$r = qc + r_q$であるから、$c$を総当りしながらこれを$r$に代入すると未知数は$q$だけであり、しかも整数であるから、2次方程式の整数解を求めることに帰着される。よって、$c$を総当りしながらこれを解けば$q$が求まり、ついでに$r$も求まる。加えて$n=pqr$なので$p$も求まって$n$を完全に素因数分解出来たから復号出来る。

Code

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes


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

# PR.<d> = PolynomialRing(Zmod(n))

# candidates = []
# for k in tqdm(range(100, e)):
#     f = e * (d*2**470 + s) - 1 + k*rq - k
#     f = f.monic()
#     roots = f.small_roots(X=2**43, beta=0.2, epsilon=1/20)

#     for x in roots:
#         candidates.append((k, x))

# print(candidates)

k, _d = (1576, 3248825676044)
d = _d*2**470+s

PR.<q> = PolynomialRing(ZZ)
for c in range(1, 11):
    f = k*(q*(q*c+rq) - q - (q*c+rq) + 1) - (e*d - 1)
    roots = f.roots()
    for x, _ in roots:
        if n % x == 0:
            _q = x
            r = _q*c + rq
            p = n // (_q*r)
            phi = (p-1) * (_q-1) * (r-1)
            d = inverse_mod(e, phi)
            m = power_mod(cipher, d, n)
            print(long_to_bytes(m))

Flag

ctf4b{GoodWork!!!YouAreTrulyOmniscientAndOmnipotent!!!}