Cracking a prime cryptosystem.

Invented more than 20 years ago, the so-called RSA cryptosystem is widely used to provide privacy for electronic mail, ensure authenticity of digital data, and handle credit-card payments on the Internet. The system's security hinges on the observation that factoring numbers into their prime-number components becomes impractical for sufficiently large numbers.

No one has yet discovered an efficient recipe for factoring large numbers, and many mathematicians and computer scientists believe that no such method exists (SN: 5/7/94, p. 292). In the RSA scheme, the numbers involved typically have 309 decimal digits (1,024 bits).

The RSA cryptosystem has other potential vulnerabilities, however, and researchers have expended considerable effort to expose such weaknesses (SN: 10/3/98, p. 217). "At the moment, it appears that proper implementations [of RSA] can be trusted to provide security in the digital world," computer scientist Dan Boneh of Stanford University concludes in the February NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY.

One important, open question concerns whether cracking the RSA cryptosystem is, in fact, as hard as factoring. The specific mathematical procedure used for encrypting and decrypting data might contain a loophole that a malicious eavesdropper could exploit to intercept and decrypt a message without having to factor a large number.

Boneh and Ramarathnam Venkatesan of the Microsoft Corp. in Redmond, Wash., have recently uncovered mathematical evidence that, in certain cases, using techniques rooted in algebra to break the RSA cryptosystem may indeed be easier than factoring. Nonetheless, the result "does not point to any weakness of the system," the researchers contend. Though breaking may be easier than factoring, the time required to break the cryptosystem is still likely to be so long that the operation is impractical.