martes, 7 de abril de 2015

Criptografía (VII): la máquina Enigma (VI)

En el post anterior conté brevemente cómo Rejewski y su colegas consiguieron deducir el cableado de los rotores y del reflector de la máquina Enigma utilizada por el ejército alemán en la II Guerra Mundial y en éste trataré sobre cómo lograron hacerse con la clave del día para descifrar los mensajes.

Con las réplicas de la máquina Enigma que fue posible construir tras la deducción del cableado de los rotores y del reflector sólo era posible descifrar los mensajes si caían en sus manos las claves del día con las que habían sido cifrados, ya que probar el número astronómico de posibles claves quedaba fuera de la capacidad humana (en esa época no había ordenadores).

Así que Rejewski y sus colegas se propusieron idear un método para obtener las claves del día a partir de esa gran debilidad de operación de la máquina que era la repetición dos veces de forma consecutiva de la "clave de sesión" al inicio de cada mensaje y que tan buenos resultados les había dado anteriormente.

¿Cómo lo hicieron?. Pues, otra vez, demostrando ser unos genios al deducir un sistema para reducir de forma muy significativa el número de posibles claves a probar para que esta tarea quedara ya dentro de lo humanamente posible en aquella época, es decir, al establecer un elegante método que combinaba su genio matemático con la fuerza bruta necesaria para rematar esta tarea.

El método que establecieron se basaba en las permutaciones del primer y cuarto caracteres (AD), del segundo y quinto (BE) y del tercero y sexto (CF), comentadas en el post anterior, que se producían al teclear dos veces de forma consecutiva las letras que indicaban la posición inicial de lo rotores que el operador había elegido para cifrar un mensaje concreto ("clave de sesión") y que como sabemos a lo largo de un mismo día se cifraban siempre con la misma clave (clave del día).

En el ejemplo de mensajes interceptados que puse en el post anterior obtuvimos que la permutación AD podía expresarse ordenada por la longitud de sus ciclos de la siguiente manera:

AD = (JNVU)(RYSZ)(ACIKETMLX)(BGPDOFWHQ).

Es decir, si en el mensaje interceptado el primer carácter es "J" el cuarto es siempre "N", si el primer carácter es "N" el cuarto es "V", si el primer carácter es "V" el cuarto es "U", y así sucesivamente.

Supongamos ahora que en el tablero de conexiones se conectan las correspondientes letras que hacen que con la clave del día la letra que se cifra como "B" pase a cifrarse como "E" y viceversa, y la que se cifra como "W" pase a cifrarse como "Z" y al contrario. Por tanto, los seis primeros caracteres del primer mensaje interceptado de nuestro ejemplo (ver post anterior), que son "BDZ GOW", pasarían a ser ahora "EDW GOZ" y, por consiguiente, la permutación AD sería ahora:

AD = (JNVU)(RYSW)(ACIKBTMLX)(EGPDOFZHQ).

Es decir, las letras conectadas en el tablero de conexiones sólo afectan a que cambian ciertas letras en algunos ciclos de la permutación, pero no a su estructura (número de ciclos y longitud o número de elementos de los mismos), por lo que ésta es una característica del cifrado de la máquina Enigma que es reflejo de la ubicación de los rotores en las ranuras que los alojan y de su posición inicial (parte de la clave del día), con independencia de las conexiones que se establezcan en el tablero.

Y, en este punto, yo me pregunto: ¿Y... eso es bueno o malo?. Pues bien, para ellos obtener esta conclusión fue muy importante; a partir de esta característica podían reducir de forma muy considerable el número de posibilidades a probar para obtener el orden y posición inicial de los rotores de la clave del día. Como sabemos, este número de posibilidades era todavía muy elevado (26 x 26 x 26 x 6 = 105.456), pero dejaba ya abierta la puerta al empleo de la fuerza bruta.

Pero, ¿cómo?. Sigamos con nuestro ejemplo. A partir de las tres permutaciones AD, BE y CF obtenidas en el post anterior:

