08/09/2012

El enigma de Turing (parte 3)

Esta es la tercera parte de la serie El enigma de Turing. Link a la primera parte. Link a la segunda parte.

Habíamos dejado a Turing regresando de Princeton. Mientras trabajaba en sus temas de Lógica y la situación política en Europa se complicaba cada vez más, Turing se había interesado por la criptografía: la ciencia de crear y romper códigos para mandar mensajes cifrados. Se le ocurrió de que un buen método criptográfico sería convertir un texto en un número (como había hecho Gödel con las proposiciones matematicas, y él mismo con las tablas de las máquinas de computar) y multiplicarlo por otro número muy grande. Así el desencriptado se convertía en un problema de factorización, que podía ser muy difícil. Fue una idea premonitoria, porque así funciona la mayoría de los códigos de encriptación hoy en día (cada vez que usamos la tarjeta de crédito o nos conectamos a Gmail, por ejemplo). Turing, que tenía un gusto por armar cosas con sus propias manos (a diferencia de muchos matemáticos) inclusive fabricó una máquina electromecánica, con relés y electroimanes, que hacían esta codificación. ¡Él mismo enrolló los solenoides para fabricar relés caseros!

EL ENIGMA

Finalmente estalló la guerra. Por ser una nación insular, la subsistencia de Gran Bretaña dependía fuertemente del transporte marítimo de mercadería. Enormes convoys de suministros, fuertemente escoltados, cruzaban permanentemente el Atlántico. Sin embargo, las pérdidas eran enormes, y ponían en peligro la supervivencia de Inglaterra. El principal peligro venía de los U-boats, los submarinos alemanes, rápidos e indetectables, que recibían instrucciones codificadas del Alto Mando.

Las transmisiones eran codificadas mediante una máquina llamada Enigma. Tenía un teclado sencillo, sobre el cual había unas lamparitas que reproducían el mismo arreglo de letras. Adentro había un circuito eléctrico de configuración variable. Cuando se presionaba una letra en el teclado, el circuito la codificaba en otra letra y se encendía la lamparita correspondiente. Al mismo tiempo, el mecanismo variable (unas ruedas, que se ven en la foto atrás de las lamparitas) avanzaba un paso, de manera que la siguiente letra que se presionaba era codificada por un circuito distinto. El mensaje codificado se enviaba por correo o telégrafo. La persona que recibía el mensaje encriptado configuraba su máquina de la misma manera que la codificadora (con una clave preestablecida, que no se enviaba), tipeaba el galimatías, y las lamparitas daban el mensaje decodificado. No era más que un código de substitución, mucho más sencillo que la multiplicación de números grandes que había ideado Alan. Pero el mecanismo de los rotores móviles hacía que una misma letra se substituyera por letras distintas a lo largo del mensaje, dificultando enormemente su descifrado.

En 1932 tres matemáticos polacos habían desarrollado un método para decodificar los mensajes de la Enigma. De una manera que encajaba perfectamente con el pensamiento de Turing habían concluido que, si se usaba una máquina para codificar el mensaje, había que usar una máquina para romper el código. Y diseñaron una máquina, a la que llamaron Bomb, que hacía el trabajo. No se sabe si eligieron el nombre por el tic-tac que hacía la máquina, o por un postre helado que les encantaba.

BLETCHLEY PARK

Los británicos ya habían empezado a colaborar con los polacos, y lograron obtener toda la información sobre la Bomb antes de la ocupación de Polonia. Pero el Servicio de Criptografía británico era más bien anticuado: un puñado de clasicistas y traductores, algo completamente inútil para el conflicto que se venía. En particular, eran incapaces de descifrar la Enigma. Alguien tuvo el buen tino de reclutar un pequeño grupo de especialistas “de tipo profesoral”, matemáticos, físicos, ingenieros y campeones de ajedrez (!). Uno de ellos fue Alan Turing, recién regresado de Princeton. Luchando a brazo partido contra la burocracia de la administración pública y la rigidez de la institución militar lograron transformar por completo el Servicio. Su mejor argumento, por supuesto, es que ellos sí podían decodificar los mensajes cifrados. Finalmente reunieron un equipo enorme, multidisciplinario y súper secreto en una mansión campestre llamada Bletchley Park. Llegaron a trabajar allí más de 10000 personas, así que no cabían todos en el caserón. Se construyeron unos “huts”, unas barracas. Turing estuvo a cargo del Hut 8, dedicado al desencriptado de los mensajes de la Marina alemana.

En Bletchley Park rediseñaron y mejoraron la máquina polaca y la llamaron Bombe. Turing demostró que era posible reducir enormemente el espacio de búsqueda de códigos aplicando la lógica matemática: había recorridos en el espacio de configuraciones del circuito que llevaban a contradicciones, y que podían ser abandonados. Para implementar esta mecanización de las deducciones lógicas no se necesitaba matemática muy avanzada, eran más bien aplicaciones de conceptos sencillos. ¡Nada como el problema de Hilbert! De hecho, las Bombe no eran máquinas de Turing. Además, la decodificación no era en absoluto automática. Dependía en buena parte de "adivinar" partes de los mensajes, algo que era posible sólo gracias a la rígida estructura de los mensajes militares. Para ensamblar esta adivinación con la búsqueda sistemática, la teoría requería la formalización de los procedimientos de toma de decisión basada en información parcial. El formalismo que desarrolló Turing es esencialmente idéntico al de Claude Shannon, a quien Alan conoció pocos años después en Bell Labs, y que hoy llamamos Teoría de la Información.

BOMBE VS. ENIGMA

La primera Turing Bombe entró en funcionamiento en 1940. Pesaba una tonelada y simulaba el funcionamiento en paralelo de 30 Enigmas (la de la foto es una reconstrucción reciente). Finalmente lograron descifrar los mensajes codificados con la Enigma. Al principio cada mensaje les llevaba semanas de trabajo. Pero rápidamente lograron reducir el tiempo a minutos. Los mensajes de la Luftwaffe empezaron a desencriptarse a fines de 1940, pero recién a mediados del '41 pudieron hacerlo con los de los U-boat, que usaban una Enigma más sofisticada. Alcanzaron tal maestría que las pérdida navales cayeron significativamente. Sorprendentemente, los alemanes estaban tan convencidos de la infalibilidad de la Enigma, que en lugar de sospechar que les estaban descifrando los mensajes, sospecharon que los estaban espiando. Así que dedicaron esfuerzos inútiles a cazar espías mientras en Bletchley Park leían sus mensajes como quien lee el Argentinisches Tageblatt.

En febrero de 1942 los alemanes agregaron un nuevo rotor a la Enigma naval y los ingleses perdieron la ventaja. Las pérdidas aumentaron enorme y peligrosamente. Los aliados empezaron a perder más tonelaje que el que podían construir en los astilleros. ¡Si la situación no se revertía, perderían la batalla del Atlántico! En Bletchley Park empezaron a usar la novísima tecnología electrónica (en lugar de electromecánica) que estaba empezando a usarse en las compañías de teléfonos, para alcanzar mayores velocidades de cálculo. Pero fue una tecnología que terminó usándose en otro sistema, no en la Enigma.

En noviembre 1942 Turing fue enviado a Estados Unidos para coordinar al más alto nivel las actividades de desencriptado en conjunto, intentando resolver la crisis de la Enigma naval. Se pasó dos meses en Bell Labs, donde conoció a Harry Nyquist y a Shannon, dos matemáticos que en la década siguiente harían trabajos fundamentales del inicio de la era digital. En Bell querían encriptar las transmisiones telefónicas transatlánticas entre Roosevelt y Churchill. Los métodos que idearon son la base de todas las técnicas de codificación digital de señales analógicas que usamos ahora todo el tiempo, tales como el JPG y el MP3.

A principios de marzo del 43 descubrieron una debilidad de la nueva Enigma y pudieron volver a desencriptarla. Inglaterra y Estados Unidos recobraron el control del Atlántico, situación que se mantendría hasta el final de la guerra. Uno a uno, todos los modelos de Enigma cayeron ante el poder de cómputo de Bletchley Park.

UN CEREBRO ELECTRÓNICO

Alan volvió a Inglaterra, pero su trabajo ya no era esencial en Bletchley Park, así que pudo liberarse un poco de sus responsabilidades. Se convirtió en una especie de consultor todo-propósito del Servicio, y se dedicó a aprender electrónica y a un proyecto propio de codificación electrónica del lenguaje hablado. Su posición administrativa era muy influyente a pesar de su juventud (tenía 30 años), y fue fundamental para lograr el apoyo gubernamental para empezar a desarrollar máquinas más veloces que las Bombes, basadas en la electrónica. Las primeras de este tipo se llamaron Colossus. Tenían miles de válvulas, y nadie les tenía mucha fe al principio, pero funcionaron. Fueron las primeras computadoras electrónicas, pero a diferencia de las computadoras modernas, estaban también dedicadas a un propósito específico, como las Bombes. Alan, al ver funcionar estas máquinas desencriptadoras, se entusiasmó vislumbrando el poder que una verdadera máquina de Turing podría lograr con la ayuda de la tecnología electrónica. Empezó a diseñar la construcción de su propia Máquina Universal. Se refería a su proyecto como “construir un cerebro”.

¡Y de nuevo le ganaron de mano del otro lado del Atlántico! Se publicó un proyecto, llamado EDVAC, proponiendo construir precisamente lo que quería hacer Alan: una computadora electrónica, digital binaria y programable. John von Neumann, uno de sus principales promotores, le enchufaba el Computable Numbers a cada persona que se involucraba en el proyecto. La reacción en Inglaterra fue, con todo, razonablemente buena: crearon un laboratorio para llevar adelante un proyecto similar, y Alan Turing fue nombrado director científico. La guerra, además, había terminado. ¿Qué más se podía pedir?

Finaliza en la Cuarta Parte de El enigma de Turing...


La EDVAC finalmente se construyó, y fue la primera computadora en el sentido moderno. Usaba una memoria externa de cable magnético, su memoria interna era acústica (aproximadamente 1 kilobyte, más tres registos de una palabra cada uno), operaba a una velocidad de procesamiento de menos de 1 kilohertz, tenía una unidad de control con osciloscopio y un timer. Sus 6000 válvulas de vacío y 12 mil diodos consumían 56 kilowatts. Ocupaba 45 metros cuadrados, pesaba 8 toneladas y la operaban 30 personas en cada turno de 8 horas. Costó 500 mil dólares, empezó a funcionar en 1951 y se la usó durante 10 exitosos años.

1 comentario:

  1. Hola Guillermo,

    Muy buena la serie de publicaciones de Turing. Te dejo un link donde se muestran fotos actuales de Bletchley Park, quizás te interesa: http://www.cyberhades.com/2012/09/29/visita-a-bletchley-park-primera-parte/

    Saludos,
    Manuel G.

    ResponderEliminar