Step 230. RSA Attacks 2: Fermat Factorization, Wiener’s Attack — When Key Generation Is Botched, the Math Collapses

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★★☆ | Estimated time: 4 hours

Prerequisites: Step 229 (RSA Attacks 1) — last chapter was mistakes in "how you use it"; today is mistakes in "how you make it."

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.

• What you need: Python 3 (measured: 3.12.14), the prime-generation code from Step 228, the iroot instincts from Step 229.
• Caution: factordb.com lookups are a "concept introduction" only today — this chapter’s runtime environment uses no external network.

RSA’s security hangs on "factoring n is hard." But that hardness holds only when key generation is sound. If p and q are too close, factoring finishes just by sweeping near the square root of n (Fermat); if the private exponent d is too small, d can be computed mathematically from the public values (n, e) alone (Wiener). Today you implement both attacks yourself, craft vulnerable keys, and break them yourself. The two classics of "something’s off about this n" in CTF.

1. Learning Objectives

By the end of this chapter, you will be able to:

• Implement Fermat factorization and explain the relationship between the p–q distance and the iteration count
• Factor an n made from close primes, compute d, and decrypt a ciphertext
• Implement continued-fraction expansion yourself and recover a small d with Wiener’s attack
• Build the diagnostic habit of "Fermat → suspect small d → factordb" when facing an unfamiliar RSA public key

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

2-1. Fermat Factorization — A Difference of Squares

Every odd composite n can be written as a difference of squares: n = a² - b² = (a-b)(a+b). Then p = a-b, q = a+b. The method is simple — start from a = isqrt(n) + 1, test whether a² - n is a perfect square, and if not, bump a by 1 and repeat.

The iteration count is proportional to a - √n ≈ (p-q)² / (8√n). In other words, the closer p and q, the overwhelmingly faster it is. With proper key generation (independent random primes), the difference is on the scale of √n so it runs effectively forever, but with botched generation like "previous prime + small offset," it ends in a single iteration — you’ll confirm this in today’s measurements.

2-2. Wiener’s Attack — A Small d Has Nowhere to Hide

In RSA, e·d ≡ 1 (mod φ(n)), so there’s an integer k with e·d = k·φ(n) + 1. Rearranging gives e/n ≈ k/d — k/d appears as an approximation of e/n. If d is small enough (d < n^0.25 / 3 is the classic condition), k/d is guaranteed to appear in the list of continued-fraction convergents of e/n.

A continued fraction expands a fraction into the form a0 + 1/(a1 + 1/(a2 + ...)), and its truncated prefixes — the convergents — yield, in order, the best approximations with small denominators. Take each convergent’s denominator as a d candidate, compute φ(n) = (e·d - 1)/k, and check whether the discriminant of the quadratic x² - (n-φ(n)+1)x + n = 0 built from that φ(n) is a perfect square — if so, p and q are confirmed, and d is found. It’s all fast integer arithmetic, so even a 1024-bit key falls in milliseconds.

2-3. The Diagnostic Habit — What to Check When Handed an n

When a CTF hands you a public key (n, e): ① look up n on factordb.com (plenty of numbers have already been factored by someone — an external service, so today it’s concept only), ② run Fermat briefly (close primes break instantly), ③ if e is abnormally large — close to n in size — that’s a strong hint of a small d, so run Wiener. Today you build ② and ③ yourself.

3. Follow Along

All output in this chapter was measured 2026-09-09 on Python 3.12.14.

3-1. Implementing Fermat Factorization

from math import isqrt

def fermat_factor(n, limit=10_000_000):
    a = isqrt(n)
    if a * a < n:
        a += 1
    for i in range(limit):
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:          # if a² - n is a perfect square, n = (a-b)(a+b)
            return a - b, a + b, i + 1
        a += 1
    return None, None, limit

isqrt gives the exact integer square root — float ** 0.5 carries the same precision trap as Step 229 Wall 1, so it’s forbidden.

3-2. Breaking a Key Made from Close Primes

Reproduce the botched generation "the next prime after adding a small offset to the previous prime" on purpose.

def next_prime(n):
    n |= 1
    while not is_probable_prime(n):
        n += 2
    return n

p = gen_prime(512)
q = next_prime(p + secrets.randbelow(2000) * 2)   # a very close prime
n = p * q
print("p-q difference (bits):", (q - p).bit_length(), "bits")

