¿Cómo se rompió Enigma y qué matemáticas se usaron?

Permutaciones y ciclos

Una permutación reordena las letras: cada letra va a parar a una letra, y dos letras distintas nunca van a parar a la misma. Se escribe por ciclos. Con ocho letras A a H, la permutación que lleva A→C, C→E, E→A, B→F, F→D, D→B y deja quietas G y H se escribe

Su tipo de ciclos es la lista de longitudes: $3,3,1,1$. Para multiplicar permutaciones se lee de izquierda a derecha, como hace Rejewski: $XY$ significa aplicar primero $X$ y después $Y$. Cada posición de la máquina en un instante dado es una permutación del alfabeto, y por el reflector es una involución sin puntos fijos: se compone de 13 parejas $(x\,y)$ y ninguna letra queda quieta.

Las tres permutaciones que se podían ver

Llama $A$, $B$, $C$, $D$, $E$, $F$ a las seis permutaciones de la máquina al cifrar las letras 1 a 6 del mensaje (son seis distintas porque el rotor de la derecha gira una posición con cada pulsación). Nadie las conocía. Pero la clave repetida dos veces permite reconstruir, con unos 80 mensajes del mismo día, las tres composiciones $AD$, $BE$ y $CF$. Si la letra $x$ de la clave sale cifrada como $a$ en el puesto 1 y como $b$ en el puesto 4, entonces $A$ lleva $x$ a $a$ y, como $A$ es una involución, también lleva $a$ a $x$; después $D$ lleva $x$ a $b$. Así que $AD$ lleva $a$ a $b$: la letra 1 cifrada a la letra 4 cifrada, sin saber $x$. Con la 2 y la 5 sale $BE$, y con la 3 y la 6, $CF$. Por ejemplo, de los comienzos dmq vbn, von puy y puc fmq se lee que $AD$ lleva d a v, v a p y p a f. Rejewski publicó el resultado completo de un día:

Mira los ciclos: dos de longitud 10, dos de longitud 2 y dos de longitud 1. Y en las otras dos permutaciones de su ejemplo, dos de longitud 9, dos de longitud 3 y dos de longitud 1 para $BE$, y dos de longitud 13 para $CF$. No es casualidad.

El teorema de los pares

Teorema (Rejewski). Si $X$ e $Y$ son dos permutaciones de las mismas $2n$ letras formadas solo por parejas (involuciones sin puntos fijos), entonces en el producto $XY$ cada longitud de ciclo aparece un número par de veces: los ciclos van por pares de la misma longitud.

Rejewski lo demuestra siguiendo las letras una a una. Aquí va otra demostración, en cuatro pasos. Sea $P = XY$.

