Researchers find flaw in public key encryption

New York Times : Arjen K. Lenstra of école Polytechnique Fédérale de Lausanne, Switzerland, James P. Hughes of California, and their colleages have discovered a weakness in the public-key cryptography algorithm used worldwide for online shopping, banking, and other secure internet services. The algorithm uses the product of two large prime numbers, along with another number, to generate a public “key"; to encrypt data, a second person uses a formula that contains the public number. For this to be secure, the original two prime numbers must be randomly generated. Lenstra and his team analyzed several databases of public keys using the Euclidean algorithm to find the greatest common divisor of two integers. They found that in two out of every one thousand public keys, the numbers weren’t truly random. Lenstra’s team wasn’t able to discover why the random number generators failed in those cases, and they noted that the problem appears in the work of more than one software developer.