TL;DR

  • Multi-Prime RSAの問題で(q−1)(r−1)(q-1)(r-1)を法としたddの下位bitとrrをqqで割ったものをくれる
  • eeが比較的小さいことから、ed−1=k(q−1)(r−1)ed -1 = k(q-1)(r-1)となるkkを総当りし、qqで法をとると、rrをqqで割った余りが与えられているので、未知数がddだけになる
  • ddの下位bitは十分な量分かっているのでCoppersmith's Attackで求められる
  • r≈qr \approx qであるから、rrをqqで割った際の法も小さく、これを総当りすれば求めたddとその時のkkを利用してqqが根である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,rp,q,rでMulti-Prime RSAによる暗号化が行われており、それに加えてヒントパラメータが次のように与えられている。

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

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

e(d′×2470+s)≡1mod  (q−1)(r−1) e(d'\times 2^{470} + s) \equiv 1 \mod (q-1)(r-1)

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

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

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

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

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

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

e(d′×2470+s)−1≡−krq+kmod  q e(d'\times 2^{470} + s) - 1 \equiv -kr_q + k \mod q

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

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

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

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

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!!!}