1. $X$ da la vuelta a $P$. Como $XX$ y $YY$ son la identidad, el inverso de $P$ es $YX$, y $XPX = XXYX = YX = P^{-1}$. Dicho letra a letra: si $P$ lleva $u$ a $v$, entonces $P$ lleva $X(v)$ a $X(u)$.
2. $X$ manda ciclos a ciclos de la misma longitud. Si $(a_1\,a_2\,\dots\,a_k)$ es un ciclo de $P$, por el paso 1 las letras $X(a_k),\dots,X(a_2),X(a_1)$ forman un ciclo de $P$, también de longitud $k$, recorrido al revés. Falta ver que ese ciclo no puede ser el de partida.
3. Nunca es el mismo ciclo. Supón que $X$ manda el ciclo $C=(a_1\,\dots\,a_k)$ a sí mismo, con los índices contados módulo $k$. Si $X(a_1) = a_m$, el paso 1 da $X(a_2) = a_{m-1}$, $X(a_3) = a_{m-2}$ y, en general, $X(a_i) = a_{m+1-i}$: $X$ refleja el ciclo como un espejo. Como $Y = XP$ (se aplica primero $X$ y luego $P$), $Y(a_i) = P(a_{m+1-i}) = a_{m+2-i}$: otro espejo, con el número $m+2$ en lugar de $m+1$. Un espejo $a_i \mapsto a_{s-i}$ deja quieta la letra $a_i$ cuando $2i$ y $s$ se diferencian en un múltiplo de $k$. Si $k$ es impar, eso pasa siempre para algún $i$. Si $k$ es par, pasa cuando $s$ es par, y de los dos números $m+1$ y $m+2$ uno es par. En cualquier caso, $X$ o $Y$ dejaría una letra quieta, y ninguna de las dos lo hace. Así que $X$ manda cada ciclo a otro distinto.
4. Los ciclos quedan emparejados. Si $X$ manda $C$ a $C'$, también manda $C'$ a $C$, porque $XX$ es la identidad. Los ciclos de $P$ se reparten, pues, en parejas $\{C, C'\}$ de ciclos distintos y de la misma longitud, y cada longitud aparece un número par de veces.

Un ejemplo pequeño: con $X=(A\,B)(C\,D)(E\,F)(G\,H)$ e $Y=(A\,F)(B\,C)(D\,E)(G\,H)$, el producto $XY$ es $(A\,C\,E)(B\,F\,D)(G)(H)$, el de arriba: dos ciclos de 3 y dos de 1, en pares. (Si $X$ e $Y$ comparten una pareja, como $(G\,H)$, salen dos ciclos de longitud 1.) Lo he comprobado también por ordenador: con 8 letras, en los 11 025 pares posibles de involuciones sin puntos fijos, y con 26 letras, en 200 000 pares elegidos al azar. En todos los casos, cada longitud aparece un número par de veces.

Y hay un recíproco que Rejewski considera especialmente importante: si una permutación de un número par de letras tiene cada longitud de ciclo un número par de veces, es producto de dos de estas involuciones. Aplicado a $AD$, $BE$ y $CF$, deja para cada una de $A$, $B$ y $C$ entre una decena y unas decenas de posibilidades (y entonces $D$, $E$ y $F$ quedan fijadas). Juntando las tres salen miles de combinaciones; para quedarse con la buena, Rejewski aprovechó las costumbres de los operadores, que repetían claves fáciles como tres letras iguales.

El teorema que más pesó: la conjugación

Aquí viene lo más importante. El tablero de cables $S$ también intercambia letras por parejas, así que $S^{-1}=S$. La corriente pasa por el tablero al entrar y al salir, de modo que lo que se observa no es la máquina «limpia» sino la máquina rodeada por el tablero. Si $A'$ y $D'$ son las permutaciones de los rotores y el reflector, sin cables, entonces $A = S\,A'\,S^{-1}$ y $D = S\,D'\,S^{-1}$, y al multiplicar los dos $S^{-1}S$ del medio se anulan:

Esto se llama conjugar $A'D'$ por $S$, y en la práctica es cambiar el nombre de las letras: si $A'D'$ tiene un ciclo $(a_1\,a_2\,\dots\,a_k)$, entonces $AD$ tiene el ciclo $(S(a_1)\,S(a_2)\,\dots\,S(a_k))$. Los ciclos conservan su longitud y solo cambian las letras que contienen. Con el ejemplo de antes y $S=(A\,C)(B\,G)(D\,H)$, renombrar las letras da $X'=(A\,H)(B\,D)(C\,G)(E\,F)$ e $Y'=(A\,G)(B\,D)(C\,F)(E\,H)$, y su producto es $(A\,E\,C)(F\,H\,G)(B)(D)$: otra vez $3,3,1,1$, con las letras cambiadas.

Esta es la clave. El tablero de cables es el que aporta casi toda la dificultad de la clave: con 10 cables hay

formas de colocarlos (más de $10^{14}$; con los seis cables que describe Rejewski, $100\,391\,791\,500$). Pero no cambia el tipo de ciclos de $AD$, $BE$ y $CF$. Ese tipo, llamado la característica del día, solo depende del orden de los rotores y de su posición inicial (si el rotor central no se mueve durante esas seis pulsaciones, algo que Rejewski desprecia porque pasa pocas veces). Con los tres rotores de entonces, que admitían 6 órdenes, son

casos. Es un número que se puede catalogar. Rejewski ideó un aparato eléctrico, el «ciclómetro», con el que se recorrieron todas esas posiciones anotando el tipo de ciclos de cada una. Cada día bastaba mirar la característica de los mensajes interceptados y buscarla en el catálogo para acotar qué orden y qué posición de los rotores se habían usado, sin saber nada de los cables. No siempre daba una respuesta única (Rejewski avisa de que dos posiciones distintas pueden tener la misma característica), pero dejaba muy pocas.

Así, un problema con un número astronómico de claves se partía en dos: un catálogo de unos cien mil casos y, después, el tablero. Si hay que quedarse con un solo resultado matemático de toda la historia de Enigma, es este, sin exagerar su alcance: ni este teorema ni ninguna otra cosa ganó la guerra por sí sola.

Cuántas claves, entonces

Con tres rotores elegidos entre cinco (60 órdenes), $26^3 = 17\,576$ posiciones y el tablero de 10 cables, sin contar el ajuste de los anillos:

Con los 6 órdenes y los seis cables que describe Rejewski para los primeros años, eran $6\cdot 17\,576\cdot 100\,391\,791\,500 \approx 1{,}1\cdot 10^{16}$. Son números inmensos, y aun así no bastaron. La lección es la misma que en cómo romper un cifrado sin la clave y en por qué funciona RSA: el tamaño del espacio de claves no es lo que decide la seguridad; lo decide si la estructura del cifrado deja pasar información. Aquí la dejaba pasar por dos sitios, la simetría del reflector y la clave repetida, y las permutaciones lo aprovecharon.