Breaking RSA with Wiener's Attack

Breaking RSA with Wiener’s Attack

Introduction

Every RSA decryption and signature costs a full modular exponentiation with d. A smaller d makes that faster. It’s a tempting optimization on constrained hardware. In 1990, Michael Wiener analyzed exactly this mistake. Once d drops below roughly the fourth root of n, it can be recovered. All it takes is the public key, (n, e). The tool is continued fractions. There’s no brute force over d, and no factoring attempt. It’s just a classical number-theoretic technique, applied to a ratio the attacker already has.

Table of Contents

• Why a Small d Is Dangerous
• The Attack: Continued Fractions
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Wiener vs. Fermat: Two Ways to Break a Bad Key
• Limitations of This Attack
• FAQ
• References

Why a Small d Is Dangerous

RSA key generation, as the base guide covers, almost always fixes e first. A standard value like 65537 is typical. Then d falls out as whatever the modular inverse happens to be. That produces a d roughly the same size as n. For a real key, that’s hundreds of digits. Reversing that choice seems harmless: pick a small d directly, and derive e from it. e is public anyway, so who cares if it comes out large?

Wiener’s 1990 result is the answer: everyone should care. The math connects e and d through ed ≡ 1 (mod φ(n)). That can be rearranged into ed − kφ(n) = 1 for some integer k. When d is small, e/n becomes an extremely good rational approximation of k/d. It’s good enough that k/d shows up among the early convergents of e/n’s continued fraction expansion. Continued fractions are the classic tool for finding such approximations. They use nothing but the Euclidean algorithm. That turns recovering d into checking a short list of candidates. The entire private key comes with it.

The Attack: Continued Fractions

1. Compute the continued fraction expansion of e/n. Run the Euclidean algorithm on e and n. The sequence of quotients it produces, [a₀; a₁, a₂, …], is the continued fraction.
2. Compute the convergents. Each prefix of that sequence defines a fraction k/d. The standard recurrence is h₀ = a₀, h₁ = a₁a₀+1, then hᵢ = aᵢhᵢ₋₁ + hᵢ₋₂ (denominators follow the same pattern). Each convergent is the best approximation to e/n at its denominator size.
3. Test each convergent k/d as a candidate. Check whether φ_candidate = (ed − 1) / k comes out to a whole number. If it doesn’t, move to the next convergent.
4. Verify against n = pq and φ(n) = n − p − q + 1. A legitimate candidate must also satisfy 0 < φ_candidate < n; anything outside that range can be discarded immediately. p and q are then roots of x² − (n − φ_candidate + 1)x + n = 0. Solve that quadratic. If both roots are positive integers whose product is n, the candidate is correct. d, p, and q are all recovered together.
5. If no convergent works, d wasn’t small enough for this attack. Boneh’s clean formulation of Wiener’s theorem needs two things: d < (1/3) n^(1/4), and comparable-size p, q. In practice, the method sometimes succeeds a little past that bound too. It just loses the guarantee.

The remarkable part is how few candidates typically need testing. A continued fraction with a dozen or so terms is cheap to compute. It usually finds the right convergent within the first several tries. Continued fractions aren’t an arbitrary choice here either. They produce the best possible rational approximation to a ratio, at any given denominator size. That’s exactly the property this attack leans on.

A Worked Example

Using the visualizer’s default values, n = 272483 (secretly 521 × 523) and e = 232663:

1. Continued fraction expansion: e/n = [0; 1, 5, 1, 5, 2, 1, 2, 1, 18, 4, 3, 2], 13 terms, computed by ordinary long division.
2. Convergents, in order: 0/1, 1/1, 5/6, 6/7, 35/41, 76/89, 111/130, 298/349, 409/479, 7660/8971, 31049/36363, 100807/118060, 232663/272483.
3. Testing them one by one: the first two (0/1, 1/1) fail the integer-φ check immediately. The third, 5/6, fails too. Testing the fourth convergent, 6/7: φ_candidate = (232663 × 7 − 1) / 6 = 1628640 / 6 = 271440, a whole number.
4. Solving the quadratic with that φ: x² − (272483 − 271440 + 1)x + 272483 = x² − 1044x + 272483 = 0. The roots come out to 523 and 521, both prime, both positive integers, and 523 × 521 = 272483 exactly. (The code below always assigns the larger root to p.)
5. Recovered private exponent: d = 7. That’s the denominator of the convergent that worked. Nothing more exotic than that.
6. Decrypt. A ciphertext of 84802, captured off the wire, decrypts as C^d mod n = 123456, the original message. It’s recovered from the public key alone.

