Alan Turing y el descifrado de la Enigma

Alan Turing nació el 23 de junio de 1912 en Londres, hijo de un funcionario británico de la India. Sus padres se habían trasladado a Londres únicamente para que su hijo naciese en Gran Bretaña. Su padre regresó a la India unos meses después, y su madre cuando Alan tenía año y medio, dejando al niño en Inglaterra. Por ello Turing pasó gran parte de su infancia en internados o viviendo con amigos de la familia. Desde muy joven dio muestras de una habilidad extraordinaria para las matemáticas, aunque en otras materias no era un estudiante destacado. En 1931 ingresó en el prestigioso King’s College de la Universidad de Cambridge. Cuatro años más tarde consiguió el puesto de profesor en el King's College. En 1937 publicó un estudio titulado Sobre los números computables, en el que imaginaba una máquina programable que pudiese hacer operaciones matemáticas automáticamente, como multiplicar, dividir o hacer raíces cuadradas, y en la que los datos iniciales se introducirían por medio de una cinta de papel perforada y los resultados saldrían igualmente en otra cinta de papel. Al artefacto imaginario se le bautizó como máquina universal de Turing. Era el principio teórico de un ordenador, aunque la tecnología de la época aún no permitía hacerlo realidad. Sus propuestas no pasaron desapercibidas, y Turing se hizo un nombre en el mundillo matemático. Los años siguientes Turing continuó sus estudios en la Universidad de Princeton. Tras obtener el doctorado regresó en 1939 al King's College. Con 27 años se había convertido en un matemático reconocido y había alcanzado el éxito profesional.

Pero en septiembre de 1939 la brillante trayectoria académica de Turing se interrumpió. Nada más comenzar la guerra recibió una invitación para trabajar en el CG&CS (la Escuela Gubernamental de Códigos y Cifras), con sede en Bletchley Park. Allí Turing se tuvo que enfrentar al problema de descifrar la clave Enigma alemana. Como comenté en la entrada sobre Bletchley Park, los británicos no partían de cero en sus investigaciones, ya que podían aprovechar los avances que habían hecho en los años anteriores los criptoanalistas polacos. Sin embargo, debido al aumento de la complejidad y de la seguridad de la Enigma las técnicas polacas ya no eran suficientes y había que encontrar métodos de descifrado más avanzados (para conocer el funcionamiento de la máquina de cifrado Enigma ver La Enigma; para saber la historia de los trabajos polacos ver Los polacos contra la Enigma).

Turing ideó una máquina basada en las "bombas" polacas (de hecho se las siguió llamando "bombas") para probar posiciones de los modificadores automáticamente y buscar la clave de los mensajes cifrados. Cuando hablé de Bletchley Park comenté que los criptoanalistas utilizaban atajos que les adelantaban su trabajo, como los "cillis" y los puntales. La gran novedad del planteamiento de Turing fue su idea de poner a trabajar máquinas en serie para aprovechar los puntales por medio de lo que se conocen como bucles.

¿Qué es un bucle? Para comprenderlo (y para explicarlo) lo mejor es poner un ejemplo. Imaginemos que en un texto cifrado conocemos un puntal, es decir, un fragmento de texto del que sabemos (o suponemos) su significado. Para no liarlo mucho, las letras del texto llano o sin cifrar (las que entran en la máquina) las escribiré en verde, y las del texto cifrado (o las que salen de la máquina) en rojo. Supongamos que el texto cifrado es TSOANLZRK y el texto llano LUFTWAFFE. Es decir:

                           1   2   3    4    5    6   7    8   9

Texto llano          L   U   F   T   W   A   F   F   E

Texto cifrado      T   S   O   A   N    L   Z   R   K

Las letras de 1 serían la entrada y la salida correspondientes a una determinada posición P de los modificadores de la Enigma. Como cada vez que se teclea una letra los modificadores giran una posición, 2 equivaldría a P+1, 3 a P+2, 4 a P+3, y así sucesivamente. A partir de un puntal como este los criptoanalistas tenían un dato con el que empezar a trabajar: se trataría de ir cambiando posiciones de los modificadores hasta encontrar P, la posición en la que al escribir en la entrada LUFTWAFFE tuviésemos a la salida TSOANLZRK. Pero ese no dejaba de ser el comienzo del problema. El número de posiciones posibles seguía siendo de miles de billones.

Y ahora viene el truco: En la posición P (que desconocemos) sabemos que al teclear L tenemos una T a la salida. Pero si nos fijamos, en la letra 4 (o posición P+3) tenemos también una T, pero a la entrada de la máquina de cifrado. Su salida es una A, y a su vez A es la entrada 6 (o P+5). Y por último en la salida de 6 tenemos una L, y resulta que L era la entrada de la primera posición, la P. Ya tenemos el bucle:

                                      L -> T/T -> A/A -> L

El siguiente paso es poner las máquinas trabajando en serie. La primera tendría una posición determinada N de los modificadores. Su salida estaría unida a la entrada de la segunda, con una posición de modificadores N+3. A su vez la salida de esta estaría unida a la tercera, en N+5. Por último la salida de la tercera volvería a unirse a la entrada de la primera. Y a continuación ponemos a trabajar las máquinas sincronizadamente, cambiando todas a la siguiente posición de modificadores al mismo tiempo. Si convertimos el circuito que hemos establecido en un circuito eléctrico, conectándolo a una batería, e intercalamos una lámpara en cualquier punto de él, el circuito sólo se cerraría (y por tanto la lámpara se encendería para avisarnos) cuando al meter una L a la entrada de la primera máquina tuviésemos también una L a la salida de la tercera. Es decir, cuando N sea P, la posición de los modificadores que estamos buscando. Y lo más importante: el bucle nos da sólo la posición de los modificadores, los cambios de letras que hubiese en el clavijero no influyen porque se anulan entre sí. Por ejemplo, si la L está intercambiada en el clavijero por la Z, la L se convertiría en Z a la entrada de los modificadores en la primera máquina, pero en la tercera, como sólo nos valdría la posición que saque una L, ésta sería la que sacase una Z a la entrada del clavijero. Así se eliminan de un plumazo los cien mil millones de combinaciones posibles que introduce el clavijero.

Quedarían por solucionar otros problemas, el primero de ellos precisamente el de deducir los cambios de letras en el clavijero. Pero una vez que se hubiese averiguado la posición de los modificadores los cambios en el clavijero se podían encontrar fácilmente con un simple análisis de frecuencia. Las máquinas conectadas en serie habrían hecho la mayor parte del trabajo. El gran problema de verdad, donde los criptoanalistas tenían que demostrar su habilidad y su intuición, era el de encontrar puntales con los que empezar a trabajar.

Cada bomba estaba formada por doce juegos de modificadores, por lo que podían encargarse de bucles mucho mayores que el de tres letras que puse como ejemplo. Como había 17.576 orientaciones posibles de los modificadores, probando una posición por segundo se tardaría un máximo de cinco horas en probar todas las posiciones posibles.

Foto de una bomba de Bletchley Park:

La primera bomba comenzó a funcionar en marzo de 1940. Sus resultados no fueron todo lo buenos que se podía esperar. En agosto entró en servicio un nuevo modelo mejorado. A partir de ahí lo único que se hizo fue ir aumentando el número de bombas y los resultados fueron cada vez mejores. Al final, los expertos de Bletchley Park podían encontrar la clave de un mensaje cifrado con una máquina Enigma en menos de una hora.

Reproducción moderna de una bomba:

El descifrado de la Enigma fue decisivo en la guerra, pero los criptoanalistas de Bletchley Park tuvieron que mantener en secreto su contribución a la victoria aliada durante décadas, hasta que en los años 70 el gobierno británico levantó el secreto sobre el tema. Algunos no llegaron a recibir en vida el reconocimiento que merecían. Uno de ellos fue Alan Turing. Después de la guerra continuó trabajando en estudios teóricos de cibernética y participó en el desarrollo de algunas de las primeras computadoras de la historia. Pero su carrera se vio truncada de repente en 1952, cuando fue detenido por un delito de indecencia y perversión sexual. Al ir a denunciar un robo cometido en su casa Turing confesó ingenuamente que mantenía una relación homosexual (al parecer su amante había sido cómplice del ladrón). En el juicio Turing se negó a defenderse, como protesta por que la homosexualidad fuese considerada un delito en Inglaterra. Fue declarado culpable y se le dio a escoger entre la castración química o ingresar en prisión. Turing eligió lo primero, y fue sometido a un tratamiento con hormonas que aparte de impotencia le causaron obesidad y otros problemas físicos. La prensa informó ampliamente de su juicio, por lo que su humillación fue además pública. Por si fuera poco, el gobierno británico le retiró todas sus acreditaciones de seguridad, lo que le impidió seguir trabajando en investigaciones sobre computación. El 7 de junio de 1954 Alan Turing se suicidó con una manzana mojada en cianuro, una idea que había tomado de su película favorita, Blancanieves y los siete enanitos.

¿Qué habría pasado si el Ejército hubiese conocido su homosexualidad cuando Turing trabajaba en el CG&CS? Jack Goods, un criptoanalista compañero suyo en Bletchley Park, comentó: “Afortunadamente las autoridades no sabían que Turing era homosexual. Si no, podríamos haber perdido la guerra”. En septiembre del 2009 el primer ministro británico Gordon Brown emitió un comunicado en el que pedía disculpas públicamente en nombre de su gobierno por el trato que había recibido Alan Turing en los últimos años de su vida.

Fuentes: 

Simon Singh: Los códigos secretos

www.bletchleypark.org.uk

http://es.wikipedia.org/wiki/Alan_Turing

http://www.mathcomp.leeds.ac.uk/turing2012/