Criptografía (CCXLVIII): Ataque de diccionario al cifrado de Vigenère en python

Continúo poniendo scripts de programación en python para automatizar tareas que tengan relación con la criptografía.

Ya puse una entrada con un script en python para cifrar y descifrar textos en claro y criptogramas, respectivamente, utilizando el cifrado de Vigenère.

Pues bien, ahora le toca el turno a un script para atacar a un criptograma cifrado utilizando este criptosistema sin conocer la clave  empleada en el cifrado.

El tipo de ataque a realizar mediante este script se denomina ataque de diccionario, y consiste en intentar averiguar la clave probando todas las palabras de un diccionario hasta encontrar aquella que se utilizó en el cifrado, es decir, aquella cuya aplicación en el descifrado del criptograma produzca un texto en claro inteligible. Lógicamente, la eficacia de este tipo de ataque dependerá de que la clave empleada en el cifrado sea una palabra y, además, de que ésta se encuentre en el diccionario usado en el ataque.

Como diccionario se pueden emplear diccionarios de palabras en diferentes idiomas en los que pueda estar escrito el texto en claro (para intentar averiguar cuál es puede calcularse previamente el Índice de Coincidencia - IC - del criptograma) o diccionarios, de los muchos existentes en Internet, con las claves más utilizadas.

En el script que pongo a continuación se utilizan dos diccionarios, uno en inglés (english_dict.txt) y otro en español (espanol_dicc.txt), también de los muchos que existen en Internet.

Además de lo que es el ataque de diccionario en sí mismo, para afinarlo un poco, utilizo también sendos diccionarios de trigramas (english_trig.txt) y (espanol_trig.txt), y sendos diccionarios de palabras de 4 o más letras muy frecuentes en ambos idiomas (english_word.txt) y (espanol.pala.txt).

Adicionalmente, para que el script funcione se necesita el siguiente módulo, que será importado en el programa principal, para el cálculo del Índice de Coincidencia (IC) de los textos en claro que se vayan obteniendo:

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# ÍNDICE DE COINCIDENCIA (IC):
#
# Cálculo del IC de un texto.
#
# http://mikelgarcialarragan.blogspot.com/

def calculo_ic(texto,alfabeto):
    # Cálculo de la frecuencia relativa de cada uno de los caracteres del alfabeto en el texto.
    frecuencia_relativa=[0 for caracter in alfabeto]
    for caracter in alfabeto:
        frecuencia_relativa[alfabeto.index(caracter)]=texto.count(caracter)
    # 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=[]
    for caracter in alfabeto:
        pares_caracteres_iguales.append(frecuencia_relativa[alfabeto.index(caracter)]*(frecuencia_relativa[alfabeto.index(caracter)]-1)/2)
    # 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 IC.
    ic = 0
    for caracter in alfabeto:
        ic = ic + (pares_caracteres_iguales[alfabeto.index(caracter)]/pares_caracteres_posibles)
    return ic

El script es el siguiente:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# ATAQUE DE DICCIONARIO AL CIFRADO DE VIGENÈRE:
#
# Ataque de diccionario a un criptograma cifrado mediante el criptosistema de Vigenère
#
# http://mikelgarcialarragan.blogspot.com/

import re
from unicodedata import normalize
from ic import calculo_ic
from tqdm import tqdm

# FUNCIÓN DE DESCIFRADO:
# La función de descifrado es: Dk(Ci) = (Ci - Ki) mod n
def descifrar(alfabeto,criptograma,clave):
    texto_claro = ''
    i = 0
    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 main():
# SELECCIÓN DE ALFABETO:
# Se solicita que se indique el alfabeto a emplear.
    alfabeto = ""
    while alfabeto == "":
        print ("")
        print ("*** SELECCIÓN DE ALFABETO ************************")
        print ('1. Alfabeto inglés  (26 caracteres, "Ñ" excluida).')
        print ('2. Alfabeto español (27 caracteres, "Ñ" incluida).')
        print ("")
        opcion = input("Por favor, seleccione el alfabeto a utilizar: ")
        if opcion == "1":
            alfabeto = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        elif opcion == "2":
            alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
        else:
            print ("*** ERROR: Opción no válida.")
    print ("")
    alfabeto_seleccionado = opcion
    print ("[+] Alfabeto:", alfabeto)
    print ("[+] Tamaño del alfabeto (n):", len(alfabeto))

# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Ataque de diccionario al cifrado de Vigenère.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- ATAQUE DE DICCIONARIO:")
            # Se introduce el criptograma. Se convierten los caracteres a mayúsculas y
            # se eliminan los espacios, las tildes, diéresis, etc.
            criptograma = "*"
            while not criptograma.isalpha():
                criptograma = input('Criptograma a atacar: ').upper()
                criptograma = criptograma.replace(' ','')
                criptograma = re.sub(r"([^n\u0300-\u036f]|n(?!\u0303(?![\u0300-\u036f])))[\u0300-\u036f]+",
                                      r"\1", normalize("NFD", criptograma), 0, re.I)
                criptograma = normalize("NFC", criptograma)
                if criptograma.isalpha():
                    print ("[+] Criptograma a atacar:", criptograma)
                    posibles_soluciones = []
                    if alfabeto_seleccionado == "1":
                        f_diccionario = open("english_dict.txt")
                        f_trigramas = open("english_trig.txt")
                        f_palabras = open("english_word.txt")
                    else:
                        f_diccionario = open("espanol_dicc.txt")
                        f_trigramas = open("espanol_trig.txt")
                        f_palabras = open("espanol.pala.txt")
                    diccionario = f_diccionario.readlines()
                    trigramas = f_trigramas.readlines()
                    palabras = f_palabras.readlines()
                    barra_progreso = tqdm(total = len(diccionario))
                    for clave in diccionario:
                        barra_progreso.set_description("Procesando las entradas del diccionario...".format(clave))
                        barra_progreso.update(1)
                        clave = clave.strip()
                        texto_claro = descifrar(alfabeto,criptograma,clave)
                        ic = calculo_ic(texto_claro,alfabeto)
                        if ic > 0.06:
                            puntos = 0
                            for trigrama in trigramas:
                                trigrama = trigrama.strip()
                                puntos = puntos + texto_claro.count(trigrama)
                            for palabra in palabras:
                                palabra = palabra.strip()
                                puntos = puntos + texto_claro.count(palabra) * len(palabra)
                            if puntos > 0:
                                posibles_soluciones.append([ic, puntos, clave, texto_claro])
                    barra_progreso.close()
                    f_palabras.close()
                    f_trigramas.close()
                    f_diccionario.close()
                    posibles_soluciones.sort(key=lambda x:x[1], reverse=True)
                    if (len(posibles_soluciones)) > 0:
                        print("[+] Descifrado más inteligible. 1 .- Clave: ", posibles_soluciones[0][2], "--> Texto en claro: ", posibles_soluciones[0][3])
                        if (len(posibles_soluciones)) > 1:
                            mostrar_10_mas = "S"
                            inicio_siguientes = 1
                            while mostrar_10_mas == "S":
                                mostrar_10_mas = input("¿Mostrar los siguientes 10 descifrados más inteligibles ('S')?: ").upper()
                                if mostrar_10_mas == "S":
                                    fin_siguientes = inicio_siguientes + 10
                                    if fin_siguientes > len(posibles_soluciones):
                                        fin_siguientes = len(posibles_soluciones)
                                    for posible_solucion in range(inicio_siguientes, fin_siguientes):
                                        print(posible_solucion+1, ".- Clave: ", posibles_soluciones[posible_solucion][2], "--> Texto en claro: ", posibles_soluciones[posible_solucion][3])
                                    if fin_siguientes == len(posibles_soluciones):
                                        print("*** FIN: No hay más posibles soluciones.")
                                        mostrar_10_mas = "N"
                                    else:
                                        inicio_siguientes+=10
                    else:
                        print("[+] No se han encontrado posibles descifrados inteligibles.")
                else:
                    print ("*** ERROR: El criptograma a atacar sólo debe contener caracteres alfabéticos.")
        elif opcion == "2":
            print ("*** FIN ******************************************")
            salir = True
        else:
            print ("*** ERROR: Opción no válida.")
	
if __name__ == '__main__':
    main()

Lo ejecuto para un criptograma cuyo texto en claro está escrito en inglés:

Lo ejecuto para un criptograma cuyo texto en claro está escrito en español: