Chapter 26: Attacks on RSA

26.1 Introduction

The RSA cryptosystem, introduced in 1978 by Rivest, Shamir, and Adleman, remains one of the most widely deployed public-key schemes. Its security rests on the computational difficulty of factoring the product \(n = pq\) of two large primes. However, improper parameter choices can render RSA vulnerable to a variety of elegant mathematical attacks that do not require factoring \(n\) at all.

In this chapter we study five classical attacks:

Attack	Weakness exploited	Key idea
Small public exponent (\(e=3\))	Tiny \(e\), small message	Cube root of ciphertext
Common modulus	Same \(n\) with two coprime exponents	Extended GCD recovers \(m\)
Wiener’s continued fraction	Small private exponent \(d\)	Convergents of \(e/n\) reveal \(d\)
Hastad’s broadcast	Same \(m\) sent to \(e\) recipients	CRT + integer \(e\)-th root
Fermat factorization	\(p \approx q\)	Difference of squares

Each attack illustrates a fundamental principle: cryptographic security requires not just hard problems, but careful implementation.

Prerequisites

Familiarity with RSA key generation and the extended Euclidean algorithm (Chapter 25).

26.2 Utility Functions

We begin with basic number-theoretic helpers that all subsequent attacks rely on. These use only Python’s standard library and NumPy.

import numpy as np
import math
import random

def gcd(a, b):
    """Euclidean algorithm for GCD."""
    while b:
        a, b = b, a % b
    return abs(a)

def extended_gcd(a, b):
    """Extended Euclidean algorithm.
    Returns (g, x, y) such that a*x + b*y = g = gcd(a, b).
    """
    r, r1 = a, b
    s, s1 = 1, 0
    t, t1 = 0, 1
    while r1 != 0:
        q = r // r1
        r, r1 = r1, r - q * r1
        s, s1 = s1, s - q * s1
        t, t1 = t1, t - q * t1
    return r, s, t

def mod_inverse(a, n):
    """Compute modular inverse of a modulo n."""
    g, x, _ = extended_gcd(a, n)
    if g != 1:
        raise ValueError(f"{a} and {n} are not coprime")
    return x % n

