Una Breve Aproximación al Código Nazi: Enigma

En ocasiones queremos que determinada información se almacene de forma segura, o nos interesa que llegue a un destinatario sin que en el camino caiga en manos no deseadas. Esta necesidad de proteger la información ya existía en las civilizaciones clásicas y, desde entonces, se han desarrollado métodos cada vez más sofisticados para lograr ese objetivo. La ciencia (o rama conjunta de la matemática e informática) que se encarga de diseñar y estudiar dichos métodos se conoce como criptografía. En este artículo no vamos a hablar de la criptografía actual ni de las prometedoras tendencias futuras (e.g. criptografía cuántica), sino de la máquina de cifrado por antonomasia: Enigma. Una vez hayamos explicado los componentes y el funcionamiento de la misma, podremos hacer un sencillo ejercicio de matemática discreta que espero resulte didáctico y entretenido.

Recién finalizada la Gran Guerra, el ingeniero alemán Arthur Scherbius desarrolló una máquina para la encriptación de datos inicialmente bancarios y empresariales, pero que en 1925 fue adoptada por el ejército alemán para la comunicación de información militar. La máquina, cuyo nombre podría haber sido tomado del título de la obra Enigma Variations del compositor británico Edwar Elgar, se empleó antes y durante el desarrollo de la Segunda Guerra Mundial, por lo que romper el sistema de cifrado se convirtió en una de las más altas prioridades de las potencias aliadas enfrentadas a la Alemania nazi. Aunque se emplearon distintos modelos con algunas diferencias notables, aquí vamos a hablar del funcionamiento genérico común a todas las versiones.

1. Partes de la máquina enigma

Con una apariencia similar a la de una máquina de escribir, Enigma estaba compuesta por cuatro partes principales:

1. Teclado: . En él se escribían el texto en claro (mensaje a encriptar) y el criptograma (mensaje encriptado) para convertir uno en el otro y viceversa.
2. Panel de lámparas: Es aquí donde se indica la letra por la que se codifica la introducida en el teclado.
3. Mecanismo de cifrado: Es el corazón de la máquina, ya que es en él donde se produce el proceso de cifrado, y está compuesto por tres rotores y un reflector. Tanto un rotor como un reflector son un disco con 26 posiciones (cada una de las letras del alfabeto) con conexiones internas entre ellas, pero tienen nombres distintos ya que existen diferencias en su estructura y principalmente en su funcionamiento (que veremos con más detalle más adelante). Para aumentar la seguridad, existían varios reflectores y rotores diferentes (distintas conexiones internas).
4. Clavijero: En él aparecen las letras del alfabeto, que se pueden conectar entre sí mediante cables para intercambiarlas antes de que el mecanismo de cifrado las codifique.

2. ¿Cómo funciona?

La manera en la que Enigma encripta un mensaje es sustituyendo cada letra que aparece en él por otra (no necesariamente distinta a la original), de manera que el resultado es un mensaje ininteligible. Veamos por encima entonces qué recorrido sigue una letra, por ejemplo la M, para convertirse en otra. En primer lugar, al pulsar la tecla M del teclado se manda una corriente eléctrica que va al clavijero. Allí, si la letra M está conectada mediante un cable a cualquier otra, entonces Enigma lo que hará será codificar esa otra letra, y si no, codifica la M directamente. Supongamos que la M está conectada a la letra C en el clavijero. Como la C ocupa la tercera posición del alfabeto, entonces la corriente sigue su camino hasta la tercera posición del primero de los tres rotores, que supongamos es una J. Internamente en este rotor, la J supongamos está conectada con la letra L, y como la letra L ocupa la posición 12 del alfabeto, entonces la corriente va a la posición 12 del segundo rotor, donde habrá otra letra. Este mismo proceso tiene lugar en los dos siguientes rotores hasta llegar al reflector, donde este, como su propio nombre indica, refleja la corriente de vuelta a los rotores, no sin antes haber cambiado la letra que le llegue por otra (que dependerá del reflector que estemos usando). Así, la corriente sigue su camino de vuelta por los rotores (esta vez se recorren en sentido contrario) donde siguen cambiándose letras unas por otras en función de su posición en el alfabeto, de la posición del rotor y de las conexiones internas de los rotores. Finalmente, al salir la corriente por el primer rotor, esta se manda al clavijero para hacer un último cambio de letras si existiese tal conexión mediante un cable, y de ahí al panel de lámparas donde se iluminará la letra final que codifica a la M, pongamos que es una R.

Más formalmente, podemos decir lo siguiente. Sea $\mathfrak{A}$ el alfabeto de 26 letras. Definimos la función Enigma $\mathbb{E}$, que aplica $\mathfrak{A}$ en sí mismo, y la escribimos como producto de permutaciones. Sean $a,x \in \mathfrak{A}$ las letras original y encriptada, respectivamente; y sean C, D, M, I, y R las transformaciones del clavijero, del rotor derecho, central e izquierdo, y del reflector, respectivamente. Entonces

