# 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

## Euclid's algorithm

Given two integers x and y, Euclid's algorithm computes the greatest common divisor of x and y, written gcd{x,y}. This is the largest integer that divides both x and y, or 0 if x and y are both 0.

For example, 20 divides both 120 and 220 (i.e., 120/20 and 220/20 are integers), and no larger integer divides both 120 and 220, so 20 = gcd{120,220}.

If two RSA public keys share a prime factor (but not both prime factors) then feeding the keys to Euclid's algorithm will produce exactly that prime factor: gcd{pq,pq'} = p if q and q' are different primes. Two research teams announced in 2012 that tens of thousands of RSA public keys on the Internet were factorable in this way (and even more efficiently factorable by batch gcd). Properly generated keys have negligible chance of sharing a prime factor, but these keys had been generated by bad random-number generators.

Euclid's algorithm is also the last step in many other factorization algorithms.

## How it works

Euclid's algorithm replaces y by the remainder y mod x, then swaps x and y, then repeats. Eventually x reaches 0, and then the greatest common divisor is exactly y (or -y if y is negative):
```     def greatestcommondivisor(x,y):
while x != 0: x,y = y%x,x
return abs(y)

# example:
print greatestcommondivisor(4187,5989)
# output: 53
# double check:
print gcd(4187,5989)
# output: 53
```
An optimized version of this algorithm is built into Sage as gcd(x,y).

Example done by hand:

```     sage: x,y = 120,220
sage: x,y = y%x,x; print x
100
sage: x,y = y%x,x; print x
20
sage: x,y = y%x,x; print x
0
```
This computation finds gcd{120,220} = 20.

Larger example done by hand:

```     sage: x,y = 26167,37627
sage: x,y = y%x,x; print x
11460
sage: x,y = y%x,x; print x
3247
sage: x,y = y%x,x; print x
1719
sage: x,y = y%x,x; print x
1528
sage: x,y = y%x,x; print x
191
sage: x,y = y%x,x; print x
0
```
This computation finds gcd{26167,37627} = 191.
Version: This is version 2012.12.27 of the euclid.html web page.