El criptoanálisis del método Vigenère (II)

Aquí viene la segunda parte del criptoanálisis de cifrados polialfabéticos (en concreto lo hemos estado haciendo con el método Vigenère).

El método Kasisky tiene el problema de que en muchas ocasiones las posibilidades de la longitud de la clave son demasiadas. Además, pueden existir coincidencias de secuencias en el texto cifrado que no sean representaciones de la misma secuencia en el texto en claro, lo cual dificulta enormemente encontrar la longitud de la clave, ya que la diferencia entre ellas no será múltimplo del tamaño de clave y por lo tanto nos confundirá.

Aún con esos problemas el método se estuvo utilizando tal y como lo vimos durante casi un siglo, hasta que un criptógrafo del ejército de EEUU, William F. Friedman (que a mi me parece que se da un aire al abuelo de la familia Monster), descubrió que podía hacer un cálculo con los índices de coincidencia de las letras para determinar la longitud de la clave de manera mas directa y precisa. Este método, además, es mucho mas versátil ya que se puede aplicar a todos los cifrados polialfabéticos.



Su ataque se fundamenta en que si en un texto de un lenguaje determinado elegimos dos letras al azar, la probabilidad de que sean la misma es conocida (por métodos estadísticos). Esto se puede comparar con los datos obtenidos de realizar la misma operación en el texto cifrado y de esta forma hacernos una idea de la cantidad de alfabetos que se han utilizado para cifrar el mensaje. Esto ocurre porque al quedar difuminadas las frecuencias relativas de las letras (que además estarán mas difuminadas cuantos mas alfabetos se hayan utilizado para cifrar) cambiará este índice de coincidencia. Es decir, si, por ejemplo, en el inglés la probabilidad del uso de la E es la mayor de todas. Entonces, si superponemos dos textos, la probabilidad de que coincida una E sobre otra será alta. En cambio, en un texto cifrado la probabilidad observada será mucho menor, y dependerá del número de alfabetos con el que esté cifrado.

Al final, todo esto se reduce a una fórmula (que saco directamente de la wikipedia):


Donde la I es el índice de coincidencia, que viene dado por la siguiente expresión de combinatoria:



... donde los distintos valores para las enes vienen dados por las frecuencias absolutas de las apariciones en el criptograma de las 26 letras del alfabeto inglés, n es la longitud del texto, y el 0.065 es la probabilidad de que dos letras al azar en un texto inglés sean las mismas.

Este método realmente funciona para cualquier cifrado polialfabético, y en su momento consiguió romper muchos de los cifrados de algunas máquinas de rotores utilizadas. (De las máquinas de rotores ya hablaré mas adelante).

Ahora, apliquemos al ejemplo del post sobre cifrado polialfabético este método.

Hacemos un conteo de las frecuencias de las letras (A=2, B=4, C=2, D=3, E=3, F=1, G=2, H=1, I=5, J=2, K=2, L=0, M=2, N=1, O=0, P=1, Q=3, R=5, S=4, T=3, U=9, V=2, W=6, X=0, Y=1, Z=1). Antes de continuar con el método, una observación: se puede apreciar que las frecuencias relativas difieren poco unas de otras (salvo alguna excepción), que es lo que dijimos que provoca un cifrado polialfabético.

Seguimos. Calculamos el índice de coincidencia, que a mi me sale de 0,049, y lo introducimos en la primera expresión (.027*65/(64*0.049 -.038*65 + .065)) y nos da un resultado de 2,4. La longitud de la clave, por tanto, debe ser cercana a 2 o 3. Si, tenéis razón: no hemos obtenido el resultado correcto (que es 4), pero es que hay que tener en cuenta que este es un método que mejora mucho con la longitud de los criptogramas. Aun así, no tendríamos que hacer muchas pruebas hasta que diéramos con la clave correcta, ya que el resultado nos ha orientado acerca de la longitud de clave. Combinado con el método Kasisky nos permite ir seleccionando longitudes de clave que se aproximen a este valor.

Bueno, con esto queda explicado el criptoanálisis del cifrado Vigenère. Espero que os haya gustado, aunque reconozco que este post puede hacerse un poco pesado.

Es muy divertido romper textos utilizando estos métodos. Una vez que se consiguen entender, su aplicación es muy sencilla y mas rápida de lo que parece. Este tipo de criptoanálisis me trae buenos recuerdos, ya que en mi examen de criptografía me pusieron un texto cifrado y tuve que aplicar estos dos métodos para romperlo, asi que por primera vez disfruté en un exámen.

Una curiosidad descubierta en la wikipedia mientras me documentaba un poco: la universidad donde estudió William F. Friedman fue Cornell, la misma en la que han sido profesores gente como (el grandísimo) Richard P. Feynman, (el ínclito) Carl Sagan, Diane Fossy o... ¡John Cleese!... ¡todo acaba otra vez en Monty Python! ;-)