# FactHacks

RSA factorization
in the real world

 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.