viernes, 25 de septiembre de 2015

Reto: criptoanálisis cifrado ADFGVX (II)

En el post anterior planteé un reto para resolver el criptoanálisis de mensajes cifrados con el método ADFGVX y en éste pongo la solución del primer paso y planteo, con las pistas necesarias para resolverlo, el siguiente paso a dar.

La pregunta para resolver el primer paso era la siguiente:

¿Cuál es la longitud de la clave empleada para cifrar los mensajes y la disposición de los dígrafos de los dos primeros mensajes cifrados después de la transposición de las columnas?.

Decía que para resolverlo había que identificar fragmentos comunes en los mensajes, ya que estos nos darían una pista muy importante sobre la longitud de la clave.

Veamos, por tanto, esas secuencias de caracteres comunes entre los mensajes:

Primer mensaje cifrado:

GGGGFXGDVXDDGADDFDFFFAGAXDDXXAGDDDDADADXGDAAXDXXAGXXVGDDAGXXGDFAXGDAGGGDXFGADDFAXFAGGDDAAGDXAXDFXGAXGDXGDADGVDXGDFADXGDXVXGGDDVGGGDXGFDFAFFFGDADDGVAVVVGDGDV

Longitud: 156.

Segundo mensaje cifrado
:

GDXVXGGDDVGGGGDAGGGDXFGADDXGDAAXDXXAGXXADDGVAVVVGDGDVFAXFAGGDDAAGDDXGFDFAFFFGDAXADDFDFFFAGAXDGGDDAGXXGDFAXAXXAGDDDDADADDADGVDXGDFADXXAXDFXGAXGDXGGGGGFXGDVXDDG

Longitud: 158.

Tercer mensaje cifrado:

FDDGDGAXDGGDAXGXXDAGADDADDAVDADVXXXXXAAVAVFVGAXXAFGFDFGADDXDDDXDAFGGDGFFFDFDFAXGDADFXDFVGDXXGXVDAAXGGGAADDXGADGDAAVGXDAAAGDFDDFADG

Longitud: 130.

Cuarto mensaje cifrado:

XGGGXDADAXAXXDGXAXDXGADDAXGDDAFAFFADXAXXXXXXXDGDDDAAGDAXAAAXAAAGDDDAXAVAGVGDADDGVXFGGDGXAXXGFFDXDGFFADADGDADFFXDDDGGGGGFGADXDAXDGVGAFDAFADDXXAFDGGAXAGVGFFAVDDFDAFAGXADADGXVGAVAFGXAXAGGDDVGDXXAGDDDXGDDDADDFVFAXGDDAAGXGAXXXDXXAFFDDGDDFXFAGAVVAADGDD

Longitud: 246.

Quinto mensaje cifrado:

DVDXVAXAVDADAFADXFDGXGFDAAGFDFFGDAXDVXGAGXDADDDADGDVAXDGXVDADDDGAVXDDGFXFDFDGGXDXAXVGAXDGFXDFFGFFXDFDGDXGXGFAGFXDXGAGFFGADDGFVADDADDFGAADAGDAAAAAXAAXAXGGGGXXVGGDADADFXGXGDDADFGDXFXDXDGXDFXFAXGXDDGAXAGFAAAVGGG

Longitud: 208.

Sexto mensaje cifrado:

GDDGXVAAFGFGAADDDXDXDDVFDADDDDAXAADXDAXFDGAXADFFAGDDXFXFDFDXDDGDDFXDXFXGXVVAAVGDAAFFAFAFDFVXAXAGAA

Longitud: 98.

Como se observa, el primero y segundo mensajes presentan gran cantidad de fragmentos comunes entre ellos y, aunque existen otras coincidencias entre otros mensajes, estos son ya suficientes para contestar a la primera pregunta.

Ambos mensajes parecen tener 12 columnas, por lo que ésta sería la longitud de la clave. Además, las coincidencias entre estos dos mensajes y el quinto, esta vez al final de los mensajes, y que también parece tener 12 columnas, confirmaría la hipótesis de que la clave tiene una longitud de 12 caracteres.

El primero de los mensajes tiene una longitud de 156 caracteres y, por tanto, tendría 12 columnas de 13 caracteres cada una de ellas (156 / 12 ---> Cociente = 13 y Resto = 0), siendo la disposición de los dígrafos después de la transposición de las columnas la siguiente:

PRIMER MENSAJE
1 2 3 4 5 6 7 8 9 10 11 12
G A D X V G F X D G D D
G D X G G D A A A D X D
G D X D D A X X D X G G
G F A A D G F D G V F V
F D G A A G A F V X D A
X F D X G G G X D G F V
G F D D X D G G X G A V
D F D X X X D A G D F V
V A D X G F D X D D F G
X G A A D G A G F V F D
D A D G F A A D A G G G
D X A X A D G X D G D D
G D D X X D D G X G A V

