Fun_People Archive
27 Apr
More info on Bellcore and RSA 129 (without the squeamish ossifrage)

Date: Wed, 27 Apr 94 22:23:17 PDT
To: Fun_People
Subject: More info on Bellcore and RSA 129 (without the squeamish ossifrage)

Forwarded-by: bostic@vangogh.CS.Berkeley.EDU (Keith Bostic)
Forwarded-by: /dev/null@gauss.asd.sgi.com

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.

© 1994 Peter Langston