FactHacks 
RSA factorization in the real world 

Euclid's algorithmGiven 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 randomnumber generators. Euclid's algorithm is also the last step in many other factorization algorithms. How it worksEuclid'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: 53An 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 0This 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 0This computation finds gcd{26167,37627} = 191. Version: This is version 2012.12.27 of the euclid.html web page. 