Presentación de RSA en Scientific American
En Martin Gardner, RSA y otros pasatiempos matemáticos cuentan una historia sobre la presentación de RSA en la revista Scientific American (traducida como Investigación y Ciencia por aquí). El matemático martin Gardner tenía una columna sobre pasatiempos matemáticos y en agosto de 1977 presentaba los fundamentos de RSA con un reto a los lectores sobre la factorización de números primos, que es una historia que a veces contamos en clase cuando hablamos de la parte algorítmica de estas cosas.
El desafío consistía en factorizar la clave pública en sus dos factores y emplearlos para descifrar el mensaje. El texto llano es una frase inglesa convertida en un número mediante el procedimiento habitual (a=0, b=1…) elevado a 9007 módulo r. Rivest estimaba que usando el mejor algoritmo de factorización conocido y el más rápido de los ordenadores disponibles (del año 77) serían necesario del orden de 40 cuatrillones de años para resolver el reto.
La cosa tiene su gracia porque, al final, el desafío se resolvió 17 años después (utilizando, eso sí) 600 voluntarios con alrededor de 1600 máquinas calculando durante seis meses.
Puede leerse gratis el principio del artículo traducido en Comunicaciones secretas y el artículo original escaneado en A new kind of cipher that would take millions of years to break.
Buena lectura para estos días de navidad.