The Magic Words are Squeamish Ossifrage

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 algorithms, and quite 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 $100 prize associated with the challenge, which the winners donated to the Free Software Foundation.

ee also

* Brute force attack
* RSA numbers

External links

* [ Technical paper on Derek Atkins' Web site] (postscript file)

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • The Magic Words are Squeamish Ossifrage — El texto The Magic Words are Squeamish Ossifrage (del inglés «Las Palabras Mágicas son Quebrantahuesos Aprensivo») era la solución de un reto de factorización propuesto por los inventores de RSA en 1977. El problema apareció en la columna de… …   Wikipedia Español

  • Ciphertext — The Zimmermann Telegram (as it was sent from Washington to Mexico) encrypted as ciphertext. This article is about encrypted information. For an overview of cryptographic technology in general, see Cryptography. In cryptography, ciphertext (or… …   Wikipedia

  • RSA Factoring Challenge — The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in… …   Wikipedia

  • RSA — (аббревиатура от фамилий Rivest, Shamir и Adleman)  криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для… …   Википедия

  • RSA numbers — In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that are part of the RSA Factoring Challenge. The challenge was to find the prime factors but it was declared inactive in 2007. [RSA… …   Wikipedia

  • Timeline of cryptography — Below is a timeline of notable events related to cryptography.BCE *3500s The Sumerians develop cuneiform writing and the Egyptians develop hieroglyphic writing. *1500s The Phoenicians develop an alphabet *600 500 Hebrew scholars make use of… …   Wikipedia

  • List of ciphertexts — Some famous ciphertexts (or cryptograms) are:*The Babington Plot ciphers *The Zimmermann Telegram *The Magic Words are Squeamish Ossifrage *The cryptogram in The Gold Bug *Beale ciphers *Voynich Manuscript *Dorabella Cipher *Quipu *Kryptos… …   Wikipedia

  • Derek Atkins — For the Scottish footballer, see Derek Atkins (footballer). 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… …   Wikipedia

  • Ленстра, Арьен — Арьен Ленстра (нидерл. Arjen Klaas Lenstra) (род. 1956, Гронинген)  голландский математик, криптоаналитик. Арьен Ленстра занимается разработкой эффективных криптографических алгоритмов (XTR, VSH), разработкой и реализацией… …   Википедия

  • Competición de factorización RSA — La Competición de factorización RSA fue un desafío propuesto por los Laboratorios RSA el 18 de marzo de 1991 para fomentar la investigación en la teoría computacional de números y la dificultad práctica de la factorización de números enteros… …   Wikipedia Español

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.