La máquina que perdió una guerra

Tras la Primera Guerra Mundial, los cifradores eran el cuello de botella de todos los ejércitos: cifrar a mano era lento y propenso a errores, y los cifrados lo bastante sencillos para usarlos bajo el fuego se podían romper. Varios inventores tuvieron la misma idea a la vez: cablear la sustitución dentro de un disco giratorio y dejar que la máquina cambiara de sustitución tras cada letra. Edward Hebern en Estados Unidos, Hugo Koch en los Países Bajos, Arvid Damm en Suecia y Arthur Scherbius en Alemania, que patentó su máquina en 1918 y la vendió con el nombre de Enigma a partir de 1923. La marina alemana la adoptó en 1926, el ejército de tierra en 1928 y la aviación después; en 1945 había decenas de miles en servicio.

§Cómo funciona Enigma

Al pulsar una tecla se cierra un circuito eléctrico que termina en una de 26 lámparas. Por el camino, la corriente atraviesa:

1. el clavijero (Steckerbrett), donde unos cables intercambian parejas de letras (diez parejas, por reglamento);
2. tres rotores, elegidos entre cinco y colocados en cualquier orden; cada rotor es un cableado fijo y revuelto de 26 contactos de una cara a 26 de la otra, y su anillo desplaza el cableado respecto a las letras del borde;
3. el reflector (Umkehrwalze), que conecta las letras por parejas y devuelve la corriente a través de los tres rotores por otro camino;
4. otra vez el clavijero, y una lámpara.

Antes de que pase la corriente, el rotor de la derecha avanza un paso. Cuando pasa por su muesca arrastra también al rotor central; cuando el central llega a su propia muesca, arrastra al de la izquierda y a sí mismo en la siguiente pulsación: el famoso doble paso. Como los rotores se mueven, la misma letra se cifra de forma distinta cada vez, y la sustitución solo se repite tras $26\times 25\times 26=16900$ letras.

§Un retrato matemático

Cada pulsación aplica una permutación de las 26 letras. Llamemos $P$ al clavijero, $R_1,R_2,R_3$ a los tres rotores en su posición actual (derecha, centro, izquierda) y $U$ al reflector. La corriente pasa por $P$, $R_1$, $R_2$, $R_3$, $U$ y vuelve, así que la permutación es

Demostración

Sea $S=R_3{R}_2{R}_{1}P$, de modo que $E=S^{-1}US$. El reflector empareja letras, así que $U^2=\mathrm{id}$ y $U(y)\ne y$ para toda $y$. Entonces $E^2=S^{-1}US{S}^{-1}US=S^{-1}{U}^{2}S=\mathrm{id}$. Y si $E(x)=x$, entonces $U(S(x))=S(x)$, un punto fijo de $U$, que no existe.

La simetría era una comodidad: la misma máquina, con la misma configuración, cifraba y descifraba. La ausencia de puntos fijos fue un regalo para el enemigo, como muestra el ataque del crib más abajo.

Contar el clavijero

Hay que elegir qué 20 letras se conectan y cómo se emparejan, dejando 6 sueltas. Pongamos las 26 letras en cualquier orden ($26!$ formas), conectemos las 20 primeras por parejas consecutivas y dejemos sueltas las 6 últimas. Cada cableado se cuenta $6!$ veces (orden de las letras sueltas) $\times 10!$ (orden de las parejas) $\times 2^{10}$ (orden dentro de cada pareja).

Casi todo ese número viene del clavijero. La genialidad de Rejewski fue encontrar una magnitud que el clavijero no cambia.

§Rejewski: un teorema rompe Enigma

En 1932 la Oficina de Cifrado polaca encargó el problema a Marian Rejewski, un matemático de 27 años de Poznań, y después a Jerzy Różycki y Henryk Zygalski. El procedimiento alemán les ayudó: cada mensaje empezaba con una clave de mensaje de tres letras, elegida por el operador, cifrada dos veces con la configuración del día («para asegurarse de que llega»). Así, las letras 1 y 4 de cada mensaje eran cifrados de la misma letra, igual que la 2 y la 5, y la 3 y la 6. Llamando $A,B,\dots ,F$ a las permutaciones de las seis primeras posiciones, los mensajes del día revelaban los productos $AD$, $BE$ y $CF$ (si $A(x)=y$ y $D(x)=z$, entonces $AD$ lleva $y$ a $z$, porque $A$ es una involución).

Demostración

