Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

.

.

“A new kind of cipher that would take millions of years to break.”

Ese era el título del artículo publicado por Martin Gardner (conocidísimo divulgador científico norteamericano) en la sección Mathematical Games de la revista Scientific American, vol. 237(2), pp. 120-124, en agosto de 1977 (puede descargarse aquí).

En él, Gardner describía el método de criptografía de clave pública conocido como RSA, recién desarrollado por los investigadores del M.I.T. R.L. Rivest, A. Shamir y L.M. Adleman, y que sería publicado un año después en su artículo:

R.L. Rivest, A. Shamir y L.M. Adleman: “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, 21(2), pp. 120-126, 1978.

En el artículo divulgativo de Scientific American, Gardner publicaba además el reto de descifrar un mensaje cifrado por el grupo del M.I.T. (ver figura). El reto exigía factorizar un nº de 128 cifras. El primer lector que descifrase el mensaje sería premiado con una recompensa de 100 dólares por el M.I.T. Se estimaba entonces que eran necesarios 2 millones de veces la edad del Universo de cálculo ininterrumpido del mejor computador de aquel momento para descifrar el mensaje. El M.I.T. no estaba dispuesto a pagar los 100 dólares fácilmente…

En abril de 1994, Atkins, Graff, Lenstra y Leyland resolvieron el problema propuesto por Gardner en 1977 tras más de 6 meses de cálculo, utilizando unos 1600 computadores de todo el mundo trabajando como una máquina paralela virtual. Ganaron los 100 dólares prometidos y los donaron a la Free Software Foundation. La solución era:

The Magic Words are Squeamish Ossifrage

—————

Mañana veremos en clase los detalles del algoritmo RSA, como aplicación de los métodos eficientes de multiplicación y potenciación de números grandes que hemos visto en clase los días pasados.

Comentarios