Coppersmith's Heirs

RSA with e = 3 encrypts two messages related by a known shift (m and m+1), which is the Franklin-Reiter setup. Both x^3 - c1 and (x+1)^3 - c2 vanish at x = m, so their GCD over Z_N[x] is the linear factor x - m and the plaintext drops straight out. No factoring and no Sage needed; a pure-python polynomial Euclid mod N is enough.

Solve

1. Read output.txt: N, e = 3, c1 = m^3 mod N, c2 = (m+1)^3 mod N.
2. Build g1(x) = x^3 - c1 and g2(x) = (x+1)^3 - c2 = x^3 + 3x^2 + 3x + (1 - c2).
3. Take their GCD over Z_N[x] with a polynomial Euclid implemented mod N (every leading coefficient is inverted mod N). The GCD is the monic linear polynomial x - m, so the plaintext is minus its constant term.

Full working solver (saved as solve.py next to output.txt):

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes

N = 25242631456189260899103953086025597423270381338227101278425339663707221286863571815628817568633363700487351744535327223302902166155224734081357864317697494480015742585201495799365124931714032040973257536285830468868216042553816713280054883129862628603506318548886560770574582787826438548226354262413194850373268643355637925202070532838594033854601698962041514556491317263842400887700032276578064109922106998852012020713187265571676022527382693861112041344317096915949017604970204841686995028544205723017188986614246476526624290916242149669988369169621826988203291645531798341711106625032088919324690744101854252364477
e = 3
c1 = 26636060683933356201841204437377666907271525456413989856427901422837285094809828700289647560426241292625396211795152899193917770890648391593898129758917971520354420943423846038529650780407118497903135120455307924212036374482371916897442296632415698846760038738874255390814501949445020686953715368262807170710544669029
c2 = 26636060683933356201841204437377666907271525456413989856427901422837285094809828700289647560426241292625422968620581653058575356577537137086801190927096827660133801361313014751725605696685192932049286801179194193093887760711136154935160351070836012492813693142994442663240280863805311329527256632832379343378154731000


def poly_trim(a):
    while len(a) > 1 and a[-1] % N == 0:
        a.pop()
    return a


def poly_monic(a):
    a = poly_trim([x % N for x in a])
    inv = pow(a[-1], -1, N)
    return [(x * inv) % N for x in a]


def poly_mod(a, b):
    a = [x % N for x in a]
    b = poly_trim([x % N for x in b])
    binv = pow(b[-1], -1, N)
    while True:
        a = poly_trim(a)
        if len(a) < len(b) or (len(a) == 1 and a[0] == 0):
            break
        coef = (a[-1] * binv) % N
        shift = len(a) - len(b)
        for i in range(len(b)):
            a[shift + i] = (a[shift + i] - coef * b[i]) % N
    return poly_trim(a)


def poly_gcd(a, b):
    a, b = poly_trim(a[:]), poly_trim(b[:])
    while not (len(b) == 1 and b[0] == 0):
        a, b = b, poly_mod(a, b)
    return poly_monic(a)


g1 = [(-c1) % N, 0, 0, 1]
g2 = [(1 - c2) % N, 3, 3, 1]

g = poly_gcd(g1, g2)
assert len(g) == 2, f"gcd not linear (degree {len(g) - 1}); attack failed"
m = (-g[0]) % N
print("[Franklin-Reiter] recovered m =", m)
print("flag =", long_to_bytes(m).decode())

$ python3 solve.py
[Franklin-Reiter] recovered m = 2986459745180674882576714403872600682967912946001312431923994339305796544991462219441875605841655576618109
flag = SVIUSCG{c0pp3r5m1th_fr4nkl1n_r3173r_ch41n3d}

The output also leaks d_high = d >> 1536 (top 512 bits of the private key) as a second independent path, but the Franklin-Reiter GCD already recovers the plaintext, so that path is not needed.

Flag: SVIUSCG{c0pp3r5m1th_fr4nkl1n_r3173r_ch41n3d}