domingo, 23 de agosto de 2015

Criptografía (XIV): cifrado ADFGVX y criptoanálisis Painvin (I)

En el primer post de esta serie sobre criptografía comenté el cifrado de Vigenère y el método Kasiski para atacar un cifrado polialfabético.

Este método de criptografía clásica para cifrar mensajes aparecía en un post titulado "Criptografía: el arte de esconder mensajes", publicado en uno de los blogs de EiTB, y fue lo que me animó a escribir esa primera entrada.

Pues bien, también en la entrada del citado blog se hablaba del cifrado ADFGVX, empleado por el ejército alemán a finales de la I Guerra Mundial, y en este post explico cómo se cifraban los mensajes utilizando ese método y en el siguiente las labores de criptoanálisis realizadas por Georges Painvin para conseguir descifrarlos.

Este método, inventado por el coronel Fritz Nebel, debe su curioso nombre a que en el texto cifrado sólo aparecen esas seis letras, que fueron elegidas porque son muy diferentes entre sí en código morse y eso evitaba errores al transmitir los mensajes.

El método de cifrado original se llamaba ADFGX (la letra "V" se incluyó posteriormente) y se basaba en una tabla de 5 filas y 5 columnas. En las 25 cuadrículas (5 x 5) de esa tabla se colocaban de forma aleatoria las 26 letras del alfabeto inglés (como hay una letra más que cuadrículas, la "I" y la "J" compartían una misma casilla), de la siguiente manera:
Evidentemente, tanto el emisor como el receptor debían utilizar la misma tabla.  

Veamos un ejemplo de cifrado utilizando este método. Para cifrar el mensaje "EJEMPLO CIFRADO" utilizando como clave la palabra "CLAVE" daríamos los dos siguientes pasos:

1º) En primer lugar sustituiríamos cada uno de los caracteres del texto a cifrar por el dígrafo o grupo de dos letras que le corresponde en la tabla anterior, es decir, cada letra del texto en claro se sustituye por la letra de la fila y de la columna que corresponden a la cuadrícula en la que está.

En el ejemplo: la "E" del texto a cifrar se sustituiría por "FF":
La "J" se sustituiría por "AD" y así  sucesivamente. De esta forma obtendríamos lo siguiente:
Si nos quedáramos aquí el cifrado sería muy débil, ya que hasta ahora se trataría de un sistema de sustitución monoalfabético (cada letra del texto a cifrar se sustituiría siempre por el mismo dígrafo en el texto cifrado) que no resistiría un análisis de frecuencias realizado con poco esfuerzo, por lo que era necesario dar un paso adicional antes de obtener el texto cifrado definitivo.

2º) El segundo paso consistía en introducir una palabra clave para transponer o cambiar de orden las columnas con objeto de alterar los dígrafos e imposibilitar así un análisis de frecuencias.

En nuestro ejemplo utilizaremos como clave la palabra "CLAVE" y actuaríamos como se indica a continuación.

Debajo de nuestra palabra clave iríamos colocando en una primera fila cada uno de los caracteres obtenidos en el paso anterior y tras completar todos los caracteres de la clave continuaríamos en la fila siguiente, de la siguiente forma:
Ahora ordenaríamos la columnas por el orden alfabético de los caracteres de la clave:
Y, finalmente, para obtener el texto cifrado leeríamos las columnas de izquierda a derecha y de arriba a abajo, de la siguiente manera:
Con lo que obtendríamos:

Obviamente, para descifrar el mensaje bastaría con seguir estos mismos pasos en sentido inverso. Es decir:

1º) Ordenaríamos nuestra palabra clave por el orden alfabético de sus caracteres y justo debajo iríamos colocando en una primera columna y de arriba abajo cada uno de los caracteres del texto cifrado, y tras completar un número de caracteres igual al cociente que resulte de dividir la longitud del mensaje cifrado (en nuestro caso 28) entre la longitud de la clave (en nuestro caso 5) continuaríamos en la columna siguiente (en nuestro ejemplo el cociente de 28 / 5 es 5).

