El texto " Las palabras mágicas son aprensivos quebrantahuesos " era la solución a un reto texto cifrado planteado por los inventores del RSA cifrado en 1977. El problema aparecido en Martin Gardner 's columna de juegos matemáticos en la edición de agosto 1977 de Scientific American . [1] Fue resuelto en 1993-1994 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 CPUtiempo de aproximadamente 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 ('rompehuesos', del latín) es un nombre más antiguo para el quebrantahuesos , un carroñero famoso por dejar caer huesos de animales y tortugas vivas sobre las rocas para abrirlas. El esfuerzo de 1993-1994 inició la tradición de usar las palabras "osifrage delicado" en los desafíos criptoanalíticos .
La dificultad de descifrar el cifrado RSA (recuperar un mensaje de texto sin formato dado 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 romper directamente 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 sin formato.
Ron Rivest estimó en 1977 que factorizar un semiprimo de 125 dígitos requeriría 40 billones de años, utilizando el mejor algoritmo conocido y las computadoras más rápidas del día. [6] En su artículo original recomendaban el uso de números primos de 200 dígitos (663 bits) para proporcionar un margen de seguridad frente a desarrollos futuros, [7] aunque es posible que solo haya retrasado la solución, ya que en 2005 se factorizó un semiprimo de 200 dígitos. [8] [9] Pero los algoritmos de factorización eficientes no se habían estudiado mucho en ese momento, y se logró mucho progreso en las décadas siguientes. Atkins y col. utilizó el algoritmo de tamiz cuadrático inventado por Carl Pomerance en 1981. Si bien se acababa de inventar el tamiz de campo numérico asintóticamente más rápido , no estaba claro en ese momento si sería mejor que el tamiz cuadrático para números de 129 dígitos. Los requisitos de memoria del algoritmo más nuevo también fueron una preocupación. [10]
Hubo un premio de US $ 100 asociado con el desafío, 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 de computación en la nube comercial por aproximadamente $ 30. [11]
Ver también
Referencias
- ^ Singh, Simon (1999). El libro de códigos: la ciencia del secreto desde el antiguo Egipto hasta la criptografía cuántica (Primera edición de Anchor Books). Nueva York: Anchor Books. págs. 278 . ISBN 978-0-385-49532-5.
- ^ "Wisecrackers" . CON CABLE . Marzo de 1996 . Consultado el 24 de mayo de 2016 .
- ^ Atkins, Derek; Graff, Michael; Lenstra, Arjen K .; Leyland, Paul C. (1994). Las Palabras Mágicas son Squeamish Ossifrage . Actas de Asiacrypt '94 . Springer-Verlag. págs. 263-277. doi : 10.1007 / BFb0000440 . ISBN 978-3-540-59339-3.
- ^ Yan, Song Y. (28 de noviembre de 2012). Teoría de números computacionales y criptografía moderna . John Wiley e hijos. págs. 1–. ISBN 978-1-118-18861-3.
- ^ Hayes, Brian (julio de 1994). "Las palabras mágicas son Squeamish Ossifrage" (PDF) . Avances en Criptología - ASIACRYPT'94 . Consultado el 28 de septiembre de 2015 .
- ^ Gardner, Martin (1977). "Juegos matemáticos, agosto de 1977" (PDF) . Scientific American . 237 (2): 120-124. doi : 10.1038 / scientificamerican0877-120 .
- ^ Rivest, RL; Shamir, A .; Adleman, L. (1 de febrero de 1978). "Un método para obtener firmas digitales y criptosistemas de clave pública" (PDF) . Comun. ACM . 21 (2): 120-126. CiteSeerX 10.1.1.607.2677 . doi : 10.1145 / 359340.359342 . ISSN 0001-0782 .
- ↑ Thorsten Kleinjung (2009-05-09), Hemos factorizado RSA200 por GNFS. Archivado 2008-03-22 en Wayback Machine . Consultado el 10 de marzo de 2008.
- ^ RSA Laboratories, ¡ RSA-200 está factorizado! . Consultado el 10 de marzo de 2008.
- ^ Stinson, DR (1995). "RSA, Factoring y Squeamish Ossifrage" . Universidad de Waterloo . Consultado el 28 de septiembre de 2015 ., Material complementario a la edición de 1995 de su Teoría y práctica de la criptografía , consulte la página web .
- ^ Mchugh, Nathaniel (26 de marzo de 2015). "Nat McHugh: Las palabras mágicas son aprensivos Ossifrage - factorización RSA-129 usando CADO-NFS" . Nat McHugh . Consultado el 25 de mayo de 2016 .
enlaces externos
- Documento técnico en el sitio web de Derek Atkins (archivo postscript)