Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions

When RSA's private exponent d is small relative to the modulus, the continued-fraction expansion of e/N provably surfaces d as one of its convergents — no factoring attempt, no brute force, just an Euclidean-style expansion and a handful of integer checks.

The signal that gives it away

- A public exponent `e` that is huge — full-size, roughly the same bit-length as `N` — instead of a small textbook e like 3 or 65537. This is the actual tell, not "e looks random": since e·d ≡ 1 (mod φ(n)) forces e·d = 1 + k·φ(n) for some integer k, making d small mathematically forces e up to compensate, so a challenge that hands you an oversized e (sometimes even framed as "we made decryption faster by picking a tiny d") is signalling this attack directly. - The proven trigger is a numeric bound, not a vibe: `d < (1/3)·N^{1/4}`. The 1/3 factor is part of the theorem, not a rounding nicety — do the arithmetic before assuming you're in range. For a 1024-bit N, N^{1/4} = 2^{256}, so the ceiling on d is roughly 2^{255} — about 255 bits, not a small fraction of N's bit-length; check the actual bit-length of a candidate d against N's before spending time on the expansion. - Wiener's original proof assumes balanced primes, q < p < 2q — true by default for almost any challenge that generates p, q the normal way (same bit-length), so in practice this is rarely the reason the attack fails. If convergents come up empty despite d looking small, unbalanced primes are one of the few legitimate reasons, alongside simply having the wrong bound. - Don't confuse this with the opposite regime: a small e (e=3, e=5) is Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n territory, a completely different attack on a completely different artifact. Large e -> think Wiener/Boneh-Durfee; small e -> think small-exponent/Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring.

How it's exploited

1. Compute the continued-fraction expansion of `e/N` with the ordinary Euclidean algorithm: repeatedly take the integer quotient and recurse on the remainder. 2. Generate the convergents `h_k/k_k` via the standard recurrence h_k = a_k·h_{k-1} + h_{k-2} (same recurrence for the denominators k_k), where a_k are the continued-fraction terms from step 1: ``python def convergents(a, b): # continued-fraction convergents of a/b h0, h1, k0, k1 = 0, 1, 1, 0 while b: q, a, b = a // b, b, a % b h0, h1 = h1, q * h1 + h0 k0, k1 = k1, q * k1 + k0 yield h1, k1 ` Each yielded pair (h, k) is a candidate (k, d) — the numerator is the candidate k from e·d = 1 + k·φ(n), the denominator the candidate d itself. In SageMath the same list comes for free: continued_fraction(e/N).convergents(). 3. **Test every candidate (k, d) against the RSA-Wiener consistency check, in this order (cheapest first):** - d must be odd — φ(n) is always even for n = p·q with odd primes, so e·d ≡ 1 (mod φ(n)) forces both e and d odd. An even candidate d is an instant discard, no further arithmetic needed. - φ = (e·d − 1) / k must be an exact integer (reject any candidate where it isn't). - Solve x² − (N − φ + 1)x + N = 0. If it has **integer** roots, those roots are p and q — verify p·q == N before trusting the run. 4. **The first convergent that passes all three checks gives you the real d** (and, as a byproduct, the factorization of N) — you don't need to search further once one hits. 5. **Field-tested tooling:** the owiener Python package wraps exactly this loop (d = owiener.attack(e, N)); RsaCtfTool includes the same attack as one of its automatic modules. Reaching for the packaged implementation first is faster than re-deriving the recurrence under time pressure — write it out by hand only if the packaged version is unavailable or you need to adapt it (e.g. multi-prime N). 6. **If no convergent passes the consistency check**, that failure is itself the signal to stop here: d is not below (1/3)N^{1/4}`, and continued fractions structurally cannot find it no matter how the search is tuned. Pivot to Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292, which reaches the wider window (1/3)N^{1/4} < d < N^{0.292} via lattice reduction over LLL Reduction — the polynomial-time workhorse behind almost every lattice attack instead of continued fractions — it is the direct escalation path when Wiener comes back empty.

What does NOT work

- Treating a "convergent found" result as automatically correct without the full three-part check. A convergent that merely produces an integer φ but fails the integer-roots test is not a match — false positives at the φ-integer stage are common enough that skipping straight to pow(c, d, N) on an unverified d wastes a run. Always finish the quadratic-roots check and confirm p·q == N. - Re-running or re-tuning the continued-fraction search after it has already failed. This is not a parameter-tuning problem like a lattice attack's m/t — the bound d < (1/3)N^{1/4} is the entire content of the theorem. If no convergent of e/N matches, no amount of retrying, re-deriving, or double-checking the Euclidean steps changes that; the technique has exhausted its search space. Escalate to Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 instead of iterating on this one. - Applying this when `e` is small. A small e (3, 5, 17, 65537) is the opposite artifact and belongs to Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n or Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring depending on what else is given; Wiener's whole premise is that e is large precisely because d is small, so a small e is direct evidence you're looking at the wrong technique, not a variant of this one. - Assuming unbalanced primes silently break the attack in a way worth chasing first. In practice almost every challenge-generated RSA key has p and q of comparable bit-length, so this is a real but rare failure mode — check the bound and the consistency logic first; only suspect deliberately unbalanced primes if everything else checks out and convergents still come up empty.

Built on the general convergent/best-rational-approximation machinery of continued fractions; the algorithmic core lives entirely in this page rather than a separate reference, since Wiener's attack is the only place in this wiki that needs it. Related: RSA Fundamentals — the routing hub: which artifact points to which attack Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction LLL Reduction — the polynomial-time workhorse behind almost every lattice attack Lattice Fundamentals — encoding a bounded unknown as a short vector