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.

jueves, 26 de marzo de 2015

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

En estos últimos posts sobre la máquina Enigma me propongo compartir lo que he aprendido sobre cómo se consiguió "romper" su cifrado.

Se trata de una historia muy larga y muy compleja, por lo que intentaré simplificar lo que he entendido sobre ella para no aburrir y hacerla lo más comprensible que me sea posible.

Las debilidades de la máquina Enigma que propiciaron el criptoanálisis vinieron por una parte de su diseño, las menos y relativamente poco importantes, y por otra parte de su utilización (operación), las más y las que al final resultaron decisivas para poder "romper" su cifrado.

Todo ello, junto con la información que se filtró y obtuvieron los aliados sobre su funcionamiento y uso, hizo posible el criptoanálisis.

Las citadas debilidades pueden resumirse en las siguientes:

1.- La introducción del reflector proporcionó una ventaja muy importante desde el punto de vista de operación de la máquina, ya que el cifrado y descifrado se podían realizar, siempre que se dispusiera de una máquina igual, con la misma configuración (clave) y sin necesidad de hacer ninguna modificación, pero, al mismo tiempo, fue su debilidad de diseño más importante.

2.- Para no generar un elevado número de mensajes con la misma clave, algo que podía dar pistas a los criptoanalistas, los alemanes decidieron que cada mensaje debía tener su propia clave, lo que pensaban que aumentaba la seguridad y para lo que actuaban de la forma que comento más adelante, pero esto permitió a los criptoanalistas deducir el cableado de los rotores y del reflector; primer paso, necesario pero no suficiente, para atacar de forma sistemática el cifrado de los mensajes.

Y digo no suficiente porque la máquina Enigma seguía el principio de Kerckhoffs, por el cual:

"La seguridad del sistema debe recaer en la seguridad de la clave, debiéndose suponer conocidos el resto de los parámetros del sistema criptográfico".

Es decir, los alemanes eran plenamente conscientes de que se filtrarían los detalles técnicos de funcionamiento de la máquina y de que incluso algunas de las máquinas podían caer en manos del enemigo, pero tampoco les preocupaba en exceso porque la verdadera fortaleza de su cifrado residía en la clave. Aunque los aliados consiguieran fabricar réplicas de la máquina Enigma, el verdadero desafío consistía en conocer la clave.

La forma de operar a la que he hecho referencia anteriormente para que cada mensaje tuviera su propia clave era la siguiente:

Mensualmente los operadores recibían un libro con las claves a utilizar cada día y, para no enviar durante todo un día mensajes con la misma clave (en un mismo día se transmitía una cantidad ingente de ellos), se les ocurrió que fuera el operador quien estableciera la clave para cada mensaje a transmitir (lo que llamaron "clave de sesión"), de la siguiente manera:

2.1.- Para cifrar un mensaje el operador debía configurar la máquina con la clave del día (la que figuraba en el libro que había recibido) y teclear tres letras a su elección que indicaban la posición inicial de los rotores (parte de la clave) con la que iba a cifrar ese mensaje concreto. Para evitar errores (de operación y/o de transmisión) hacía esto dos veces seguidas.

Es decir, por ejemplo, un operador podía elegir 1-2-3 ("ABC") como posición inicial de los rotores con la que cifrar un mensaje concreto y tecleaba "ABCABC" (lo que con la clave del día podría cifrarse como "BJEGSM").

Después, manteniendo el resto de la configuración (clave del día), giraba los rotores hasta la posición inicial que él había elegido 1-2-3 ("ABC") y tecleaba el mensaje a cifrar.

2.2.-Para descifrar el mensaje, el operador que lo recibía debía configurar la máquina con la clave del día (la que figuraba en el libro que había recibido) y teclear los seis primeros caracteres del mensaje. En nuestro ejemplo "BJEGSM", con lo que vería como texto en claro "ABCABC" (es decir, dos veces de forma consecutiva la posición inicial de los rotores que había sido elegida por el otro operador para cifrar el mensaje concreto), con lo que lo único que debía hacer para obtener el texto en claro correspondiente al mensaje cifrado era girar los rotores hasta esa posición inicial 1-2-3 ("ABC") y teclear el resto del mensaje recibido.

Un sistema ingenioso para que cada mensaje tuviera su propia clave ("clave de sesión"), evitando así transmitir muchos de ellos con la misma clave, pero que, como digo, abrió la puerta al criptoanálisis.