Mientras que el segundo mensaje tiene una longitud de 158 caracteres y, por tanto, tendría 2 columnas de 14 caracteres y 10 de 13 caracteres (158 / 12 ---> Cociente = 13 y Resto = 2), siendo la disposición de los dígrafos después de la transposición de las columnas la siguiente (las dos columnas largas son fácilmente identificables si consideramos que es lógico pensar que la diferencia entre ambos, dos mensajes muy esteriotipados, está al inicio de los mismos y, sobretodo, teniendo en cuenta las coincidencias que este segundo mensaje presenta al final con el quinto):

SEGUNDO MENSAJE
1 2 3 4 5 6 7 8 9 10 11 12
G G X A F D X G A D X G
D D G D A X A G X A A G
X A D D X G D D X D X G
V G A G F F D D A G D G
X G A V A D F A G V F F
G G X A G F D G D D X X
G D D V G A F X D X G G
D X X V D F F X D G A D
D F X V D F F G D D X V
V G A G A F A D A F G X
G A G D A G G F D A D D
G D X G G D A A A D X D
G D X D D A X X D X G G
V D

Vale, con esos dos primeros mensajes tan parecidos, casi idénticos, determinar la longitud de la clave no es tarea muy difícil, pero... ¿podríamos haberla averiguado sin mensajes que presenten tantos fragmentos comunes e incluso sin que tuvieran fragmentos en común?.

Ya comentaba en un post anterior que Painvin no estableció un método general de solución al cifrado ADFGVX (bastante hizo este genio con descifrar algunos mensajes en tan poco tiempo; tarea en absoluto fácil), sino que sus labores de criptoanálisis se centraron en mensajes muy esteriotipados, pero William Friedman sí lo hizo posteriormente, muy posteriormente. Lo que digo no para quitar ningún mérito, ni a uno (por la premura de tiempo que tuvo, descifrar los mensajes en el menor tiempo posible era vital), ni a otro (método elegante donde los haya).

Para ello, sigamos el siguiente razonamiento según Friedman:

a) En primer lugar, para averiguar si la longitud de la clave es par o impar, consideremos que si la clave tiene un número par de caracteres, después de la transposición de las columnas, los caracteres de cada columna serán todos ellos sólo de inicio o sólo de final de los dígrafos antes de la transposición; mientras que si la longitud de la clave es impar los caracteres de cada columna contendrán alternativamente un carácter de inicio y otro de final, o viceversa.

Por tanto, suponiendo que no se está utilizando una clave con más de 25 caracteres, en nuestro reto podemos afirmar que:

- Los primeros seis caracteres del primer mensaje cifrado (longitud 156) estarán en la misma columna: GGGGFX.
- Los primeros seis caracteres del segundo mensaje cifrado (longitud 158) estarán en la misma columna: GDXVXG.
- Los primeros cinco caracteres del tercer mensaje cifrado (longitud 130) estarán en la misma columna: FDDGD.
- Los primeros nueve caracteres del cuarto mensaje cifrado (longitud 246) estarán en la misma columna: XGGGXDADA.
- Los primeros ocho caracteres del quinto mensaje cifrado (longitud 208) estarán en la misma columna: DVDXVAXA.
- Los primeros tres caracteres del sexto mensaje cifrado (longitud 98) estarán en la misma columna: GDD.

De lo indicado anteriormente se deduce que los caracteres situados en posiciones impares en una misma columna sólo aparecerán con similar frecuencia a sus respectivos caracteres en posiciones pares si, y sólo si, la longitud de la clave es par.

Por tanto, si los situamos en dos tablas de frecuencias, una para los caracteres 1º, 3º, 5º,... y otra para 2º, 4º, 6º, ..., ambas tablas mostrarán frecuencias similares para los caracteres si la longitud de la clave es par o diferentes si es impar.

En nuestro caso:

Tabla de frecuencias 1º, 3º, 5º,...

A D F G V X
2 5 2 5 1 5 20

Tabla de frecuencias 2º, 4º, 6º,...

A D F G V X
2 5 0 6 2 2 17

Lógicamente, cuantos más mensajes cifrados se tengan mejor (en nuestro reto sólo disponemos de seis), pero la similitud o diferencia entre ambas tablas comienza a percibirse con un número de caracteres no muy elevado en cada una de ellas.

b) Después, para averiguar la longitud concreta de la clave, sin tener en cuenta los posibles fragmentos comunes que puedan aparecer en los mensajes cifrados, siguiendo este mismo razonamiento:

