Return to Timeline of the History of Computers
1994
RSA-129 Cracked
Ronald L. Rivest (b. 1947), Martin Gardner (1914–2010), Derek Atkins (b. 1971)
The math behind the RSA public key cryptography system first appeared in Martin Gardner’s column Mathematical Games, in the August 1977 issue of Scientific American. In addition to the algorithm, Gardner presented a challenge to readers: an encrypted message that could be cracked only by factoring a 129-digit number that had just two factors, a 64-digit prime and a 65-digit prime. Ronald Rivest, one of the inventors of the RSA algorithm, told Gardner that it would take 40 quadrillion years to factor the number, an estimate that was apparently based on 1977-era factoring technology. Rivest offered a $100 prize to the successful codebreaker.
Unlike other encryption algorithms, RSA-encrypted messages could be made arbitrarily difficult to crack, simply by using longer prime numbers to create a key. The number that Gardner published was 129 decimal digits, or 426 bits in length. By the early 1990s, it was clear that wasn’t strong enough for commercial communications: experts were recommending keys of 512 bits, and 1024 bits for high-security applications.
In 1992, Derek Atkins, then a 21-year-old computer science student at MIT, decided to attack the 129-digit number. Atkins realized the number was within reach if he could enlist hundreds of people from all over the internet to help, all contributing time to help factor the number. He assembled a group of collaborators, who took existing factoring software and modified it to work on this larger problem. On August 19, 1993, the group announced on a Usenet group that they were looking for help.
Over the next few months, more than 600 people contributed computer time to cracking RSA-129. After eight months, the 129-digit number was factored, revealing the secret message from 1977: THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
Factoring RSA-129 didn’t take 40 quadrillion years after all, but it did require about 100 quadrillion calculations. The $100 prize was donated to the Free Software Foundation, the nonprofit developing the open source GNU operating system.
SEE ALSO Public Key Cryptography (1976), RSA Encryption (1977), Quantum Computer Factors “15” (2001)
After he encrypted these words in 1977, MIT professor Ron Rivest thought that he would never see them again.