Skip to content
ctfpal
All tools
Modern cryptoRuns locallyNo account

Fermat factorization for close RSA primes

Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.

Open in ctfpal

Fermat’s method rests on writing n = a^2 - b^2 = (a+b)(a-b). Start at a = ceil(sqrt(n)) and step upward, checking each time whether a^2 - n is a perfect square. When it is, b falls out and the factors are a+b and a-b.

Why closeness is fatal

The number of steps required is proportional to how far apart p and q are. If they were generated by picking one prime and then searching for the next prime after it - a shortcut that appears in bad key generators and in most CTF challenges that use this attack - the gap is tiny and the search terminates in single-digit iterations, on a 2048-bit modulus, instantly.

from math import isqrt

def fermat(n):
    a = isqrt(n)
    if a * a < n:
        a += 1
    while True:
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1

Part of a module

5. RSA and the parameters that break it

Work the RSA decision tree - small modulus, close primes, tiny exponent, shared modulus - and learn to read a key for its weakness.

Practise on real challenges

Go deeper

  • The RSA attack decision treeRSA challenges are not solved by knowing every attack - they are solved by reading the parameters and picking the one attack that matches. A decision tree from e and n to Fermat, Wiener, Hastad, common modulus, and the oracle attacks.

Related tools