"The Magic Words are Squeamish Ossifrage" was the solution to a challenge

ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...

posed by the inventors of the RSA cipher in 1977. The problem appeared in

Martin Gardner Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lew ...

's ''

Mathematical Games column Over a period of 24 years (January 1957 – December 1980), Martin Gardner wrote 288 consecutive monthly "Mathematical Games" columns for ''Scientific American'' magazine. During the next years, through June 1986, Gardner wrote 9 more columns, ...

'' in the August 1977 issue of ''

Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it ...

''. It was solved in 1993–94 by a large, joint computer project co-ordinated by Derek Atkins, Michael Graff,

Arjen Lenstra Arjen Klaas Lenstra (born 2 March 1956, in Groningen) is a Dutch mathematician, cryptographer and computational number theorist. He is currently a professor at the École Polytechnique Fédérale de Lausanne (EPFL) where he heads of the Laborator ...

and

Paul Leyland Paul Leyland is a British number theorist who has studied integer factorization and primality testing. He has contributed to the factorization of RSA-129, RSA-140, and RSA-155, as well as potential factorial primes as large as 400! + 1. He ...

. More than 600 volunteers contributed CPU time from about 1,600 machines (two of which were

fax Fax (short for facsimile), sometimes called telecopying or telefax (the latter short for telefacsimile), is the telephonic transmission of scanned printed material (both text and images), normally to a telephone number connected to a printer o ...

machines) over six months. The coordination was done via the

Internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...

and was one of the first such projects. ''Ossifrage'' ('bone-breaker', from Latin) is an older name for the

bearded vulture The bearded vulture (''Gypaetus barbatus''), also known as the lammergeier and ossifrage, is a very large bird of prey and the only member of the genus ''Gypaetus''. Traditionally considered an Old World vulture, it actually forms a separate mi ...

, 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 Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic s ...

challenges. The difficulty of breaking the RSA cipher—recovering a

plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of com ...

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 In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can deci ...

of the 1977 ciphertext involved the factoring of a 129-digit (426 bit) number,

RSA-129 In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories ...

, in order to recover the plaintext.

Ron Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial In ...

estimated in 1977 that factoring a 125-digit semiprime would require 40

quadrillion Two naming scales for large numbers have been used in English and other European languages since the early modern era: the long and short scales. Most English variants use the short scale today, but the long scale remains dominant in many non-E ...

years, using the best

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

known and the fastest computers of the day. In their original paper they recommended using 200-digit (663 bit) primes to provide a margin of safety against future developments, though it may have only delayed the solution as a 200-digit semiprime was factored in 2005.

Thorsten Kleinjung Thorsten (Thorstein, Torstein, Torsten) is a Scandinavian given name. The Old Norse name was ''Þórsteinn''. It is a compound of the theonym ''Þór'' (''Thor'') and ''steinn'' "stone", which became ''Thor'' and ''sten'' in Old Danish and Old Swed ...

(2005-05-09)
We have factored RSA200 by GNFS
. Retrieved on 2008-03-10. 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 Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number ...

in 1981. While the asymptotically faster

number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...

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. There was a US$100 prize associated with the challenge, which the winners donated to the

Free Software Foundation The Free Software Foundation (FSF) is a 501(c)(3) non-profit organization founded by Richard Stallman on October 4, 1985, to support the free software movement, with the organization's preference for software being distributed under copyleft (" ...

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

References

External links

Technical paper on Derek Atkins' Web site
(postscript file) {{DEFAULTSORT:Magic Words are Squeamish Ossifrage, The History of cryptography Scientific American Public-key cryptography 1977 in science

See also

References

External links