lunes, 11 de julio de 2016

Criptografía (XXI): cifrado Vigenère y criptoanálisis IC (II)

Decía en el post anterior que iba a poner un ejemplo de un ataque basado en el Índice de Coincidencia (ICa un criptograma cifrado con un sistema de sustitución polialfabética con clave periódica, método de criptoanálisis desarrollado por William Friedman en 1920. Pues vamos allá con el ejemplo.

Supongamos que interceptamos el siguiente mensaje cifrado:
Longitud texto cifrado = 426.

Y supongamos también que creemos que, con casi toda certeza, el texto en claro está escrito en español y que sospechamos que se ha empleado para cifrarlo un sistema de sustitución monoalfabética o uno de sustitución polialfabética con clave periódica. Veamos que información podría aportarnos el IC.

En primer lugar recordar que el IC que se espera obtener de un texto escrito en español, o lo que es lo mismo la probabilidad de que dos letras tomadas al azar de un texto escrito en dicho idioma resulten ser iguales, debe estar próximo a 0,0775 y que en un sistema de cifrado de sustitución monoalfabética este IC se mantiene en el texto cifrado, mientras que si se emplea un sistema de cifrado de sustitución polialfabética éste será significativamente menor en el texto cifrado que en el texto en claro.

Pues bien, con la fórmula y siguiendo el procedimiento indicados en el post anterior obtenemos los siguientes resultados para cada una de las posibles longitudes de la clave:

- Longitud de la clave (t) = 1:

Se trataría realmente de un cifrado de sustitución monoalfabética, ya que todos los caracteres del texto en claro habrían sido cifrados por el alfabeto correspondiente al único carácter de la clave, por lo que calculamos el IC correspondiente a todo el texto cifrado (C).
IC(C) = 0,0487
Donde:
C: criptograma.

Tal y como se observa, este IC está bastante alejado del que se espera encontrar en un texto cifrado utilizando una sustitución monoalfabética, o lo que es lo mismo empleando una sustitución polialfabética con un período o longitud de la clave (t) igual a 1, por lo que podríamos descartar esta longitud de la clave.

Longitud de la clave (t) = 2:

Calculamos el IC de los dos subcriptogramas cuyos caracteres del texto en claro habrían sido cifrados con el alfabeto correspondiente a cada uno de los caracteres de la clave, respectivamente. En cada uno de ambos subcriptogramas el cifrado sería una sustitución monoalfabética.

Por tanto, calculamos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c3c5c7..., c425) = IC(GTIF... H).
IC(C2) = IC(c2c4c6c8,..., c426) = IC(DZUN... Q).

Obteniéndose como resultado:
IC(C1) = 0,0469
IC(C2) = 0,0504

Por tanto, en este caso también podemos descartar un cifrado polialfabético con periodo o longitud de la clave (t) igual a 2, ya que ambos IC están alejados del que se espera encontrar en un texto cifrado utilizando sustitución monoalfabética (en cada uno de los dos subcriptogramas).

Longitud de la clave (t) = 3:

De forma análoga que en el caso anterior calculamos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c4c7c10..., c424) = IC(GZFN... V).
IC(C2) = IC(c2c5c8c11,..., c425) = IC(DING... H).
IC(C3) = IC(c3c6c9c12,..., c426) = IC(TUZW... Q).

Obteniéndose como resultado:
IC(C1) = 0,0495
IC(C2) = 0,0460
IC(C3) = 0,0489

Por tanto, nuevamente podemos descartar un cifrado polialfabético con periodo o longitud de la clave (t) igual a 3, ya que el IC de los tres subcriptogramas está lejos del que se espera encontrar en un texto cifrado utilizando sustitución monoalfabética (en cada uno de los tres subcriptogramas).

Longitud de la clave (t) = 4:

Calculamos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c5c9c13..., c425) = IC(GIZP... H).
IC(C2) = IC(c2c6c10c14,..., c426) = IC(DUNG... Q).
IC(C3) = IC(c3c7c11c15,..., c423) = IC(TFGS... R).
IC(C4) = IC(c4c8c12c16,..., c424) = IC(ZNWF... V).

Obteniéndose como resultado:
IC(C1) = 0,0448
IC(C2) = 0,0441
IC(C3) = 0,0501
IC(C4) = 0,0602

En este caso también podemos descartar un cifrado polialfabético con periodo o longitud de la clave (t) igual a 4, ya que el IC de los cuatro subcriptogramas está lejos del que se espera encontrar en un texto cifrado utilizando sustitución monoalfabética (en cada uno de los cuatro subcriptogramas).

Longitud de la clave (t) = 5:

Volvemos a hacer los cálculos:

IC(Ci) = IC(cici+tci+2tci+3t,...)

