FactHacks

 RSA factorization
in the real world
Introduction
Sage
Basic subroutines:
Euclid
Product tree
Remainder tree
Weak primes:
Batch gcd
Fermat
Lattice
Small primes:
Batch trial division
rho
p-1
ECM
Small keys:
Smooth
QS
NFS

Fermat's factorization method

Fermat's factorization method factors N into p and q very quickly if p and q share half of their leading bits, i.e., if the gap between p and q is below the square root of p. It becomes much slower if p and q share significantly fewer bits.

One can save time in RSA decryption by choosing, e.g., p and q very close to 2^512. Fermat's factorization method shows that this is unsafe if "very close" means, e.g., between 2^512-2^256 and 2^512+2^256. Fermat's factorization method is also a first step towards understanding the quadratic sieve.

Lattice techniques show that it's always unsafe to choose p very close to 2^512, even if q is chosen randomly.

How it works

Sage code: 
     def fermatfactor(N):
       if N <= 0: return [N]
       if is_even(N): return [2,N/2]
       a = ceil(sqrt(N))
       while not is_square(a^2-N):
         a = a + 1
       b = sqrt(a^2-N)
       return [a - b,a + b]
Examples: 
     sage: print fermatfactor(91)
     [7, 13]
     sage: print fermatfactor(1009) # this one is prime
     [1, 1009]
     sage: print fermatfactor(6557)
     [79, 83]
     sage: N = 115792089237316195423570985008721211221144628262713908746538761285902758367353
     sage: print fermatfactor(N)
     [340282366920938463463374607431817146293, 340282366920938463463374607431817146421]
     sage: N = 115792089237316195448679392282006640413199890130332179010243714077028592474181
     sage: print fermatfactor(N)
     [340282366920938463463374607431817146293, 340282366920938463537161584701547790417]
In the last example, q was chosen as the next prime after p+2^66+974892437589, and both p and q were very close to 2^128. In the previous example, q was chosen as the next prime after p; this would happen if the RSA implementor generated both p and q from the same sequential search.

Speed degenerates rapidly when p and q share fewer than half their leading bits: 

     sage: p = next_prime(2^512 + randrange(2^264))
     sage: q = next_prime(p + 2^264 + randrange(2^262))
     sage: time f = fermatfactor(p * q)
     Time: CPU 0.18 s, Wall: 0.17 s
     sage: p = next_prime(2^512 + randrange(2^265))
     sage: q = next_prime(p + 2^265 + randrange(2^263))
     sage: time f = fermatfactor(p * q)
     Time: CPU 0.37 s, Wall: 0.37 s
     sage: p = next_prime(2^512 + randrange(2^266))
     sage: q = next_prime(p + 2^266 + randrange(2^264))
     sage: time f = fermatfactor(p * q)
     Time: CPU 0.91 s, Wall: 0.91 s
     sage: p = next_prime(2^512 + randrange(2^267))
     sage: q = next_prime(p + 2^267 + randrange(2^265))
     sage: time f = fermatfactor(p * q)
     Time: CPU 4.64 s, Wall: 4.67 s
     sage: p = next_prime(2^512 + randrange(2^268))
     sage: q = next_prime(p + 2^268 + randrange(2^266))
     sage: time f = fermatfactor(p * q)
     Time: CPU 18.53 s, Wall: 18.57 s
     sage: p = next_prime(2^512 + randrange(2^269))
     sage: q = next_prime(p + 2^269 + randrange(2^267))
     sage: time f = fermatfactor(p * q)
     Time: CPU 50.85 s, Wall: 50.94 s
Version: This is version 2012.12.28 of the fermat.html web page.