Pero, tal  y cómo se observa en el segundo paso del cifrado, después de colocar debajo de nuestra palabra clave los caracteres obtenidos en el primer paso quedan dos huecos, lo que hace que después de transponer las columnas conforme al orden alfabético de los caracteres de la clave no todas las columnas tengan el mismo número de caracteres que el cociente que hemos calculado (si se dan los citados huecos algunas de ellas tendrán un carácter más, en nuestro ejemplo algunas de ellas tendrán 6 caracteres en lugar de 5). Si no tuviéramos en cuenta que se pueden producir esos huecos no se podría obtener el mensaje en claro correcto.

¿Cómo podemos saber si en el proceso de cifrado se han producido huecos y, en ese caso, que columnas tienen un carácter más que el cociente que resulta de dividir la longitud del mensaje cifrado entre la longitud de la clave?. Pues muy fácil, simplemente teniendo en cuenta el resto de dicha división:

- Si el resto es 0 no se han producido huecos en el proceso de cifrado y por tanto todas las columnas tienen el mismo número de caracteres que el cociente (en nuestro ejemplo 5).

- Si el resto es distinto de 0 sí se han producido huecos y el número de columnas con un carácter más que el cociente será precisamente igual al resto (en nuestro ejemplo el resto de 28 / 5 es 3, lo que nos indica que hay tres columnas de 6 caracteres y, por tanto, dos columnas de 5 caracteres).

Las columnas que tienen un carácter más que el cociente son las correspondientes a los "n" primeros caracteres de la clave (donde "n" es igual al resto).

En resumen y para nuestro ejemplo:

- Longitud del mensaje cifrado = 28.
- Longitud de la clave = 5.
- 28 / 5 ---> cociente = 5; resto = 3.
- Debajo de los tres primeros caracteres de la clave ("C", "L" y "A") hay que colocar  6 caracteres (cociente + 1) del texto cifrado. 
- Debajo del resto de caracteres de la clave ("V" y "E") hay que colocar 5 caracteres (cociente) del texto cifrado.

Con lo que se obtendría la ubicación correcta de los caracteres individuales de los dígrafos, es decir, la disposición que se obtuvo en el último paso del cifrado:
Después ordenaríamos las columnas conforme a la clave original y leeríamos fila a fila los caracteres situados debajo de la misma:
Con lo que obtendríamos los siguientes dígrafos:


FF AD FF DG GF AF XF GG AD FG DX DD DF XF

Y ahora ya, para completar el descifrado del mensaje acudiríamos a la tabla en la que se basa este método y que habríamos pactado con el emisor del mensaje, y sustituiríamos cada dígrafo por la letra que se encuentra en la intersección de la fila correspondiente a su primer carácter y la columna de su segundo carácter.

En nuestro ejemplo: el dígrafo "FF" se sustituiría por la "E" para obtener la letra del texto en claro:
El dígrafo "AD se sustituiría por la "J" y así  sucesivamente. De esta forma obtendríamos el siguiente texto en claro:
Lo alemanes empezaron a utilizar el cifrado ADFGX en marzo de 1918 y en junio de ese mismo año introdujeron la letra "V " en los dígrafos. El método para cifrar y descifrar los mensajes era el mismo, pero ahora la tabla tenía 6 filas y 6 columnas que contenían las 26 letras del alfabeto inglés y los 10 dígitos (del 0 al 9) dispuestos de forma aleatoria, y pasó a conocerse como ADFGVX

Como hemos visto este método combinaba la sustitución y la transposición, y tanto el emisor como el receptor debían utilizar la misma tabla y conocer la clave para cifrar y descifrar los mensajes.


La importancia y urgencia de descifrar los mensajes alemanes venían dadas porque el ejercito alemán se encontraba ya a escasos 60 kilómetros de París y se disponía a lanzar su ofensiva final hacia la capital francesa.

Para los franceses era vital averiguar por dónde se produciría el ataque para concentrar sus fuerzas en ese punto y poder así contener el avance alemán, para lo que el descifrado de los mensajes podía ser fundamental; tarea a la que se puso en cuerpo y alma el capitán Georges Painvin. Lo que consiguió y dio a los franceses una ventaja decisiva para derrotar a los alemanes y evitar la caída de París. Pero, ¿cómo lo hizo?. Sobre este tema trataré en un próximo post.

No hay comentarios:

Publicar un comentario