The Magic Words are Squeamish Ossifrage

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 Martin Gardner Mathematical Games («Juegos Matemáticos») de la revista Scientific American.[1] Fue resuelto en 1994 por un gran proyecto computacional conjunto coordinado por Derek Atkins, Michael Graff, Arjen Lenstra y Paul Leyland. Más de 600 voluntarios aportaron tiempo de cálculo de unas 1600 máquinas (dos de ellas de fax) durante más de seis meses. La coordinación se realizó a través de Internet y supuso uno de las primeros proyectos de estas características.

Squeamish puede traducirse como 'aprensivo' o 'sensible', mientras que ossifrage es un término obsoleto para referirse en inglés al quebrantahuesos, un buitre carroñero conocido por arrojar los huesos de sus presas desde gran altura para romperlos contra las rocas y que podría considerarse como una de las criaturas menos aprensivas. El hito de 1994 inauguró la tradición de usar las palabras squeamish ossifrage en los retos criptoanalíticos.

La dificultad de romper la cifra RSA, esto es, recuperar un texto llano a partir de un texto cifrado y una clave pública, está íntimamente relacionado con la dificultad de factorizar números grandes. Aunque no está demostrado si ambos problemas son matemáticamente equivalentes, factorizar es actualmente el único método para romper RSA directamente. El descifrado del texto de 1977 involucró la factorización de un número de 129 cifras decimales, RSA-129, para recuperar el texto llano.

Ron Rivest estimó en 1977 que factorizar un número de 125 dígitos requeriría 40 cuatrillones de años, incluso con la muy prudente suposición de que la multiplicación modular podía llevarse a cabo en un nanosegundo; esto le llevó a pensar que RSA-129 no podría ser roto jamás en la práctica. Sin embargo no tuvo en cuenta la posibilidad de mejora de los algoritmos de factorización, entre los que se dieron grandes avances en las décadas siguientes. Atkins et al. emplearon el método de la criba cuadrática inventado por Carl Pomerance en 1981.[2] A pesar del reciente desarrollo de la asintóticamente más rápida criba en cuerpos de números, no estaba claro en aquel momento que esta sería mejor que la criba cuadrática para números de 129 cifras. También se tuvieron en cuenta los requisitos de memoria del nuevo algoritmo.

El premio ofrecido por el reto era de 100 $, que los ganadores donaron a la Free Software Foundation.

Notas al pie

  1. Gardner, Martin (agosto 1977). «A new kind of cipher that would take millions of years to break» (en inglés). Scientific American. http://www.fortunecity.com/emachines/e11/86/cipher1.html. Consultado el 14-2-2010.  Una versión en español se publicó en Investigación y Ciencia.
  2. Pomerance, Carl (1996). «A Tale of Two Sieves» (en inglés). Notices of the American Mathematical Society (43):  pp. 1473-1485. http://www.ams.org/notices/199612/pomerance.pdf. Consultado el 14-2-2010. 

Referencias

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • 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… …   Wikipedia

  • 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

Compartir el artículo y extractos

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