3.- La falta de disciplina de los operadores, ya que en muchas ocasiones a la hora de establecer la posición inicial de los rotores como "clave de sesión" utilizaban el mismo carácter ("AAA",...) o caracteres consecutivos ("ABC",...) o letras consecutivas del teclado ("QWE") o un mismo operador siempre repetía los tres mismos caracteres, etc., lo que también daba pistas a los criptoanalistas.

4.- Para dificultar aún más el criptoanálisis, los alemanes establecieron otras estrictas normas para la operación de las máquinas, entre ellas, por ejemplo, que no se podía conectar una letra en el panel de conexiones ni con el carácter anterior ni con el posterior, que un rotor no podía estar alojado en una misma ranura más de un día, etc., lo que aunque en principio dificultaba el criptoanálisis se volvió en su contra, ya que si se conseguía conocer una clave esto permitía desechar muchas combinaciones posibles cuando se cambiaba.

5.- La emisión de un elevado número de mensajes, siempre a la misma hora, con una estructura similar y con palabras predecibles (por ejemplo: los partes metereológicos), lo que también daba pistas a los criptoanalístas.

Pero, ¿cómo lo consiguieron?.

Desde luego nada fácil; es más, algo absolutamente complejo.

En los siguientes posts de esta serie intentaré contar brevemente cómo lo hicieron, en la medida en la que mi capacidad y talento me lo permitan (poco en ambos casos), pero por lo que he comentado en este post creo que queda claro que al igual que con los ordenadores:

"El eslabón de seguridad más débil de la máquina Enigma fue la gente; la que estableció las normas para su uso y la que la utilizaba".

lunes, 23 de marzo de 2015

Criptografía (IV): la máquina Enigma (III)

Decía en el post anterior que la segunda versión de mi propia máquina Enigma ya se acerca bastante a las utilizadas por el ejército alemán en la II Guerra Mundial, pero que todavía le faltan ciertas características de funcionamiento adicionales y otros componentes que le fueron incluyendo.

Para avanzar un paso más, en la tercera versión de mi máquina Enigma los rotores son intercambiables (pueden permutarse), es decir, cada uno de ellos puede encajarse en cualquiera de las tres ranuras que los alojan. De esta manera y considerando las 6 posibilidades diferentes (3! = 3 x 2) de encajar los rotores en las ranuras, los alfabetos de sustitución que es posible utilizar son: 26 x 26 x 26 x 6 = 105.456.

Ahora la clave para cifrar y descifrar los mensajes viene dada por: el orden del alojamiento de los rotores en la ranuras (por ejemplo: 2-3-1) y la posición inicial de cada uno de los rotores (por ejemplo: 5-26-1).

En el ejemplo de clave que he puesto, recordar que los rotores se identificaban en las máquinas Enigma con números romanos (I, II y III)  y las letras se identificaban en cada rotor con un número (A=1, B=2,...Z=26), esto significa que el operador debe encajar el rotor II en la ranura 1, el rotor III en la ranura 2 y el rotor I en la ranura 3, y después girar el primero de los rotores así alojados hasta hacer coincidir el número 5 (carácter "E") con su indicador de posición, el número 26 (letra "Z") del segundo rotor con su indicador de posición y el número 1 (carácter "A") del tercer rotor con su respectivo indicador de posición.

Pero para hacer aún más difícil el criptoanálisis añado un nuevo componente a esta tercera versión de mi máquina: el tablero de conexiones.

Este tablero de conexiones, que tiene representadas las 26 letras y está situado en la parte frontal de la máquina, sirve para puentear letras del teclado, de tal forma que sin ninguna clavija insertada la corriente pasa directamente desde el teclado hasta el rotor de entrada, mientras que si, por ejemplo, conectamos en el tablero la letra "A" con la "B" y pulsamos la tecla correspondiente a cualquiera de ellas la corriente se dirige hasta el rotor de entrada por el "camino" correspondiente a la otra, es decir, las letras del teclado intercambian sus "caminos" hacia el rotor de entrada.

Para conseguir esto cada letra en el tablero de conexiones tiene dos conectores (el superior con el teclado - representado en la siguiente figura a la derecha de cada letra del tablero - y el inferior con el rotor de entrada - representado a la izquierda de cada letra del tablero), de tal forma que al insertar una clavija en una letra se desconectan ambos, de la siguiente manera:


