Wiener’s attack on small RSA private exponents

A 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: e is large - typically comparable in magnitude to n rather than the usual 65537.
• Bound: works for d < n^(1/4)/3. Boneh-Durfee extends this to roughly d < n^0.292 using lattice reduction.
• Cost: milliseconds, regardless of key size.