The Magic Words are Squeamish Ossifrage

"The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American.[1] It was solved in 1993–94 by a large, joint computer project co-ordinated by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland.[2][3][4][5] More than 600 volunteers contributed CPU time from about 1,600 machines (two of which were fax machines) over six months. The coordination was done via the Internet and was one of the first such projects.

Ossifrage ('bone-breaker', from Latin) is an older name for the bearded vulture, a scavenger famous for dropping animal bones and live tortoises on top of rocks to crack them open. The 1993–94 effort began the tradition of using the words "squeamish ossifrage" in cryptanalytic challenges.

The difficulty of breaking the RSA cipher—recovering a plaintext message given a ciphertext and the public key—is connected to the difficulty of factoring large numbers. While it is not known whether the two problems are mathematically equivalent, factoring is currently the only publicly known method of directly breaking RSA. The decryption of the 1977 ciphertext involved the factoring of a 129-digit (426 bit) number, RSA-129, in order to recover the plaintext.

Ron Rivest estimated in 1977 that factoring a 125-digit semiprime would require 40 quadrillion years, using the best algorithm known and the fastest computers of the day.[6] In their original paper they recommended using 200-digit (663 bit) primes to provide a margin of safety against future developments,[7] though it may have only delayed the solution as a 200-digit semiprime was factored in 2005.[8][9] However, efficient factoring algorithms had not been studied much at the time, and a lot of progress was made in the following decades. Atkins et al. used the quadratic sieve algorithm invented by Carl Pomerance in 1981. While the asymptotically faster number field sieve had just been invented, it was not clear at the time that it would be better than the quadratic sieve for 129-digit numbers. The memory requirements of the newer algorithm were also a concern.[10]

There was a US$100 prize associated with the challenge, which the winners donated to the Free Software Foundation.

In 2015, the same RSA-129 number was factored in about one day, with the CADO-NFS open source implementation of number field sieve, using a commercial cloud computing service for about $30.[11]

See also

[edit]

References

[edit]
  1. ^ Singh, Simon (1999). The Code Book: The Science of Secrecy From Ancient Egypt To Quantum Cryptography (First Anchor Books ed.). New York: Anchor Books. pp. 278. ISBN 978-0-385-49532-5.
  2. ^ "Wisecrackers". WIRED. March 1996. Retrieved 2016-05-24.
  3. ^ Atkins, Derek; Graff, Michael; Lenstra, Arjen K.; Leyland, Paul C. (1994). The Magic Words are Squeamish Ossifrage. Springer-Verlag. pp. 263–277. doi:10.1007/BFb0000440. ISBN 978-3-540-59339-3. {{cite book}}: |work= ignored (help)
  4. ^ Yan, Song Y. (28 November 2012). Computational Number Theory and Modern Cryptography. John Wiley & Sons. pp. 1–. ISBN 978-1-118-18861-3.
  5. ^ Hayes, Brian (July 1994). "The Magic Words are Squeamish Ossifrage" (PDF). Advances in Cryptology – ASIACRYPT'94. Retrieved 28 September 2015.
  6. ^ Gardner, Martin (1977). "Mathematical Games, August 1977" (PDF). Scientific American. 237 (2): 120–124. doi:10.1038/scientificamerican0877-120.
  7. ^ Rivest, R. L.; Shamir, A.; Adleman, L. (1978-02-01). "A Method for Obtaining Digital Signatures and Public-key Cryptosystems" (PDF). Commun. ACM. 21 (2): 120–126. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342. ISSN 0001-0782. S2CID 2873616.
  8. ^ Thorsten Kleinjung (2005-05-09), We have factored RSA200 by GNFS Archived 2008-03-22 at the Wayback Machine. Retrieved on 2008-03-10.
  9. ^ RSA Laboratories, RSA-200 is factored!. Retrieved on 2008-03-10.
  10. ^ Stinson, D. R. (1995). "RSA, Factoring, and Squeamish Ossifrage". University of Waterloo. Retrieved 28 September 2015., Supplementary Material to the 1995 edition of his Cryptography Theory and Practice, see web page.
  11. ^ Mchugh, Nathaniel (2015-03-26). "Nat McHugh: The Magic Words are Squeamish Ossifrage - factoring RSA-129 using CADO-NFS". Nat McHugh. Retrieved 2016-05-25.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=The_Magic_Words_are_Squeamish_Ossifrage&oldid=1181720658"