Criptografía (CCLXXIV): Ataque de diccionario a la sustitución simple monoalfabética 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 la sustitución simple monoalfabética.

Cuando se utiliza una clave (alfabeto de sustitución) aleatoria este criptosistema gana en robustez comparado con otros sistemas criptográficos anteriores, imposibilitando, por ejemplo, un ataque de fuerza bruta, ya que el espacio de claves es muy grande.

Sin embargo, una clave aleatoria complica recodar la clave por parte del emisor y receptor de los mensajes, ya que tienen que recordar la disposición, sin ningún sentido, de todas las letras del alfabeto de sustitución, por lo que en la práctica éstos solían acordar una clave fácil de recordar a partir de la que se construía el alfabeto de sustitución, de la siguiente forma: primero se colocaba la clave acordada sin repetir letras y después el resto de letras del alfabeto en su orden normal sin incluir las letras ya incluidas de la clave.

Ejemplo: supongamos que la clave acordada es "SUSTITUCION". El alfabeto de sustitución sería:

"SUTICONABDEFGHJKLMÑPQRVWXYZ"

Con esta forma de construir la clave (el alfabeto de sustitución) se gana en agilidad y cierta seguridad, ya que no hay que anotarla en ningún lugar, pero los criptogramas pueden ser vulnerables a un ataque de diccionario si la clave empleada para construir el alfabeto de sustitución es una palabra y ésta está en el diccionario con el que se realiza el ataque.

Ya puse un post para realizar un ataque de este tipo al cifrado de vigenère en el que expliqué en qué consiste y cómo llevarlo a cabo. En el script de esa entrada se utilizan dos diccionarios, uno en inglés (english_dict.txt) y otro en español (espanol_dicc.txt), que serán también los que utilice el script que voy a poner en este post; también se utiliza el índice de coincidencia, que también lo utiliza este script para realizar un primer filtrado de los textos descifrados, y, adicionalmente, se utilizan archivos de trigramas y palabras frecuentes para afinar la detección de cuando el descifrado produce un texto inteligible, sin embargo en esta ocasión voy a emplear para esto último la calificación o puntuación basada en las estadísticas de tetragramas de la aptitud ('fitness') de los textos que se vayan descifrando durante el ataque.

Por tanto, para que el script que voy a poner a continuación funcione se necesita importar los dos siguientes módulo en el programa principal:

#!/usr/bin/env python

#!/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

Y:

#!/usr/bin/env python

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

# CALIFICACIÓN APTITUD ('FITNESS') DE UN TEXTO:
#
# Califica la semejanza de un texto con respecto a un texto escrito en inglés o español.
#
# http://mikelgarcialarragan.blogspot.com/

import re
from unicodedata import normalize
from math import log10

# TEST FITNESS:
def test_fitness(texto,idioma):
    N = 0
    probabilidad_ngramas = {}
    if idioma == "Inglés":
        f_ocurrencias_ngramas = open("english_quadgrams.txt")
    else:
        f_ocurrencias_ngramas = open("tetragramas_español.txt")
    for ngrama in f_ocurrencias_ngramas:
        n_grama, ocurrencias = ngrama.split(' ')
        probabilidad_ngramas[n_grama] = int(ocurrencias)
        N += int(ocurrencias)
    f_ocurrencias_ngramas.close()

    fitness = 0
    for i in range(len(texto)-3):
        n_grama = texto[i:i+4]
        if n_grama in probabilidad_ngramas.keys():
            fitness += log10(float(probabilidad_ngramas[n_grama])/N)
        else:
            fitness += log10(0.01/N)

    return fitness

El script es el siguiente:

#!/usr/bin/env python

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

# ATAQUE DE DICCIONARIO AL CIFRADO DE SUSTITUCIÓN SIMPLE MONOALFABÉTICA:
#
# Ataque de diccionario a un criptograma cifrado mediante sustitución simple monoalfabética.
#
# http://mikelgarcialarragan.blogspot.com/

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

# FUNCIÓN DE DESCIFRADO:
def descifrar(alfabeto,criptograma,clave):
    texto_claro = ''
    i = 0
    for caracter in criptograma:
        texto_claro = texto_claro + alfabeto[clave.find(caracter)]
        i+=1
    return texto_claro

def main():
# SELECCIÓN DE IDIOMA:
# Se solicita que se indique el idioma en el que se supone que está escrito el texto en claro.
    idioma = ""
    while idioma == "":
        print ("")
        print ("*** SELECCIÓN DE IDIOMA **************************")
        print ('1. Inglés.')
        print ('2. Español.')
        print ("")
        opcion = input("Por favor, seleccione el idioma en el que se supone que está escrito el texto en claro: ")
        if opcion == "1":
            idioma = "Inglés"
            alfabeto = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        elif  opcion == "2":
            idioma = "Español"
            alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
        else:
            print ("*** ERROR: Opción no válida.")
    print ("")
    print ("[+] Idioma:", idioma)

# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Ataque de diccionaro al cifrado por sustitución simple monoalfabética.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- ATAQUE DE DICCIONARIO AL CIFRADO POR SUSTITUCIÓN SIMPLE MONOALFABÉTICA:")
            # 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(' ','')
                if idioma == 1:
                    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)
                    print ("[+] Tamaño criptograma:", len(criptograma), "caracteres.")
                    posibles_soluciones = []
                    if idioma == "Inglés":
                        f_diccionario = open("english_dict.txt")
                    else:
                        f_diccionario = open("espanol_dicc.txt")
                    diccionario = f_diccionario.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()
                        alfabeto_sustitucion = ""
                        for caracter in range(0, len(clave)):
                            if clave[caracter] not in alfabeto_sustitucion:
                                alfabeto_sustitucion += clave[caracter]
                        for caracter in range(0, len(alfabeto)):
                            if alfabeto[caracter] not in alfabeto_sustitucion:
                                alfabeto_sustitucion += alfabeto[caracter]
                        texto_claro = descifrar(alfabeto,criptograma,alfabeto_sustitucion)
                        ic = calculo_ic(texto_claro,alfabeto)
                        if ic > 0.06:
                            fitness = test_fitness(texto_claro,idioma)
                            posibles_soluciones.append([ic, fitness, clave, texto_claro])
                    barra_progreso.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:

Tal y como se observa en la figura anterior, se obtiene la clave correcta "SUSTITUCION". El script, debido al tamaño del diccionario empleado, ha tardado 39:58, un tiempo un poco largo, aunque yo creo que asumible, y ha demostrado ser eficaz en el descifrado, aún con un criptograma bastante corto.

No obstante, lo dicho, recordar que, lógicamente, este método sólo tendrá éxito en caso de que la palabra clave se encuentre en el diccionario utilizado en el ataque.

Quizás también te interese: