martes, 26 de mayo de 2015

"The Imitation Game" - Descifrando Enigma (I)

Todavía no he visto la película "The Imitation Game" (en castellano su título es "Descifrando Enigma"), pero tengo muchas ganas de verla (creo que aquí se ha estrenado a principios de este año).

Estoy leyendo críticas y comentarios sobre ella que me hacen, aún más, querer verla.

Sobre la película, en sí misma, evidentemente no puedo hablar (mi opinión) hasta verla, aunque parece ser que todos coinciden en la interpretación magistral de Benedict Cumberbatch como Alan Turing.

Sin embargo, por lo que voy leyendo sobre esta película, parece ser que no se ajusta mucho a la realidad de los hechos, ya que se le atribuye casi en exclusiva a Alan Turing el haber conseguido "romper" el código de la máquina Enigma (sin ninguna duda una mente prodigiosa con una contribución decisiva a este asunto y, además y entre otras cuestiones, a la inteligencia artificial), obviando la previa y no menos decisiva contribución polaca para ello y sin la que Turing hubiera tenido que partir de cero.
Como digo, previamente al excelente trabajo realizado por Alan Turing y sus colaboradores (tampoco hay que olvidarse de ellos, ya que fueron muchos), los matemáticos polacos del Biuro Szyfrów (Oficina polaca de Cifrado del Estado Mayor) consiguieron deducir el secreto del cableado interno de la máquina y lograron"romper" su código. Todo ello con unos medios muchísimo más escasos, tanto humanos como materiales, de los que dispuso Alan Turing, basándose única y exclusivamente en su genio matemático y cuyo trabajo de criptoanálisis fue revelado a los británicos en 1939, justo antes del inicio de la II Guerra Mundial.

Por tanto, además de que con esta película (producción británica) de alguna forma se salda una deuda histórica con un genio como Alan Turing (fue condenado por homosexual, parece ser que se suicidó por ello y ha tenido que "esperar" a un "perdón" póstumo real por la reina Isabel II en el centenario de su nacimiento, en 2013. ¡Sin comentarios!) no creo que deberíamos olvidarnos en este caso de la contribución polaca a la lucha contra el Nazismo; desentrañar el cifrado de las comunicaciones del ejército alemán fue de vital importancia para acortar la guerra y salvar cientos de miles de vidas

En otro post, cuando vea la película, contaré mis impresiones sobre la misma (si me ha gustado, si creo que refleja bien la historia de la máquina de cifrado más famosa del siglo XX,...) y, además, otras curiosidades (destino de sus protagonistas, etc.).

lunes, 25 de mayo de 2015

La pequeña historia de la máquina Enigma (I)

En paralelo con la serie de posts en los que comparto lo que voy aprendiendo sobre el funcionamiento de la máquina Enigma utilizada por el ejército alemán durante la II Guerra Mundial y su criptoanálisis por parte de los aliados, en éste comienzo a poner en su contexto histórico los hechos que se cuentan en dicha serie.

En este primer post se muestra, de forma muy resumida, la cronología de los hechos más relevantes de la máquina Enigma con relación a los sucesos de la convulsa historia europea de la época, desde la patente de la versión comercial de la máquina hasta el inicio de la II Guerra Mundial.


En un post posterior completaré esta cronología con los sucesos acaecidos en la II Guerra Mundial y tras su finalización con relación a la máquina de cifrado más famosa del siglo XX.

viernes, 22 de mayo de 2015

Criptografía X: la máquina Enigma (IX)

Decía en el post anterior que, como en el simulador que incluí en él no se aprecia la operativa en la práctica (cómo se iban apilando las hojas apropiadas), me propongo poner en este post un ejemplo para ver si he comprendido correctamente el método de las hojas Zygakski.

Pues bien, consideremos que entre los mensajes interceptados nos encontramos con que nueve de ellos presentan las siguientes "hembras" en las posiciones 1-4 ("1,4-female" en la terminología que ellos acuñaron):

1.- PTJ XZI XPG; 2.- CEH CMS CID; 3.- BUG RCJ RVU; 4.- EON NSF NLG; 5.- XLV IEJ IRU;
6.- BWY SXN SBU; 7.- AGY WDH WWT; 8.- KGS OXT OXU; 9.- CWI UBG UHS.
Nota: los tres primeros caracteres se corresponden con el indicador (los tres caracteres que se transmitían en claro y que el operador había elegido para cifrar la "clave de sesión") y los seis siguientes con los caracteres correspondientes al doble cifrado de ésta.

1º) Lo primero que debemos hacer es establecer una hipótesis de partida (a probar) para el orden de los rotores y fijar un carácter para el ajuste del anillo del rotor lento. En nuestro caso elegimos "I-III-II" y la letra "Q".

2º) Seleccionamos como primera hoja la rotulada con la letra "B" correspondiente al orden de los rotores elegido para probar ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "P" (primera letra del primer indicador) = "B", y la ponemos sobre una mesa iluminada por debajo:

Como se observa en la figura anterior, la luz de la mesa iluminada por debajo atraviesa 326 cuadrados perforados.

3º) A continuación seleccionamos la hoja  rotulada con la letra "O" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "C" (primera letra del segundo indicador) = "O", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "O") coincidan en las coordenadas "PC" de la anterior (hoja "B"), ya que "T" (segunda letra del primer indicador) - "E" (segunda letra del segundo indicador) = "P" y "J" (tercera letra del primer indicador) - "H" (tercera letra del segundo indicador) = "C":

Como se observa en la figura anterior, ahora la luz atraviesa sólo 148 cuadrados perforados, frente a los 326 que atravesaba antes.

4º) Continuamos con la hoja  rotulada con la letra "P" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "B" (primera letra del tercer indicador) = "P", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "P") coincidan en las coordenadas "ZD" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "U" (segunda letra del tercer indicador) = "Z" y "J" (tercera letra del primer indicador) - "G" (tercera letra del tercer indicador) = "D":

Tal y como se ve en la figura anterior, ahora la luz atraviesa sólo 56 cuadrados perforados, frente a los 148 que atravesaba antes.

5º) Seguimos con la hoja  rotulada con la letra "M" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "E" (primera letra del cuarto indicador) = "M", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "M") coincidan en las coordenadas "FW" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "O" (segunda letra del cuarto indicador) = "F" y "J" (tercera letra del primer indicador) - "N" (tercera letra del cuarto indicador) = "W":

Ahora la luz atraviesa sólo 26 cuadrados perforados, frente a los 56 que atravesaba antes.

6º) Seleccionamos la hoja  rotulada con la letra "T" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "X" (primera letra del quinto indicador) = "T", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "T") coincidan en las coordenadas "IO" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "L" (segunda letra del quinto indicador) = "I" y "J" (tercera letra del primer indicador) - "V" (tercera letra del quinto indicador) = "O":

Tal y como vemos, la luz atraviesa sólo 14 cuadrados perforados, frente a los 26 que atravesaba antes.

7º) Elegimos ahora la hoja  rotulada con la letra "P" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "B" (primera letra del sexto indicador) = "P", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "P") coincidan en las coordenadas "XL" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "W" (segunda letra del sexto indicador) = "X" y "J" (tercera letra del primer indicador) - "Y" (tercera letra del sexto indicador) = "L":

Observamos que la luz atraviesa ahora sólo 6 cuadrados perforados, frente a los 14 que atravesaba antes.

8º) Continuamos ahora con la hoja  rotulada con la letra "Q" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "A" (primera letra del séptimo indicador) = "Q", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "Q") coincidan en las coordenadas "NL" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "G" (segunda letra del séptimo indicador) = "N" y "J" (tercera letra del primer indicador) - "Y" (tercera letra del séptimo indicador) = "L":

La luz atraviesa ahora sólo 4 cuadrados perforados, frente a los 6 que atravesaba antes.

9º) Seguimos con la hoja  rotulada con la letra "G" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "K" (primera letra del octavo indicador) = "G", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "G") coincidan en las coordenadas "NR" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "G" (segunda letra del octavo indicador) = "N" y "J" (tercera letra del primer indicador) - "S" (tercera letra del octavo indicador) = "R":

La luz únicamente atraviesa ya 2 cuadrados perforados, frente a los 4 que atravesaba antes.

10º) Y, finalmente, terminamos con la hoja  rotulada con la letra "O" correspondiente al mismo orden de los rotores ("I-III-II"), ya que "Q" (letra fijada para el ajuste del anillo del rotor lento) - "C" (primera letra del noveno indicador) = "O", y la ponemos sobre la anterior de tal manera que las coordenadas "AA" de la nueva hoja (hoja "O") coincidan en las coordenadas "XB" de la primera hoja (hoja "B"), ya que "T" (segunda letra del primer indicador) - "W" (segunda letra del noveno indicador) = "X" y "J" (tercera letra del primer indicador) - "I" (tercera letra del noveno indicador) = "B":

Como se observa la luz atraviesa ya un único cuadrado perforado, el de coordenadas "JD", lo que ya identifica de forma unívoca el orden de los rotores y el ajuste de lo anillos de la clave del día.

El orden de los rotores y el ajuste del anillo del rotor lento se obtienen directamente, es decir, serían "I-III-II" y "Q", respectivamente, mientras que el ajuste del anillo del rotor central se obtiene mediante la diferencia entre el segundo carácter del primer indicador ("T") y la coordenada correspondiente al rotor central del cuadrado perforado ("J") y  el ajuste del anillo del rotor rápido se obtiene mediante la diferencia entre el tercer carácter del primer indicador ("J") y la coordenada correspondiente al rotor rápido del cuadrado perforado ("D"); dando como resultado "J" y "F", respectivamente.

Por tanto, la clave del día contendría los siguientes valores:

Orden de los rotores: "I-III-II".
Ajuste de los anillos: "Q-J-F".

Lo que coincide con el resultado obtenido con el simulador que incluí en el post anterior, aunque en éste he puesto un ejemplo de la operativa que no se aprecia en dicho simulador para comprobar que lo he entendido correctamente. Creo que sí, si no es así y como siempre, por favor, que algún amable lector de este humilde blog me saque del error.

Para finalizar decir que en posteriores posts compartiré  lo que voy aprendiendo sobre cómo continuó esta apasionante historia, al menos para mí, de la máquina Enigma utilizada por el ejército alemán durante la II Guerra Mundial.

martes, 19 de mayo de 2015

Criptografía (IX): la máquina Enigma (VIII)

Tras la modificación realizada en 1938 por los alemanes al procedimiento de operación de la máquina Enigma (ver post anterior) y que invalidó el método de criptoanálisis utilizado hasta ese momento, lejos de desanimarse y "tirar la toalla", los polacos se pusieron inmediatamente a trabajar en nuevas ideas para volver a conseguir descifrar de forma masiva los mensajes del ejército alemán.

Los alemanes, pese al cambio introducido en la operativa de la máquina, seguían transmitiendo dos veces de forma consecutiva los caracteres cifrados de la "clave de sesión" (posición de los rotores elegida por el operador para cifrar cada mensaje concreto) y cualquier repetición es un verdadero filón para los criptoanalistas. Ese fue el "clavo ardiendo" que necesitaban y al que se agarraron para idear nuevos métodos para "romper" su código.

Es decir, ahora no era posible, en base a la característica de los mensajes interceptados en un día y a través del catálogo, deducir cuáles eran el orden de los rotores y su posición inicial, pero seguía existiendo la relación entre el primero y cuarto caracteres, el segundo y quinto, y el tercero y sexto de los seis caracteres correspondientes al doble cifrado de la "clave de sesión".

Así, estudiando las características diarias observaron que frecuentemente aparecían en las tres permutaciones (AD, BE y CF) ciclos de longitud 1 en los caracteres correspondientes a ese doble cifrado de la "clave de sesión", o, lo que es lo mismo, se daba una "curiosa" repetición de dichos caracteres. Otra repetición más y, por tanto y como ya he dicho, otro filón a explotar por parte de los criptoanalistas.

Para mí esto no pasaría de ser una curiosidad que perfectamente se podía producir por mera casualidad, pero a ellos les llevó a preguntarse si a partir de esto era posible deducir el orden de los rotores y el ajuste de los anillos o posición relativa de los mismos respecto a su núcleo con el cableado, que como sabemos formaban parte de la clave del día. La respuesta era sí.

Pero, aclaremos un poco más esto. Supongamos que en uno de los mensajes interceptados los seis caracteres correspondientes al doble cifrado de la "clave de sesión" son "SWO SJQ". Ellos acuñaron el término "hembra" (en inglés "female") para referirse a las repeticiones de caracteres que se producían y, en este caso, decían que había una "hembra" en las posiciones 1-4 (el carácter "S" se repite en ambas). Si esto ocurría en las posiciones 2-5 y 3-6, para cualquier carácter, entonces se habían encontrado también "hembras" en las respectivas posiciones.

Uno de los que inventó un método para descifrar nuevamente los mensajes alemanes, basado en esta repetición de caracteres ("hembras"), fue otro matemático polaco llamado Henryk Zygalski.

Su método consistía en la utilización de hojas perforadas, conocidas como hojas Zygalski, de tal manera que cada hoja se correspondía con un carácter del rotor lento para un orden dado de alojamiento de los rotores en las ranuras. Es decir, para cada posible orden de ubicación de estos había 26 hojas (una por cada carácter del rotor lento) y, por tanto, en total había: número de posibles órdenes de los rotores en las ranuras x número de hojas por orden de alojamiento de los rotores = 3! x 26 = 6 x 26 = 156 hojas.

A continuación comparto lo que he aprendido sobre la preparación y la forma de utilización de estas hojas, aunque puedo estar equivocado (si es así, por favor, que algún amable lector de este blog me saque del error).

En cada hoja había una tabla en la que las filas (de arriba a abajo) representaban las posiciones (caracteres) correspondientes al rotor central y las columnas (de izquierda a derecha) las posiciones (caracteres) del rotor rápido.

Tal y como se muestra en la figura y por la operativa de funcionamiento de este método, esta tabla se duplicaba en horizontal (columnas de la "A" a la "Y") y en vertical (filas de la "A" a la "Y"), por lo que cada hoja disponía en la intersección de todas sus filas y columnas de un total de 51 x 51 =  2.601 cuadrados, que podían ser perforados.

A partir del catálogo de características, para cada ciclo de longitud 1 en las posiciones 1-4 se perforaba, en la hoja correspondiente a la ubicación de los rotores en las ranuras y al carácter del rotor lento de esa "hembra", el cuadrado de la tabla superior izquierda que se encontraba en la intersección de la fila del carácter del rotor central y la columna de la letra del rotor rápido, y como esa tabla estaba duplicaba en horizontal y vertical se perforaba también ese mismo cuadrado en el resto de las tablas de la hoja.

Una vez preparadas todas las hojas y a partir de los indicadores (los tres caracteres que se transmitían en claro y que el operador había elegido para cifrar la "clave de sesión") de aquellos mensajes interceptados que presentaban "hembras" en los caracteres correspondientes al doble cifrado de la "clave de sesión", se iban apilando las hojas adecuadas siguiendo un método predeterminado hasta que todas ellas coincidían en un solo cuadrado perforado, lo que identificaba unívocamente el orden de los rotores y el ajuste de los anillos o posición relativa de los mismos respecto a su núcleo con el cableado.

Lo primero que había que hacer era tomar como hipótesis de partida (a probar) un orden de los rotores y fijar un carácter para el ajuste del anillo del rotor lento, para después ir apilando una hoja sobre otra con un cierto desplazamiento, que se calculaba mediante la diferencia entre la segunda letra del primer indicador y la segunda letra del nuevo indicador (coordenada del desplazamiento correspondiente al rotor central, es decir, de la fila) y la tercera letra del primer indicador y la tercera letra del nuevo indicador (coordenada del desplazamiento correspondiente al rotor rápido, es decir, de la columna). Por tanto, había que superponer la parte superior izquierda de la nueva hoja (correspondiente a las coordenadas "AA") encima de las coordenadas de la primera hoja así calculadas.

Con el suficiente número de mensajes interceptados con "hembras", tengo entendido que habitualmente unos doce eran suficientes, si tras apilar todas las hojas éstas no coincidían en un único o varios cuadrados perforados la hipótesis de partida se revelaba como falsa y había que probar con otra, mientras que si coincidían en uno o varios cuadrados perforados esto daba una o varias posibles soluciones para el orden de los rotores y el ajuste de los anillos para ese día (el orden de los rotores y el ajuste del anillo del rotor lento se obtenían directamente, mientras que el ajuste de los anillos del rotor central y rápido se calculaba mediante la diferencia entre el segundo carácter del primer indicador y la coordenada correspondiente al rotor central del cuadrado perforado, y la diferencia entre el tercer carácter del primer indicador y la coordenada del rotor rápido de ese mismo cuadrado, respectivamente). Estas posibles soluciones eran probadas en un réplica de la máquina Enigma.

Una vez obtenidos el orden de los rotores y el ajuste de los anillos no era difícil averiguar las conexiones realizadas en el tablero y obtener la clave del día, con lo que ya era posible otra vez descifrar masivamente los mensajes del ejército alemán.

En los siguientes enlaces se puede ver una simulación del método de las hojas Zygalski y se explican los cálculos realizados, respectivamente:

- Simulación del método de las hojas Zygalski.
- Explicación de los cálculos realizados.

No obstante, para ver si lo he comprendido correctamente y ya que en el simulador anterior no se aprecia la operativa del método en la práctica, en el siguiente post me propongo poner un ejemplo apilando las hojas correspondientes para ver si obtengo el resultado correcto.

Para finalizar este post decir que los polacos inventaron otros métodos para "romper" el código de la máquina Enigma, aunque todos ellos duraron poco tiempo, ya que los alemanes, muy poco antes del inicio de la II Guerra Mundial, continuaron introduciendo nuevas novedades en la máquina y en su operativa para intentar hacer al sistema invulnerable a los métodos de criptoanálisis. De todo ello hablaré en siguientes posts de esta serie.