lunes, 30 de marzo de 2015

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

En este post comienzo a contar brevemente e intentaré que de forma comprensible (aunque como dije en el anterior se trató de un proceso largo y complejo) cómo consiguieron los criptoanalistas "romper" el código Enigma.

Para ello nos tenemos que remontar a antes de la II Guerra Mundial, años en los cuales el matemático polaco Marian Rejewski, basándose en el análisis de los seis primeros caracteres de los mensajes interceptados, es decir, en la repetición dos veces al inicio de cada mensaje de los tres caracteres elegidos por el operador para indicar la posición inicial de los rotores con la que iba a cifrar un mensaje concreto (ver lo explicado en el post anterior sobre la "clave de sesión"), consiguió deducir el cableado de los rotores y del reflector.

A Rejewski le fueron muy útiles sus conocimientos de permutaciones en la teoría de grupos, pero para contarlo de una forma lo más comprensible posible voy a intentar describir sólo el cómo lo hizo, sin detallar exhaustivamente el por qué, es decir, prescindiendo de adentrarme en teorías matemáticas complejas para únicamente exponer la operativa que utilizó.

Básicamente, lo que hizo fue estudiar cómo cambiaban las letras en esos seis primeros caracteres del mensaje interceptado que sabía que habían sido cifradas con la misma clave del día tras pulsarse dos veces las mismas letras del teclado, es decir, los cambios o transformaciones que se producían entre el primer carácter y el cuarto, el segundo y el quinto, y el tercero y el sexto.

En el ejemplo que puse en el post anterior los seis primero caracteres del mensaje interceptado (la "clave de sesión" repetida dos veces) serían "BJEGSM" y relacionando el primer carácter con el cuarto, el segundo con el quinto y el tercero con el sexto obtenemos los siguientes cambios o transformaciones de letras:

B -> G; 
J -> S; E -> M.

Esto lo único que nos dice es que una misma tecla (desconocemos cuál es) ha transformado "B" en "G", otra misma tecla (que también desconocemos) "J" en "S" y otra (también desconocida) "E" en "M".

Hasta el momento no es gran cosa, pero si interceptamos el número de mensajes suficiente en un mismo día (los seis primeros caracteres de todos ellos habrán sido cifrados con la misma clave del día) podemos ir completando unas tablas con los cambios que se producen.

Ejemplo: supongamos que se interceptan cuarenta mensajes con los siguientes seis primeros caracteres de cada uno de ellos:

1. BDZ GOW; 2. BJE GSM; 3. MOT LDJ; 4. IIW KAB; 5. FXC WBN;
6. HAN QIK; 7. MIP LAX; 8. ZQV RCF; 9. VHG UJL; 10. DWB OFI;
11. VNM UWO; 12. BWX GFT; 13. SDF ZOP; 14. SPB ZMI; 15. XCB AEI;
16. UTA JYG; 17. DOZ ODW; 18. CGC IQN; 19. PYO DHE; 20. QKI BGZ;
21. TEZ MUW; 22. AON CDK; 23. NDR VOS; 24. ARO CNE; 25. BUC GKN;
26. KGY EQA; 27. EVC TLN; 28.WLW HRB; 29. YQK SCC; 30. LIX XAT;
31. OON FDK; 32. JAU NIQ; 33. NMW VZB; 34. BBD GPH; 35. VZS UXU;
36. ROJ YDV; 37. USE JTM; 38. DQL OCY; 39. FFH WVR; 40. GRQ PND.

Con lo que podríamos ir completando tres tablas con los cambios o transformaciones que se observan en las letras (una para el primer y cuarto caracteres de los mensajes interceptados, otra para el segundo y quinto y otra para el tercero y sexto).

En todas esas tablas se colocan en la primera fila los caracteres de la "A" a la "Z" ordenados alfabéticamente y en la segunda se anotan las letras a las que cambian estos en los mensajes interceptados.

En nuestro ejemplo:

- Primer y cuarto caracteres de los mensajes interceptados:


Con esta tabla, por ejemplo, para la "A" las transformaciones que se observan hasta llegar otra vez a la "A" son las siguientes:


Haríamos esto para todos los caracteres de la "A" a la "Z":

A -> C ->  I ->  K -> E ->  T -> M -> L ->  X -> A.
B -> G -> P -> D -> O -> F -> W -> H -> Q -> B.
...
Z -> R -> Y -> S -> Z.

Llamando A a la permutación que experimenta la primera letra que se pulsa en el teclado y D a la que sufre esa misma letra cuando se pulsa en cuarta posición, la permutación del primer y cuarto caracteres (AD) se podría expresar ordenada por la longitud de sus ciclos de la siguiente manera:

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

Segundo y quinto caracteres de los mensajes interceptados:


Siguiendo los mismos pasos que en el caso anterior, obtendríamos las siguientes cadenas para todos los caracteres de la "A" a la "Z":

A -> I ->  A. 
B -> P -> M -> Z -> X -> B.
...
Z -> X -> B -> P -> M -> Z.

Y, por tanto, llamando B a la permutación que experimenta la segunda letra que se pulsa en el teclado y E a la que sufre esa misma letra cuando se pulsa en quinta posición, la permutación del segundo y quinto caracteres (BE) se podría expresar ordenada por la longitud de sus ciclos de la siguiente manera:

BE = (AI)(DO)(BPMZX)(HJSTY)(CEUKGQ)(FVLRNW).

Tercer y sexto caracteres de los mensajes interceptados:


