Cornerstone of Internet Security Cracked

A popular encryption tool for keeping credit card numbers and other information secret on the Internet has been cracked. Last week, scientists announced at a press conference in Amsterdam that they had broken the RSA-155 code, which protects credit card transactions and secure e-mail in Europe. The feat suggests that anyone trafficking in confidential information on the Internet may soon have to switch to more-sophisticated encryption software.


Prime prize. The Dutch team factored a 155-digit number into two primes.

Using RSA-155, one party can send a secure message to another by using the recipient's "public key"--a 155-digit product of two large prime numbers--to transform the original text or string of numbers into ciphertext. Decoding the message requires the two prime numbers, known only to the recipient. For a long time this encryption was considered secure, as factoring a 155-digit number was thought to be beyond the scope of practical computations.

Two years ago, however, a group led by Herman te Riele of the Centre for Mathematics and Computer Science (CWI) in Amsterdam succeeded in factoring a monster 180-digit number belonging to a special set, called Cunningham numbers, that are easier than ordinary numbers to factor (see InScight, 17 September 1997). After improving the software and the algorithm--called Number Field Sieve--used for pinpointing likely prime numbers, Te Riele's team, including researchers from CWI and from Microsoft and Sun Microsystems, devoted 5 months on 300 personal computers and a Cray 916 supercomputer to finding the two prime factors of a 155-digit number.

"Our aim was to show that in principle this can be done," Te Riele says. For the moment, he says there's little reason for European users to worry that someone will snoop on their Internet credit card purchases--cracking the code still takes too much computing firepower and expertise. He figures it will take only 2 to 3 years, however, before such code-cracking becomes common enough to threaten ordinary users.

One of the inventors of the RSA code says he had already reconciled himself to someone breaching the code. "I and fellow cryptographers have been recommending for a long time that keys of that size are too short," says Ronald Rivest, a cryptographer at the Massachusetts Institute of Technology. All Internet commerce, says Te Riele, may have to soon move to the more intractable codes--involving 232 digits--that are now standard in the United States or the even longer codes of 309 digits used for government and military transactions.