Incorporando el tablero de conexiones, el esquema de funcionamiento de la tercera versión de mi máquina Enigma podría ser el siguiente:


Con los rotores intercambiables y el tablero de conexiones, ahora la clave para cifrar y descifrar los mensajes está formada por:

- El orden de alojamiento de los rotores en las ranuras.
- La posición inicial de cada uno de los rotores.
- Las conexiones a realizar en el tablero de clavijas (pares de letras para las que se intercambiarán sus "caminos" hacia el rotor de entrada).

Veamos un ejemplo de cifrado. Supongamos que queremos cifrar el mensaje "PRUEBA" con la clave:

- 1-2-3.
1-1-1.
- A/B, P/S.

Para ello el operador debe encajar el rotor I en la ranura 1, el rotor II en la ranura 2 y el rotor III en la ranura 3, después girar cada uno de los rotores así alojados hasta hacer coincidir el número 1 (carácter "A") con sus respectivos indicadores de posición, posteriormente conectar en el tablero de conexiones la letra "A" con la "B" y la "P" con la "S", y ahora ya teclear cada uno de los caracteres del texto en claro:



Y para descifrar, como siempre, otro operador con una máquina igual debería establecer esa misma configuración (clave) y después teclear cada uno de los caracteres del texto cifrado:



Esta tercera versión de mi máquina Enigma, salvo algún detalle que me falta de contar, es ya muy parecida a algunas de las utilizadas por el ejército alemán en la II Guerra mundial, y digo algunas porque tal y como ya he dicho en esta serie de posts se utilizaron diferentes modelos.

El tablero de conexiones hacía que el cifrado de la máquina Enigma fuera "casi" invulnerable para su época, ya que incrementaba de manera muy significativa las posibilidades.

La fórmula para calcular el número de posibilidades de conectar pares de letras de un total de 26 con 'n' cables (con cada uno de ellos se conecta un par de letras) es la siguiente:


Aplicando esta formula se obtiene el siguiente número de posibilidades en función del número de cables que utilicemos:


Considerando los 3 rotores intercambiables y que la máquina Enigma estándar del ejercito alemán disponía de 10 cables para conectar pares de letras en el tablero de conexiones, el número de posibilidades que a mí me salen (si lo he entendido bien y no me equivoco) es aproximadamente (lo he hecho en Excel, que tiene 15 dígitos de precisión) de:

26 x 26 x 26 x 6 x 150.738.274.937.250 = 15.896.255.521.782.600.000

Pero, aunque el modelo original de la máquina tenía 3 rotores, poco antes del inicio de la II Guerra Mundial la Wehrmacht y la Luftwaffe (las fuerzas de tierra y aéreas del ejército alemán, respectivamente) ampliaron el juego de rotores de 3 a 5 (identificados con los números romanos I, II, III, IV y V) que eran utilizables de 3 en 3 en las tres ranuras dispuestas para alojarlos, mientras que posteriormente la Kriegsmarine (armada o marina de guerra alemana) amplió a 8 el juego de rotores (identificados con los números romanos I, II, III, IV, V, VI,VII y VIII) y los modelos que utilizaba le permitían utilizarlos de 4 en 4.

Por lo que teniendo en cuenta sólo la ampliación del juego de rotores realizada tanto por la Wehrmacht como por la Luftwaffe (5 rotores utilizables de 3 en 3) y los 10 cables ya comentados para conectar pares de letras en el tablero de conexiones, me sale que el número de posibilidades asciende a:

26 x 26 x 26 x 60 x 150.738.274.937.250 = 158.962.555.217.826.000.000

Es decir, con los 15 dígitos de precisión que tiene Excel y si no me equivoco, aproximadamente 159 trillonesciento cincuenta y ocho trillones novecientos sesenta y dos mil quinientos cincuenta y cinco billones doscientos diecisiete mil ochocientos veintiséis millones.