$$\mathbb{E} : \mathfrak{A} \rightarrow \mathfrak{A} \\ a \mapsto x = \mathbb{E}(a) = C^{-1}D^{-1}M^{-1}I^{-1}RIMDC(a)$$

Para codificar entonces un mensaje entero, sólo habría que teclearlo letra a letra y Enigma nos devolverá por cada letra introducida la letra por la que se codifica. Sin embargo, podría preguntarse el lector, qué seguridad hay en el sistema si cada vez que pulsemos la letra M, Enigma la codificará por una R, de manera que con un poco de esfuerzo (tal vez con análisis de frecuencias), pueda revelarse la correspondencia de letras. Pues bien, aquí reside el interés de esta máquina, y es que una misma letra se codifica cada vez por otra distinta. Es decir, si pulsamos la letra M tres veces seguidas, primero se iluminará la R, luego la O, y luego la V, por ejemplo. Esto se consigue de la siguiente manera: cada vez que se codifica una letra, el primer rotor gira una posición, de manera que como hemos visto en el ejemplo, si la letra que ocupaba la tercera posición era una J, ahora será una K. Es más, cuando se hayan codificado 26 letras, y por tanto el primer rotor haya girado 26 veces (una vuelta completa), el segundo rotor girará una vez; y cuando este haya girado 26 veces, el tercer rotor girará también. Es una idea similar a la de las manecillas de los segundos, minutos y horas en un reloj.

Por lo tanto, el hecho de que al teclear un mensaje obtengamos un criptograma u otro dependerá de la configuración inicial de la máquina: conexiones en el clavijero, qué rotores se usan, en qué orden, cuál es su posición inicial, y qué reflector se usa. Esta configuración era conocida como la clave de la máquina. Para más seguridad, la clave cambiaba cada día, y para saber qué clave utilizar, desde Berlín se enviaban unos cuadernillos mensualmente a los frentes de combate donde se especificaba esta información. Para poder desencriptar un mensaje lo que había que hacer era simplemente configurar la máquina Enigma de la misma manera en la que se había codificado el mensaje y teclear el criptograma. Esto es así ya que al haber definido $\mathbb{E}$ como se indica arriba, entonces se tiene que la inversa $\mathbb{E}^{-1}$ coincide con $\mathbb{E}$, es decir, $\mathbb{E}^{-1}=\mathbb{E}:$

$$\mathcal{E}^{-1} : \mathfrak{A} \rightarrow \mathfrak{A} \\ x \mapsto \mathcal{E}^{-1}(x)$$

$$\mathbb{E}^{-1}(x) = (C^{-1}D^{-1}M^{-1}I^{-1}RIMDC)^{-1}(x) = \\ C^{-1}D^{-1}M^{-1}I^{-1}R^{-1}I^{-1}(M^{-1})^{-1}(D^{-1})^{-1}(C^{-1})^{-1}(x) = \\ C^{-1}D^{-1}M^{-1}I^{-1}RIMDC(x) = \mathbb{E}(x)$$

(donde hemos usado que $R^{-1}=R$ por el funcionamiento de un reflector). En consecuencia, la composición de $\mathbb{E}$ consigo misma aplicada a una letra $a$ será la identidad, ya que $\mathrm{id}_{\mathfrak{A}} = \mathbb{E}^{-1} \circ \mathbb{E} = \mathbb{E} = \mathbb{E} \circ \mathbb{E}^{2}$:

$$\mathfrak{A} \xrightarrow{\mathcal{E}} \mathfrak{A} \xrightarrow{\mathcal{E}} \mathfrak{A} \\ a \mapsto \mathbb{E}(a) = x \mapsto \mathbb{E}(x) = \mathbb{E}(\mathbb{E}(a))$$

$$\mathbb{E}(\mathbb{E}(a)) = C^{-1}D^{-1}M^{-1}I^{-1}RIMDC(C^{-1}D^{-1}M^{-1}I^{-1}RIMDC(a)) = a$$

3. Número de claves

Conociendo los factores que intervienen en la encriptación del mensaje, nos planteamos el siguiente problema: ¿cuál es el número de claves posibles? Tendremos que aplicar los principios más básicos de la combinatoria, y para ello conviene recordar lo siguiente. Por un lado, el número combinatorio $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, cuenta el número de subconjuntos de $k$ elementos que podemos extraer de un conjunto de n elementos; o lo que es lo mismo, el número de maneras distintas de seleccionar $k$ elementos de un conjunto de $n$ elementos. Por otro lado, la regla del producto describe un procedimiento que nos permite contar el número de elementos que conforman un conjunto, construyéndolos paso a paso para posteriormente hacer una multiplicación. En este caso, la regla la aplicamos obteniendo el número de claves posibles que introduce cada variable de las enumeradas más arriba para por último multiplicarlos todos. En primer lugar, pongamos que el número de reflectores que tenemos disponibles es $3$, y de entre ellos tenemos que elegir tan sólo $1$, es decir, hay $\binom{3}{1}$ formas distintas de elegir el reflector. Por su parte, pongamos que disponemos de $5$ rotores, pero tenemos que seleccionar tan sólo tres de ellos, y además importa en qué orden lo hagamos. El número de formas distintas de seleccionar tres elementos de un conjunto de $5$ es precisamente $\binom{3}{1}$, y por cada uno de ellos, el número de formas distintas de colocar tres elementos en tres huecos, de manera que cada elemento vaya a un hueco distinto (biyecciones de un conjunto en sí mismo, o más comúnmente, permutaciones) es precisamente $3!$. Una vez fijados el reflector, los rotores y su orden, tenemos que elegir sus posiciones iniciales. Por cada una de las $26$ posibilidades para el primer rotor hay otras $26$ para el segundo, y para cada una de estas hay otras $26$ para el tercero, por lo que tenemos, por la regla del producto, $26^{3}$ posiciones iniciales.