Con lo que en este caso las cadenas para todos los caracteres de la "A" a la "Z" serían las siguientes:

A -> G ->  L ->  Y ->  A
B -> I -> Z -> W -> B.
...
Z -> W -> B -> I -> Z.

Y, de forma análoga que en los casos anteriores, llamando C a la permutación que experimenta la tercera letra que se pulsa en el teclado y F a la que sufre esa misma letra cuando se pulsa en sexta posición, la permutación del tercer y sexto caracteres (CF) se podría expresar ordenada por la longitud de sus ciclos de la siguiente manera:

CF = (CNK)(EMO)(AGLY)(BIZW)(DHRSUQ)(FPXTJV).


Muy bien, ¿pero esto vale para algo?. A mí desde luego para nada más que para pasar el rato, pero para un genio como Rejewski fue el hilo del que tirar para desmadejar el ovillo.

Cuento muy brevemente en qué se basó:

Cuando se pulsa una letra en el teclado las permutaciones que ese carácter sufre en la máquina Enigma hasta obtenerse el correspondiente carácter cifrado son las siguientes:


1º) En el camino de ida hacia el reflector:
      - La del tablero de conexiones (S).
      - La del primer rotor (N).
      - La del segundo rotor (M).
      - La del tercer rotor (L).

2º) La del reflector (R).

3º) En el camino de vuelta del reflector las permutaciones son las inversas a las del camino de ida y cuya notación sería la siguiente:
      - La del tercer rotor (L-1).
      - La del segundo rotor (M-1).
      - La del primer rotor (N-1).
      - La del tablero de conexiones (S-1).

Sin embargo, con estas permutaciones no se tiene en cuenta el giro de los rotores, lo que obligó a Rejewski a introducir una permutación más, que llamó P, para convertir cualquier letra en su siguiente, es decir:

A -> B ->  C ->  D ->  E ...

Y, por tanto:

P = (ABCDEFGHIJKLMNOPQRSTUVWXYZ).

Así Rejewski obtuvo un modelo matemático de la máquina Enigma.

En este modelo, para simplificar el problema, sólo consideró la rotación que se producía en el primer rotor tras pulsarse una tecla, obviando deliberadamente la posibilidad de que al teclear los seis primeros caracteres con la misma clave del día se produjera también la rotación del segundo e incluso la del tercer rotor; la probabilidad de que el segundo rotor se mueva tras pulsarse esas seis teclas es relativamente baja (6/26) y la del tercero aún menor, y si se consideran esas posibles rotaciones se complicaría de forma muy significativa el modelo.

Dicho lo anterior, el modelo que ideó Rejewski fue el siguiente:

- Las permutaciones de las seis primeras letras pulsadas en el teclado (A, B, C, D, E y F, respectivamente) pueden expresarse como (el subíndice indica el desplazamiento a la posición inicial o número de veces que ha girado el primer rotor):

A = SPNP-1MLRL-1M-1PN-1P-1S-1
B = SP2NP-12MLRL-1M-1P2N-1P-12S-1
C = SP3NP-13MLRL-1M-1P3N-1P-13S-1
D = SP4NP-14MLRL-1M-1P4N-1P-14S-1
E = SP5NP-15MLRL-1M-1P5N-1P-15S-1
F = SP6NP-16MLRL-1M-1P6N-1P-16S-1

- Y las permutaciones compuestas (las que se obtienen de aplicar una y después la otra) del primer y cuarto caracteres (AD), del segundo y quinto (BE) y del tercero y sexto (CF) pueden expresarse respectivamente como:

AD = SPNP-1MLRL-1M-1PN-1P3NP-14MLRL-1M-1P4N-1P-14S-1
BE = SP2NP-12MLRL-1M-1P2N-1P3NP-15MLRL-1M-1P5N-1P-15S-1
CF = SP3NP-13MLRL-1M-1P3N-1P3NP-16MLRL-1M-1P6N-1P-16S-1

El siguiente paso consistía en obtener A, B, C, D, E y F a partir de las permutaciones compuestas AD, BE y CF que Rejewsky había observado para muchos días en los mensajes interceptados.

Cosa nada fácil operar con estas ecuaciones, ¿cómo lo hizo?. Imposible contarlo sin acudir a complicadas propiedades de las permutaciones, que por otra parte se escapan a mi capacidad y talento, por lo que me limitaré a decir que Rejewski se valió de sus profundos conocimientos matemáticos sobre éstas y de la ayuda de ciertos colegas (a los que finalmente, como al propio Rejewski, ni siquiera se les reconoció suficientemente su esfuerzo en esta tarea) para finalmente deducir el cableado de los rotores y del reflector

De lo dicho en este post, sin quitarle ningún mérito al genial Rejewski, es evidente que para ello fueron determinantes dos de las debilidades de la máquina Enigma que comentaba en el post anterior: la forma de operación en cuanto al establecimiento de la clave de sesión (su repetición dos veces de forma consecutiva al inicio de cada mensaje y que era cifrada con la misma clave del día) su propiedad de cifrado recíproco (que venía dada por el reflector), pero también fueron de gran ayuda las pistas que "amablemente" proporcionaban los operadores alemanes cuando establecían la clave de sesión (letras consecutivas del alfabeto o del teclado, caracteres repetidos, etc.).

Después de lograr esto se podían ya construir réplicas de la versión militar de la máquina Enigma, pero como decía en el post anterior el verdadero desafío era cómo obtener la clave. Asunto del que hablaré en el siguiente post.

No hay comentarios:

Publicar un comentario