Interesting People mailing list archives
RSA 129 (fwd) BELLCORE GUIDES GLOBAL TEAM IN CRACKING CODE
From: David Farber <farber () central cis upenn edu>
Date: Wed, 27 Apr 1994 09:11:57 -0400
The following press release was issued by Corporate Communications on April 26, 1994 BELLCORE GUIDES GLOBAL TEAM IN CRACKING CODE Morristown, N.J. -- A Bellcore scientist has guided an international team in cracking a code once thought uncrackable. The team consisted of three academics and more than 600 volunteers on the Internet from around the world, and the code they cracked was based on a 129-digit number called RSA 129. The renowned number is: 114,381,625,757,888,867,669,235,779,976,146,612,010,218, 296,721,242,362,562,561,842,935,706,935,245,733,897,830, 597,123,563,958,705,058,989,075,147,599,290,026,879,543,541 The 129-digit number is called RSA 129 for its originators, Ronald Rivest, Adi Shamir and Leonard Adleman (RSA). The three embedded a message using the code in 1977 and challenged anyone to crack it. The achievement of Arjen Lenstra and the team has important implications for future security technologies, since the codes protecting such security are often based on the difficulty of factoring very long numbers--that is, breaking a number down into prime numbers. (A prime number is only evenly divisible by one and itself). In France, similar codes protect telephone "smart cards." And they have other applications besides telecommunications--in banking, in the security systems of nuclear power stations, and in the military. Lenstra, Bellcore's factoring expert, guided the global effort to factor RSA 129. Lenstra designed the computational software used by the Internet volunteers, and the software used in the final stages of factoring. Dr. Paul Leyland, a computer-systems manager at Oxford University in England, and two students, Derek Atkins, from M.I.T., and Michael Graff of Iowa State University, monitored the day-to-day progress and managed the hundreds of volunteers on the Internet. "In 1977, this would have been unimaginable," says Bellcore's Lenstra. "The evolution of computing technologies and of the Internet has made the network vulnerable -- but, ironically enough, provides the means for protecting it by enabling the use of larger numbers than would have been feasible or necessary a few years ago." Bellcore, on behalf of most of the nation's local telephone companies, evaluates the security of networks. This includes studying cryptographic systems and trying to break them. To ensure "trustworthy networks," Bellcore examines ways to protect the privacy of information traveling on the networks as well as information stored in network databases. This role is critical, as the emerging information superhighway will foster new ways of doing business electronically. The ability to factor large numbers could potentially threaten many security codes based on a widely used cryptographic system created by Rivest, Shamir, and Adleman. The RSA system is based on the principle that it's infeasible to factor large numbers equalling the product of two large primes. Lenstra and the team broke RSA 129 down into two prime numbers, one of 64 digits, one of 65. Identifying these two primes allowed them to break the code. The numbers were: 3,490,529,510,847,650,949,147,849,619,903,898,133, 417,764,638,493,387,843,990,820,577 32,769,132,993,266,709,549,961,988,190,834,461,413,177, 642,967,992,942,539,798,288,533 The RSA code acts like a locked box with two keys. One key is a large, composite number which the owner may distribute publicly. Anyone can use that key to open the box and put a message in for the owner. But once the message is put in, the locked box can only be opened again by the owner, who has the second key, which is composed of the two factors of the composite number. Only the owner knows these numbers, because he or she has purposely constructed the composite number from two large prime numbers. "Cracking the RSA code provides a very useful benchmark on the difficulty of factoring numbers, and thus provides very useful guidance to users of the RSA cryptosystem as to how large their prime numbers should be," says Rivest of MIT. The use of modern security technology, such as the RSA system, is an important aspect of Bell Atlantic's ability to provision a secure information highway, says Ravi Ganesan, Manager of Center of Excellence for Electronic Commerce at Bell Atlantic. "These security tools are critical enablers for the long-term viability of electronic commerce technologies, which we are aggressively pursuing," he adds. "Consequently, the analysis of these security technologies, and the quantification of their strength and vulnerabilities, is critical. In this context, the efforts of Arjen Lenstra and others at Bellcore in providing Bell Atlantic state-of-the-art evaluations of important security tools is invaluable." Background This attack on RSA 129 originated last summer after Bellcore's Lenstra was asked by Atkins, Leyland and Graff to suggest a factoring challenge that would involve volunteers on the Internet. Lenstra proposed the formidable RSA 129. The team eventually involved volunteers on every continent but Antarctica. Volunteers worked in the Australia, Belgium, Brazil, Canada, Chile, Denmark, Finland, France, Germany, Holland, Ireland, Israel, Italy, Japan, New Zealand, Norway, Portugal, South Africa, Spain, Sweden, Switzerland, the United Kingdom, the United States and Venezuela. "We wanted to demonstrate, in public, how a team of enthusiasts could factor a number of the same size as those being used to protect commercial information," Leyland says. As the international mathematical challenge began, the problem was broken into thousands of tiny pieces and sent to the Internet volunteers to perform the preliminary calculations on their computers, on their own time. Graff corresponded on the Internet with potential volunteers, dividing the work between them. They then sent the results to Atkins at M.I.T. to be checked for accuracy. Atkins arranged for the use of a file server at M.I.T. to collect and process the work of the volunteers. He also handled system administration, making sure the data was backed up regularly. Leyland became the team's chief trouble shooter, and also produced regular status reports to keep the volunteers informed and interested. Once compiled and checked, the data was sent to Lenstra, who in turn assembled the data in one mammoth calculation on a MasPar supercomputer to produce the factors of RSA 129. "Just as it was impossible to predict in 1977 that RSA 129 would be broken, so it is impossible to predict how quickly other such codes can be broken," Lenstra says. "But the ability to break codes is getting better all the time, aided by increasingly powerful computing tools. Bellcore's work supports its customers in designing and implementing telecommunications systems that use longer numbers to assure the privacy and security of information traveling and stored on their networks," he added. Bellcore performs research and other technical services for the telecommunications companies of Ameritech, Bell Atlantic, BellSouth, NYNEX, Pacific Bell, Southwestern Bell and U S WEST, as well as Cincinnati Bell, Inc., The Southern New England Telephone Company and other leaders in industry and government.
Current thread:
- RSA 129 (fwd) BELLCORE GUIDES GLOBAL TEAM IN CRACKING CODE David Farber (Apr 27)