Las Palabras Mágicas son Squeamish Ossifrage - The Magic Words are Squeamish Ossifrage

" 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 . Fue resuelto en 1993-1994 mediante un gran proyecto informático conjunto coordinado por Derek Atkins , Michael Graff , Arjen Lenstra y Paul Leyland . Más de 600 voluntarios contribuyeron con el tiempo de la CPU 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 utilizar las palabras "ossifrage 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 momento. En su artículo original, recomendaban el uso de números primos de 200 dígitos (663 bits) para proporcionar un margen de seguridad contra desarrollos futuros, aunque es posible que solo haya retrasado la solución, ya que en 2005 se factorizó un semiprimo de 200 dígitos. Pero los algoritmos de factorización eficientes no lo habían hecho. se ha estudiado mucho en ese momento, y se logró un gran progreso en las décadas siguientes. Atkins y col. usó 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.

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.

Ver también

Referencias

enlaces externos