home / ctf / pwnsec

Gap Gap

p-1 and q-1 share a 600-bit prime, which turns 30 redacted digits of d into a Coppersmith root modulo an unknown divisor of N-1.

2026.09.19 PwnSec CTF 2026 104 pts Crypto
FLAG pwnsec{473c7c9b771d4ce1}

0. In one paragraph

p-1 and q-1 are built to share a 600-bit prime g, and the private exponent d is published with only its middle 30 decimal digits redacted. Because g | ed-1, the missing digits are a small root of a linear polynomial modulo an unknown divisor g of (N-1)/2 — textbook Coppersmith with beta ≈ 0.29. Recovering d gives 2g = gcd(N-1, ed-1), and the shared structure then hands over a + b and ab, so p and q fall out of a quadratic.

1. The generator

N_BITS = 2048; G_BITS = 600
D_DIGITS = 124; PREFIX_DIGITS = 47; MIDDLE_DIGITS = 30; SUFFIX_DIGITS = 47

g = getPrime(G_BITS)
p = 2*g*a + 1          # a, b chosen so p, q are each 1024 bits
q = 2*g*b + 1
h = p*b + a            # required to be prime as well
# (a+b) odd, gcd(a,b) == 1, |p-q|.bit_length() >= 960

N   = p*q
lam = 2*g*a*b          # lcm(p-1, q-1), since gcd(a,b)=1

d = <124-digit odd integer>, gcd(d, lam) == 1
e = d^-1 mod lam
k = (e*d - 1)//lam     # with gcd(k, 2g) == 1 and e.bit_length() >= lam.bit_length()-4

d_leak = d_str[:47] + "*"*30 + d_str[-47:]
c = pow(bytes_to_long(flag), e, N)

Two things matter. First, p-1 and q-1 share the 600-bit factor 2g — the “gap” the title refers to. Second, d is only 124 digits (~412 bits) and 94 of those digits are published; just 30 decimal digits (~100 bits) are hidden.

The handout also ships a second, static parameter set (output_static_decoy.txt) alongside the one the live instance prints (our_output.txt); the attack below is run against the instance’s values.

2. The hidden digits are a Coppersmith root modulo g

Write the unknown middle block as x < 10^30:

d = d_high * 10^77 + x * 10^47 + d_low

From e*d ≡ 1 (mod lam) and lam = 2gab we get g | (e*d - 1). Substituting:

e*d - 1 = [ e*(d_high*10^77 + d_low) - 1 ] + [ e*10^47 ] * x
          \___________ A ____________/       \____ B ____/

A + B*x ≡ 0  (mod g)

g is unknown, but it divides N - 1 = 2g(2gab + a + b), so it divides the known modulus M = (N-1)/2. That is exactly the setting Coppersmith’s method covers with the beta parameter: find a small root of a monic polynomial modulo an unknown divisor of M that is at least M^beta.

M is ~2047 bits and g is 600 bits, so beta = 600/2047 ≈ 0.293 — the exploit uses 0.29. Halving (both A and B are even, and we work modulo M = (N-1)/2) and normalising to a monic polynomial:

A = e*(d_high*10**77 + d_low) - 1
B = e*10**47
M = (N - 1)//2

f = x + (A//2) * inverse_mod(B//2, M) mod M
roots = f.small_roots(X=10**30, beta=0.29, epsilon=0.03)

The bound is comfortable: Coppersmith recovers roots up to about M^(beta²/deg) = M^0.0841 ≈ 2^172, and 10^30 ≈ 2^99.7. One root comes back, and d is complete.

3. From d to the factorisation

Recovering d is not the end — we still need p and q to decrypt (or just use d directly, but the factorisation is free at this point):

two_g = gcd(N - 1, e*d - 1)     # = 2g
g     = two_g // 2

h = (N - 1) // two_g            # = 2gab + a + b
S = h % two_g                   # = a + b  (a+b is ~424 bits < 2g, so no wraparound)
P = (h - S) // two_g            # = ab

a and b are then the roots of z² - Sz + P:

delta = isqrt(S*S - 4*P)
a, b  = (S + delta)//2, (S - delta)//2
p, q  = 2*g*a + 1, 2*g*b + 1
assert p*q == N

The step that makes this work is S = h mod 2g being exactly a + b: a and b are about 423 bits each while 2g is 601 bits, so the reduction does not wrap. That is a direct consequence of the generator forcing both primes to 1024 bits with the same 600-bit g.

m = pow(c, d, N)
m.to_bytes((m.bit_length()+7)//8, 'big')
# pwnsec{473c7c9b771d4ce1}

4. Running it without Sage

exploit.sage is the original, human-verified outline and leans on Sage’s Polynomial.small_roots(). With no Sage installed, solve.py is a pure-Python reimplementation of that one call: Howgrave-Graham’s formulation with the beta/epsilon parametrisation, using fpylll for the LLL reduction instead.

m = ceil(max(beta**2 / (delta*epsilon), 7*beta/delta))
t = floor(delta * m * (1/beta - 1))

with delta = deg(f) = 1, beta = 0.29, epsilon = 0.03 — matching Sage’s parameter choice so the lattice is the same one Sage would build. The polynomial x^j * f(x)^i * M^(m-i) shifts are assembled, scaled by powers of X, reduced with LLL.reduction, and the short vectors are turned back into integer polynomials whose integer roots are then tested against the original congruence.

One implementation detail worth keeping: the constant term is reduced to a centred representative (c0 -= M when c0 > M/2) before building the lattice. It keeps the basis entries small and the reduction well behaved.

5. Takeaways

  • Sharing a large prime factor between p-1 and q-1 is the whole vulnerability. It makes g a divisor of N-1 that the attacker can aim Coppersmith at, and once g is known the remaining unknowns a + b and ab fall out of one modular reduction.
  • Partial exponent exposure is far more dangerous than it looks. 30 decimal digits hidden out of 124 sounds like plenty of margin; against a linear Coppersmith with a 600-bit unknown divisor, roughly 172 bits of margin was available and only 100 were used.
  • If Sage is unavailable, small_roots is not a black box — mirroring its m/t parameter choice on top of fpylll reproduces it closely enough to be interchangeable.

Files

  • chall.py — the challenge generator
  • exploit.sage — original attack outline (requires Sage)
  • solve.py — the same attack with a pure-Python small_roots on fpylll
  • our_output.txt — parameters from the live instance (used by the solve)
  • output_static_decoy.txt — the static parameter set shipped with the handout
#rsa#coppersmith#lattice#lll