Con este número de posibilidades (las utilizadas por la Kriegsmarine aún tenían másno me extraña que los alemanes pensaran que la máquina Enigma era invulnerable, pero... se equivocaban, aunque esto es ya otra historia que, en todo caso, será objeto de algún post posterior sobre este tema.  

jueves, 19 de marzo de 2015

Criptografía (III): la máquina Enigma (II)

Partiendo de la primera versión de mi propia máquina Enigma (ver post anterior) me propongo llegar a una segunda versión un poco más aproximada a aquellas que utilizaba el ejército alemán en la II Guerra Mundial (y digo aquellas porque llegaron a utilizar diferentes modelos).

En esta segunda versión utilizaremos tres rotores en lugar de uno e incluiremos un reflector.

El primer rotor gira un veintiseisavo (1/26) de una  vuelta completa con cada pulsación de una tecla, el segundo un veintiseisavo (1/26) de una vuelta tras una rotación completa del primero y el tercero un veinteseisavo (1/26) de una vuelta tras una rotación completa del segundo.

Con un único rotor, tal y como comentaba en el post anterior, la máquina utilizaría 26 alfabetos diferentes (volvería a su posición inicial tras pulsarse 26 teclas), con dos usaría 676 alfabetos (ambos volverían a su posición inicial tras pulsarse 26 x 26 = 676 teclas) y con tres el número de alfabetos es 17.576 (los tres rotores volverían a su posición inicial tras pulsarse 26 x 26 x 26 = 17.576 teclas).

En cada rotor cada contacto de una cara está conectado o cableado a un contacto de la cara contraria, por ejemplo como se muestra en la figura, y cada rotor está cableado de una manera diferente.

Cada uno de los contactos de la segunda cara del primer y segundo rotor se conecta a otro de la primera cara del rotor siguiente, y los de la segunda cara del tercer rotor se conectan a un contacto del reflector.

El reflector es en realidad otro rotor, pero no gira y sólo tiene contactos en su primera cara. Su misión consiste en reenviar de vuelta la señal que recibe de la salida del tercer rotor, otra vez a través de los tres rotores, hacia el panel de luces por un "camino" diferente.

De esta forma, el esquema de funcionamiento de la segunda versión de mi máquina Enigma podría ser el siguiente:


Los rotores se identificaban en las máquinas Enigma con números romanos y ahora la clave para cifrar los mensajes consiste en las tres letras que marcan la posición inicial de cada uno de ellos, es decir, si la clave es "A-B-C" el operador debe girar manualmente el primer rotor hasta hacer coincidir el carácter "A" con su indicador de posición, el segundo hasta que la letra "B" coincida con su indicador de posición y el tercero hasta que la "C" coincida con su respectivo indicador.

Realmente, las letras se identificaban en cada rotor con un número (A=1, B=2,...Z=26), por lo que en el caso anterior la clave sería en realidad "1-2-3".

Veamos un ejemplo de cifrado. Supongamos que queremos cifrar el mensaje "PRUEBA" con la clave "1-1-1". Para ello el operador debe girar cada rotor hasta hacer coincidir el carácter "A" con sus respectivos indicadores de posición y posteriormente teclear cada uno de los caracteres del texto en claro:


Y para descifrar, como ya sabemos, otro operador con una máquina igual debería girar cada rotor hasta hacer coincidir el carácter "A" con sus respectivos indicadores de posición y después teclear cada uno de los caracteres del texto cifrado:


Ahora mi segunda versión de la máquina Enigma ya se parece bastante a las utilizadas por el ejército alemán en la II Guerra Mundial, pero éstas eran aún más complejas, ya que tenían algunas características adicionales a las comentadas y les introdujeron nuevos componentes para hacer más difícil el criptoanálisis.

De estas características y componentes trataré en el siguiente post.

domingo, 15 de marzo de 2015

Criptografía (II): la máquina Enigma (I)

Posiblemente la máquina de cifrado más famosa del siglo XX fue la máquina Enigma, utilizada por el ejército alemán en la II Guerra Mundial.

Se trataba de una máquina electromecánica que automatizaba el proceso de cifrado y descifrado de mensajes utilizando un sistema de sustitución polialfabético con tal número de alfabetos involucrados que se consideraba la hacían invulnerable a los métodos de criptoanálisis conocidos hasta la fecha.

La máquina Enigma constaba de una unidad de cifrado de varios rotores (discos circulares planos), montados sobre un mismo eje, con 26 contactos eléctricos (uno por cada letra del alfabeto inglés) en cada una de las caras de cada rotor.

Además, también tenía una batería, un teclado similar al de una máquina de escribir y un panel de luces (una por cada letra del alfabeto inglés).

Para cifrar los mensajes se introducía mediante el teclado cada carácter del texto a cifrar y en el panel de luces se mostraba el carácter cifrado que le correspondía.

Al pulsar el operador en el teclado una letra del mensaje a cifrar la corriente eléctrica de la batería se dirigía hacia el contacto eléctrico correspondiente a la letra con la que se conectaba en la primera cara del primer rotor, desde ahí al contacto de la letra con la que se conectaba en su cara posterior y después hacia el de la letra con la que se conectaba en la primera cara del segundo rotor, y así sucesivamente hasta atravesar todos los rotores. A partir de ahí y a través de un reflector, en el camino de vuelta la corriente eléctrica atravesaba de nuevo todos los rotores (contactos de las letras conectadas en ambas caras) hasta la salida del primer de ellos, que, a su vez, se conectaba a una de las letras del panel de luces, diferente a la letra introducida en el teclado, que el operador apuntaba y después, una vez completado el proceso de cifrado de todo el mensaje, transmitía.

Ya hablaremos de la operación para descifrar los mensajes (que adelanto que era la misma, siempre y cuando se dispusiera de la misma máquina y se conociera la "clave"), pero hasta el momento queda claro, ¿no?. Pues, por favor, que alguien me lo explique que yo no he entendido nada :).

