Criptografía (CCXXXV): Ataque de diccionario al cifrado Vigenère (I)

Hace poco una persona ha puesto un comentario en la primera entrada sobre el cifrado de Vigenère que puse en este blog pidiéndome ayuda para atacar un criptograma cifrado mediante este criptosistema.

En concreto el comentario que se puso fue el siguiente:

"Buenas Mikel necesitaba ayuda para encontrar la clave de este mensaje en Vigenère: VPXZGIAXIVWPUBTTMJPWIZITWZT, es para un trabajo de carrera y me está costando la vida resolverlo, muchas gracias espero que leas este comentario."

A lo que yo le respondí lo siguiente:

"Buenas anónimo:

El criptograma es muy corto, tiene sólo 27 caracteres, por lo que no será fácil criptoanalizarlo, pero es que, además, a simple vista no veo cadenas de caracteres, de tres o más caracteres, repetidas en él, por lo que no es posible emplear el método Kasiski.
De todas formas, antes que nada: ¿estás seguro/a de que el texto en claro se ha cifrado utilizando el método de Vigenère?
Voy a hacer una comprobación previa antes de intentar el descifrado y para ello voy a calcular el Índice de coincidencia (como digo el criptograma es muy corto y el índice de coincidencia calculado no será excesivamente fiable, pero me dará una idea de si se puede tratar de un cifrado de sustitución polialfabética, como es el caso de un cifrado de Vigenère o no).
A mí me sale que el Índice de coincidencia (IC) del criptograma es: 0,06552707, lo que está más cerca del esperado para un texto en claro cifrado con un sistemas de sustitución monoalfabética (el IC del inglés es de 0,0685 y el del español 0,0755) o de transposición (sólo de trasposición parece claro que no es), e incluso con una mezcla de criptosistemas de ambos tipos, que de uno en el que se haya utilizado un criptosistema de sustitución polialfabética (en el que se esperaría un IC de aproximadamente 0,0370), como lo es el de Vigenère.
Por tanto, pregunta: ¿Cómo sabes que el texto en claro se ha cifrado utilizando el método de Vigenère?"

Le respondí así porque el citado primera post era sobre el criptoanálisis utilizando el método Kasiski y en el criptograma del comentario yo no veía cadenas de caracteres repetidas, de tres o más caracteres, y por tanto no se podía utilizar este método, y, además, porque ya me ha ocurrido que algún lector de este blog puso un comentario para que le ayudara con un criptograma cifrado utilizando el cifrado de Vigenère y al final resultó que estaba cifrado mediante sustitución monoalfabética simple.

A lo que el lector me contestó que:

"Puedo asegurar que está escrito en Vigenère, es un mensaje propuesto por los profesores de mi universidad, es bastante costosos estoy intentándolo atacar por todos lados pero es muy complicado, lo único que he podido averiguar es que la clave es de 6 caracteres."

Bueno, pues me puse a ello. Me daba una pista adicional ("la clave es de 6 caracteres"), pero: ¿Cómo podía atacar un criptograma tan corto (27 caracteres) en cuyo criptoanálisis, además, no podía emplear el método Kasiski?

En este punto decidí utilizar un ataque de diccionario (en inglés, 'dictionary attack'), pero era consciente de que este método sólo funcionaría en el caso de que la clave empleada en el cifrado fuese una palabra y, además, si ésta se encontraba en el diccionario usado en el ataque. Por tanto, me descargué un diccionario de Internet con palabras del idioma en el que pudiera estar escrito el texto en claro y me "encomendé a todos los santos" para que la clave utilizada estuviera entre dichas palabras.

El diccionario que me bajé de Internet fue uno con palabras en inglés (pero, por si acaso, también me descargué otro con palabras en español). En primer lugar supondría que el texto claro estaba escrito en inglés y si no conseguía descifrar el criptograma lo intentaría considerando que el idioma del texto en claro era el español.

Para implementar este ataque creé un script de python para descifrar el criptograma con todas las palabras (claves) de longitud igual a 6 (la pista que me dio la persona que puso el comentario) que figurasen en el diccionario, y mostrar aquellas claves de cuya aplicación en el descifrado se obtuviera un texto en claro con un Índice de Coincidencia (IC) mayor que 0,065 (ya expliqué en el segundo punto de este post qué es el IC y cómo se calcula). ¿Por qué 0,065?, porque el IC de un texto claro escrito en inglés se aproximará a 0,0685.