AD = (JNVU)(RYSZ)(ACIKETMLX)(BGPDOFWHQ);
BE = (AI)(DO)(BPMZX)(HJSTY)(CEUKGQ)(FVLRNW);
CF = (CNK)(EMO)(AGLY)(BIZW)(DHRSUQ)(FPXTJV),

podemos establecer una notación para expresar la longitud o número de elementos de cada uno de sus ciclos, de la siguiente manera:

AD -> (4 4 9 9).
BE -> (2 2 5 5 6 6).
CF -> (3 3 4 4 6 6).

Por lo que podemos expresar las longitudes de los ciclos de las tres permutaciones como:

(4 4 9 9)(2 2 5 5 6 6)(3 3 4 4 6 6).

Además, Rejewski observó que, aunque el número de ciclos y sus longitudes cambiaban cada día, en cada permutación los ciclos de la misma longitud aparecían siempre por parejas.

El siguiente paso consistió en crear un catálogo con esta información (características). Así comenzó el ataque de fuerza bruta.

Sin duda un ardua y tediosa tarea que comenzaron a realizar con las réplicas de la máquina Enigma que fue posible fabricar gracias a la labor anterior realizada por Rejewski. Había que poner los rotores en un orden concreto (encajarlos en sus correspondientes ranuras), girarlos hasta una posición inicial concreta, teclear dos veces de forma consecutiva los tres caracteres de una de las posibles "claves de sesión" (desde la "AAA" hasta la "ZZZ") y calcular el número de ciclos y la longitud de los mismos que le correspondían... y repetir esto "sólo" 105.455 veces más.

Un trabajo que podía llevar muchísimo tiempo, por lo que pronto se dieron cuenta de que, si no querían tardar una eternidad en elaborar el catálogo, tenían que simplificar esta tarea de alguna manera. Para ello, diseñaron y fabricaron una máquina que llamaron ciclómetro.

Básicamente, el ciclómetro constaba de 2 juegos de rotores y, además, de 26 lámparas y 26 interruptores correspondientes a las 26 letras del alfabeto.

