" Las palabras mágicas son un osífrago aprensivo " fue la solución a un desafío de texto cifrado planteado por los inventores del cifrado RSA en 1977. El problema apareció en la columna Mathematical Games de Martin Gardner en la edición de agosto de 1977 de Scientific American . [1] Se resolvió en 1993-94 mediante un gran proyecto informático conjunto coordinado por Derek Atkins , Michael Graff , Arjen Lenstra y Paul Leyland . [2] [3] [4] [5] Más de 600 voluntarios contribuyeron con tiempo de CPU de alrededor de 1.600 máquinas (dos de las cuales eran máquinas de fax ) durante seis meses. La coordinación se realizó a través de Internet y fue uno de los primeros proyectos de este tipo.
Ossifrage (del latín "rompehuesos") es un nombre antiguo para el buitre barbudo , un carroñero famoso por dejar caer huesos de animales y tortugas vivas sobre las rocas para abrirlas. El esfuerzo de 1993-94 inició la tradición de usar las palabras "ossifrage aprensivo" en los desafíos criptoanalíticos .
La dificultad de descifrar el código RSA (recuperar un mensaje de texto simple a partir de un texto cifrado y la clave pública) está relacionada con la dificultad de factorizar números grandes. Si bien no se sabe si los dos problemas son matemáticamente equivalentes, la factorización es actualmente el único método conocido públicamente para descifrar directamente el código RSA. El descifrado del texto cifrado de 1977 implicó la factorización de un número de 129 dígitos (426 bits), RSA-129 , para recuperar el texto simple.
En 1977, Ron Rivest estimó que factorizar un semiprimo de 125 dígitos requeriría 40 cuatrillones de años, utilizando el mejor algoritmo conocido y las computadoras más rápidas de la época. [6] En su artículo original recomendaron utilizar primos de 200 dígitos (663 bits) para proporcionar un margen de seguridad contra desarrollos futuros, [7] aunque es posible que solo haya retrasado la solución, ya que un semiprimo de 200 dígitos se factorizó en 2005. [8] [9] Sin embargo, los algoritmos de factorización eficientes no se habían estudiado mucho en ese momento, y se lograron muchos avances en las décadas siguientes. Atkins et al. utilizaron el algoritmo de criba cuadrática inventado por Carl Pomerance en 1981. Si bien la criba de campo numérico asintóticamente más rápida acababa de inventarse, no estaba claro en ese momento que fuera mejor que la criba cuadrática para números de 129 dígitos. Los requisitos de memoria del algoritmo más nuevo también eran una preocupación. [10]
El desafío tenía un premio de 100 dólares estadounidenses asociado, que los ganadores donaron a la Free Software Foundation .
En 2015, el mismo número RSA-129 se factorizó en aproximadamente un día, con la implementación de código abierto CADO-NFS del tamiz de campo numérico, utilizando un servicio comercial de computación en la nube por aproximadamente $30. [11]
{{cite book}}: |work=ignorado ( ayuda )