b.1) Si la longitud de la clave es par, como todos los caracteres de una misma columna serán todos ellos de inicio o final de los dígrafos antes de la transposición, habrá que detectar en qué puntos de los mensajes cifrados cambia la frecuencia de aparición de los mismos, ya que dicha frecuencia es diferente en función de si los caracteres son de inicio o de final, o, lo que es lo mismo, habrá que identificar el final de una columna y el comienzo de la siguiente.

b.2) Mientras que si la longitud de la clave es impar, como los caracteres de una misma columna serán alternativamente de inicio y final de los dígrafos antes de la transposición, o viceversa, lo que habrá que hacer es detectar en qué puntos de los mensajes cifrados cambia la frecuencia de los caracteres situados en posiciones impares (1º, 3º, 5º,...) y, al mismo tiempo, de los caracteres en posiciones pares (2º, 4º, 6º,...), lo que también indicará el final de una columna y el inicio de la siguiente.

Sin embargo, esta solución general, que creo que tendría éxito en la mayoría de las ocasiones, queda totalmente anulada si el criptógrafo de turno es consciente de que la debilidad de este sistema radica en la frecuencia de aparición de los diferentes caracteres en función de si se trata de un carácter de inicio o final de los dígrafos antes de su transposición.

Es decir, normalmente, dicha frecuencia es muy o bastante diferente si un carácter es de inicio con respecto a la de ese mismo carácter si es de final, pero si, consciente de esta circunstancia, el criptógrafo "aplana" o hace que las frecuencias de los caracteres sean muy similares en la tabla a partir de la que se obtienen los dígrafos antes de la transposición, con independencia de que estos se sitúen al principio o final de los dígrafos, creo que poco o absolutamente nada conseguiríamos con este método.

Pero volvamos a nuestro reto (si es el caso y le interesa a alguien, en un post posterior pondré un ejemplo del método general de solución): el siguiente paso consiste en deshacer la transposición de las columnas, es decir:

Considerando que el orden de la columnas después de su transposición es el que hemos determinado anteriormente (del 1 al 12), la pregunta para resolver el siguiente paso es:

¿Cuál es el orden de las columnas antes de su transposición? o, lo que es lo mismo, ¿Cuál es el orden de los caracteres de la clave antes de su ordenación alfabética?.

Para averiguarlo, en primer lugar, recordar que, conforme a este sistema, las columnas largas (de más caracteres) que hemos obtenido deben ir necesariamente antes de las cortas previamente a la transposición de las columnas.

Iré poniendo más pistas para la ordenación de las columnas en forma de comentarios a esta entrada, y en el siguiente post pondré la solución y plantearé el siguiente paso.