fp, fq, iters = fermat_factor(n)
print("factoring success:", fp * fq == n, "| iterations:", iters)

phi = (fp - 1) * (fq - 1)
d = pow(65537, -1, phi)
m = int.from_bytes(b"weak key!", "big")
c = pow(m, 65537, n)
rec = pow(c, d, n)
print("decrypted:", rec.to_bytes((rec.bit_length()+7)//8, "big"))

p-q difference (bits): 9 bits
factoring success: True | iterations: 1
decrypted: b'weak key!'

How to read the output: a 1024-bit RSA modulus was factored in 1 iteration. The difference was only 9 bits (a few hundred), so a = isqrt(n) + 1 was already the answer. Factoring → φ(n) → d → decryption — the entire private key recomputed from one public key.

3-3. Distance vs Iterations — How Far Does It Break?

The same experiment with growing differences (measured):

p,q difference ~2^200: 1 iteration, success=True, 0.00s
p,q difference ~2^264: 1908 iterations, success=True, 0.00s

Even a 2^200 difference breaks instantly — for a 512-bit prime, 2^200 is "the same neighborhood." By contrast, two properly independent primes (256 bits each):

proper key (two 256-bit primes): success after 200k iterations? False | 0.11s

How to read it: iterations are proportional to (p-q)² / (8√n), so they grow steeply as the difference widens even a little. The decision criterion is "do the iterations start exploding" — if it doesn’t finish within tens of thousands, this key is not a Fermat target. Fermat is a "quick diagnostic," not a universal factoring machine.

3-4. Wiener’s Attack — Computing d via Continued Fractions

Build the convergent generator and the attack function.

def convergents(num, den):
    # yield continued-fraction convergents (numerator, denominator) of num/den in order
    h_prev, h_cur = 0, 1
    k_prev, k_cur = 1, 0
    a, b = num, den
    while b:
        q_, r_ = divmod(a, b)
        yield q_ * h_cur + h_prev, q_ * k_cur + k_prev
        h_prev, h_cur = h_cur, q_ * h_cur + h_prev
        k_prev, k_cur = k_cur, q_ * k_cur + k_prev
        a, b = b, r_

def wiener(e, n):
    for k, d_cand in convergents(e, n):
        if k == 0 or (e * d_cand - 1) % k != 0:
            continue
        phi_cand = (e * d_cand - 1) // k
        s = n - phi_cand + 1              # s = p + q
        disc = s * s - 4 * n              # discriminant
        if disc < 0:
            continue
        t = isqrt(disc)
        if t * t == disc and (s + t) % 2 == 0:
            return d_cand                 # p, q confirmed → this d is real
    return None

Build a vulnerable key — draw d small first, then compute e backward (the same structure as real-world incident cases):

p3, q3 = gen_prime(512), gen_prime(512)
n3 = p3 * q3
phi3 = (p3 - 1) * (q3 - 1)
while True:
    d_small = secrets.randbits(240) | 1       # below n^(1/4) ≈ 256 bits
    if math.gcd(d_small, phi3) == 1:
        break
e_big = pow(d_small, -1, phi3)
print("weak key: d bits =", d_small.bit_length(), ", e bits =", e_big.bit_length())

d_found = wiener(e_big, n3)
print("d recovered by Wiener == original d:", d_found == d_small)
print("recovered d bits:", d_found.bit_length() if d_found else None)

weak key: d bits = 238 , e bits = 1021 (n is 1024 bits)
d recovered by Wiener == original d: True
recovered d bits: 238

How to read the output: a 238-bit private key d was computed in 0.002 seconds from the public values (n, e) alone. And the diagnostic hint is right there in the output — e is abnormally large at 1021 bits, nearly the size of n. When d is small, e is forced to grow to the scale of φ(n), so a giant e is circumstantial evidence of a small d.

3-5. Diagnostic-Order Practice

Drill the order for diagnosing an unfamiliar (n, e) with today’s tools: ① run fermat_factor(n, limit=100_000) briefly → if it fails, ② if e.bit_length() is close to n’s, run wiener(e, n) → if both fail, ③ a factordb lookup (external, concept only) → if that fails too, this problem belongs to a different attack. Each stage takes no more than a few seconds, so there’s no reason not to run them.

4. Missions & Exercises

Mission — The Weak-Key Triage Tool rsa_triage.py

1. Write a function triage(n, e) — run ① 100k iterations of Fermat, then ② if e is large, Wiener, in that order, and return the result together with one of "fermat", "wiener", "unknown"
2. Generate two vulnerable keypairs (close primes, small d) and one proper keypair, and demonstrate the triage tool classifying all three correctly
3. For each broken key, continue on to computing d and decrypting a "flag{weak_key}" ciphertext — a diagnosis is complete only when it ends in recovery
4. (Optional) On the proper key, print how many seconds each attack takes before giving up

Exercises

Exercise 1. Explain why Fermat factorization’s iteration count is proportional to (p-q)² / (8√n), via the relationship between a = (p+q)/2 and √n.

Exercise 2. Why must key-generation libraries draw p and q "completely independently"? Answer with evidence from which measurement broke the q = next_prime(p + K) style of generation today.

Exercise 3. In Wiener’s attack, how was each convergent k/d verified? Explain the flow: get p+q from a φ(n) candidate and confirm via a quadratic equation.

Exercise 4. You saw a public key whose e is as large as n. Starting from e·d ≡ 1 (mod φ(n)), explain why this hints at a small d.

def triage(n, e):
    fp, fq, iters = fermat_factor(n, limit=100_000)
    if fp:
        d = pow(e, -1, (fp - 1) * (fq - 1))
        return "fermat", d
    if e.bit_length() > n.bit_length() * 3 // 4:   # e large on n's scale → suspect small d
        d = wiener(e, n)
        if d:
            return "wiener", d
    return "unknown", None

6. Common Pitfalls & Fixes

Wall 1. ValueError: isqrt() argument must be nonnegative

Symptom: ValueError: isqrt() argument must be nonnegative (measured 2026-09-09).
Cause: it arrives via two paths — you forgot to handle n being a perfect square in fermat_factor, or you skipped the disc < 0 check in wiener.
Fix: check the if disc < 0: continue in wiener. Most candidate convergents have negative discriminants, so this branch is normal operation.

Wall 2. Fermat never finishes

Symptom: it keeps iterating for minutes.
Cause: that key is a proper key that Fermat can’t break — in 3-3, the proper key failed even at 200k iterations (measured). Iterations scale with the square of the difference, so there’s no "just a bit longer."
Fix: set a limit and give up past it. With Fermat, the answer comes within 100k iterations or it never comes — one or the other.

Wall 3. Wiener returns None

Symptom: you clearly made a small d, yet wiener returns None.
Cause: d is outside the condition — d < n^0.25 / 3 is the classic ceiling, so for a 1024-bit n, a d past roughly 250 bits can fail. Or the convergent update order in convergents may be flipped.
Fix: draw d at 240 bits or below as in 3-4, confirm success inside the condition first, then experiment with the boundary.

Wall 4. Letting through candidates whose phi_cand doesn’t divide evenly

Symptom: a wrong d gets "found," or nothing is found even after a full pass.
Cause: the (e * d_cand - 1) % k != 0 filter was skipped — if it doesn’t divide evenly, φ(n) wouldn’t be an integer, so that candidate is physically impossible.
Fix: all three checks from 3-4 must be present — the two filters (k == 0, the remainder check) and the discriminant perfect-square test. Continued fractions without verification are just guessing.

Wall 5. Testing perfect squares with a float square root

Symptom: the check int((a*a - n) <strong> 0.5) </strong> 2 == a*a - n is occasionally wrong.
Cause: the same float-precision issue as Step 229 Wall 1 — ** 0.5 isn’t exact on large numbers.
Fix: every square root is math.isqrt. Both of today’s attacks must complete using integer arithmetic alone.

7. Summary

Today’s Concepts

Today’s Commands & Code

An Instinct More Important Than Commands

Yesterday was mistakes in "how you use it" (small e, n reuse); today was mistakes in "how you make it" (close primes, small d). The common thread is one — verification beats guessing. Fermat’s perfect-square test and Wiener’s discriminant check were both devices that turn a "plausible-looking candidate" into a "confirmed answer." Your attacker toolbox has grown, and now, facing an unfamiliar n, your hand will reach for isqrt first.

Once every box is checked, Step 230 is complete.