A private exponent as small as d = 7 falls out of four tested convergents. That’s the entire attack. No brute force, no factoring attempt, beyond one quadratic equation at the very end.

Python Implementation

The interactive visualizer above runs this exact attack in JavaScript. Same continued fraction expansion, same convergent testing, same quadratic solve. Here’s the same attack in Python.

Key Features

• Uses Python’s exact integer arithmetic throughout, including math.isqrt for the discriminant check. That leaves no floating-point rounding risk in the perfect-square test.
• Rejects any candidate φ outside 0 < φ < n before it ever reaches the quadratic solve. That’s a cheap filter Euler’s totient must always satisfy.
• Stops at the first valid convergent, matching Wiener’s theorem exactly. For a genuinely small d, at most one convergent should ever pass both tests.
• Recovers p and q as a side effect, not just d. The quadratic solve needs them anyway, to verify the candidate.

Code

# wiener_breaker.py
#
# Recovers a small RSA private exponent d from the public key (n, e)
# alone, using continued fractions. Wiener's 1990 result: if
# d < (1/3) * n^(1/4), the fraction k/d hides among the early convergents
# of the continued fraction expansion of e/n, and testing each one is
# enough to find it. No brute force over d, no factoring attempt.

import math


def continued_fraction(num, den):
    cf = []
    while den:
        cf.append(num // den)
        num, den = den, num % den
    return cf


def convergents(cf):
    nums, dens = [], []
    for i, a in enumerate(cf):
        if i == 0:
            h, k = a, 1
        elif i == 1:
            h, k = a * cf[0] + 1, a
        else:
            h, k = a * nums[-1] + nums[-2], a * dens[-1] + dens[-2]
        nums.append(h)
        dens.append(k)
    return list(zip(nums, dens))


def wiener_attack(e, n):
    """Returns {'d', 'p', 'q'} (p >= q, matching the visualizer), or None if no small enough d is found."""
    cf = continued_fraction(e, n)
    for k, d in convergents(cf):
        if k == 0 or (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        if not 0 < phi < n:
            continue
        b = n - phi + 1
        disc = b * b - 4 * n
        if disc < 0:
            continue
        sq = math.isqrt(disc)
        if sq * sq != disc or (b + sq) % 2 != 0:
            continue
        p, q = (b + sq) // 2, (b - sq) // 2
        if p * q == n and p > 1 and q > 1:
            return {'d': d, 'p': p, 'q': q}
    return None


if __name__ == '__main__':
    n = 272483
    e = 232663
    ciphertext = 84802

    result = wiener_attack(e, n)
    print(f"Recovered d = {result['d']}")
    print(f"Recovered p = {result['p']}, q = {result['q']}")
    assert result['p'] * result['q'] == n

    message = pow(ciphertext, result['d'], n)
    print(f"Decrypted message: {message}")

Running this against the same public key as the visualizer produces:

Recovered d = 7
Recovered p = 523, q = 521
Decrypted message: 123456

This matches the visualizer’s own result exactly. It matches the worked example above, step for step.

For Fun: The Whole Attack in 5 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version fuses the convergent search, the quadratic test, and decryption into one expression.

import math; n,e,c=272483,232663,84802; cf=[]; H,K=[0,1],[1,0]; a,b=e,n
while b: cf.append(a//b); a,b=b,a%b
for x in cf: H.append(x*H[-1]+H[-2]); K.append(x*K[-1]+K[-2])
res=next(((d,p,q) for kk,d in zip(H[2:],K[2:]) if kk and (e*d-1)%kk==0 for phi in [(e*d-1)//kk] for b2 in [n-phi+1] for disc in [b2*b2-4*n] if disc>=0 for sq in [math.isqrt(disc)] if sq*sq==disc and (b2+sq)%2==0 for p,q in [((b2+sq)//2,(b2-sq)//2)] if p*q==n and p>1 and q>1), None)
print(f"Recovered d = {res[0]}\nRecovered p = {res[1]}, q = {res[2]}\nDecrypted message: {pow(c,res[0],n)}")

Verified against the readable version’s output: d = 7, p = 523, q = 521, decrypted message 123456. The for ... in [...] clauses bind intermediate values, like phi and disc. That’s a trick for avoiding a walrus operator or a separate loop body.

Interactive Visualizer

Try it above. Enter any (n, e) pair, and watch the continued fraction expansion play out. It goes convergent by convergent, until one produces a valid key. Add a captured ciphertext to see the recovered d decrypt a real message.

Wiener vs. Fermat: Two Ways to Break a Bad Key

Both attacks share a lesson. RSA’s security proof depends on preconditions the textbook formula never enforces. Nothing in “choose e, compute d as its inverse” stops d from coming out small. It just takes e chosen backwards from a small d instead. Wiener’s attack is the formal proof that this shortcut isn’t safe.

Limitations of This Attack

Wiener’s theorem gives a specific bound. It guarantees success roughly when d < (1/3) n^(1/4). Above that threshold, k/d isn’t guaranteed to appear among e/n’s convergents. This attack simply won’t find it. It’s not a general attack on RSA private exponents, only on ones chosen unusually small.

The bound also assumes p and q are of comparable size. That’s the normal case for properly generated RSA keys. Extremely unbalanced primes can throw off the approximation this attack relies on. That can weaken or break the guarantee entirely.

The attack also needs e generated backwards, from a small d. That means picking d first, then deriving e from it. Standard practice is the opposite: fix e = 65537, let d fall out large. Almost every real implementation follows that standard. Exploitable cases are rare in the wild. Mostly they show up in older or custom protocols that chose small d for performance.

Extensions exist. Boneh and Durfee’s 1999 lattice-based improvement pushes the bound closer to d < n^0.292. It recovers somewhat larger private exponents than the classical method covers. Those use lattice reduction rather than continued fractions, out of scope for this post.

FAQ

How small does d actually need to be for this attack to work?

Wiener’s original bound is roughly d < (1/3) n^(1/4). For a 2048-bit RSA modulus, that’s still a 512-bit number, enormous in absolute terms. But it’s tiny relative to a full-size private exponent, which is what actually matters here. That’s the striking part. A d that looks comfortably large can still be well within this attack’s reach.

Does this attack need to know p or q in advance?

No. It needs only the public key, (n, e). Recovering p and q is a side effect of verifying the candidate d. It’s not a prerequisite for finding it.

Why does nobody just pick e small and derive d normally instead?

Because that’s exactly what standard practice does: fix e = 65537, derive d. That’s safe. A small e doesn’t make d small. It makes d roughly the same size as n instead. The dangerous mistake runs the other direction. It picks d small on purpose, then derives e from it.

Is this the same as the common modulus attack or Fermat factorization?

No. Fermat factorization exploits p and q being close together, using only n. The common modulus attack exploits reusing one n with two different e values. Wiener’s attack exploits d specifically being small. All three are precondition failures in RSA’s security proof, but each targets a different precondition.

Can this attack be extended to recover slightly larger private exponents?

Yes. Boneh and Durfee’s 1999 lattice-based attack extends the recoverable range to roughly d < n^0.292. That’s noticeably larger than Wiener’s n^0.25-ish bound. It needs lattice basis reduction (LLL) instead of the simpler continued-fraction approach this post covers.

References

1. Wiener, M. J. “Cryptanalysis of Short RSA Secret Exponents.” IEEE Transactions on Information Theory, 1990. Available at: https://ieeexplore.ieee.org/document/54902

2. Boneh, D. and Durfee, G. “Cryptanalysis of RSA with Private Key d Less than N^0.292.” EUROCRYPT 1999.

3. Boneh, D. “Twenty Years of Attacks on the RSA Cryptosystem.” Notices of the AMS, 1999. Available at: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

4. Wikipedia. “Wiener’s attack.” Available at: https://en.wikipedia.org/wiki/Wiener%27s_attack