Wiener’s attack on small RSA private exponents
Recover a small private exponent d from n and e using continued fractions. Works whenever d is below roughly the fourth root of n.
Open in ctfpalA small private exponent makes decryption fast, which is why someone might choose one. Wiener showed that when d < n^(1/4)/3, that choice leaks the key entirely - and the giveaway is visible in the public key, because a small d forces a correspondingly enormous e.
The continued fraction insight
From e*d = 1 mod phi(n) it follows that e/n is a very close approximation to d's counterpart over phi(n). The convergents of the continued fraction expansion of e/n therefore contain the correct k/d pair. Enumerate the convergents, test each candidate d by decrypting a known value or by checking that the implied phi yields integer roots for p and q, and stop at the one that works. There are only a few dozen convergents to try.
- Precondition:
eis large - typically comparable in magnitude tonrather than the usual 65537. - Bound: works for
d < n^(1/4)/3. Boneh-Durfee extends this to roughlyd < n^0.292using lattice reduction. - Cost: milliseconds, regardless of key size.
Part of a module
5. RSA and the parameters that break it
Work the RSA decision tree - small modulus, close primes, tiny exponent, shared modulus - and learn to read a key for its weakness.
Practise on real challenges
Go deeper
- The RSA attack decision treeRSA challenges are not solved by knowing every attack - they are solved by reading the parameters and picking the one attack that matches. A decision tree from e and n to Fermat, Wiener, Hastad, common modulus, and the oracle attacks.
Related tools
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Fermat factorization for close RSA primes
Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.
Biased nonce lattice attack (hidden number problem)
Recover an ECDSA key from many signatures whose nonces leak only a few bits, by reducing the hidden number problem to a lattice with LLL.
Hastad broadcast attack on RSA
Recover a message sent to several recipients under a small public exponent, using the Chinese remainder theorem and an exact integer root.