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