Donde:
t: período o longitud de la clave.
Ci: subcriptograma i-ésimo del que hay que calcular el IC (1 ≤ i ≤ t).
m: longitud del criptograma o mensaje cifrado.
ci: carácter i-ésimo del criptograma o texto cifrado (1 ≤ i ≤ m).

Es decir:

IC(C1) = IC(c1c6c11c16..., c426) = IC(GUGF... Q).
IC(C2) = IC(c2c7c12c17,..., c422) = IC(DFWO... P).
IC(C3) = IC(c3c8c13c18,..., c423) = IC(TNPA... R).
IC(C4) = IC(c4c9c14c19,..., c424) = IC(ZZGO... V).
IC(C5) = IC(c5c10c15c20,..., c425) = IC(INSE... H).

Obteniéndose como resultado:
IC(C1) = 0,0728
IC(C2) = 0,0829
IC(C3) = 0,0826
IC(C4) = 0,0737
IC(C5) = 0,0770

Como se observa, el IC obtenido para cada subcriptograma se acerca bastante al que se espera encontrar en un texto cifrado correspondiente a un texto en claro escrito en español (0,0775) utilizando sustitución monoalfabética (en cada uno de los cinco subcriptogramas), por lo que podemos concluir que muy probablemente se trate de un cifrado de sustitución polialfabética con periodo o longitud de la clave (t) igual a 5.

Pero, antes de proceder a realizar un análisis de frecuencias de los caracteres de los cinco subcriptogramas, veamos qué resultado obtendríamos para la longitud de la clave si utilizamos el método Kasiski. Recordar que para ello, ver este post, hay que localizar secuencias de caracteres, de longitud 3 o mayor, repetidas en el criptograma, ya que dichas secuencias repetidas, con casi toda probabilidad, eran las mismas también antes del cifrado y la clave ha debido coincidir en la misma posición en el momento de cifrarlas. Con nuestro criptograma:
Es decir:

- 2 cadenas "GDT" separadas por 210 posiciones.
- 2 cadenas "IOOL" separadas por 155 posiciones.
- 2 cadenas "QFSC" separadas por 185 posiciones.
- 2 cadenas "OEE" separadas por 25 posiciones.
- 2 cadenas "COX" separadas por 340 posiciones.
- 2 cadenas "XMHCAYS" separadas por 120 posiciones.
- 2 cadenas "USS" separadas por 160 posiciones.
- 2 cadenas "ÑON" separadas por 185 posiciones.
- 2 cadenas "GXC" separadas por 40 posiciones.
- 2 cadenas "SYI" separadas por 20 posiciones.
- 2 cadenas "AGM" por 10 posiciones.
- 2 cadenas "GVOÑ" separadas por 15 posiciones.
- 2 cadenas "GEEVAQI" separadas por 30 posiciones.
- 2 cadenas "FORVW" separadas por 65 posiciones.

Por lo que la longitud más probable de la clave sería el máximo común divisor o mayor número entero que divide a todas esas posiciones sin dejar resto, es decir, mcd(10, 15, 20, 25, 30, 40, 65, 120, 155, 160, 185, 210, 340) = 5.

Circunstancia que nos viene a confirmar, casi con total seguridad, que el mensaje o texto en claro ha sido cifrado utilizando un sistema de sustitución polialfabética con clave periódica y longitud de la clave igual a 5.

Realicemos ahora el análisis de frecuencias sobre los caracteres de cada uno de los cinco subcriptogramas (en cada uno de ellos los caracteres del texto en claro habrían sido cifrados con una misma letra de la clave, es decir, en cada uno de ellos la sustitución realizada sería monoalfabética):
¿Qué información nos aporta este análisis de frecuencias?: el carácter más frecuente en cada subcriptograma es el candidato a ser la "E" en el texto en claro (la letra más frecuente en español), el siguiente más frecuente es el candidato a ser la "A" (la segunda letra más frecuente), el tercero es el candidato a ser la "O" (la tercera letra más frecuente) y así sucesivamente. Esto es así, con bastante probabilidad, para los caracteres más frecuentes en textos muy grandes (en un texto en español se espera encontrar aproximadamente: 13,68% de caracteres "E", 12,53% de caracteres "A" y 8,68% de caracteres "O",...), aunque en un texto no suficientemente extenso esto podría no ser necesariamente así, por lo que tendremos que afinar los resultados obtenidos en este análisis de frecuencias de las letras con los correspondientes al análisis de frecuencias de bigramas y trigramas.

En cualquier caso veamos que información podemos obtener en un primer análisis de las frecuencias obtenidas:

