Description
Everything seems secure; strong numbers, familiar parameters but something small might ruin it all. Can you recover the message? Download the message.txt and source encryption.py .
Setup
Download message.txt and encryption.py.
Inspect the RSA parameters: n, e, and ciphertext c.
cat message.txt
cat encryption.py
Solution
- Step 1Identify Wiener's attack conditionThe title hints at 'small trouble' -- the RSA private exponent d is unusually small. Wiener's theorem: if d < n^(1/4)/3, the private key can be recovered from the public key (n, e) using continued fractions.
- Step 2Apply Wiener's continued fraction attackCompute the continued fraction expansion of e/n, then check each convergent p/q as a candidate for k/d (where e*d = k*phi(n) + 1). Verify by checking that the resulting phi(n) is consistent.python3 << 'EOF' from math import isqrt def wiener(e, n): # Continued fraction expansion of e/n def cf_expansion(num, den): while den: yield num // den num, den = den, num % den def convergents(cf): p0, p1 = 1, 0 q0, q1 = 0, 1 for a in cf: p0, p1 = a*p0 + p1, p0 q0, q1 = a*q0 + q1, q0 yield p0, q0 for k, d in convergents(cf_expansion(e, n)): if k == 0: continue phi_candidate = (e*d - 1) // k b = n - phi_candidate + 1 disc = b*b - 4*n if disc >= 0: sq = isqrt(disc) if sq*sq == disc: return d return None n = YOUR_N e = YOUR_E c = YOUR_C d = wiener(e, n) print("d =", d) m = pow(c, d, n) print(bytes.fromhex(hex(m)[2:])) EOF
Flag
picoCTF{w13n3r_4tt4ck_...}
The RSA private exponent d is small enough for Wiener's continued fraction attack to recover it directly from the public key.