def integer_kth_root(x, k):
    """Compute the integer k-th root of x using Newton's method.
    Returns the largest integer r such that r^k <= x.
    """
    if x < 0:
        raise ValueError("x must be non-negative")
    if x == 0:
        return 0
    # Initial guess via floating-point
    r = int(round(x ** (1.0 / k)))
    # Refine with Newton's method for large integers
    # r_{i+1} = ((k-1)*r_i + x // r_i^{k-1}) // k
    while True:
        rk = r ** k
        if rk == x:
            return r
        r_next = ((k - 1) * r + x // (r ** (k - 1))) // k
        if r_next >= r:
            break
        r = r_next
    # Final adjustment: ensure r^k <= x < (r+1)^k
    while r ** k > x:
        r -= 1
    while (r + 1) ** k <= x:
        r += 1
    return r

def is_perfect_power(x, k):
    """Check if x is a perfect k-th power."""
    r = integer_kth_root(x, k)
    return r ** k == x, r

# --- Simple RSA helpers for demonstrations ---
def is_probable_prime(n, trials=5):
    """Miller-Rabin primality test."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    for _sp in [3,5,7,11,13,17,19,23,29,31,37,41,43,47]:
        if n == _sp: return True
        if n % _sp == 0: return False
    # Write n-1 as 2^s * d
    s, d = 0, n - 1
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(trials):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def gen_prime(bits):
    """Generate a random probable prime of the given bit length."""
    while True:
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_probable_prime(p):
            return p

print("Utility functions loaded.")
print(f"gcd(48, 18) = {gcd(48, 18)}")
print(f"mod_inverse(7, 120) = {mod_inverse(7, 120)}")
print(f"integer_kth_root(27, 3) = {integer_kth_root(27, 3)}")
print(f"is_perfect_power(125, 3) = {is_perfect_power(125, 3)}")

Utility functions loaded.
gcd(48, 18) = 6
mod_inverse(7, 120) = 103
integer_kth_root(27, 3) = 3
is_perfect_power(125, 3) = (True, 5)

26.3 Attack 1: Small Public Exponent (\(e = 3\))

The vulnerability

When the public exponent is small (commonly \(e = 3\)) and the plaintext \(m\) is also small enough that \(m^e < n\), the ciphertext is simply

\[ c = m^3 \bmod n = m^3\]

since no modular reduction takes place. The attacker recovers \(m\) by computing the ordinary cube root of \(c\).

When does this apply?

This attack works whenever \(m < n^{1/e}\). For a 2048-bit modulus with \(e=3\), messages shorter than about 682 bits are vulnerable.

import numpy as np
import math
import random

def small_exponent_attack(c, e):
    """Recover plaintext m from c = m^e when m^e < n (no modular reduction).
    Returns m if c is a perfect e-th power, else None.
    """
    r = integer_kth_root(c, e)
    if r ** e == c:
        return r
    return None

# --- Demonstration ---
# Generate RSA parameters with e=3
random.seed(42)
e = 3
while True:
    p = gen_prime(64)
    q = gen_prime(64)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    if gcd(e, phi_n) == 1:
        break
d = mod_inverse(e, phi_n)

# Choose a small message (much smaller than n^{1/3})
m_original = 123456789012345678901234567890
c = pow(m_original, e, n)

print(f"n has {n.bit_length()} bits")
print(f"m has {m_original.bit_length()} bits  (threshold ~ {n.bit_length() // e} bits)")
print(f"m^e < n? {m_original ** e < n}")
print()

# Attack
m_recovered = small_exponent_attack(c, e)
print(f"Original message:  {m_original}")
print(f"Recovered message: {m_recovered}")
print(f"Attack successful: {m_recovered == m_original}")

n has 128 bits
m has 97 bits  (threshold ~ 42 bits)
m^e < n? False

Original message:  123456789012345678901234567890
Recovered message: None
Attack successful: False

Countermeasure

The standard defense is OAEP padding (Optimal Asymmetric Encryption Padding, RFC 8017), which randomizes the message so that \(m^e\) is always at least as large as \(n\).

26.4 Attack 2: Common Modulus Attack

The vulnerability

Suppose the same modulus \(n\) is shared between two users who have different public exponents \(e_1, e_2\) with \(\gcd(e_1, e_2) = 1\). If the same plaintext \(m\) is encrypted to both:

\[ c_1 = m^{e_1} \bmod n, \qquad c_2 = m^{e_2} \bmod n\]

then an attacker who knows \((n, e_1, c_1, e_2, c_2)\) can recover \(m\) without knowing either private key.

Key idea: By the extended Euclidean algorithm, find integers \(x, y\) such that \(x e_1 + y e_2 = 1\). Then:

\[ c_1^x \cdot c_2^y \equiv m^{x e_1 + y e_2} = m^1 = m \pmod{n}\]

Note: if \(x\) or \(y\) is negative, we use the modular inverse (e.g., \(c_1^{-1} \bmod n\)).

import numpy as np
import math
import random

def common_modulus_attack(n, e1, c1, e2, c2):
    """Recover plaintext m given two ciphertexts of the same message
    under the same modulus but different coprime exponents.
    
    Parameters
    ----------
    n  : RSA modulus (shared)
    e1 : first public exponent
    c1 : first ciphertext  (c1 = m^e1 mod n)
    e2 : second public exponent
    c2 : second ciphertext (c2 = m^e2 mod n)
    
    Returns
    -------
    m : recovered plaintext
    """
    g, x, y = extended_gcd(e1, e2)
    if g != 1:
        raise ValueError(f"e1 and e2 are not coprime (gcd = {g})")
    
    # Handle negative exponents via modular inverse
    if x < 0:
        c1 = mod_inverse(c1, n)
        x = -x
    if y < 0:
        c2 = mod_inverse(c2, n)
        y = -y
    
    m = (pow(c1, x, n) * pow(c2, y, n)) % n
    return m

# --- Demonstration ---
random.seed(123)
p = gen_prime(64)
q = gen_prime(64)
n = p * q
phi_n = (p - 1) * (q - 1)

# Two coprime exponents sharing the same modulus
e1 = 65537
e2 = 65539  # next prime after 65537 -- coprime to e1
assert gcd(e1, e2) == 1
assert gcd(e1, phi_n) == 1 and gcd(e2, phi_n) == 1

d1 = mod_inverse(e1, phi_n)
d2 = mod_inverse(e2, phi_n)

# Message must be smaller than n for RSA to work correctly
m_original = 31415926535897932384626433832
assert m_original < n, f"Message {m_original} must be less than modulus {n}"
c1 = pow(m_original, e1, n)
c2 = pow(m_original, e2, n)

# Attack -- no knowledge of d1 or d2!
m_recovered = common_modulus_attack(n, e1, c1, e2, c2)

print(f"n              = {n}")
print(f"n has {n.bit_length()} bits")
print(f"m has {m_original.bit_length()} bits")
print(f"m < n? {m_original < n}")
print(f"Original message:  {m_original}")
print(f"Recovered message: {m_recovered}")
print(f"Attack successful: {m_recovered == m_original}")

n              = 235870101702825942936038743701899910433
n has 128 bits
m has 95 bits
m < n? True
Original message:  31415926535897932384626433832
Recovered message: 31415926535897932384626433832
Attack successful: True

Lesson

Never reuse the RSA modulus \(n\) across different key pairs. Each user must generate their own independent primes.

26.5 Attack 3: Wiener’s Continued Fraction Attack

Background

In 1990, Michael Wiener showed that if the private exponent \(d\) is small – specifically, if

\[ d < \frac{1}{3} n^{1/4}\]

then \(d\) can be efficiently recovered from the public key \((n, e)\) alone, using the theory of continued fractions.

The mathematical idea

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

\[ ed - k\,\phi(n) = 1\]

Dividing by \(d\,\phi(n)\):

\[ \frac{e}{\phi(n)} - \frac{k}{d} = \frac{1}{d\,\phi(n)}\]

Since \(\phi(n) \approx n\), the fraction \(k/d\) is a very close rational approximation to \(e/n\). By a classical theorem in Diophantine approximation, such close approximations appear among the convergents of the continued fraction expansion of \(e/n\).

Algorithm

1. Compute the continued fraction expansion of \(e/n\).

2. For each convergent \(k/d\), check whether the corresponding \(\phi(n) = (ed - 1)/k\) yields a valid factorization of \(n\).

3. Validate by checking that \(\phi(n)\) gives integer roots to \(x^2 - (n - \phi(n) + 1)x + n = 0\).

import numpy as np
import math
import random

def continued_fraction(numerator, denominator):
    """Generate the continued fraction coefficients [a0; a1, a2, ...] of numerator/denominator.
    
    Returns
    -------
    list of int : the continued fraction coefficients
    """
    coefficients = []
    while denominator != 0:
        q = numerator // denominator
        coefficients.append(q)
        numerator, denominator = denominator, numerator - q * denominator
    return coefficients

def convergents(cf_coeffs):
    """Generate all convergents p_i/q_i from continued fraction coefficients.
    
    Yields
    ------
    (p, q) : numerator and denominator of each convergent
    """
    # p_{-1} = 1, p_{-2} = 0;  q_{-1} = 0, q_{-2} = 1
    p_prev, p_curr = 0, 1
    q_prev, q_curr = 1, 0
    for a in cf_coeffs:
        p_prev, p_curr = p_curr, a * p_curr + p_prev
        q_prev, q_curr = q_curr, a * q_curr + q_prev
        yield p_curr, q_curr

def wiener_attack(n, e):
    """Wiener's continued fraction attack on RSA with small d.
    
    Parameters
    ----------
    n : RSA modulus
    e : public exponent
    
    Returns
    -------
    d : recovered private exponent, or None if the attack fails
    """
    cf = continued_fraction(e, n)
    for k, d_candidate in convergents(cf):
        if k == 0:
            continue
        # Check: (e * d - 1) must be divisible by k
        if (e * d_candidate - 1) % k != 0:
            continue
        phi_candidate = (e * d_candidate - 1) // k
        # 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 * s - 4 * n
        if discriminant < 0:
            continue
        sqrt_disc = math.isqrt(discriminant)
        if sqrt_disc * sqrt_disc != discriminant:
            continue
        p_cand = (s + sqrt_disc) // 2
        q_cand = (s - sqrt_disc) // 2
        if p_cand * q_cand == n:
            return d_candidate
    return None

# Quick test with known small parameters
print("continued_fraction(355, 113) =", continued_fraction(355, 113))
print("Convergents:")
for p, q in convergents(continued_fraction(355, 113)):
    print(f"  {p}/{q} = {float(p/q):.10f}")
print(f"  Exact: 355/113 = {float(355/113):.10f}")

continued_fraction(355, 113) = [3, 7, 16]
Convergents:
  3/1 = 3.0000000000
  22/7 = 3.1428571429
  355/113 = 3.1415929204
  Exact: 355/113 = 3.1415929204

26.5.1 Wiener’s Attack – Demonstration

We generate a deliberately vulnerable RSA key pair with a small private exponent \(d\), then show that Wiener’s attack recovers it.

import numpy as np
import math
import random

def generate_wiener_vulnerable_key(bits=256):
    """Generate an RSA key pair that is vulnerable to Wiener's attack.
    
    We choose a small d < n^{1/4} / 3, then compute e = d^{-1} mod phi(n).
    """
    while True:
        p = gen_prime(bits // 2)
        q = gen_prime(bits // 2)
        if p == q:
            continue
        n = p * q
        phi_n = (p - 1) * (q - 1)
        # Choose small d: d < n^{1/4} / 3
        bound = math.isqrt(math.isqrt(n)) // 3
        d = random.randrange(3, min(bound, phi_n), 2)  # odd, small
        if gcd(d, phi_n) != 1:
            continue
        e = mod_inverse(d, phi_n)
        if e < n:  # e should be reasonable
            # Verify the key works
            test_m = 42
            if pow(pow(test_m, e, n), d, n) == test_m:
                return n, e, d, p, q

random.seed(2026)
n, e, d_true, p, q = generate_wiener_vulnerable_key(bits=256)

print(f"n       = {n}")
print(f"n bits  = {n.bit_length()}")
print(f"e       = {e}")
print(f"d_true  = {d_true}")
print(f"d bits  = {d_true.bit_length()}")
print(f"Bound n^(1/4)/3 = {math.isqrt(math.isqrt(n)) // 3}")
print()

# Run Wiener's attack
d_recovered = wiener_attack(n, e)
print(f"Recovered d = {d_recovered}")
print(f"Attack successful: {d_recovered == d_true}")

# Verify decryption
m = 2718281828459045235360287471352662497757
c = pow(m, e, n)
m_dec = pow(c, d_recovered, n)
print(f"Decryption check: {m_dec == m}")

n       = 70743892589268025781434552282324487839275612031774457156060346649815373462537
n bits  = 256
e       = 41773685468847482240353352545180890379536189209248091024966610572557309276087
d_true  = 1460006531104029223
d bits  = 61
Bound n^(1/4)/3 = 5436269561784850578

Recovered d = 1460006531104029223
Attack successful: True
Decryption check: True

26.5.2 Visualizing Convergent Approximations

The following plot shows how the convergents of \(e/n\) approach the true value \(k/d\). The correct convergent is marked.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import math

# Use the Wiener-vulnerable key from the previous cell
cf = continued_fraction(e, n)

# Collect convergent ratios and their errors vs e/n
conv_list = list(convergents(cf))
exact_ratio = e / n  # float approximation for plotting

indices = []
log_errors = []
correct_idx = None

for i, (p_i, q_i) in enumerate(conv_list):
    if q_i == 0:
        continue
    # Compute |p_i/q_i - e/n| using exact integer arithmetic
    # |p_i * n - e * q_i| / (q_i * n)
    numerator_diff = abs(p_i * n - e * q_i)
    if numerator_diff == 0:
        continue
    # Use log10 for plotting
    log_err = float(np.log10(float(numerator_diff))) - float(np.log10(float(q_i))) - float(np.log10(float(n)))
    indices.append(i)
    log_errors.append(log_err)
    if q_i == d_true:
        correct_idx = len(indices) - 1

indices = np.array(indices)
log_errors = np.array(log_errors)

fig, ax = plt.subplots(figsize=(10, 5))
ax.plot(indices, log_errors, 'b.-', markersize=6, label='Convergent error')
if correct_idx is not None:
    ax.plot(indices[correct_idx], log_errors[correct_idx], 'r*', markersize=18,
            label=f'Correct convergent (d={d_true})', zorder=5)
ax.set_xlabel('Convergent index $i$', fontsize=12)
ax.set_ylabel(r'$\log_{10}|p_i/q_i - e/n|$', fontsize=12)
ax.set_title("Wiener's Attack: Convergent Approximations to $e/n$", fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('wiener_convergents.png', dpi=150, bbox_inches='tight')
plt.show()

Wiener’s bound

The attack is guaranteed to succeed when \(d < n^{1/4}/3\). Boneh and Durfee (2000) later improved this bound to \(d < n^{0.292}\) using lattice techniques, though that attack is significantly more complex to implement.

26.6 Attack 4: Hastad’s Broadcast Attack

The vulnerability

In 1985, Johan Hastad showed that if the same plaintext \(m\) is encrypted with the same small exponent \(e\) and sent to \(e\) different recipients with moduli \(n_1, n_2, \ldots, n_e\), then \(m\) can be recovered.

Given:

\[ c_i \equiv m^e \pmod{n_i} \quad \text{for } i = 1, \ldots, e\]

By the Chinese Remainder Theorem (CRT), since the \(n_i\) are pairwise coprime, there exists a unique \(x\) with \(0 \le x < N = \prod n_i\) such that \(x \equiv c_i \pmod{n_i}\).

Since \(m < n_i\) for all \(i\), we have \(m^e < N\), so \(x = m^e\) exactly (no modular reduction). Then \(m = \lfloor x^{1/e} \rfloor\).

import numpy as np
import math
import random

def crt(remainders, moduli):
    """Chinese Remainder Theorem (Gauss's algorithm).
    
    Given remainders [c1, c2, ...] and pairwise coprime moduli [n1, n2, ...],
    returns the unique x in [0, N) where N = prod(moduli) such that
    x = ci (mod ni) for all i.
    """
    N = 1
    for ni in moduli:
        N *= ni
    x = 0
    for ci, ni in zip(remainders, moduli):
        Ni = N // ni
        mi = mod_inverse(Ni, ni)
        x += ci * Ni * mi
    return x % N

def hastad_broadcast(ciphertexts, moduli, e):
    """Hastad's broadcast attack.
    
    Parameters
    ----------
    ciphertexts : list of int, ciphertext from each recipient
    moduli      : list of int, RSA modulus for each recipient
    e           : public exponent (same for all recipients)
    
    Returns
    -------
    m : recovered plaintext, or None if attack fails
    """
    assert len(ciphertexts) >= e, f"Need at least e={e} ciphertexts"
    assert len(ciphertexts) == len(moduli)
    
    # Use first e ciphertexts
    x = crt(ciphertexts[:e], moduli[:e])
    perfect, m = is_perfect_power(x, e)
    if perfect:
        return m
    return None

# --- Demonstration with e = 3 ---
e = 3

# Use small moduli: products of primes where gcd(3, phi) == 1
# n1 = 55 = 5 * 11, phi = 4 * 10 = 40, gcd(3, 40) = 1 ✓
# n2 = 77 = 7 * 11  -> phi = 60, gcd(3,60)=3 ✗
# n2 = 91 = 7 * 13, phi = 6 * 12 = 72, gcd(3, 72) = 3 ✗
# n2 = 221 = 13 * 17, phi = 12 * 16 = 192, gcd(3, 192) = 3 ✗
# n2 = 323 = 17 * 19, phi = 16 * 18 = 288, gcd(3, 288) = 3 ✗
# n2 = 3233 = 53 * 61, phi = 52 * 60 = 3120, gcd(3, 3120) = 3 ✗
# We need (p-1)*(q-1) not divisible by 3.
# p-1 not div by 3 => p mod 3 != 1 => p mod 3 == 2
# q-1 not div by 3 => q mod 3 != 1 => q mod 3 == 2
# Primes ≡ 2 (mod 3): 2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, ...
# n1 = 5 * 11 = 55, phi = 40, gcd(3,40) = 1 ✓
# n2 = 17 * 23 = 391, phi = 352, gcd(3,352) = 1 ✓  
# n3 = 29 * 41 = 1189, phi = 1120, gcd(3,1120) = 1 ✓

n1 = 5 * 11    # = 55
n2 = 17 * 23   # = 391
n3 = 29 * 41   # = 1189
moduli = [n1, n2, n3]

# Verify pairwise coprimality
for i in range(len(moduli)):
    for j in range(i + 1, len(moduli)):
        assert gcd(moduli[i], moduli[j]) == 1, f"Moduli {moduli[i]} and {moduli[j]} not coprime"

# Choose a message: m^3 < N = 55 * 391 * 1189 = 25,565,145
# So m < cube_root(25565145) ≈ 294
m_original = 42

ciphertexts = [pow(m_original, e, ni) for ni in moduli]

print(f"Message m = {m_original}")
print(f"m has {m_original.bit_length()} bits")
print(f"Moduli: {moduli}")
print(f"N = {n1*n2*n3}")
print(f"m^e = {m_original**e} < N = {n1*n2*n3}: {m_original**e < n1*n2*n3}")
print(f"Ciphertexts: {ciphertexts}")
print()

# Attack
m_recovered = hastad_broadcast(ciphertexts, moduli, e)
print(f"Recovered m = {m_recovered}")
print(f"Attack successful: {m_recovered == m_original}")

Message m = 42
m has 6 bits
Moduli: [55, 391, 1189]
N = 25569445
m^e = 74088 < N = 25569445: True
Ciphertexts: [3, 189, 370]

Recovered m = 42
Attack successful: True

Historical note

Hastad’s original 1985 result applied to unpadded RSA. Coppersmith (1997) later showed that even certain forms of padding do not prevent broadcast attacks, using his lattice-based technique for finding small roots of polynomials modulo composite numbers.

26.7 Attack 5: Fermat Factorization

The vulnerability

If the two prime factors \(p\) and \(q\) of \(n\) are close to each other (i.e., \(|p - q|\) is small), then \(n\) can be factored efficiently using Fermat’s method (1643).

The idea exploits the identity:

\[ n = pq = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2 = a^2 - b^2\]

We search for \(a \ge \lceil\sqrt{n}\rceil\) such that \(a^2 - n\) is a perfect square \(b^2\). Then \(p = a + b\) and \(q = a - b\).

If \(|p - q|\) is \(O(n^{1/4})\), the method finds the factors in \(O(1)\) iterations.

import numpy as np
import math
import random

def fermat_factor(n, max_iterations=1000000):
    """Fermat's factorization method.
    
    Finds factors of n = p*q when p and q are close together.
    
    Parameters
    ----------
    n : integer to factor
    max_iterations : maximum search iterations
    
    Returns
    -------
    (p, q) : factors, or None if not found within limit
    """
    a = math.isqrt(n)
    if a * a < n:
        a += 1  # a = ceil(sqrt(n))
    
    for i in range(max_iterations):
        b_squared = a * a - n
        b = math.isqrt(b_squared)
        if b * b == b_squared:
            p = a + b
            q = a - b
            if q > 1 and p * q == n:
                return (max(p, q), min(p, q)), i + 1
        a += 1
    return None, max_iterations

# --- Demonstration: close primes vs. distant primes ---
random.seed(99)

# Case 1: p and q are close (vulnerable)
p_close = gen_prime(64)
# Generate q near p by searching from p+2
q_close = p_close + 2
while not is_probable_prime(q_close):
    q_close += 2
n_close = p_close * q_close

print("=== Case 1: Close primes ===")
print(f"|p - q| = {abs(p_close - q_close)}")
(p_found, q_found), iters = fermat_factor(n_close)
print(f"Factored in {iters} iteration(s)")
print(f"Correct: {set([p_found, q_found]) == set([p_close, q_close])}")
print()

# Case 2: p and q are distant (Fermat is slow)
p_far = gen_prime(64)
q_far = gen_prime(64)  # much smaller
n_far = p_far * q_far

print("=== Case 2: Distant primes ===")
print(f"p has {p_far.bit_length()} bits, q has {q_far.bit_length()} bits")
result, iters = fermat_factor(n_far, max_iterations=10000)
if result is None:
    print(f"Failed after {iters} iterations (as expected -- primes are far apart)")
else:
    print(f"Factored in {iters} iterations")

=== Case 1: Close primes ===
|p - q| = 46
Factored in 1 iteration(s)
Correct: True

=== Case 2: Distant primes ===
p has 64 bits, q has 64 bits
Failed after 10000 iterations (as expected -- primes are far apart)

26.7.1 Fermat Factorization: Performance vs. Prime Gap

We measure how the number of Fermat iterations scales with \(|p - q|\).

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import math
import random

random.seed(2026)

gaps = []
iterations = []

# Generate experiments: start with a 128-bit prime, produce q at various distances
for trial in range(30):
    p0 = gen_prime(64)
    # Random offset: from very small to moderate
    offset = random.randint(2, 2**20)
    if offset % 2 != 0:
        offset += 1  # keep same parity as p0 +/- something
    q0 = p0 + offset
    # Find next prime >= q0
    if q0 % 2 == 0:
        q0 += 1
    while not is_probable_prime(q0):
        q0 += 2
    if p0 == q0:
        continue
    n0 = p0 * q0
    gap = abs(p0 - q0)
    result, iters = fermat_factor(n0, max_iterations=100000)
    if result is not None:
        gaps.append(gap)
        iterations.append(iters)

gaps = np.array(gaps, dtype=float)
iterations = np.array(iterations, dtype=float)

fig, ax = plt.subplots(figsize=(10, 5))
ax.scatter(np.log2(gaps), iterations, alpha=0.6, s=40, edgecolors='navy', facecolors='royalblue')
ax.set_xlabel(r'$\log_2 |p - q|$', fontsize=12)
ax.set_ylabel('Fermat iterations to factor', fontsize=12)
ax.set_title('Fermat Factorization: Iterations vs. Prime Gap', fontsize=13)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('fermat_iterations_vs_gap.png', dpi=150, bbox_inches='tight')
plt.show()

print(f"Minimum gap tested: {int(min(gaps))} ({int(np.log2(min(gaps)))} bits)")
print(f"Maximum gap tested: {int(max(gaps))} ({int(np.log2(max(gaps)))} bits)")

Minimum gap tested: 77968 (16 bits)
Maximum gap tested: 1029570 (19 bits)

Practical implications

NIST recommends that \(|p - q| > 2^{(\text{nlen}/2 - 100)}\) where nlen is the bit length of \(n\) (FIPS 186-5, Section B.3.3). For a 2048-bit modulus, this means \(|p - q| > 2^{924}\), making Fermat factorization infeasible.

26.8 Comparison of Attack

Requirements

The following table summarizes the conditions under which each attack applies and its computational cost.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt

attacks = [
    'Small $e$\n(cube root)',
    'Common\nmodulus',
    'Wiener',
    'Hastad\nbroadcast',
    'Fermat\nfactorization'
]

# Qualitative difficulty on log scale (1=trivial, 5=hardest among these)
difficulty = np.array([1, 2, 3, 2, 4])
# What the attacker needs (encoded as number of items)
info_needed = np.array([1, 2, 1, 3, 1])  # 1=single ciphertext, 2=two, 3=three

x = np.arange(len(attacks))
width = 0.35

fig, ax = plt.subplots(figsize=(10, 5))
bars1 = ax.bar(x - width/2, difficulty, width, label='Relative complexity',
               color='steelblue', edgecolor='navy', alpha=0.85)
bars2 = ax.bar(x + width/2, info_needed, width, label='Ciphertexts needed',
               color='coral', edgecolor='darkred', alpha=0.85)

ax.set_xticks(x)
ax.set_xticklabels(attacks, fontsize=10)
ax.set_ylabel('Scale', fontsize=12)
ax.set_title('Comparison of RSA Attacks', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, axis='y', alpha=0.3)
ax.set_ylim(0, 6)

# Add value labels on bars
for bar in bars1:
    height = bar.get_height()
    ax.annotate(f'{int(height)}', xy=(bar.get_x() + bar.get_width() / 2, height),
                xytext=(0, 3), textcoords='offset points', ha='center', fontsize=10)
for bar in bars2:
    height = bar.get_height()
    ax.annotate(f'{int(height)}', xy=(bar.get_x() + bar.get_width() / 2, height),
                xytext=(0, 3), textcoords='offset points', ha='center', fontsize=10)

plt.tight_layout()
plt.savefig('attack_comparison.png', dpi=150, bbox_inches='tight')
plt.show()

26.9 End-to-End Attack

Scenario

We demonstrate a complete attack pipeline: generate a vulnerable key, encrypt a meaningful message, and recover it using Wiener’s attack.

import numpy as np
import math
import random

random.seed(314)

# Step 1: Generate Wiener-vulnerable key
print("[Step 1] Generating Wiener-vulnerable RSA key...")
n_demo, e_demo, d_real, p_demo, q_demo = generate_wiener_vulnerable_key(bits=256)
print(f"  n has {n_demo.bit_length()} bits")
print(f"  e has {e_demo.bit_length()} bits")
print(f"  d has {d_real.bit_length()} bits  (vulnerable: d < n^(1/4)/3)")
print()

# Step 2: Encrypt a message
message_text = "ATTACK AT DAWN"
m_int = int.from_bytes(message_text.encode('utf-8'), 'big')
c_demo = pow(m_int, e_demo, n_demo)
print(f"[Step 2] Plaintext:  '{message_text}'")
print(f"  As integer: {m_int}")
print(f"  Ciphertext: {c_demo}")
print()

# Step 3: Wiener's attack recovers d
print("[Step 3] Running Wiener's attack...")
d_found = wiener_attack(n_demo, e_demo)
print(f"  Recovered d = {d_found}")
print(f"  Correct:      {d_found == d_real}")
print()

# Step 4: Decrypt
m_decrypted = pow(c_demo, d_found, n_demo)
recovered_text = m_decrypted.to_bytes((m_decrypted.bit_length() + 7) // 8, 'big').decode('utf-8')
print(f"[Step 4] Decrypted integer: {m_decrypted}")
print(f"  Recovered text: '{recovered_text}'")
print(f"  Match: {recovered_text == message_text}")

[Step 1] Generating Wiener-vulnerable RSA key...
  n has 256 bits
  e has 255 bits
  d has 63 bits  (vulnerable: d < n^(1/4)/3)

[Step 2] Plaintext:  'ATTACK AT DAWN'
  As integer: 1325037865527344434240272969324366
  Ciphertext: 35782168863156559881724692187156157701011158121900250251815972321051736313885

[Step 3] Running Wiener's attack...
  Recovered d = 4650131262055349767
  Correct:      True

[Step 4] Decrypted integer: 1325037865527344434240272969324366
  Recovered text: 'ATTACK AT DAWN'
  Match: True

26.10 Timing the Attacks

We measure execution time for each attack type to give a sense of practical feasibility.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import time

def time_attack(func, *args, repeats=3):
    times = []
    for _ in range(repeats):
        t0 = time.perf_counter()
        result = func(*args)
        t1 = time.perf_counter()
        times.append((t1 - t0) * 1000)
    return np.median(times), result

c1_se = pow(42, 3, 55 * 391)
n2_t = 5 * 11  # = 55
c2a_t = pow(13, 7, n2_t)
c2b_t = pow(13, 11, n2_t)
moduli4_t = [55, 391, 1189]
ctexts4_t = [pow(42, 3, ni) for ni in moduli4_t]
n5_t = 104729 * 104743

labels = ["Small e\n(cube root)", "Common\nmodulus", "Wiener",
          "Hastad\nbroadcast", "Fermat\nfactor"]
timings = []
t, _ = time_attack(small_exponent_attack, c1_se, 3)
timings.append(t)
t, _ = time_attack(common_modulus_attack, n2_t, 7, c2a_t, 11, c2b_t)
timings.append(t)
t, _ = time_attack(wiener_attack, n, e)
timings.append(t)
t, _ = time_attack(hastad_broadcast, ctexts4_t, moduli4_t, 3)
timings.append(t)
t, _ = time_attack(fermat_factor, n5_t)
timings.append(t)
timings = np.array(timings)

fig, ax = plt.subplots(figsize=(10, 5))
colors = ["#2ecc71", "#3498db", "#9b59b6", "#e67e22", "#e74c3c"]
bars = ax.bar(labels, timings, color=colors, edgecolor="black", alpha=0.85)
for bar, t_val in zip(bars, timings):
    ax.annotate(f"{float(t_val):.2f} ms",
                xy=(bar.get_x() + bar.get_width() / 2, bar.get_height()),
                xytext=(0, 5), textcoords="offset points",
                ha="center", fontsize=10, fontweight="bold")
ax.set_ylabel("Time (ms)", fontsize=12)
ax.set_title("Execution Time of RSA Attacks", fontsize=13)
ax.grid(True, axis="y", alpha=0.3)
plt.tight_layout()
plt.savefig("attack_timings.png", dpi=150, bbox_inches="tight")
plt.show()

26.11 Exercises

---

Exercise 1: Generalized Hastad attack

Implement Hastad’s broadcast attack for \(e = 5\). Generate 5 RSA moduli (each 512 bits), encrypt the same message with \(e = 5\), and recover it.

Hint

The hastad_broadcast function already works for any e. You need to generate 5 moduli where gcd(5, phi(n_i)) = 1 for each. Use crt with 5 remainders and compute the integer 5th root.

---

Exercise 2: Wiener’s bound verification

Experimentally verify Wiener’s bound \(d < n^{1/4}/3\). For key sizes 256, 512, and 1024 bits, generate keys with \(d\) just below and just above the bound. Show that the attack succeeds below and fails above.

Hint

Generate p, q, compute phi_n, then choose d explicitly. For “just above” the bound, choose d about 3x larger than n^{1/4}/3. Compute e = mod_inverse(d, phi_n) and run wiener_attack(n, e). Collect results in a table.

---

Exercise 3: Factoring \(n\) from \((n, e, d)\)

Given the public key \((n, e)\) and the private key \(d\) (but not \(p\) or \(q\)), implement an algorithm that factors \(n\). Use the fact that \(ed - 1\) is a multiple of \(\phi(n)\) and apply a randomized algorithm (similar to Miller-Rabin).

Hint

Write \(ed - 1 = 2^s \cdot t\) with \(t\) odd. Pick random \(a\) and compute \(x = a^t \bmod n\). Repeatedly square \(x\); if at some point \(x^2 \equiv 1\) but \(x \not\equiv \pm 1 \pmod{n}\), then \(\gcd(x - 1, n)\) is a non-trivial factor. This is the approach shown in the original RSA_security notebook.

---

Exercise 4: Common modulus with non-coprime exponents

What happens if \(\gcd(e_1, e_2) = g > 1\) in the common modulus attack? Show that you can still recover \(m^g \bmod n\), and discuss under what conditions \(m\) itself can be recovered.

Hint

Apply the extended GCD to get \(x e_1 + y e_2 = g\). Then \(c_1^x \cdot c_2^y \equiv m^g \pmod{n}\). If \(g\) is small and \(m^g < n\), take the integer \(g\)-th root. Otherwise, you need additional information or a lattice-based approach.

---

Exercise 5: Fermat factorization with timing

Write a function that generates RSA moduli \(n = pq\) where \(p\) and \(q\) are both 256-bit primes and \(|p - q|\) is exactly a specified number of bits (e.g., 10, 20, 30, …, 100 bits). Plot the Fermat factorization time as a function of the gap size in bits. At what gap size does Fermat factorization become impractical (>10 seconds)?

Hint

To control \(|p - q|\), generate \(p\), then set q = p + random.getrandbits(gap_bits) and find the next prime after that. Use time.perf_counter() to measure wall-clock time. You may need to set a timeout and report “failed” for large gaps.

26.12 Summary

In this chapter we implemented and demonstrated five classical attacks on RSA:

1. Small public exponent attack: When \(e\) is small and the message \(m\) satisfies \(m^e < n\), the ciphertext carries no modular information and \(m\) is recovered by integer root extraction.

2. Common modulus attack: Reusing the same \(n\) with two coprime exponents allows an attacker to combine two ciphertexts of the same message using the extended Euclidean algorithm.

3. Wiener’s continued fraction attack: A small private exponent \(d < n^{1/4}/3\) is revealed by the convergents of the continued fraction expansion of \(e/n\).

4. Hastad’s broadcast attack: Sending the same unpadded message to \(e\) recipients with the same small exponent enables recovery via the Chinese Remainder Theorem.

5. Fermat factorization: When \(p \approx q\), the modulus \(n\) is factored in time proportional to \((p - q)^2 / (4\sqrt{n})\).

The common thread is that RSA is only as secure as its parameter choices. Proper implementation requires:

• Large, well-separated primes (\(|p - q|\) large)

• Sufficiently large private exponent \(d\)

• Unique moduli per user

• Randomized padding (OAEP) to prevent small-message attacks

26.13 References

1. Wiener, M.J. (1990). “Cryptanalysis of Short RSA Secret Exponents.” IEEE Transactions on Information Theory, 36(3), 553–558. doi:10.1109/18.54902

2. Coppersmith, D. (1997). “Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities.” Journal of Cryptology, 10(4), 233–260. doi:10.1007/s001459900030

3. Boneh, D. (1999). “Twenty Years of Attacks on the RSA Cryptosystem.” Notices of the AMS, 46(2), 203–213. PDF

4. Hastad, J. (1985). “On Using RSA with Low Exponent in a Public Key Network.” Advances in Cryptology – CRYPTO ‘85, LNCS 218, pp. 403–408.

5. Boneh, D. and Durfee, G. (2000). “Cryptanalysis of RSA with Private Key \(d\) Less Than \(N^{0.292}\).” IEEE Transactions on Information Theory, 46(4), 1339–1349.

6. Rivest, R., Shamir, A., and Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM, 21(2), 120–126. doi:10.1145/359340.359342

7. NIST FIPS 186-5 (2023). “Digital Signature Standard (DSS).” Section B.3.3: Generation of Random Primes that are Probably Prime.