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 |
