RSA-129 Cracked

[cyphpunk@aol.com]

"Business Wire

MORRISTOWN, N.J.--April 26, 1994--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,23
5,779,976,146,612,010,218, 296,721,242,362,562,561,842,93
5,706,935,245,733,897,830, 597,123,563,958,705,058,989,07
5,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,53 3



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."


"BELLCORE NEWS RELEASE: BROKE CODE THOUGHT UNCRACKABLE  4/26/94"
       _San_Jose_Mercury_News_, 27 April 1994:Business Section.