Overview
An RSA keypair “deliberately built with an unusually small private exponent for efficiency.” We are given the public modulus N, the public exponent e, and the ciphertext c containing the flag. The hint points straight at a small d, which is the textbook setup for Wiener’s attack.
Recon
Inspecting the parameters:
import json
d = json.load(open("fianchetto_challenge.json"))
N, e, c = d["N"], d["e"], d["c"]
print(N.bit_length(), e.bit_length(), c.bit_length())
N: ~2048 bits
e: ~2048 bits <-- as large as N
c: ~2048 bits
Exploitation
The key relation is e*d = 1 + k*phi(N), so e/N ≈ k/d. For each convergent k/d of e/N:
- Check
(e*d - 1) % k == 0, then compute the candidatephi = (e*d - 1) // k. - Use
p + q = N - phi + 1to formx^2 - (p+q)x + N. - If the discriminant is a perfect square and the roots multiply to
N, the candidate is correct. - Decrypt with
m = pow(c, d, N).
import json
from math import isqrt
data = json.load(open("fianchetto_challenge.json"))
N, e, c = data["N"], data["e"], data["c"]
def cf(n, d):
while d:
q = n // d
yield q
n, d = d, n - q * d
def convergents(a):
h0, h1, k0, k1 = 0, 1, 1, 0
for q in a:
h0, h1 = h1, q * h1 + h0
k0, k1 = k1, q * k1 + k0
yield h1, k1
for k, d in convergents(cf(e, N)):
if k == 0 or (e * d - 1) % k:
continue
phi = (e * d - 1) // k
s = N - phi + 1
disc = s * s - 4 * N
if disc < 0:
continue
r = isqrt(disc)
if r * r == disc and (s + r) % 2 == 0:
p, q = (s + r) // 2, (s - r) // 2
if p * q == N:
m = pow(c, d, N)
print("d bits:", d.bit_length())
print(m.to_bytes((m.bit_length() + 7) // 8, "big"))
break
d bits: 160
b'r00t{REDACTED}'
The recovered d is only 160 bits against a 2048-bit modulus, far under the Wiener bound.
Vulnerability Analysis
Mitigations
- Never choose a small private exponent
dfor performance; keepdfull-size and use CRT-based decryption (dp,dq,qinv) for speed instead. - Use key sizes of at least 2048 bits with properly generated primes.
- Monitor for small
dduring key generation and reject keys whered < N^(1/4) / 3.
Flag
r00t{REDACTED}
Lessons / Takeaways
Techniques
- Wiener’s Attack
- RSA Small Private Exponent
- Continued Fractions