Pues bien, para intentar entenderlo me propongo diseñar la primera versión de mi propia máquina Enigma (comparto lo que voy aprendiendo sobre ella, pero igual tengo que ir haciendo correcciones a medida que vaya estudiando su funcionamiento o si algún lector de este humilde blog me indica que me he equivocado al exponerlo).

Considerando los cuatro elementos fundamentales que he comentado que la componían (aunque ya he dicho que había alguno más, e incluso se añadió algún otro para hacer todavía más complejo el criptoanális): una batería, un teclado, un rotor para la unidad de cifrado y un panel de luces, el esquema de funcionamiento para la primera versión de mi máquina Enigma podría ser el siguiente:

En mi primera versión de la máquina Enigma, con el rotor en su posición inicial, cada uno de los caracteres del alfabeto inglés (26) está conectado desde el teclado al contacto que le corresponde al mismo carácter en el rotor, éste al contacto de otro carácter del rotor, y este último a la luz del panel que corresponde a ese carácter.

De tal forma que si el operador pulsa en el teclado un carácter correspondiente al texto en claro se iluminará en el panel de luces el carácter conectado en el rotor al carácter del texto en claro. El carácter iluminado sería el carácter correspondiente al mensaje cifrado.

Además, en mi primera versión de esta máquina, el rotor puede ser girado manualmente por el operador hasta poner el carácter que desee en el indicador de posición. Ese carácter es la clave con la que se cifrará el mensaje.

Supongamos ahora que queremos cifrar el mensaje "PRUEBA" con la clave "A". Para ello, el operador giraría el rotor hasta hacer coincidir el carácter "A" con el indicador de posición, tal y como se muestra en la figura.

Veamos el proceso de cifrado:


Para descifrar el mensaje, otro operador con una máquina igual y conociendo la clave simplemente giraría el rotor hasta hacer coincidir el carácter "A" con el indicador de posición e introduciría mediante el teclado cada carácter del mensaje cifrado, tras cada uno de los cuales se iluminaría el carácter correspondiente al texto en claro. De la siguiente forma:


Hasta aquí mi primera versión de la máquina no es gran cosa (cifrado muy débil), ya que se trata de un sistema de sustitución monoalfabético (utiliza un solo alfabeto y, por tanto, cada carácter del texto a cifrar se sustituye siempre por el mismo carácter en el texto cifrado), es decir, sólo he conseguido automatizar los procesos de cifrado y descifrado del cifrado César y mejorarlo un poco, ya que el desplazamiento para sustituir una letra por otra no es fijo y, además, el desplazamiento concreto entre un determinado carácter y aquel que lo sustituye depende de la clave que se utilice (26 posibilidades).


Pero incluyamos una característica más a esta primera versión de mi máquina: con cada pulsación de una tecla el rotor gira un veintiseisavo (1/26) de una vuelta completa.

Veamos como funcionaría ahora el proceso de cifrado del mensaje "ROTOR" con la clave "A". Para ello, como ya sabemos, el operador debe girar el rotor hasta hacer coincidir el carácter "A" con el indicador de posición:


