"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 cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...

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 magic, scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writin ...

'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, until June 1986, Gardner wrote 9 more columns, br ...

'' in the August 1977 issue of ''

Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it, with more than 150 Nobel Pri ...

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

Michael Graff Michael Graff is a co-author and one of several architects of BIND 9. In April 1994, he co-authored '' The Magic Words are Squeamish Ossifrage''. Graff graduated from Iowa State University with a degree in Computer Engineering. He is curren ...

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

and

Paul Leyland Paul Leyland is a British astronomer and 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 4 ...

. More than 600 volunteers contributed

CPU A central processing unit (CPU), also called a central processor, main processor, or just processor, is the primary processor in a given computer. Its electronic circuitry executes instructions of a computer program, such as arithmetic, log ...

time from about 1,600 machines (two of which were

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

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

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

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 in the Monotypic taxon, monotypic genus ''Gypaetus''. The bearded vulture is the only known vertebrate whose diet consists of ...

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

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

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 (more specifically, encoding) is the process of transforming information in a way that, ideally, only authorized parties can decode. This process converts the original representation of the information, known as plai ...

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 an American cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity. He is an Institute Profess ...

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

quadrillion Depending on context (e.g. language, culture, region), some large numbers have names that allow for describing large quantities in a textual form; not mathematical. For very large values, the text is generally shorter than a decimal numeric repres ...

years, using the best

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

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 (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 The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is consider ...

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 : \begin & ...

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. The organisation supports the free software movement, with the organization's preference for software being distributed ...

. 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