"""Euclidean continued-fraction terms of num/den."""
The fix: replace the broken keygen's assumption with a recovery that exploits it. A flawed keygen that picks d < N^0.25/3 and sets e ≡ d⁻¹ (mod φ(N)) leaks the private exponent through the continued-fraction expansion of e/N. With k = (e·d − 1)/φ(N) we have e·d = 1 + k·φ(N), so:
|e/N − k/d| = |1 − k·(p+q−1)| / (N·d) < 3k√N / (N·d) < 3/(√N) < 1/(2d²) (when d < N^0.25/3)
By Legendre's theorem, k/d must be a convergent of e/N. The attack walks convergents, reconstructs φ(N) = (e·d − 1)/k, then verifies the quadratic x² − (N−φ+1)x + N factors N exactly. Pure Python, no lattice libraries — math.isqrt is the only import.
# wiener.py
from math import isqrt
def cf_terms(num, den):
"""Euclidean continued-fraction terms of num/den."""
terms = []
while den != 0:
q, r = divmod(num, den)
terms.append(q)
num, den = den, r
return terms
def convergents(num, den):
"""Yield convergents (h_i, k_i) of num/den via the standard recurrence."""
h_pp, h_p = 0, 1 # numerators h_{-2}=0, h_{-1}=1
k_pp, k_p = 1, 0 # denominators k_{-2}=1, k_{-1}=0
for a in cf_terms(num, den):
h = a * h_p + h_pp
k = a * k_p + k_pp
h_pp, h_p = h_p, h
k_pp, k_p = k_p, k
yield h, k
def recover_d(N, e):
"""Wiener's attack: recover private d from public (N, e).
Succeeds when the flawed keygen produced d < N^0.25 / 3.
Raises ValueError if no convergent factors N (e.g. properly
generated key with large d).
"""
for k, d in convergents(e, N):
if k == 0:
continue
if (e * d - 1) % k != 0: # φ(N) must be an integer
continue
phi = (e * d - 1) // k
if phi <= 0 or phi >= N:
continue
s = N - phi + 1 # p + q
disc = s * s - 4 * N
if disc < 0:
continue
sq = isqrt(disc)
if sq * sq != disc: # discriminant must be a perfect square
continue
if (s + sq) % 2 != 0 or (s - sq) % 2 != 0:
continue
p = (s + sq) // 2
q = (s - sq) // 2
if p > 1 and q > 1 and p * q == N and (e * d) % phi == 1:
return d # recovered private exponent
raise ValueError("Wiener attack failed: no convergent factored N")
Usage: d = recover_d(N, e) — returns the recovered private exponent for any 1024-bit (or smaller/larger) modulus produced by the flawed keygen.
**Test harness** (`test_wiener.py` + inline checks) generated flawed keypairs exactly as the problem describes — pick `d < ⌊N^0.25⌋/3`, then `e = d⁻¹ mod φ(N)` — and verified the recovered `d` matches. All 18/18 harness tests plus 3 extra checks passed; total wall time < 2 s. - **Size sweep**: 128 / 256 / 512 / 1024-bit moduli, 3 random keys each — recovered `d` matched in every case (e.g. a 1024-bit `N` with `d ≈ 5.0×10⁷⁴` recovered instantly). - **Textbook vector**: Wiener's classic example `N=90581, e=17993 → d=5` ✓. - **Exact 1024-bit modulus** (the problem's stated size), `d` well below `N^0.25/3` ✓. - **Boundary `d`**: forced `d` to ~126 bits near the `N^0.25/3` ceiling — still recovered ✓. - **`e < N`** (public exponent both large and small) ✓. - **`k = 1` degenerate convergent**: deterministically constructed `(N,e,d)` with `e·d − 1 = φ(N)` exactly — recovered ✓. - **End-to-end decrypt**: recovered `d` from a 1024-bit key, then `pow(ct, d, N)` returned the original plaintext ✓. - **Negative control**: properly generated RSA (large `d`) — attack raises `ValueError`, does not factor ✓. - **Over-limit robustness**: `d` above the strict bound — no hang/crash (may still recover, since the bound is sufficient, not necessary) ✓. - **gcd(e, N) = 1 invariant** holds for all generated keys ✓. Complexity is ~O(number of continued-fraction terms) — a handful of big-integer divisions and square roots, so brute force over the key space is never needed.
{"model": "deepseek-v4-flash", "problem_class": "python-rsa-wiener-small-d-key-recovery", "result": "passed", "tests": 21}