Two mathematicians, working with hundreds of colleagues on a thousand computers, announced yesterday that they had broken a code viewed by many cryptographers and security experts as virtually impenetrable.
The feat, in which the mathematicians factored one of the world's "most wanted" numbers, means that many security-minded organizations will need to change their cryptographic systems in order to prevent security breaches.
"In the long run, mathematical breakthroughs like this will make everyone more cautious about how far one must go to keep a message private," said Arjen Lenstra of Bellcore, the research arm of the major regional telephone companies, who with Mark Manasse of Digital Machine Corp. successfully factored a 155-digit number, a feat many mathematicians had believed to be prohibitively difficult, if not impossible.
Cryptographic systems are used to encode messages and data before they are sent among banks, corporations, governments, the military -- anyone wishing to avoid having computerized mail perused by outsiders. The sender encodes messages using a many-digit number that would be difficult or impossible to factor.
Factoring a number means finding the prime numbers by which it can be divided evenly. A prime number is one that can only be divided evenly by 1 and by itself. For example, 15 factors into 3
5. And 105 factors into 3
7. Only someone who knows the factors of the large number can decode the message.
Until now, it was thought virtually impossible to factor a number 155 digits long, and many cryptographic systems used numbers that long to encode their messages.
The work of Lenstra and Manasse, and hundreds of mathematicians who plugged the Bellcore program into their computers at night to solve additional parts of the problem, changes the game. Lenstra now says security-minded users must find numbers greater than 200 digits in order to feel safe.
Lenstra and Manasse, chewing up the equivalent of 275 years of computer time, found that the 155-digit number could be factored by 7-digit number, a 49-digit number and a 99-digit number.