Lo ejecuté, pero había muchas claves que daban como resultado un texto en claro con un IC mayor que el indicado, y, aunque con un poco de paciencia se podía ya ver la solución, decidí depurarlo un poco más.

Para ello, establecí la condición adicional de que sólo se mostrarían los textos en claro que tras la aplicación de la clave tuvieran un IC mayor que 0,065 y, además, que contuvieran alguno o algunos de los trigramas más frecuentes del inglés ("THE","AND", "ING",...), para lo que cree un pequeño fichero con dichos trigramas.

El script de python con esta depuración de los resultados fue el siguiente:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
alfabeto = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
print("[+] Alfabeto:",alfabeto)
print("[+] Tamaño del alfabeto:",len(alfabeto))

def descifrar(criptograma,clave):
    texto_claro = ''
    i = 0
# La función de descifrado es: Dk(Ci) = (Ci - Ki) mod n
    for caracter in criptograma:
        texto_claro = texto_claro + alfabeto[(alfabeto.find(caracter) - alfabeto.find(clave[i % len(clave)])) % len(alfabeto)]
        i+=1
    return texto_claro

def IC(texto):
# Cálculo de la frecuencia relativa de cada uno de los caracteres del alfabeto en el texto.
    frecuencia_relativa = []
    i = 0
    while i < len(alfabeto):
        contador = 0
        for caracter in texto:
            if caracter == alfabeto[i]:
                contador = contador +1
        frecuencia_relativa.append(contador)
        i+=1
    # Cálculo del número de pares de caracteres iguales que es posible obtener del texto tomando dos de ellos al azar.
    pares_caracteres_iguales = []
    i = 0
    while i < len(alfabeto):
        pares_caracteres_iguales.append(frecuencia_relativa[i]*(frecuencia_relativa[i]-1)/2)
        i+=1
# Cálculo del número de pares de caracteres que es posible obtener del texto.
    pares_caracteres_posibles = len(texto) *(len(texto)-1)/2
#Cálculo del Índice de Coincidencia (texto).
    IC = 0
    i = 0
    while i < len(alfabeto):
        IC = IC + (float(pares_caracteres_iguales[i])/pares_caracteres_posibles)
        i+=1
    return IC

def main():
# Se introduce el criptograma. Se convierten los caracteres a mayúsculas y se eliminan los espacios.
    criptograma = input('Criptograma a descifrar: ').upper()
    criptograma = criptograma.replace(' ','')
    print("[+] Cripotograma:")
    print(criptograma)
# Ataque de diccionario.
    f = open('english_en_EN.dict.txt')
    claves = f.readlines()
    f.close()
    posible_solución = 0
    for clave in claves:
        clave = clave.upper()
        clave = clave.strip()
        if len(clave)==6:
            texto_claro = descifrar(criptograma,clave)
            indice_coincidencia = IC(texto_claro)
            if indice_coincidencia>0.065:
                f = open('english_en_EN.trig.txt')
                trigramas = f.readlines()
                f.close()
                for trigrama in trigramas:
                    trigrama = trigrama.strip()
                    if trigrama in texto_claro:
                        posible_solución+=1
                        print("[+]",posible_solución,"IC:",indice_coincidencia,"; Clave:",clave,"Trigrama:",trigrama,"; Texto en claro:",texto_claro)

if __name__ == '__main__':
    main()

Lo ejecuté:

Y como consecuencia, veo que los resultados que satisfacen ambas condiciones son muchos menos. Ahora es todavía más fácil obtener la solución.

En la figura anterior se observa que con la clave "CIPHER" se obtiene un texto en claro con un IC de 0,06838, y en el que, además, están presentes tres de los trigramas más frecuentes en inglés: "HIS", "NOT" y ""THI", con lo que el texto en claro sería:

"THIS CRYPTOSYSTEM IS NOT SECURE"

Para finalizar dos preguntas:

- ¿Qué hubiera pasado si la persona que puso el comentario no me hubiera dicho que la clave tenía una longitud de 6 caracteres? Pues creo que no me hubiera quedado otra opción que ejecutar el script probando las diferentes longitudes de clave posibles, pero también creo que hubiera conseguido descifrarlo,

- ¿Por qué no podría llegar a obtener la longitud de la clave utilizando el IC, ver punto 3 de este post? porque el criptograma tiene una longitud muy pequeña y, como consecuencia, los subcriptogramas que obtendríamos para calcular su IC serían todavía más cortos y éste no sería nada fiable.

Quizás también te interese: