The Magic Words are Squeamish Ossifrage
Encyclopedia
The text "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 Scientific American
. It was solved in 1993–1994 by a large joint computer project co-ordinated by Derek Atkins
, Michael Graff
, Arjen Lenstra
and Paul Leyland
. 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 is an older name for the lammergeier
, a scavenging vulture that is famous for dropping animal bones and live tortoises onto rocks to crack them open. It might perhaps be considered among the least squeamish of creatures. The 1993-1994 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 if the two problems are mathematically equivalent, factoring is currently the only method of directly breaking RSA. The decryption of the 1977 ciphertext involved the factoring of a 129-digit number, RSA-129, in order to recover the plaintext
.
Ron Rivest
estimated in 1977 that factoring a 125-digit number would require 40 quadrillion years, even with the highly conservative assumption that modular multiplication could be carried out in a nanosecond
; he therefore then believed that RSA-129 could never be broken in practice. What he failed to take into account was the possibility of progress in factoring algorithm
s, 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.
There was a US$100 prize associated with the challenge, which the winners donated to the Free Software Foundation
.
, the encrypted text whose decryption leads to the hacking of OZ begins with the words "The magic words are squeamish ossifrage."
Ciphertext
In cryptography, ciphertext 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 that is unreadable by a human or computer without the proper cipher...
posed by the inventors of the RSA cipher
Cipher
In cryptography, a cipher 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. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
in 1977. The problem appeared in Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
's Mathematical Games column in Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
. It was solved in 1993–1994 by a large joint computer project co-ordinated by Derek Atkins
Derek Atkins
Derek A Atkins is a computer scientist specializing in Computer Security. He studied Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, and currently works at PGP Corporation....
, Michael Graff
Michael Graff
Michael Graff graduated from with a degree in Computer Engineering. Currently working at , a non-profit corporation. Michael is a co-author and one of several architects of BIND 9.In April 1984, Michael co-authored The Magic Words are Squeamish Ossifrage....
, Arjen Lenstra
Arjen Lenstra
Arjen Klaas Lenstra is a Dutch mathematician. He studied mathematics at the University of Amsterdam.He is currently a professor at the EPFL , in the Laboratory for Cryptologic Algorithms, and...
and Paul Leyland
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 has also studied Cunningham numbers, Cullen numbers, Woodall...
. More than 600 volunteers contributed CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
time from about 1,600 machines (two of which were fax
Fax
Fax , sometimes called telecopying, is the telephonic transmission of scanned printed material , normally to a telephone number connected to a printer or other output device...
machines) over six months. The coordination was done via the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
and was one of the first such projects.
Ossifrage is an older name for the lammergeier
Lammergeier
The Lammergeier, Lammergeyer, or Bearded Vulture, Gypaetus barbatus , is the only member of the genus Gypaetus. Traditionally considered an Old World vulture, it actually forms a minor lineage of Accipitridae together with the Egyptian Vulture , its closest living relative...
, a scavenging vulture that is famous for dropping animal bones and live tortoises onto rocks to crack them open. It might perhaps be considered among the least squeamish of creatures. The 1993-1994 effort began the tradition of using the words "squeamish ossifrage" in cryptanalytic
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
challenges.
The difficulty of breaking the RSA cipher — recovering a plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
message given a ciphertext and the public key — is connected to the difficulty of factoring
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
large numbers. While it is not known if the two problems are mathematically equivalent, factoring is currently the only method of directly breaking RSA. The decryption of the 1977 ciphertext involved the factoring of a 129-digit number, RSA-129, in order to recover the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
.
Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
estimated in 1977 that factoring a 125-digit number would require 40 quadrillion years, even with the highly conservative assumption that modular multiplication could be carried out in a nanosecond
Nanosecond
A nanosecond is one billionth of a second . One nanosecond is to one second as one second is to 31.7 years.The word nanosecond is formed by the prefix nano and the unit second. Its symbol is ns....
; he therefore then believed that RSA-129 could never be broken in practice. What he failed to take into account was the possibility of progress in factoring algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s, and a lot of progress was made in the following decades. Atkins et al. used the quadratic sieve
Quadratic sieve
The quadratic sieve algorithm is a modern integer factorization algorithm and, in practice, the second fastest method known . It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve...
algorithm invented by Carl Pomerance
Carl Pomerance
Carl Bernard Pomerance is a well-known 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 has at least 7 distinct prime factors. He immediately joined the faculty at the...
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.
There was a US$100 prize associated with the challenge, which the winners donated to the Free Software Foundation
Free Software Foundation
The Free Software Foundation is a non-profit corporation founded by Richard Stallman on 4 October 1985 to support the free software movement, a copyleft-based movement which aims to promote the universal freedom to create, distribute and modify computer software...
.
In popular culture
In the anime Summer WarsSummer Wars
is a 2009 Japanese animated science fiction romance film directed by Mamoru Hosoda, animated by Madhouse and distributed by Warner Bros. Pictures. The film's voice cast includes Ryunosuke Kamiki, Nanami Sakuraba, Mitsuki Tanimura, Sumiko Fuji and Ayumu Saitō...
, the encrypted text whose decryption leads to the hacking of OZ begins with the words "The magic words are squeamish ossifrage."
External links
- Technical paper on Derek Atkins' Web site (postscript file)