Ambos juegos de rotores estaban conectados, con la particularidad de que el rotor rápido del segundo juego (N2se sincronizaba automáticamente ajustándose 3 posiciones con respecto al rotor rápido del primero (N1).

De esta forma se simulaba el efecto de cifrar una letra, con una ubicación determinada de los rotores en las ranuras y con una posición inicial concreta de los mismos, como si ésta se hubiera pulsado en primera posición en una máquina Enigma y de cifrar esa misma letra como si se hubiera pulsado después en cuarta posición, pero esto se conseguía accionando sólo el interruptor correspondiente a esa letra (con una réplica de la máquina Enigma se hubiera tenido que pulsar esa tecla en primera posición, dos teclas más y esa misma tecla en cuarta posición). Además, los circuitos del ciclómetro permitían obtener de forma sencilla la longitud de los ciclos que le correspondían a la posible "clave de sesión" que se había probado.

Cuando se accionaba el interruptor correspondiente a la primera letra de una de las posibles "clave de sesión" se iluminaba la lámpara correspondiente a dicha letra y, además, las de aquellas que pertenecían al mismo ciclo y a otro ciclo de la misma longitud de la permutación AD (recordar que los ciclos de la misma longitud siempre ocurren a pares).

El número de lámparas que se iluminaban al accionar un interruptor era siempre el doble del número de letras en los ciclos de la permutación AD. Por ejemplo, si se encendían 8 lámparas se deducía que la permutación AD tenía, al menos, 2 ciclos de longitud 4.

Para deducir la longitud del resto de ciclos de la permutación AD bastaba con accionar el interruptor correspondiente a una de las letras que no se habían iluminado y, por ejemplo, si se iluminaban las lámparas correspondientes a 18 letras se obtenía que la permutación AD tenía, además, 2 ciclos de longitud 9. En este ejemplo ya se habrían encendido todas las lámparas, por lo que las longitudes de los ciclos de la permutación AD se podían expresar como (4 4 9 9).

Posteriormente, se actuaba de la misma manera para la permutación BE (accionado el interruptor correspondiente a la segunda letra de la "clave de sesión" que se estaba analizando) y después para CF (tercera letra de esa "clave de sesión"), con lo que, por ejemplo, podía obtenerse la siguiente característica para el conjunto de las tres permutaciones: (4 4 9 9) (2 2 5 5 6 6)(3 3 4 4 6 6).   

Pero veamos un ejemplo gráfico



Después de hacer esto se anotaba la característica en una tarjeta y se ordenaban éstas de una manera específica para facilitar su consulta.

El catálogo estaba compuesto por:

- 6 ubicaciones posibles de los rotores en las ranuras (3! = 3 x 2 x 1 = 6).
- Dentro de cada una de las anteriores se incluían las características, es decir, 263 = 17.576 entradas; una para cada una de las posibles "claves de sesión" con esa ubicación concreta de los rotores en las ranuras.

De esta forma el catálogo contenía un total de 6 x 17.576 = 105.456 entradas.

Ejemplo (los dos primeros dígitos indican el número de ciclos, los siguientes la longitud de cada uno de ellos y los tres últimos caracteres la posición inicial de los rotores):

- I, II, III:
   16 02 02 03 03 04 04 04 04 05 05 06 06 06 06 09 09 ... AAA.
   ................................................................................................ AAB.
   ...
   ................................................................................................ ZZZ.
- I, III, II:
   ................................................................................................ AAA.
   ................................................................................................ AAB.
   ...
   ................................................................................................ ZZZ.  
- ...

El catálogo se ordenaba, dentro de cada ubicación posible de los rotores en las ranuras, por número de ciclos y longitud de los mismos.


Una vez de que se completó el catálogo era posible descifrar ya los mensajes de cada día, para lo que se actuaba de la siguiente manera:

1º) A partir de los mensajes interceptados se obtenía la característica conjunta de las permutaciones AD, BE y CF (número de ciclos y longitud de los mismos en cada una de ellas).

2º) Se acudía al catálogo para localizar esa característica (lamentablemente, en ocasiones esa característica correspondía a varias entradas del catálogo, pero se reducían enormemente las posibilidades a probar).

3º) Si había habido suerte y esa característica sólo figuraba en una entrada del catálogo ya se disponía de la ubicación inicial de los rotores en sus ranuras y de la posición inicial de los mismos, mientras que si figuraba en varias entradas había que probar los mensajes interceptados en una réplica de la máquina Enigma con cada una de las posibles configuraciones iniciales que correspondían a dichas entradas (como digo muchísimas menos y, por tanto, algo perfectamente posible de hacer en poco tiempo) hasta que apareciera un texto en claro más o menos coherente.


Y digo "más o menos coherente" porque aún faltaba saber las conexiones establecidas en el tablero para intercambiar letras, pero esto no era mayor problema, ya que si en el texto en claro había palabras predecibles resultaban evidentes las letras que se habían intercambiado (conectado a pares en el tablero de conexiones). Por ejemplo: si al descifrar un parte metereológico aparecía en el texto en claro "TEWWER", los criptoanálistas podían deducir fácilmente que se habían intercambiado los caracteres "W" y "T" de la palabra "WETTER" (tiempo en alemán), y así con muchas otras palabras predecibles.

¿Esto fue todo?. Pues me temo que no (como dije en un post anterior de esta serie, se trató de un proceso muy complejo y también muy largo), ya que los alemanes a medida que se acercaba el inicio de la II Guerra Mundial introdujeron cambios, tanto en las características de la máquina Enigma como en su operativa, que dificultaban la obtención de la clave del día mediante este método, y más tarde la imposibilitaron. Pero éste será un asunto a tratar en posteriores posts.

No hay comentarios:

Publicar un comentario