Friday, February 17, 2012

We are the 99.8%: Premature report of RSA demise

If you haven’t read the paper itself [PDF], you've probably seen the NY Times article. A group of researchers led by Arjen Lenstra analyzed a few million RSA public keys and found that some 0.2% of these keys share at least one prime factor with another public key and can thus be factorized. This is due to a random number generation flaw in the process used to choose primes during the generation of these public keys.

I don’t know if their analysis technique is novel, but it’s definitely interesting. Instead of identifying some weakness in a specific key generation library, or analyzing each key separately, the team analyzed pairs of keys to see if they share a common factor. This is done by finding the GCD (Greatest Common denominator) of each pair. If a pair of keys doesn't share a prime they will have a GCD of 1. By working with a very large number of keys the researchers were able to identify a large number of faulty keys.

So is this a big deal? Not as big as you might think from reading the NY Times article.
Obligatory PHD comic