SECCON Beginners CTF 2022 - crypto/omni-RSA

exploit.sage

# SECCON Beginners CTF 2022
# crypto/omni-RSA

from Crypto.Util.number import isPrime, long_to_bytes
import gmpy2

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

# Step 1: d % ((q - 1)*(r - 1)) を求める （d2 とおく）
d2 = None

# d2*e == -k*(rq - 1) + 1 (mod q)
# k は小さいため全探索
for k in range(2000):
    if d2 != None:
        break
    # print(f"{k = }") # k = 1576

    PR.<d_part> = PolynomialRing(Zmod(n))

    f = e * (s + d_part*(2**470)) + k*(rq - 1) - 1
    f = f.monic()

    # Coppersmith's Attack
    # betaの値は q >= n^beta になるように調整
    xs = f.small_roots(X=2**45, beta=0.2, epsilon=1/10)

    for x in xs:
        print(f"d_part = {int(x)}") # d_part = 3248825676044
        d2 = int(x)*(2**470) + s

assert d2 != None

# Step 2: nを素因数分解する

# 「e, dがわかっているときにnを素因数分解する」を応用して求める
# From: https://furutsuki.hatenablog.com/entry/2021/03/16/095021#e-d%E3%81%8C%E3%82%8F%E3%81%8B%E3%81%A3%E3%81%A6%E3%81%84%E3%82%8B%E3%81%A8%E3%81%8D%E3%81%ABn%E3%82%92%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E3%81%99%E3%82%8B

k = d2*e - 1
t = k
while t%2 == 0:
    t //= 2
g = 3

ps = []
for _ in range(100):
    x = int(pow(g, t, n))
    if x > 1:
        y = GCD(x - 1, n)
        if y > 1:
            ps.append(y)
            for p in [y - rq, y + rq]:
                if isPrime(p):
                    ps.append(p)
                    ps.append(n // (p*y))
            assert len(ps) == 3
            break
    g = gmpy2.next_prime(g)

# Step 3: multi-prime RSAの復号
p, q, r = ps
assert p*q*r == n
phi = (p - 1) * (q - 1) * (r - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(cipher, d, n)))