Por último, el cálculo más interesante es el de las formas de configurar el clavijero. Pongamos que tenemos seis cables indistinguibles (cada uno intercambia dos letras entre sí), y que tenemos que utilizar los seis siempre. Para hacer la cuenta tendremos que introducir un elemento que nos facilita el cálculo pero que es erróneo y al final tendremos que corregir: vamos a numerar los cables. Es decir, realmente los cables son indistinguibles, pero ahora vamos a considerar que hay uno que es el número uno, otro el dos y así hasta el seis. Este orden espurio lo podemos corregir al final del cálculo dividiendo el resultado que obtengamos entre el número de formas de ordenar estos cables, es decir, entre $6!$, devolviendo al anonimato a cada uno de ellos.

Esto es porque, por ejemplo, el resultado:

$$cable 1: (a,b), cable 2:(c,d), cable 3: (e,f),\\ cable 4: (g,h), cable 5: (i,j), cable 6: (k,l)$$

es el mismo que, por ejemplo, el resultado:

$$cable 1: (c,d), cable 2: (a,b), cable 3: (k,l),\\ cable 4: (g,h), cable 5: (i,j), cable 6: (e,f).$$

Comencemos: de entre las 26 letras posibles, tenemos que elegir dos para que las una el cable número uno, y este número es precisamente $\binom{26}{2}$. Por cada uno de estos dos pares de letras unidos por el cable número 1, tedremos que elegir entre las 24 letras restantes otras 2 para que las una el cable número dos, que son $\binom{24}{2}$. Es decir, llevamos contadas $\binom{26}{2}\binom{24}{2}$ posibilidades. Este argumento lo reiteramos para los seis cables que tenemos, y obtenemos el siguiente número:

$$\prod_{j=0}^{5} \binom{26-2j}{2} = \\ \frac{26!}{2 \cdot (26 - 2 \cdot 1)!} \cdot \frac{(26 - 2 \cdot 1)!}{2 \cdot (26 - 2 \cdot 2)!} \cdot \ldots \cdot \frac{(26 - 2 \cdot 5)!}{2 \cdot (26 - 2 \cdot 6)!} = \\ \frac{26!}{2^6 \cdot (26 - 2 \cdot 6)!}$$

Multiplicamos este número por el $\frac{1}{6!}$ que prometimos al comienzo, y obtenemos $100.391.791.500$ posibles combinaciones en el clavijero.

Habiendo obtenido todas estas cantidades, para obtener el número de claves posibles ahora sólo falta, como indica la regla del producto, multiplicarlas:

$$\binom{3}{1} \cdot \binom{5}{3} \cdot 3! \cdot 26^{3} \cdot \frac{1}{6!} \cdot \frac{26!}{2^{6} \cdot (26 - 2 \cdot 6)!}$$

que para que lo entendamos, es la vertiginosa cifra de $317.607.502.932.720.000$ claves posibles, es decir, más de $300$ millones de millones de millones, lo que otorgaba bastante confianza al mando alemán sobre la confidencialidad de sus mensajes. Sin embargo, el código Enigma fue roto hasta en dos ocasiones. En primer lugar, antes del estallido de la guerra, los polacos, conscientes de la situación, establecieron un equipo de criptoanalistas, el Byuro Szyfrów, en el que destaca la figura del matemático Marian Rejewski. Consiguieron descubrir su funcionamiento y desarrollaron una máquina, a la que bautizaron como Bomba, capaz de desencriptar las comunicaciones alemanas. Al introducir los alemanes mejoras en Enigma y tras la invasión de Polonia, los británicos tomaron el relevo. Reunieron a sus mejores matemáticos en Bletchley Park, y liderados por Alan Turing y basándose en sus trabajos relacionados con la llamada máquina de Turing, consiguieron desarrollar una máquina, llamada también Bomba (aunque totalmente distinta a la polaca), que consiguió definitivamente romper el código Enigma. Alan Turing es considerado hoy en día uno de los padres de las ciencias de la computación y el principal precursor de la Informática.

---