The Magic Words are Squeamish Ossifrage
The text "The Magic Words are Squeamish Ossifrage" was the solution to a challenge cyphertext posed by the inventors of the RSA cypher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in Scientific American. It was solved in 1993-94 by a large joint computer project co-ordinated by a team consisting of Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland; more than 600 volunteers contributed the CPU time of about 1600 machines over a six month period. The coordination was done via the Internet and was one of the first such projects.An ossifrage is a type of raptor (like a hawk or an eagle) and is mentioned in ancient Roman texts. Why one would be squeamish is not entirely clear. The 1993-94 effort began the tradition of using the words "squeamish ossifrage" in cryptanalytic challenges, which is amusing, but unfortunate, as it provides a 'crib' for the cryptanalyst. With high quality modern ciphers this may not be very important; however, Bletchley Park cryptanalysts went to some lengths to arrange for them (they termed the effort 'gardening').
The 'hardness' of breaking the RSA cypher (ie, to discover a plaintext message given a cyphertext) is connected to the difficulty of factorizing large numbers. While it is not known if the two problems are mathematically equivalent, factorization is currently the only method of directly breaking RSA itself; this is quite different than breaking a crypto system based on RSA where messages may be vulnerable due to a protocol problem having nothing to do with RSA per se. The decryption of the 1977 ciphertext involved the factorization 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 would "never" be broken. What he failed to take into account was the possibility of progress in factoring algorithms. Quite a lot 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 if 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.
See also
External link