5 comentarios:

  1. Como digo en el post, las columnas 4 y 7 (las dos columnas largas del segundo mensaje) deben ir en las posiciones más a la izquierda antes de la transposición, es decir, se corresponden con los dos primeros caracteres de la clave antes de su ordenación alfabética, aunque no necesariamente en ese orden (el orden correcto puede ser 4-7 o 7-4).

    PISTA: ¿Podemos identificar en otros mensajes cifrados más columnas largas e ir situándolas, aunque en un orden aproximado, entre las columnas más a la izquierda antes de la transposición?.

    ResponderEliminar
  2. Siguiendo la pista indicada en el comentario anterior: las otras dos columnas largas del quinto mensaje, 3 y 5, son fácilmente identificables por sus coincidencias con el primero y segundo mensajes, y, por tanto, son las dos siguientes más a la izquierda antes de las transposición de las columnas, es decir, se corresponden con el tercer y cuarto caracteres de la clave antes de su ordenación alfabética, aunque no necesariamente en ese orden.

    Hasta el momento, sabemos que los dos primeros caracteres de la clave antes de su ordenación alfabética se corresponden con las columnas 4 y 7 después de la transposición, y los dos siguientes con las columnas 3 y 5, aunque en ambos casos no necesariamente en el orden indicado. Fijemos provisionalmente estas columnas como los primeros caracteres de la clave antes de su ordenación alfabética de la siguiente manera: 4-7-3-5.

    Considerando los fragmentos comunes de los mensajes 3 y 4 podríamos intentar identificar más columnas largas para ir situándolas a continuación, pero creo que hay riesgo de equivocarnos en algunas.

    Por tanto sigamos un método alternativo teniendo en cuenta las grandes coincidencias de fragmentos cifrados entre los dos primeros mensajes y que parecen casi idénticos.

    (La pista en el siguiente comentario).

    ResponderEliminar
  3. PISTA: el primer mensaje tiene 156 caracteres de longitud y el segundo 158. Esos dos caracteres de diferencia, hacen que, a partir de que aparezcan en el segundo mensaje, ya comentaba que parece lógico pensar que en dos mensajes tan esteriotipados figuren al inicio, los caracteres del segundo mensaje antes de la transposición estén desplazados dos caracteres a la derecha con respecto al primero.

    Fijémonos ahora en las cuatro columnas que hemos marcado como las correspondientes a los cuatro primeros caracteres de la clave antes de su transposición, 4-7-3-5 (aunque provisionalmente porque el orden de cada uno de estos pares de columnas podría ser ése o el contrario):

    Los caracteres de la columna 4 del primer mensaje (“XGDAAXDXXAGXX“) aparecen en la columna 3 del segundo mensaje y los caracteres de la columna 7 del primer mensaje (“FAXFAGGDDAAGD”) figuran en la columna 5 del segundo. Lo que coherentemente con lo indicado anteriormente (caracteres del segundo mensaje desplazados dos posiciones a la derecha antes de la transposición con respecto al primero), si la columna 4 se correspondiera con el primer carácter de la clave antes de su ordenación alfabética la columna 3 sería necesariamente el tercero, y si la columna 7 se correspondiera con el segundo la columna 5 sería necesariamente el cuarto. Podría ser al revés y también sería coherente, se decir: si la columna 7 fuera el primero la 5 sería el tercero, y la 4 sería el segundo y la 3 sería el cuarto.

    Siguiendo este razonamiento las peculiares características de los dos primero mensajes nos pueden revelar las columnas que corresponden a los dos siguientes caracteres de la clave antes de su ordenación alfabética (aunque no necesariamente en ese orden), de los dos siguientes, etc.

    ResponderEliminar
  4. Tras la pista del comentario anterior, siguiendo ese razonamiento, podemos ir fijando los siguientes pares de columnas como las correspondientes a los siguientes caracteres de la clave antes de su ordenación:

    Recordar que, hasta el momento, habíamos fijado las columnas 4 y 7 como correspondientes al 1º y 2º caracteres de la clave antes de su transposición (no necesariamente en ese orden) y las columnas 3 y 5 como el 3º y 4º caracteres de la clave antes de su transposición (aunque tampoco necesariamente en ese orden).

    Pues bien:

    1.- Los caracteres "XXAGDDDDADAD" que aparecen en la columna 3 del primer mensaje también aparecen en la columna 9 del segundo mensaje, y los caracteres "GDDAGXXGDFAX" de la columna 5 del primer mensaje figuran en la 8 del segundo mensaje. Por tanto, las columnas 9 y 8 se corresponderían con los caracteres 5º y 6º de la clave antes de su transposición (aunque tampoco necesariamente en ese orden).

    2.- Los caracteres "DADGVDXGDFADX" que aparecen en la columna 9 del primer mensaje también aparecen en la columna 10 del segundo mensaje, y los caracteres "XAXDFXGAXGDXG" de la columna 8 del primer mensaje figuran en la 11 del segundo mensaje. Por tanto, las columnas 10 y 11 se corresponderían con los caracteres 7º y 8º de la clave antes de su transposición (aunque tampoco necesariamente en ese orden).

    3.- Los caracteres "GDXVXGGDDVGGG" que aparecen en la columna 10 del primer mensaje también aparecen en la columna 1 del segundo mensaje, y los caracteres "DXGFDFAFFFGDA" de la columna 11 del primer mensaje figuran en la 6 del segundo mensaje. Por tanto, las columnas 1 y 6 se corresponderían con los caracteres 9º y 10º de la clave antes de su transposición (aunque tampoco necesariamente en ese orden).

    4.- Los caracteres "GGGGFXGDVXDDG" que aparecen en la columna 1 del primer mensaje también aparecen en la columna 12 del segundo mensaje, y los caracteres "GDAGGGDXFGADD" de la columna 6 del primer mensaje figuran en la 2 del segundo mensaje. Por tanto, las columnas 12 y 2 se corresponderían con los caracteres 11º y 12º de la clave antes de su transposición (aunque tampoco necesariamente en ese orden).

    Por tanto, sólo hay dos posibilidades para el orden de las columnas antes de su transposición:

    4-7-3-5-9-8-10-11-1-6-12-2.

    o

    7-4-5-3-8-9-11-10-6-1-2-12.

    ¿Alguna idea para determinar el orden correcto entre estas dos posibilidades o pasamos directamente al siguiente paso probando cada una de ellas (algo que tampoco costaría mucho?.

    ResponderEliminar
  5. PISTA: en este caso y una vez obtenidas esas dos posibilidades, no es necesario determinar cuál de los dos es el orden correcto, ya que creo que utilizando indistintamente uno u otro conseguiríamos descifrar los mensajes realizando un análisis de frecuencias de lo dígrafos resultantes.

    En el siguiente post pondré el resultado de este segundo paso (deshacer la transposición de las columnas) y plantearé el siguiente (análisis de frecuencias de los dígrafos una vez desecha la transposición de las columnas).

    ResponderEliminar