wieners-attack-small-d.ipynb

Kernel: SageMath 10.0

Break: Wiener's Attack on Small Private Exponent

Module 04 | Breaking Weak Parameters

Use continued fractions to recover $d$ when $d < n^{1/4}/3$.

Why This Matters

RSA decryption computes $c^d \bmod n$. When $d$ is large (as it should be), this is expensive --- especially on constrained devices like smart cards.

A tempting optimization: choose a small $d$ to make decryption fast, and let $e$ be the large value. After all, the public key is used for encryption, and the server does the heavy lifting for decryption... right?

Wrong. Michael Wiener showed in 1990 that if $d < n^{1/4}/3$, the private key can be recovered from the public key $(n, e)$ alone, using nothing more than the continued fraction expansion of $e/n$.

The attack is elegant, fast, and devastating.

The Setup: RSA with a Deliberately Small $d$

We generate an RSA modulus $n = pq$ and deliberately choose a small private exponent $d$, then compute $e = d^{-1} \bmod \varphi(n)$.

The attacker sees only the public key $(n, e)$ and must recover $d$.

# === Generate RSA key with small d ===

set_random_seed(2024)

# Generate two primes of roughly equal size (~128 bits each, so n ~ 256 bits)
p = random_prime(2^128, lbound=2^127)
q = random_prime(2^128, lbound=2^127)
n = p * q
phi_n = (p - 1) * (q - 1)

print(f'n = {n}')
print(f'n has {n.nbits()} bits')
print(f'n^(1/4) ~ 2^{RR(n.nbits())/4:.0f} ~ {Integer(floor(n^(1/4)))}')
print()

# Choose a small d: must be coprime to phi(n)
# Wiener's bound: d < n^(1/4) / 3
bound = Integer(floor(n^(1/4) / 3))
print(f'Wiener bound: d < n^(1/4)/3 = {bound}')
print(f'Wiener bound bits: {bound.nbits()}')
print()

# Pick a small d well within the bound
while True:
    d_small = ZZ.random_element(2^50, 2^55)
    if gcd(d_small, phi_n) == 1:
        break

e_large = inverse_mod(d_small, phi_n)

print(f'Private key d = {d_small}  ({d_small.nbits()} bits)')
print(f'Public key  e = {e_large}  ({e_large.nbits()} bits)')
print(f'd < n^(1/4)/3? {d_small < bound}  (attack should work)')
print()
print(f'Notice: e is almost as large as n. This is the telltale sign.')

Step 1: The Key Relationship

Since $ed \equiv 1 \pmod{\varphi(n)}$, there exists an integer $k$ such that:

$$ed = k\varphi(n) + 1$$

Dividing both sides by $d \cdot \varphi(n)$:

$$\frac{e}{\varphi(n)} = \frac{k}{d} + \frac{1}{d \cdot \varphi(n)}$$

Since $\varphi(n) \approx n$ (they differ by $O(\sqrt{n})$), we get:

$$\frac{e}{n} \approx \frac{k}{d}$$

So $k/d$ is a very good rational approximation to $e/n$. Continued fractions are guaranteed to find all such good approximations as convergents.

# === Verify the approximation ===

k_actual = (e_large * d_small - 1) // phi_n

print('The exact relationship:')
print(f'  e * d = k * phi(n) + 1')
print(f'  {e_large} * {d_small} = {k_actual} * phi(n) + 1')
print(f'  Check: {e_large * d_small == k_actual * phi_n + 1}')
print()

# How close is e/n to k/d?
approx_error = abs(RR(e_large)/RR(n) - RR(k_actual)/RR(d_small))
print(f'e/n     = {RR(e_large/n)}')
print(f'k/d     = {RR(k_actual/d_small)}')
print(f'|e/n - k/d| = {approx_error:.6e}')
print()
print(f'This is an incredibly tight approximation.')
print(f'Continued fractions will find k/d as a convergent of e/n.')

Step 2: Compute the Continued Fraction Expansion of $e/n$

The continued fraction of a rational number $a/b$ is a sequence of integers $[a_0; a_1, a_2, \ldots]$ such that:

$$\frac{a}{b} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}$$

The convergents $p_0/q_0, p_1/q_1, \ldots$ are the best rational approximations with small denominators. Wiener's theorem guarantees that $k/d$ appears among them.

# === Continued fraction expansion of e/n ===

# SageMath has built-in continued fraction support
cf = continued_fraction(e_large / n)

print('Continued fraction coefficients of e/n (first 20):')
print(list(cf)[:20])
print()

# Show the convergents
convergents = cf.convergents()
print('First 15 convergents:')
for i, conv in enumerate(convergents[:15]):
    ki = conv.numerator()
    di = conv.denominator()
    marker = ' <-- CORRECT k/d!' if di == d_small else ''
    print(f'  [{i:2d}] k/d = {ki}/{di}{marker}')

Step 3: Test Each Convergent

