Estadística contra Criptografía II

Sigue la batalla: Kasiski contra Vigenère

En este artículo, continuación de "Estadística contra Criptografía - Matemáticas contra Matemáticas", veremos un ejemplo de desencriptación de un mensaje cifrado con el método Vigenère.

Raúl Ibáñez dedicó su colaboración del 3 de marzo en el programa de radio Euskadi La mecánica del caracol a seguir tratando el tema "mensajes cifrados y criptografía" incluyendo algunos ejemplos de métodos de cifrado de mensajes un poco más complejos que los de la primera entrega. Concretamente, habló del cifrado Alberti, primer método conocido de cifrado por sustitución que utilizó dos alfabetos. Y del cifrado Vigenère, más sofisticado, que pretende evitar el análisis de frecuencias manteniendo la sencillez del cifrado de Julio César.

Puedes escuchar el programa aquí. La participación de Raúl va desde el minuto 27:42 hasta el 50:12.
También es posible descargar el audio del programa completo aquí.

En la parte final del programa Raúl propuso como reto la desencriptación del siguiente mensaje:

LNU DVMUYR MUD VL LPXAFZ UEF AIOVWVMU OV MUEVMUEZCUD VS YW CIVCF GUCUNYC GALL GRCYTIJTRNNPJ QOP JE MZITYLIA YYKRY EFDUD CAM AVRMZEAM BLE XPJCCQIEH PJTY XVNMLAE ZTIMUOF RUFC

Descifrando el reto

Traicté des chiffres
Gallica - Bibliothèque nationale de France

Como ya indicamos en el artículo dedicado al anterior reto criptográfico, lo primero que hay que determinar para desencriptar un mensaje es el idioma original y el tipo de método de cifrado utilizado. Es razonable conjeturar que también en este segundo desafío el mensaje original está en castellano y el método de cifrado es alguno de los tratados por Raúl Ibáñez. La mayor parte del tiempo estuvo dedicada al cifrado Vigenère. Vamos a estudiar la posibilidad de que haya sido éste el método de cifrado utilizado.

El cifrado Vigenère debe su nombre a una atribución errónea a Blaise de Vigenère que en 1586 publicó "Traicté des chiffres ou secrètes manières d’escrire", en el que explica este método. En realidad el método fue descrito originalmente por Giovan Battista Belasso en su libro de 1553 "La cifra del Sig. Giovan Battista Belasso".

Para entender cómo funciona el sistema de cifrado Vigenère puedes consultar la explicación del propio Raúl Ibánez en el blog del programa.

¿Cuál es la fortaleza del sistema Vigenère? La misma letra se cifra de modo diferente para tratar de evitar el análisis de frecuencias. ¿De cuántas? Tantas como la longitud de la clave utilizada. Cuanto mayor se la longitud de la clave, mayor es la dificultad para desencriptar el mensaje.

Kasiski contra Vigenère

Traicté des chiffres - Pág 50
Gallica - Bibliothèque nationale de France

Pero su fortaleza es al mismo tiempo su mayor debilidad. Cada letra, y lo que es más importante, cada palabra no puede ser cifrada de más maneras distintas que la longitud de la clave utilizada. Por lo tanto, las palabras más frecuentes en el texto original aparecerán repetidas también en el texto cifrado, menos veces, pero es inevitable que aparezcan. Además en el texto cifrado, el número de caracteres que separan la misma forma de cifrar una palabra es un número exacto de veces, es decir, un múltiplo de la longitud de la clave. Ésta es la grieta de seguridad que permite realizar un ataque criptográfico al cifrado de Vigenère y la idea clave del método Kasiski, que debe su nombre al oficial prusiano Friedrich Kasiski que lo publicó en 1863.

Comencemos por un análisis de las cadenas que se repiten y su espaciamiento para determinar las longitudes de la clave más probables:

• "UDV" se repite 2 veces (aparece 3 veces) separadas por 8 y 32 posiciones.
• "MUE" se repite 1 vez separada por 4 posiciones.       
• "MUO" se repite 1 vez separada por 108 posiciones.
• "VMU" se repite 3 veces separadas por 24, 4 y 4 posiciones.
• "VMUE" se repite 1 vez separada por 4 posiciones.

Los divisores comunes a todas las separaciones son: 2 y 4. Vamos a suponer que Raúl no ha usado una clave de 2 letras porque haría el reto demasiado fácil. Así que separamos el mensaje cifrado en 4 partes:

1.- Nos quedamos con las letras que ocupan las posiciones 1,5,9, ...

2.- Nos quedamos con las letras que ocupan las posiciones 2,6,10, ...

3.- Nos quedamos con las letras que ocupan las posiciones 3,7,11, ...

4.- Nos quedamos con las letras que ocupan las posiciones 4,8,12, ...

Ahora se trata de aplicar en cada una de las cuatro partes en las que ha quedado dividido el mensaje encriptado un análisis de frecuencias, como al tratar de romper el cifrado César, computando las veces que aparece cada carácter en el texto cifrado, calculando las correspondientes frecuencias relativas y teniendo en cuenta las frecuencias de aparición de letras en castellano. Las letras que más aparecen son, por este orden: E, A, O, S, ... Lo que nos lleva a conjeturar que la clave utilizada ha sido "RAUL".

Al descifrar el mensaje utilizando el método Vigenère con esta clave obtenemos como mensaje original:

una semana mas el regalo del problema de matematicas es el libro gardner para principiantes que se sorteara entre todas las personas que descifren este mensaje firmado raul

Muy en la línea de la autoreferencia y de dar facilidades, como en el anterior programa. La última palabra de 4 letras ayuda bastante.

Descifrado "asistido"

Es fácil encontrar en internet herramientas que facilitan en gran medida el proceso de desencriptado de este tipo de mensajes, como por ejemplo The_Black_Chamber Vigenère Cracking Tool.

Es nuestra decisión utilizarlas o no, pero claramente usarlas no es lo mejor que podemos hacer si lo que queremos es entender cómo funciona la técnica Kasiski de ataque al cifrado Vigenère. Además hay que considerar los placeres de pasar un buen rato ejercitando nuestra mente, de enfrentarse a un reto, y a veces ... vencerlo.

La facilidad con que se descifra este tipo de criptografía, de la que hemos visto un ejemplo, hace que no sea utilizada desde hace mucho tiempo cuando son necesarias unas comunicaciones realmente seguras. Sin embargo fue un sistema considerado seguro durante muchos siglos.

Para saber más:

Simon Singh: http://simonsingh.net/cryptography/
Información y utilidades criptográficas en el sitio web de Simon Singh.

The_Black_Chamber: http://www.simonsingh.net/The_Black_Chamber
Sitio de Simon Singh, donde se puede aprender criptografía y criptoanálisis, y practicar con herramientas interactivas de cifrado.

CrypTool: https://www.cryptool.org
Sitio web dedicado a la divulgación de la criptografía y el criptoanálisis. "CrypTool" es un software libre que ilustra conceptos criptográficos muy usado en entornos formativos. El sitio ofrece gran cantidad de material didáctico e incluye el proyecto CrypTool-Online: http://www.cryptool-online.org

Joan Gómez. "Matemáticos, espías y piratas informáticos. Codificación y criptografía". RBA Libros. Barcelona 2010.