Martin Gardner, RSA y otros pasatiempos matemáticos

http://feedproxy.google.com/~r/hispasec/zCAd/~3/9Vr7yQr7aFk/martin-gardner-rsa-y-otros-pasatiempos.html

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 tardo “tan solo” 17 años en conseguir
romperse. 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

http://simson.net/ref/1977/Gardner_RSA.pdf‎

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

http://www.investigacionyciencia.es/investigacion-y-ciencia/numeros/1977/10/claves-de-nuevo-tipo-cuyo-desciframiento-ocupara-unos-cuantos-millones-de-aos-2048

Antonio Ropero

antonior@hispasec.com

Twitter: @aropero

Enviado por gReader

Anuncios
Minientrada | Esta entrada fue publicada en Math, Security. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s