El criptoanálisis del método Vigenère

Por fin, con un retraso digno de Lucia alguien que se retrase mucho, llega el post sobre criptoanálisis.

Bueno, supongo que tod@s vosotr@s, querid@s lector@s (la chorradita esta de la @ para hacerse el políticamente correcto a veces tiene su punto, pero cansa mogollón), tendréis estudiado el método de cifrado polialfabético Vigenère, ya que debéis entenderlo para seguir esta explicación.

Como recordareis, se habló de que el método César se puede descifrar sin conocer la clave haciendo un análisis de frecuencias (un criptofante para Gema), cosa que inmediatamente nos revela el desplazamiento (la clave) utilizado. Como el método Vigenère utiliza múltiples desplazamientos y no tiene una longitud fija de clave, esa frecuencia relativa queda difuminada, de manera que un análisis de frecuencia no nos revelará nada.

Pero si que existen patrones que nos pueden dar pistas sobre cómo romper el algoritmo. Y es que, en los idiomas no sólo se repiten mas unas letras que otras, sino que también se repiten mas unas secuencias que otras. En español, por ejemplo, se repetirá mucho mas la secuencia "los" que la secuencia "wes" sin ninguna duda. ¿Y cómo podemos aprovechar esto? Pues fácil, si tenemos la suerte de que dichas secuencias coinciden con que estén cifradas con los mismos caracteres de la clave, ya que producirán criptogramas iguales que se repetirán a lo largo de todo el texto cifrado. Entonces, mirando las distancias entre dichas repeticiones tendremos información sobre la longitud de la clave, ya que deben ser múltiplos de la misma.

De esto se dió cuenta un criptógrafo militar prusiano a mediados del siglo XIX (fijaos lo que duró la consideración de "indescifrable" del método Vigenère) llamado Friedrich Kasiski.

Vamos a ver un ejemplo de la utilización del método:

mensaje:"Shut up. Shut up! Shut up! You can't have egg, bacon, spam and sausage without the spam"
clave: "abcd"
criptograma: "SIWWUQUKUUWSSIWWUQARUDCQTICYEF IJBBERNTRDMBPGSBWVAHGZIUJRUUVKETRDM"

He señalado en negrita las secuencias que se repiten. Podemos ver que se repite "SIWWUQ", que corresponde al primer y tercer "Shut up", y "TRDM" correspondiente a las dos apariciones de "spam". La separación entre las primeras repeticiones es de 12 posiciones, y de 24 entre las últimas. Como hemos dicho antes, estos números deben ser múltiplos de la longitud de la clave. Por lo tanto, descomponemos los números en factores primos: 12 = 2x2x3, 24= 2x2x2x3. Esto nos indica que la clave puede tener las longitudes de 2, 3, 4 (2x2), 6 (2x3) o 12 (2x2x3).

Debemos elegir una de las longitudes, y no queda mas remedio que hacerlo por prueba y error. Descomponemos el criptograma en subconjuntos en función de la longitud elegida y luego hacemos un análisis de frecuencia de letras para determinar el desplazamiento utilizado en cada uno. Es decir, si probamos con una longitud de 2, tendremos que las posiciones pares están cifradas con un alfabeto y las impares con otro y sabemos atacar a ambos conjuntos por separado, ya que no son mas que dos cifrados César. Una vez que tengamos todos nuestros subconjuntos resueltos tendremos la clave final.

Voy a dejarlo aquí porque el post ya me está quedando muy largo, asi que dejaré para los próximos algunas cosas que quería comentar. Lo que si que no me aguanto a decir es que la frase elegida para cifrar, por si os lo habeis preguntado, es de un sketch de Monty Python. Este sketch tiene la curiosidad de que es la causa por la que al correo basura se le conoce como "spam".