Como se ve en el ejemplo, la primera versión de mi máquina Enigma ya cifra utilizando un sistema de sustitución polialfabético (26 alfabetos), ya que cada letra no se sustituye siempre en el texto cifrado por el mismo carácter (en el ejemplo la primera "R" se sustituye por "T", mientras que la segunda se sustituye por "Z"), pero aún así sigue presentando un cifrado débil.

Y para descifrar, como siempre, otro operador con una máquina igual giraría el rotor hasta hacer coincidir la clave ("A") con el indicador de posición e introduciría mediante el teclado cada carácter del mensaje cifrado. De la siguiente forma:


En posteriores posts intentaré completar esta primera versión con nuevas características y elementos hasta aproximarme lo más posible a una máquina Enigma similar a las utilizadas por el ejército alemán en la II Guerra Mundial.

sábado, 7 de marzo de 2015

Criptografía (I): cifrado Vigenère y criptoanálisis Kasiski

Hace unos días mi amigo Iñaki Regidor (@Inaki_Regidor), a quien dedico esta entrada :), compartió en las redes sociales un post titulado "Criptografía: el arte de esconder mensajes" publicado en uno de los blogs de EiTB.

En ese post se explican ciertos métodos clásicos para cifrar mensajes, entre ellos el cifrado de Vigenère, y, al final del mismo, se propone un reto consistente en descifrar un mensaje, lo que me ha animado a escribir este post sobre el método Kasiski para atacar un cifrado polialfabético (conociendo la clave descifrar el mensaje es muy fácil, pero lo que contaré en este post es la forma de hacerlo sin saberla).

El mensaje a descifrar es el siguiente:

LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC

Como ya he dicho el método de Vigenère es un sistema de sustitución polialfabético, lo que significa que, al contrario que en un sistema de sustitución monoalfabético, cada carácter del texto a cifrar NO se sustituye siempre por el mismo carácter en el texto cifrado, es decir, es un sistema en el que hay implicados varios alfabetos y dependiendo de ciertas circunstancias se aplica uno u otro.

Se trata también de un sistema de cifrado simétrico, es decir, el emisor del mensaje lo cifra utilizando una clave y el receptor debe descifrarlo utilizando esa misma clave. Por tanto, el emisor y el receptor se tienen que poner de acuerdo en la clave a utilizar.

Antes de pasar a resolver el problema planteado veamos muy brevemente como funciona el cifrado de Vigenère.

1º) Se basa en la siguiente tabla:


2º) Por ejemplo, para cifrar el mensaje "EJEMPLO CIFRADO" con la clave "CLAVE", ponemos la clave encima del texto a cifrar repitiendo la clave tantas veces como haga falta hasta cubrir completamente el texto a cifrar, de la siguiente manera:


Y ahora para obtener el texto cifrado sólo queda sustituir cada carácter del texto a cifrar por el carácter de la tabla anterior que se encuentra en la intersección entre la columna que corresponde al carácter a cifrar y la fila correspondiente al carácter de la clave que está justo encima, vamos como en el juego de los barcos.

Por ejemplo: a la primera "E" del texto a cifrar, que tiene justo encima la "C" de la clave, le correspondería como carácter en el texto cifrado la letra "G". Es decir:


Si repetimos esto para cada uno de los caracteres del texto a cifrar obtenemos el siguiente mensaje cifrado o criptograma:


3º) Fácil, ¿no?. Pues para descifrar sólo tenemos que poner la clave encima del texto cifrado repitiendo la clave tantas veces como haga falta hasta cubrir completamente el texto cifrado, de la siguiente manera:


Y ahora para descifrar el texto sólo queda sustituir cada carácter del texto cifrado por el carácter de la columna que le corresponde al carácter cifrado en la fila correspondiente al carácter de la clave que está justo encima.

Por ejemplo: a la letra "G" del texto cifrado, que tiene justo encima la "C" de la clave, le correspondería como carácter en el texto descifrado la letra "E". Es decir:


Si repetimos esto para cada uno de los caracteres del texto cifrado obtenemos el siguiente mensaje descifrado o texto en claro:



Hasta aquí todo muy fácil; conociendo la clave ningún problema para descifrar el mensaje, pero supongamos que interceptamos un mensaje de este tipo y queremos descifrarlo sin saber la clave: ¿es posible?.