- En el primer subcriptograma (C1) yo diría que el número de ocurrencias de la letra "G" (16 veces), significativamente muy superior a cualquier otra, hace que lo más probable es que se corresponda con la "E" en el texto en claro y, además, creo que es razonable pensar que la "A" debe corresponderse con la "C", "F" o "O" (las letras que después de la "G" aparecen significativamente con mayor frecuencia, en 8 ocasiones cada una de ellas).

- En el segundo subcriptograma (C2) la letra "O" (16 veces) podría corresponderse con la "E" y la "C" (12 veces) con la "A".

- En el tercer subcriptograma (C3), a simple vista, reconozco un patrón que me resulta familiar: las tres letras que aparecen con significativa mayor frecuencia presentan el siguiente desplazamiento entre ellas: 0, +4, +11, pero es que además se da la circunstancia de que éstas son la "A", "E" y "O" (las tres letras más frecuentes en español). ¿Qué casualidad, no?. Pues no lo sé, pero a mí me hace pensar que esta doble "casualidad" podría indicarnos que el sistema empleado para cifrar el mensaje en claro bien podría ser el cifrado de Vigenère y, además, que el tercer carácter de la clave utilizada sería una "A" (según la tabla del citado método de cifrado la fila correspondiente a la letra "A" de la clave cifra el carácter del texto en claro como ese mismo carácter).

Si esto es así podríamos evitarnos realizar con mayor detalle el análisis de frecuencias, ya que estaríamos en disposición de obtener la clave y después descifrar el mensaje.

Veamos: si el sistema empleado para cifrar el mensaje ha sido el cifrado de Vigenère, ese desplazamiento (0, +4, +11) se mantendrá en todos los subcriptogramas para los caracteres cuya suma de sus frecuencias relativas sea la mayor (o cerca de ser la mayor); el primero se correspondería con la "A" en el texto en claro, el segundo con la "E" y el tercero con la "O", y conforme a la tabla que emplea este sistema el primero de esos caracteres se correspondería con el carácter de la clave. Es decir:

C1: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fC + fG + fQ = (8 + 16 + 5) = 29, pero hay otra suma de frecuencias que se le aproxima: fG + fK + fU = (16 + 3 + 5) = 24, por lo que en este caso me surge la duda de si el primer carácter de la clave sería la "C" o la "G", aunque es más probable que sea la "C".

C2: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fL + fO + fZ = (7 + 16 + 5) = 28 y con la de los caracteres: fO + fS + fD = (16 + 7 + 5) = 28, por lo que me surge la duda de si el segundo carácter de la clave sería la "L" o la "O", ambas letras con igual probabilidad de serlo.

C3: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres  fA + fE + fO = (14 + 10 + 10) = 34. No hay otros tres caracteres que cumplan con esa distribución cuya suma de sus frecuencias relativas sea mayor que ésta (ni siquiera que se le aproxime), lo que nos indica, con casi toda probabilidad, que la "A" se correspondería con la "A" en el texto en claro, la "E" con la "E" y la "O" con la "O", y que el tercer carácter de la clave (la fila de la tabla del cifrado de Vigenère con la que se habría cifrado el texto en claro) sería la "A".

C4: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fZ + fD + fÑ = (11 + 10 + 7) = 28, pero hay otra suma de frecuencias que se le aproxima: fV + fZ + fK = (9 + 11 + 5) = 25, por lo que en este caso también me surge la duda de si el cuarto carácter de la clave sería la "Z" o la "V", aunque es más probable que sea la "Z".

C5: La suma mayor de frecuencias teniendo en cuenta esa distribución (0, +4, +11) se corresponde con la de los caracteres:  fE + fI + fS = (10 + 12 + 9) = 31pero hay otra suma de frecuencias que, aunque se encuentra algo alejada, apunto por si acaso: fI + fM + fW = (12 + 7 + 6) = 25, por lo que en este caso, aunque es más probable que el quinto carácter de la clave sea "E", anoto también la posibilidad de que sea "I". No obstante, no consideraré a esta última, al menos en un primer intento de averiguar cuál es la clave correcta.

Por tanto, tenemos 8 posibilidades para la clave empleada: "CLAZE", "COAZE", "CLAVE", "COAVE", "GLAZE", "GOAZE", "GLAVE" y "GOAVE".

A la vista de las claves más probables parece claro que la realmente empleada fue: "CLAVE", por lo que intentaré descifrar el mensaje utilizando ésta en primer lugar y, si no lo consigo, utilizaré las otras.

Con clave = "CLAVE" y utilizando la tabla del cifrado de Vigenère (caracteres del español, "Ñ" incluido) o, lo que es lo mismo, la expresión indicada en el post anterior para la función de descifrado (DK),  obtenemos el siguiente texto en claro:

No hay comentarios:

Publicar un comentario