lotus

previous page: 3.4. Can the NSA crack RSA?
  
page up: PGP FAQ
  
next page: 3.6. How secure is the "for your eyes only" option (-m)? (PGP)

3.5. Has RSA ever been cracked publicly? What is RSA-129?




Description

This article is from the PGP FAQ, by Jeff Licquia jalicqui@prairienet.org with numerous contributions by others.

3.5. Has RSA ever been cracked publicly? What is RSA-129?

One RSA-encrypted message has been cracked publicly.

When the inventors of RSA first published the algorithm, they
encrypted a sample message with it and made it available along with
the public key used to encrypt the message. They offered $100 to the
first person to provide the plaintext message. This challenge is
often called "RSA-129" because the public key used was 129 digits,
which translates to approximately 430 bits.

Recently, an international team coordinated by Paul Leyland, Derek
Atkins, Arjen Lenstra, and Michael Graff successfully factored the
public key used to encrypt the RSA-129 message and recovered the
plaintext. The message read:

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

They headed a huge volunteer effort in which work was distributed via
E-mail, fax, and regular mail to workers on the Internet, who
processed their portion and sent the results back. About 1600
machines took part, with computing power ranging from a fax machine to
Cray supercomputers. They used the best known factoring algorithm of
the time; better methods have been discovered since then, but the
results are still instructive in the amount of work required to crack
a RSA-encrypted message.

The coordinators have estimated that the project took about eight
months of real time and used approximately 5000 MIPS-years of
computing time. (A MIPS-year is approximately the amount of computing
done by a 1 MIPS [million instructions per second] computer in one
year.)

What does all this have to do with PGP? The RSA-129 key is
approximately equal in security to a 426-bit PGP key. This has been
shown to be easily crackable by this project. PGP used to recommend
384-bit keys as "casual grade" security; recent versions offer 512
bits as a recommended minimum security level.

Note that this effort cracked only a single RSA key. Nothing was
discovered during the course of the experiment to cause any other keys
to become less secure than they had been.

For more information on the RSA-129 project, see:

ftp://ftp.ox.ac.uk/pub/math/rsa129/

 

Continue to:













TOP
previous page: 3.4. Can the NSA crack RSA?
  
page up: PGP FAQ
  
next page: 3.6. How secure is the "for your eyes only" option (-m)? (PGP)