Pues sí, siempre que el mensaje sea lo suficientemente largo para que sea eficaz el método de criptoanálisis aplicado a los cifrados de sustitución polialfabéticos al que he hecho referencia al principio de este post (método Kasiski).

Volvamos entonces al mensaje que se nos propone descifrar en el post titulado "Criptografía: el arte de esconder mensajes". El siguiente:

LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC

a) Lo primero que debemos hacer para descifrarlo sin conocer la clave es intentar averiguar cuál es la longitud de la misma.

Comentar que Kasiski se percató de la existencia de secuencias de caracteres repetidos en el texto cifrado, lo cual significaba casi con toda probabilidad que dichas secuencias no sólo eran la misma antes del cifrado sino que además la clave debía coincidir en la misma posición, por lo que lo primero que debemos hacer es detectar secuencias de letras cifradas repetidas.

Para nuestro criptograma (a simple vista, aunque esto sería mucho más fácil con un pequeño programa de ordenador) las siguientes:

LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC

Es decir:

- 3 cadenas "UDV" separadas por 8 y 32 posiciones.
- 2 cadenas "MUE" separadas por 4 posiciones.
- 2 cadenas "MUO" separadas por 108 posiciones.

Luego podemos pensar que el número de caracteres de la clave puede ser el mcd(4, 8, 32, 108) = 4. Es decir, la longitud más probable de la clave es 4, que es el máximo común divisor o mayor número entero que divide a todos estos números (posiciones) sin dejar resto.

b) Una vez que hemos averiguado la longitud de la clave (L), si no nos hemos equivocado, lo siguiente que tenemos que hacer es dividir el criptograma en L subcriptogramas (en nuestro caso 4), ya que estos han sido cifrados por una misma letra de la clave, a partir de lo que estaríamos en disposición de realizar un ataque simple de tipo estadístico monoalfabético.


Por tanto:

- El primer subcriptograma (CA) contendría los siguientes caracteres del criptograma: 1º, 5º, 9º, etc.

En nuestro caso:


- El segundo subcriptograma (CB) contendría los siguientes caracteres del criptograma: 2º, 6º, 10º, etc.

En nuestro caso:


- El tercer subcriptograma (CC) contendría los siguientes caracteres del criptograma: 3º, 7º, 11º, etc.

En nuestro caso:


- Y, finalmente, el cuarto subcriptograma (CD) contendría los siguientes caracteres del criptograma: 4º, 8º, 12º, etc.

En nuestro caso:


c) Ahora estamos ya en disposición de realizar un ataque simple de tipo estadístico monoalfabético.


A partir de aquí y considerando que la posición relativa de la letra "A" es el valor 0, la letra "E" está 4 espacios a la derecha de la "A" y la letra "O" está 11 de la letra "E"buscaremos en cada subcriptograma (Ci) caracteres frecuentes que cumplan con esa distribución: 0, +4, +11 mod 27:

- Para CA elegimos RVG (2, 8, 2), luego la letra clave sería la "R".

- Para CB elegimos AEO (5, 5, 1), luego la letra clave sería la "A".

- Para CC elegimos UYJ (11, 6, 1), luego la letra clave sería la "U".

- Para CD elegimos LOZ (3, 2, 3), luego la letra clave sería la "L".

Con la clave = "RAUL", utilizando la tabla y siguiendo los pasos para descifrar este tipo de mensajes indicados en este post, obtenemos el siguiente texto plano a partir del texto cifrado:

UNASEMANAMASELREGALODELPROBLEMADEMATEMATICASESELLIBROGARDNERPARAPRINCIPIANTESQUESESORTEARAENTRETODASLASPERSONASQUEDESCIFRENESTEMENSAJEFIRMADORAUL

Es decir:

UNA SEMANA MAS EL REGALO DEL PROBLEMA DE MATEMATICAS ES EL LIBRO GARDNER PARA PRINCIPIANTES QUE SE SORTEARA ENTRE TODAS LAS PERSONAS QUE DESCIFREN ESTE MENSAJE FIRMADO RAUL

Nota: Como se ha incluido un comentario en este post en el que me plantean ciertas dudas sobre el último paso indicado, y he recibido por otras vías dudas en el mismo sentido, he escrito un nuevo post en el que trato de contar mejor la última parte del criptoanálisisCriptografía (XIX): cifrado Vigenère y criptoanálisis Kasiski (II).