Si $(x_1{x}_2\dots x_k)$ es un ciclo de $\sigma$, entonces $({\pi }^{-1}(x_1)\dots {\pi }^{-1}(x_k))$ es un ciclo de ${\pi }^{-1}\sigma \pi$: en efecto, ${\pi }^{-1}\sigma \pi ({\pi }^{-1}(x_i))={\pi }^{-1}(\sigma (x_i))={\pi }^{-1}(x_{i+1})$. Renombrar las letras con ${\pi }^{-1}$ lleva ciclos a ciclos de la misma longitud.

El clavijero solo entra en $AD$ por conjugación, así que la estructura de ciclos de $AD$, $BE$ y $CF$ depende solo del orden y la posición de los rotores: $6\times 17576=105456$ posibilidades, un número lo bastante pequeño para catalogarlo. Los polacos construyeron una máquina, el ciclómetro, para calcular el catálogo, y desde 1933 leyeron el tráfico alemán con regularidad. Rejewski había reconstruido además el cableado de los rotores con la teoría de permutaciones, ayudado por manuales de uso y claves antiguas que un empleado alemán, Hans-Thilo Schmidt, vendió al espionaje francés (Gustave Bertrand).

Los alemanes cambiaron los procedimientos y añadieron dos rotores en 1938, lo que multiplicaba el trabajo por diez. El 25 de julio de 1939, cinco semanas antes de la invasión de Polonia, los polacos se reunieron con sus aliados británicos y franceses en el bosque de Pyry, cerca de Varsovia, y se lo dieron todo: sus métodos, las hojas perforadas de Zygalski y dos réplicas de la Enigma.

§Bletchley Park y el crib

En Bletchley Park, el centro británico de descifrado, Alan Turing diseñó una máquina nueva, la bomba (1940), mejorada con el tablero diagonal de Gordon Welchman. No necesitaba la clave de mensaje duplicada, que los alemanes abandonaron en mayo de 1940. Necesitaba un crib: una conjetura sobre parte del texto en claro y su posición. Los mensajes militares estaban llenos de ellos: WETTERBERICHT (parte meteorológico), KEINE BESONDEREN EREIGNISSE (sin novedad), indicativos, grados, el mismo saludo cada mañana.

El teorema anterior dice dónde puede ir un crib: como ninguna letra se cifra en sí misma, cualquier posición en la que una letra del crib coincida con la letra del texto cifrado que tiene debajo es imposible. Deslizar el crib por el texto cifrado elimina de golpe la mayoría de las posiciones; para cada superviviente, la bomba probaba todos los órdenes y posiciones de los rotores contra la cadena de parejas de letras que el crib implicaba.

La Enigma naval, con cuatro rotores desde 1942 y procedimientos más estrictos, resistió más; Joan Clarke, Turing y Hugh Alexander la atacaron con el Banburismus, un método estadístico, y con libros de claves capturados a submarinos y barcos meteorológicos (el U-110 en mayo de 1941, el U-559 en octubre de 1942). La información, con el nombre clave Ultra, se distribuía con un cuidado extremo para que los alemanes no sospecharan. Los historiadores calculan que acortó la guerra en Europa hasta dos años.

No solo Enigma. El alto mando alemán usaba otra máquina, el cifrado de teletipo Lorenz SZ40/42. Bill Tutte reconstruyó su lógica en 1942 sin haber visto nunca una, y Tommy Flowers construyó Colossus (1944) para atacarlo: el primer ordenador digital electrónico programable.

§Por qué cayó Enigma

• Un defecto estructural: ninguna letra se cifra en sí misma, lo que convierte cada crib en un filtro.
• Procedimientos que repiten información: la clave de mensaje duplicada dio a Rejewski sus ecuaciones.
• Texto en claro previsible: partes meteorológicos, saludos de fórmula, «sin novedad».
• Atajos humanos: los operadores elegían claves de mensaje como AAA o las iniciales de su novia (los «cillies»).
• Exceso de confianza: un espacio de claves de $2^{67}$ parecía irrompible, y los alemanes nunca consideraron en serio que se estuviera leyendo la máquina.

Todas estas lecciones reaparecen en la criptografía moderna. El capítulo siguiente plantea la pregunta opuesta: ¿existe un cifrado que no se pueda romper en absoluto?

§Para saber más

1. Marian Rejewski, «How Polish mathematicians deciphered the Enigma», Annals of the History of Computing 3(3), 1981.
2. Gordon Welchman, The Hut Six Story (1982).
3. Andrew Hodges, Alan Turing: The Enigma (1983; en español, Alan Turing: el enigma).
4. Las páginas de Tony Sale sobre códigos y cifrados y los archivos del Bletchley Park Trust.