miércoles, 23 de octubre de 2013

Martin Gardner, RSA y otros pasatiempos matemáticos

Hace dos días (el 21 de octubre) se conmemoró el 99 aniversario del nacimiento de Martin Gardner (1914-2010), uno de los grandes divulgadores científicos (principalmente de la rama de las matemáticas). Especialmente conocido por su columna su columna mensual "Juegos matemáticos" de la revista de divulgación científica "Scientific American" ("Investigación y ciencia" en su edición en castellano) entre diciembre de 1956 y mayo de 1986.

Martin Gardner 
Fuente: http://owpdb.mfo.de/detail?photo_id=1292
En agosto de 1977 en su columna del Scientific American (publicado en "Investigación y ciencia" en octubre) y bajo el título de "Claves de nuevo tipo cuyo desciframiento ocuparía unos cuantos millones de años" ("a new kind of cipher that would take millions of years to break"), Martin Gardner presentó a tres profesores del MIT hasta entonces desconocidos y el resultado de su investigación.

Los profesores no eran otros que Rivest, Shamir y Adleman, especialistas en ciencias informáticas y se anunciaba un nuevo sistema criptográfico que poco después fue conocido como RSA por las siglas de los nombres de los tres investigadores). En su artículo, tras describir la criptografía de clave pública y los avances de Diffie y Hellman, presentaba como Rivest, Shamir y Adleman a través de números primos y la dificultad de factorización de un número producto de dos primos de gran tamaño habían conseguido un método criptográfico que cumplía las condiciones del criptosistema de clave pública.

Por primera vez se presentaba el criptosistema RSA al público, además en su artículo Gardner y el grupo del MIT dejaron un desafío a sus lectores en forma de mensaje codificado y dando la clave pública empleada para cifrarlo.
Clave pública (r):
114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
Texto cifrado:
96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154

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.

En el artículo, Gardner no disponía de espacio suficiente para explicar todos los detalles prácticos del RSA por lo que pidió a los lectores interesados que solicitaran los detalles al laboratorio de informática del MIT. Los tres investigadores se vieron inundados con unas 7.000 solicitudes de documentación. Sin embargo tardaron en contestar cerca de un año, hasta solventar ciertos problemas jurídicos y otros relacionados con la patente.

Lejos de la predicción de Rivest, el desafío de Gardner tardó "tan solo" 17 años en ser descifrado. El 26 de abril de 1994 un equipo de 600 voluntarios, en un reto de computación colaborativa, empleando unas 1.600 máquinas durante más de seis meses. Hay que señalar la mejora en los algoritmos de factorización (desde la publicación original) y que el reto propuesto por Gardner empleaba una clave de 129 cifras decimales.

El artículo original de Martin Gardner sobre el RSA se encuentra publicado también en su libro "Mosaicos de Penrose y escotillas cifradas". Otros libros de Martin Gardner relacionados con la criptografía: "El idioma de los espías", "Codes, ciphers and secret writing". Al tratar casi todas las ramas de las matemáticas, ha tocado otros muchos campos ampliamente relacionados con la computación y la seguridad informática, como por ejemplo los números aleatorios y pseudoaleatorios, etc. En general la bibliografía de este autor es extensa, altamente recomendable y con artículos de gran interés.

Más información:

A new kind of cipher that would take millions of years to break
Martin Gardner

Investigación y Ciencia. Claves de nuevo tipo cuyo desciframiento ocuparía unos cuantos millones de años


Antonio Ropero
Twitter: @aropero

4 comentarios:

  1. El texto cifrado era "The Magic Words are Squeamish Ossifrage" ("Las Palabras Mágicas son Quebrantahuesos Aprensivo").
    http://es.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage

    ResponderEliminar
  2. Enhorabuena por el artículo, muy bien traído el aniversario de Martin Gardner en el contexto de la seguridad informática.
    Me parece muy interesante dar a conocer la Historia de las ciencias, y creo que Gardner es una referencia para todos los divulgadores científicos.

    ResponderEliminar