Punteros a cosas (curiosidades) mencionadas hoy en clase:

• algoritmo de coste lineal para el cálculo del k-ésimo elemento de un vector (y por tanto para el cálculo de la mediana)
• orígenes del algoritmo de Karatsuba
• premio Turing de este año
  • su algoritmo (ojo, hay una errata en esa página; cuando en un párrafo de la parte final habla del “problema del algoritmo discreto”, debería decir el “problema del logaritmo discreto”)

.

“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.

Sobre el algoritmo RSA que veremos en clase, recordamos esta anotación anterior con algunas curiosidades:
http://webdiis.unizar.es/asignaturas/AB/?p=1078

Seguramente habrás leído durante este año, en el que se conmemora el centenario del nacimiento de Alan Turing, algún artículo sobre la participación de este pionero de la Computación en la ruptura de los códigos secretos alemanes durante la Segunda Guerra Mundial (SGM), los códigos de las máquinas Enigma, en la instalación militar británica de Bletchley Park, utilizando la computadora Colossus (si no conoces la historia, aquí puedes leer algo sobre ella).

Las máquinas Enigma, desarrolladas originariamente en Alemania en la década de 1920, fueron los primeros dispositivos electromecánicos de cifrado y soportaron las comunicaciones militares del Alemania durante la SGM. La ruptura de esos códigos en Bletchley Park (Reino Unido) jugaría un papel clave en la terminación de la guerra y permitiría por tanto salvar muchas vidas humanas.

Lo que probablemente no conoces es la existencia de un “eslabón español” en la cadena de logros que llevó a la ruptura del código Enigma. La noticia fue publicada hace pocos días por la BBC. La resumimos a continuación.

Un par de máquinas Enigma utilizadas en la Guerra Civil española fueron donadas recientemente por nuestro país al GCHQ, la agencia de inteligencia de comunicaciones del Reino Unido. Esas máquinas cierran un capítulo que permanecía abierto en la historia de la ruptura del código, un capítulo que abrió el camino para el final de la SGM.

Un suboficial del ejército español encontró las máquinas casi por casualidad, hace sólo unos pocos años, en una habitación secreta del Ministerio de Defensa español, en Madrid.
 
«Nadie entró en ella porque era muy secreta», dice el General Félix Sanz Roldán, director del Centro Nacional de Inteligencia. «Y un día alguien dijo: ’Bueno, si es tan secreta, tal vez haya algo secreto dentro’. Entraron y vieron una pequeña oficina en la que se realizaron todas las operaciones de cifrado no sólo durante la guerra civil española, sino también en los años inmediatamente posteriores». En la habitación había alrededor de dos docenas de históricas máquinas Enigma.

Cuando empezó la guerra civil española en 1936, tanto la Alemania de Hitler como la Italia de Mussolini enviaron tropas para ayudar al ejército de Franco. Con el conflicto extendido por todo el país, necesitaban medios de comunicación segura entre la Legión Cóndor alemana, los italianos y las fuerzas de Franco. Para ello, Alemania donó un parque de máquinas comerciales Enigma debidamente modificadas.

En el Reino Unido existían ya expertos en una versión previa de la máquina Enigma comercializada en 1927, pero no tenían oportunidad de interceptar mensajes reales de los alemanes puesto que las señales alemanas resultaban inaudibles desde Gran Bretaña debido a la distancia. Sin embargo, las señales producidas por las máquinas enviadas a España por los alemanes en 1936 eran lo suficientemente audibles como para ser interceptadas y los británicos comenzaron a trabajar con esas señales. Tras seis o siete meses de trabajo con los mensajes españoles, ya tuvieron los primeros éxitos. En abril de 1937, los británicos consiguieron la primera desencriptación de un mensaje de Enigma.
 
La experiencia con los mensajes de las máquinas Enigma españolas resultó ser un paso crucial en el camino que condujo a la ruptura del código de las máquinas alemanas en Bletchley Park, durante la SGM.

 
En esta asignatura veremos un conocido método de encriptación, el RSA, como ejemplo de algoritmo de dividir para vencer. Detallaremos el funcionamiento de este método que, de manera algo “críptica”, aparece resumido en la siguiente transparencia.