Breaking RSA with Fermat Factorization

Breaking RSA with Fermat Factorization

Introduction

RSA’s entire security rests on one assumption. Factoring n back into p and q must be infeasible. That assumption holds beautifully when p and q are properly random. It collapses almost instantly if they’re close together. That’s a mistake real key generators have actually made. Pierre de Fermat described the method in 1643, three centuries before RSA existed. This post builds Fermat’s factorization attack. It shows exactly how close is too close, before a key generation bug becomes catastrophic.

Table of Contents

• Why Prime Distance Matters
• The Attack: Difference of Squares
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Fermat vs. General-Purpose Factoring
• Limitations of This Attack
• Mitigation: A Cheap Pre-Publication Check
• FAQ
• References

Why Prime Distance Matters

RSA key generation says almost nothing about prime distance. It only requires p and q to be distinct, large, and random. Nothing in the textbook algorithm rules out two primes sitting close together. A careless key generator can do exactly that. It starts from one random prime, then searches only a short distance for the second.

That single choice turns factoring from infeasible into trivial. Fermat’s method doesn’t try every possible factor. It only needs p and q to be close together. Specifically, their average, squared, must sit barely above n. Every RSA guide names factoring as the hard problem behind its security. Fermat’s method is a sharp reminder of something else. “Hard to factor” depends on how the primes were chosen. It’s not just about how big n is.

The Attack: Difference of Squares

Any odd n can be written as a difference of two squares: n = a² − b². That factors immediately: n = (a−b)(a+b). Finding any such a and b hands over p and q directly, as p = a−b and q = a+b. Every RSA modulus qualifies. n is a product of two odd primes, so it’s always odd. That makes a and b always come out as whole numbers.

Here’s the insight that makes this practical. If p and q are close together, a = (p+q)/2 is only slightly larger than √n. And b = (p−q)/2 is small. That turns the search into something short and bounded:

1. Start at a = ⌈√n⌉. That’s the smallest integer whose square could possibly reach n.
2. Compute b² = a² − n. Check whether it’s a perfect square.
3. If it is, p = a−b and q = a+b are the factors. Done.
4. If it isn’t, increment a by 1 and try again.

Each failed attempt costs one subtraction, one integer square root, and one comparison. The number of attempts needed is roughly proportional to ((q−p)/2)² / √n, or equivalently (q−p)² / (4√n). When p and q are close, that number is tiny. When they’re far apart, it approaches a brute-force search over half of n. That’s exactly as useless as it sounds. It’s exactly why this attack only matters for badly generated keys.

A Worked Example

Using the visualizer’s default modulus, n = 99457027:

1. Start at a₀ = ⌈√99457027⌉ = 9973. That’s the smallest integer whose square reaches n.
2. Testing a = 9973: a² − n = 99460729 − 99457027 = 3702. √3702 ≈ 60.8, not a whole number. No match.
3. The search increments a by 1 and repeats. Attempts 2 through 13 test a = 9974 through 9985. Each one fails the same way: a² − n comes out non-square.
4. Testing a = 9986 (attempt 14): a² − n = 99720196 − 99457027 = 263169. √263169 = 513 exactly. A perfect square.
5. Recover the factors: p = a − b = 9986 − 513 = 9473. q = a + b = 9986 + 513 = 10499. Both prime; 9473 × 10499 = 99457027 confirms it.
6. Rebuild the private key. With p and q known, φ(n) = 9472 × 10498 = 99437056. Given e = 65537, the private exponent falls out as d = e⁻¹ mod φ(n) = 31182849. That’s the exact same computation RSA’s own key generation runs. Here, an attacker performs it instead of the key’s owner.
7. Decrypt. A ciphertext of 96706862, captured off the wire, decrypts as C^d mod n = 424242, the original message. No private key was ever handed over.

Fourteen short attempts, no brute force, no guessing. The entire private key falls out. These two “large” primes happened to sit within a few hundred of each other.

Python Implementation

The interactive visualizer above runs this exact search in JavaScript. Same starting point, same perfect-square test, same private-key rebuild. Here’s the same attack in Python.

