SAN FRANCISCO — A team of European and American mathematicians and cryptographers have discovered an unexpected weakness in the encryption system widely used worldwide for online shopping, banking, e-mail and other Internet services intended to remain private and secure.
The flaw — which involves a small but measurable number of cases — has to do with the way the system generates random numbers, which are used to make it practically impossible for an attacker to unscramble digital messages. While it can affect the transactions of individual Internet users, there is nothing an individual can do about it. The operators of large Web sites will need to make changes to ensure the security of their systems, the researchers said. […]
The system requires that a user first create and publish the product of two large prime numbers, in addition to another number, to generate a public “key.” The original numbers are kept secret. To encrypt a message, a second person employs a formula that contains the public number. In practice, only someone with knowledge of the original prime numbers can decode that message.
For the system to provide security, however, it is essential that the secret prime numbers be generated randomly. The researchers discovered that in a small but significant number of cases, the random number generation system failed to work correctly.
The importance in ensuring that encryption systems do not have undetected flaws cannot be overstated. The modern world’s online commerce system rests entirely on the secrecy afforded by the public key cryptographic infrastructure.
The researchers described their work in a paper that the authors have submitted for publication at a cryptography conference to be held in Santa Barbara, Calif., in August. They made their findings public Tuesday because they believe the issue is of immediate concern to the operators of Web servers that rely on the public key cryptography system. […]
[The researchers] also stated that if they had been able to discover the flaw, it was also possible that it had been previously uncovered, perhaps by organizations or individuals with malicious intent: “The lack of sophistication of our methods and findings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters,” they wrote.
While they said that the publication of results that potentially undermine the security of encryption keys was inappropriate unless the parties were notified first, the researchers noted that the way they discovered the flaw made identifying potentially vulnerable parties a challenge. […]
The researchers whimsically titled their paper “Ron Was Wrong, Whit Is Right,” a reference to two pioneers in public key cryptography, Ron Rivest and Whitfield Diffie.