Superhack; July 1994; Scientific American Magazine; by Leutwyler; 2 Page(s)

In August 1977 three professors from the Massachusetts Institute of Technology dared Scientific American readers to decode a cipher they printed in Martin Gardner's "Mathematical Games" column. The numerical teaser was one of the first published examples of their newly invented encryption system, called RSA. The trio--Ronald L. Rivest, Adi Shamir and Leonard M. Adleman--offered a $100 reward for the return of a plain-text sentence, an event they predicted might not occur for some 40 quadrillion years. This past April, Bell Communications Research scientist Arjen K. Lenstra, three computer hobbyists and over 600 volunteers from the Internet claimed the check early, after only eight months of work.

It was inconceivable 17 years ago that this code could ever be broken, Lenstra says. Indeed, RSA is considered one of the most secure commercial encryption measures available. To encode a message using RSA, the text is converted into a number, which is then raised to a certain exponent; from that, a fixed, large number, or modulus, is subtracted repeatedly until the result is smaller than the modulus itself. The user can publish the exponent and large modulus (called the public keys) so that anyone can create a secret message with them. To determine the inverse function and recover that message, however, requires knowledge of those two prime numbers (those divisible only by 1 and themselves) that when multiplied yield the public key. Although it is trivial to generate products of large, prime numbers, it is inordinately difficult to factor these products.