Key Features

• Uses math.isqrt, Python’s exact integer square root. No floating-point rounding risk, for either the search or the perfect-square check.
• Bounded search: a hard iteration cap stops the function from running forever. That matters when p and q aren’t close. It matches the practical limit the visualizer enforces. fermat_factor returns None on failure, never a partial or garbage result.
• Reuses ordinary RSA math for the private-key rebuild. Once p and q are known, deriving d matches generate_keypair in the base RSA guide. It’s just run by the attacker instead.
• p always comes out smaller than q, for free. b is always positive, so a − b is always less than a + b. The two factors arrive pre-sorted, with no extra work needed.

Code

# fermat_breaker.py
#
# Breaks RSA when p and q were generated too close together. Any odd n
# can be written as a difference of two squares, n = a^2 - b^2, which
# factors immediately via n = (a-b)(a+b). If p and q are close, a search
# starting from ceil(sqrt(n)) finds that a, b pair almost immediately.

import math


def fermat_factor(n, max_iter=300000):
    """Returns {'p', 'q', 'iterations'} with p <= q, or None if no match is found within max_iter."""
    a = math.isqrt(n)
    if a * a < n:
        a += 1
    for i in range(max_iter):
        b2 = a * a - n
        b = math.isqrt(b2)
        if b * b == b2:
            return {'p': a - b, 'q': a + b, 'iterations': i + 1}
        a += 1
    return None


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a, m):
    g, x, _ = egcd(a % m, m)
    if g != 1:
        return None
    return x % m


if __name__ == '__main__':
    n = 99457027
    e = 65537
    ciphertext = 96706862

    result = fermat_factor(n)
    p, q = result['p'], result['q']
    print(f"Recovered factors: p={p}, q={q}, after {result['iterations']} attempts")
    assert p * q == n

    phi = (p - 1) * (q - 1)
    d = mod_inverse(e, phi)
    print(f"phi(n) = {phi}")
    print(f"Recovered private exponent d = {d}")

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

Running this against the same modulus as the visualizer produces:

Recovered factors: p=9473, q=10499, after 14 attempts
phi(n) = 99437056
Recovered private exponent d = 31182849
Decrypted message: 424242

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, the readable version above is the one for that. This version just runs the entire attack, decryption included, with no function definitions at all.

import math
n=99457027; e=65537; c=96706862; a=math.isqrt(n) + (math.isqrt(n)**2 < n)
while math.isqrt(a*a - n)**2 != a*a - n: a += 1
b=math.isqrt(a*a - n); p=a-b; q=a+b; phi=(p-1)*(q-1); d=pow(e,-1,phi); m=pow(c,d,n)
print(f"Recovered factors: p={p}, q={q}"); print(f"phi(n) = {phi}"); print(f"Recovered private exponent d = {d}"); print(f"Decrypted message: {m}"); assert p*q==n

Verified against the readable version’s output: p=9473, q=10499, phi(n) = 99437056, d = 31182849, message 424242. The while loop’s condition folds the perfect-square check directly into the loop test. pow(e, -1, phi) replaces the separate mod_inverse function with Python 3.8+’s built-in modular inverse.

Interactive Visualizer

Try it above. Enter any modulus and watch the search for a perfect square, row by row. Add a public exponent and a captured ciphertext. Watch the recovered factors turn into a full private key. That key then decrypts a message, with nothing else given away.

Fermat vs. General-Purpose Factoring

Fermat’s method isn’t a faster way to factor arbitrary RSA moduli. It’s a demonstration that RSA’s security proof has a hidden precondition. P and q must be far apart. The textbook algorithm never states that as a requirement. A well-implemented key generator satisfies it automatically. Two independently random large primes are astronomically unlikely to land close together by chance. A buggy one doesn’t.

Fermat’s method also isn’t a historical dead end. Its core idea is expressing a target as a difference of squares. That’s the direct conceptual ancestor of the quadratic sieve. The sieve is one of the fastest known factoring algorithms. It just finds that difference far more cleverly than a plain one-step-at-a-time search.

