John Markoff at The New York Times is reporting on a new flaw in the RSA encryption method. European and American mathematicians posted their research online ahead of a conference, because they thought the flaw was too profound to delay.
RSA relies on the product of two large prime numbers. These prime numbers are typically generated by subjecting random numbers to a test that quickly eliminates the non-primes. The primes must be generated randomly in order to guarantee the system’s security.
(Developers of quantum computers have long sought to use them to hack secret messages by factoring that product, but fortunately they’ve only factored nothing more complex than 15 so far. Other researchers have sought to counter this factoring vulnerability.)
By examining a database containing millions of 1024-bit public keys, the researchers found that there were a sizable number--27 000 out of 7.1 million—had a prime factor in common, making them vulnerable.
Interestingly, Intel engineers recently wrote in IEEE Spectrum of a way to greatly improve the randomness of encryption numbers using digital circuits on a computer processor. Other engineers have sought such randomness in the vagaries of transistor characteristics in RFID memory chips.