For each convergent $k_i/d_i$, the attacker checks whether $d_i$ is the correct private key. The test is:

1. If $k_i = 0$, skip (not meaningful).

2. Compute $\varphi_i = (e \cdot d_i - 1) / k_i$. If this isn't an integer, skip.

3. If $\varphi_i$ is an integer, try to factor $n$ using $\varphi(n) = n - p - q + 1$, which gives $p + q = n - \varphi_i + 1$. Solve the quadratic $x^2 - (p+q)x + n = 0$.

4. If the roots are integers and their product is $n$, we found $d$.

# === Wiener's attack: full implementation ===

def wiener_attack(e, n):
    """Attempt to recover d from public key (n, e) using Wiener's attack."""
    cf = continued_fraction(e / n)
    convergents = cf.convergents()
    
    for i, conv in enumerate(convergents):
        ki = conv.numerator()
        di = conv.denominator()
        
        if ki == 0:
            continue
        
        # Check if (e*di - 1) / ki is an integer
        if (e * di - 1) % ki != 0:
            continue
        
        phi_candidate = (e * di - 1) // ki
        
        # phi(n) = n - p - q + 1, so p + q = n - phi + 1
        s = n - phi_candidate + 1  # s = p + q
        
        # p and q are roots of x^2 - s*x + n = 0
        discriminant = s^2 - 4*n
        if discriminant < 0:
            continue
        
        sqrt_disc = isqrt(discriminant)
        if sqrt_disc^2 != discriminant:
            continue
        
        p_candidate = (s + sqrt_disc) // 2
        q_candidate = (s - sqrt_disc) // 2
        
        if p_candidate * q_candidate == n:
            return di, p_candidate, q_candidate, i
    
    return None

# Run the attack
t0 = walltime()
result = wiener_attack(e_large, n)
t1 = walltime()

if result:
    d_recovered, p_recovered, q_recovered, convergent_index = result
    print(f'=== ATTACK SUCCESSFUL ===')
    print(f'Found d at convergent index {convergent_index}')
    print(f'Recovered d = {d_recovered}')
    print(f'Actual d    = {d_small}')
    print(f'Match: {d_recovered == d_small}')
    print()
    print(f'Also recovered the factorization:')
    print(f'  p = {p_recovered}')
    print(f'  q = {q_recovered}')
    print(f'  p*q = n? {p_recovered * q_recovered == n}')
    print()
    print(f'Attack time: {(t1-t0)*1000:.2f} ms')
else:
    print('Attack failed (d was too large for Wiener bound)')

# === Verify: use the recovered d to decrypt ===

m = 314159265358979  # A secret message
c = power_mod(m, e_large, n)
m_decrypted = power_mod(c, d_recovered, n)

print(f'Message:    m = {m}')
print(f'Ciphertext: c = m^e mod n')
print(f'Decrypted:  c^d mod n = {m_decrypted}')
print(f'Match: {m == m_decrypted}')
print()
print('The attacker can now decrypt ALL messages encrypted with this public key.')

The Fix: Standard Key Generation

The defense is simple: use standard RSA key generation where $e$ is small (typically $e = 65537 = 2^{16} + 1$) and $d$ is large (roughly the same size as $n$).

With standard key generation:

• $d \approx n$, so $d \gg n^{1/4}$

• The continued fraction expansion has $O(\log n)$ convergents

• None of them will have a denominator close to $d$

Wiener's attack only works when $d < n^{1/4}/3$. For a 2048-bit RSA key, this means $d$ must be less than 512 bits --- a standard $d$ is around 2048 bits.

Exercises

1. Boundary testing: Try generating keys where $d$ is just above $n^{1/4}/3$. At what point does the attack start failing? Does it fail abruptly or gradually?

2. Key sizes: Run the attack on 512-bit, 1024-bit, and 2048-bit RSA keys with small $d$. How does the attack time scale with key size?

3. Boneh-Durfee extension: Wiener's bound is $d < n^{1/4}$. Boneh and Durfee (1999) extended this to $d < n^{0.292}$ using lattice techniques. How much more of the key space does this cover?

Summary

Component	Role in the Attack
$ed \equiv 1 \pmod{\varphi(n)}$	Creates the approximation $e/n \approx k/d$
Continued fractions	Efficiently enumerate all good rational approximations
Convergent test	Check each $d_i$ candidate by trying to factor $n$
Small $d$ bound	$d < n^{1/4}/3$ guarantees $k/d$ appears as a convergent

Key takeaways:

• Choosing a small $d$ for fast decryption is catastrophically insecure.

• Wiener's attack recovers $d$ in polynomial time using only the public key.

• The attack also recovers the factorization of $n$ as a bonus.

• Standard RSA key generation (small $e$, large $d$) is immune to this attack.

• The beautiful mathematics: the theory of continued fractions, developed by Euler in the 1700s, directly breaks a modern cryptosystem when parameters are chosen poorly.

---

Back to Module 04: Number Theory and RSA