Limitations of This Attack

This attack is only fast when p and q are genuinely close. The number of search iterations grows roughly with ((q−p)/2)² / √n. It degrades quickly as the gap widens. For two properly independent random primes at realistic RSA size, that gap is enormous. Fermat’s method would need more iterations than any computer could run. The universe would reach heat death first. It’s not a general factoring algorithm, and it was never meant to be one.

The search can’t know in advance whether p and q are close enough to try. In practice, an attacker would run this alongside other techniques. It works best as a cheap first check, not a full factoring strategy. Weaker conditions than “close together” can sometimes still be exploited. A known run of shared high-order bits between p and q is one example. Lattice-based Coppersmith techniques can exploit that. Those are a fundamentally different toolkit, well outside what pure Fermat factorization covers.

Finally, this implementation caps its search at a fixed limit, matching the visualizer’s own bound. That avoids running forever against a modulus this technique simply doesn’t fit. A “not found” result doesn’t prove n is safe. It only proves this one cheap attack didn’t succeed within that bound. A motivated attacker facing that result would simply move on. Pollard’s rho, the elliptic curve method (ECM), and full GNFS all remain options. None of them are covered here. Ruling out Fermat’s method rules out exactly one specific mistake, nothing more.

Mitigation: A Cheap Pre-Publication Check

The FAQ below already hints at the fix. Nothing stops a key generator from running this same bounded search against its own n. It costs almost nothing, and runs before that key is ever published:

def is_fermat_vulnerable(n, max_iter=1000):
    """True if a cheap, bounded Fermat search would factor n."""
    return fermat_factor(n, max_iter) is not None

A real n with properly independent primes will never trip this check. The search simply exhausts its iteration budget and returns None. If it ever does trip, something upstream picked p and q too close together. That key should never be issued. Beyond this check, standards and audited libraries generate p and q fully independently. Some go further and explicitly verify |p − q| is large, before accepting any candidate key pair.

FAQ

How close do p and q actually have to be for this to work?

Close enough that √n rounds to somewhere near their average. A common rule of thumb: this method succeeds quickly whenever |p − q| stays under roughly n^(1/4). For a real 2048-bit modulus, that still allows a gap of a few hundred bits. That’s well beyond what independent random generation would ever produce. Security researcher Hanno Böck has demonstrated recovering factors with gaps approaching 2⁵¹⁷. That took only a modest number of search rounds. The exact threshold always depends on how much computation an attacker spends.

Does this attack need the public exponent e?

No. Factoring n needs only n itself. e and a captured ciphertext are optional additions in the visualizer above. They show the full consequence. Once p and q are known, decrypting real traffic takes only ordinary RSA math.

Is this a realistic attack against modern RSA implementations?

Rarely, against a library that generates primes correctly. It’s realistic against custom or legacy key-generation code. Picture code that picks one prime, then searches nearby for the second. That’s not hypothetical. Hanno Böck’s 2022 research found exactly this flaw in real deployed firmware. It traced back to a Rambus SafeZone module (CVE-2022-26320). Standards and audited libraries generate p and q fully independently for exactly this reason.

How is this different from finding p and q are literally equal?

A shared-prime bug is a related but distinct mistake. Two different keys accidentally share one factor. That’s caught by computing gcd across many public keys, not by factoring any single one. Fermat’s method targets one key’s own p and q being close together. It has nothing to do with two different keys sharing a factor.

Could a defender detect this before publishing a key?

Yes, trivially. Run Fermat’s own search, bounded to a few iterations, against a freshly generated n. A success within that bound means the key generator has a bug. That’s true no matter what caused it.

References

1. Fermat, P. de. Described in correspondence, 1643; see the general method’s treatment in Crandall, R. and Pomerance, C. “Prime Numbers: A Computational Perspective.” Springer, 2005.

2. Wikipedia. “Fermat’s factorization method.” Available at: https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

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. Böck, H. “Fermat Factorization in the Wild.” IACR ePrint 2023/026. Available at: https://eprint.iacr.org/2023/026