Criptografía (CCLXXIII): Ataque 'Hill Climbing' 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, y también puse un post con la explicación de la implementación del algoritmo 'Hill Climbing' que me propongo realizar para atacar criptogramas cifrados mediante este criptosistema utilizando 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.

Para que el script con este ataque funcione se necesita importar el siguiente módulo en el programa principal, que se encargará, precisamente, de la calificación de la aptitud ('fitness') de los textos que se vayan obteniendo en el descifrado con respecto al idioma en el que se escribió el texto en claro, es decir, de la obtención de una calificación o puntuación de la mayor o menor semejanza de un texto dado con respecto a un texto escrito en dicho idioma:

#!/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 HILL CLIMBING AL CIFRADO DE SUSTITUCIÓN SIMPLE MONOALFABÉTICA:
#
# Ataque utilizando el algoritmo hill climbing con estadística de tetragramas a un criptograma cifrado
# mediante sustitución simple monoalfabética.
#
# http://mikelgarcialarragan.blogspot.com/

import re
from unicodedata import normalize
from fitness_texto import test_fitness
import random
from tqdm import tqdm

# FRECUENCIA RELATIVA MONOGRAMAS:
def frecuencia_relativa_monogramas(alfabeto,texto):
    frecuencias_relativas=[]
    for caracter in alfabeto:
        frecuencias_relativas.append([caracter,texto.count(caracter)])
    frecuencias_relativas.sort(key=lambda x:x[1], reverse=True)
    return frecuencias_relativas

# 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"
            monogramas = ['E','T','A','O','I','N','S','H','R','D','L','C','U','M','W','F','G','Y','P','B','V','K','J','X','Q','Z']
        elif  opcion == "2":
            idioma = "Español"
            alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
            monogramas = ['E','A','O','S','R','N','I','D','L','C','T','U','M','P','B','G','Y','V','Q','H','F','Z','J','Ñ','X','W','K']
        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 hill climbing a un criptograma cifrado mediante sustitución simple monoalfabética.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- ATAQUE HILL CLIMBING AL CIFRADO DE 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.")
                    frecuencias_relativas = frecuencia_relativa_monogramas(alfabeto,criptograma)
                    nueva_clave = clave_mejor = ""
                    for i in range(0, len(alfabeto)):
                        nueva_clave += frecuencias_relativas[monogramas.index(alfabeto[i])][0]
                    fitness_mejor = -9999999
                    limite_maximo_iteraciones = 5000
                    limite_maximo_iteraciones_sin_mejora = limite_maximo_iteraciones // 2
                    barra_progreso = tqdm(total = limite_maximo_iteraciones)
                    for i in range(0, limite_maximo_iteraciones):
                        barra_progreso.set_description("Descifrando y calculando 'fitness'...".format(nueva_clave))
                        barra_progreso.update(1)
                        texto_claro = descifrar(alfabeto,criptograma,nueva_clave)
                        fitness = test_fitness(texto_claro,idioma)
                        if fitness > fitness_mejor:
                            clave_mejor = nueva_clave
                            fitness_mejor = fitness
                            n_iteraciones_sin_mejora = 0
                        else:
                            n_iteraciones_sin_mejora += 1
                            if n_iteraciones_sin_mejora > limite_maximo_iteraciones_sin_mejora:
                               break
                        n = m = random.randint(0, len(alfabeto)-1)
                        while n == m:
                            m = random.randint(0, len(alfabeto)-1)
                        nueva_clave = list(clave_mejor)
                        nueva_clave[n%len(alfabeto)], nueva_clave[m%len(alfabeto)] = nueva_clave[m%len(alfabeto)], nueva_clave[n%len(alfabeto)]
                        nueva_clave = ''.join(nueva_clave)
                    barra_progreso.close()
                    if n_iteraciones_sin_mejora > limite_maximo_iteraciones_sin_mejora:
                        print("[+] Fin: se ha superado el límite máximo de iteraciones sin mejora.")
                    print("[+] Nº iteración realizadas:", i+1)
                    print("[+] Nº iteraciones sin mejora a la finalización del algoritmo:", n_iteraciones_sin_mejora-1)
                    print("[+] Mejor puntuación aptitud texto descifrado:", fitness_mejor)
                    print("[+] Mejor clave encontrada para el descifrado:", clave_mejor)
                    texto_claro = descifrar(alfabeto,criptograma,clave_mejor)
                    print("[+] Texto en claro descifrado con la mejor clave encontrada:", texto_claro)
                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 atacar varios criptogramas de diferentes tamaños, con objeto de comprobar su eficacia y eficiencia:

Consideraciones preliminares: En el script se establecen en 5.000 el límite máximo de iteraciones a realizar y en la mitad (2.500) el número de iteraciones a realizar sin mejora de la aptitud ('fitness') de los textos descifrados. Ambos parámetros pueden ser cambiados a conveniencia.

1.- Criptograma: "DROXUSWFIXCLUCDÑOULXCEFSFXAQAWUWQOUFRDAQRNDWFEFEDOULXCEFSFXDÑMQDQRUECEDAEDWDKWFSÑCRFAFRAQAWUWQUECAOFRWDKWFOULXCEFAUIQUDREFQRAUAWDNCXDIQÑCXÑCAQRUECEDASQDEDRADXQRCAFÑCÑDWXCDÑOCAFNCAOFNQRSCXDAEDÑDWXCAWXUFAEDÑDWXCANDTOÑCAEDÑFCRWDXUFXDRWXDFWXFADÑXDODSWFXEDAOULXCDÑWDKWFXDCÑUTCREFÑCAQAWUWQOUFRURPDXACÑFAOULXCEFASFXAQAWUWQOUFRAFROFNSCXCJÑDACÑFAOULXCEFASFXWXCRASFAUOUFRDRQROULXCEFSFXWXCRASFAUOUFRÑCAQRUECEDAEDÑWDKWFSÑCRFAFROCNJUCECAQACREFQRCFXEDRCOUFREULDXDRWDGRFXNCÑNDRWDJCAWCRWDOFNSÑDHCSDXFÑCAQRUECEDADRAUNUANCARFAFRNFEULUOCECASFXDÑOFRWXCXUFDRQROULXCEFSFXAQAWUWQOUFRÑCAQRUECEDAEDÑWDKWFSÑCRFNCRWUDRDRDÑNUANFFXEDRÑFMQDBCODDAAQAWUWQUXÑCASXFSUCAQRUECEDAEDÑWDKWFSÑCRFDKUAWDREUPDXAFAWUSFAEDOULXCEFASFXAQAWUWQOUFRAUDÑOULXCEFFSDXCAFJXDÑDWXCAAUNSÑDAADEDRFNURCOULXCEFSFXAQAWUWQOUFRAUNSÑDAUFSDXCAFJXDIXQSFAEDÑDWXCAADEDRFNURCSFÑUIXCLUOFADEUODMQDQROULXCEFDANFRFCÑLCJDWUOFAUQACQRCAQAWUWQOUFRLUHCSCXCWFEFDÑNDRACHDNUDRWXCAMQDADEUODMQDDASFÑUCÑLCJDWUOFAUQACEULDXDRWDAAQAWUWQOUFRDADREULDXDRWDANFNDRWFAEDÑNDRACHDQRWUSFDASDOUCÑEDOULXCEFSFÑUCÑLCJDWUOFAFRÑFABFNFLFRFADRÑFAMQDQRCQRUECEEDÑWDKWFSÑCRFDAAQAWUWQUECSFXQRCEDDRWXDPCXUCASFAUJUÑUECEDADKUAWDRWDADRÑFAOULXCEFAEDAQAWUWQOUFRAUNSÑDQROCXCOWDXDRDÑWDKWFFXUIURCÑDAXDDNSÑCTCEFSFXQROCXCOWDXEDWDXNURCEFEDÑCÑLCJDWFEDAQAWUWQOUFRDAEDOUXADDAWCJÑDODRSCXDHCAEDOCXCOWDXDAEFREDDÑADIQREFDÑDNDRWFEDÑCSCXDHCDAWCJÑDODDÑOCXCOWDXMQDAQAWUWQGDCÑSXUNDXDÑDNDRWFEDÑCSCXDHCCPDODADÑAUAWDNCQACDÑNUANFCÑLCJDWFSCXCDÑWDKWFDROÑCXFGSCXCDÑWDKWFOULXCEFDAWFSDXNUWDCSXFPDOBCXDÑFXEDREDLURUEFSFXÑFACÑLCJDWFASCXCCAULCOUÑUWCXÑCEDAOXUSOUFREDÑFACÑIFXUWNFAECREFADCAUÑFAÑÑCNCEFAOULXCEFAEDCÑLCJDWFURPDXWUEFGEDCÑLCJDWFEDASÑCTCEFFWXCAPDODADÑFXEDRRFADQWUÑUTCGADEUODMQDDAQRCÑLCJDWFNDTOÑCEFFQRCÑLCJDWFAURXCRIFADEUODMQDQRAUAWDNCEDOULXCEFEDAQAWUWQOUFRAUNSÑDDANFRFCÑLCJDWUOFOQCREFOCECOCXCOWDXADAQAWUWQGDAUDNSXDSFXQREDWDXNURCEFOCXCOWDXEDÑCÑLCJDWFEDÑWDKWFOULXCEFDRDAWDWUSFEDOULXCEFACÑCÑLCJDWFQACEFSCXCDÑWDKWFOULXCEFADÑDÑÑCNCCÑLCJDWFEDAQAWUWQOUFRAUOCECAUNJFÑFEDÑWDKWFDROÑCXFDAAQAWUWQUEFSFXQRAUNJFÑFEUAWURWFAEDÑWDKWFOULXCEFGADCRDÑRQNDXFEDAUNJFÑFADÑRQNDXFEDAUNJFÑFAEDÑWDKWFDROÑCXFPDNFAMQDDÑSFAUJÑDRQNDXFEDAQAWUWQOUFRDAMQDADSQDEDREDLURUXDADÑRQNDXFSFAUJÑDEDSDXNQWCOUFRDA"

Tamaño: 2.131 caracteres.

Clave empleada en el cifrado: "CJOEDLIBUPZÑNRVFSMXAWQHYKGT"

Tiempo de ejecución: 02:42

Mejor clave encontrada: "CJOEDLIBUHZÑNRVFSMXAWQPYKGT"

Comentarios tras el ataque realizado: La clave que se obtiene es la correcta (los dos únicos caracteres de ella que no se corresponden a la clave original son los correspondientes a la "J" y "W" del texto plano, que están intercambiados, pero ninguno de ellos aparece en el texto en claro), por lo que el criptograma se descifra correctamente al primer intento de ataque.

2.- Criptograma: "KATMUDSPBMXZUXKGTUZMXIPDPMJÑJSUSÑTUPAKJÑALKSPIPIKTUZMXIPDPMKGFÑKÑAUIXIKJIKSKYSPDGXAPJPAJÑJSUSÑUIXJTPASKYSPTUZMXIPJUBÑUKAIPÑAJUJSKLXMKBÑGXMGXJÑAUIXIKJDÑKIKAJKMÑAXJPGXGKSMXKGTXJPLXJTPLÑADXMKJIKGKSMXJSMUPJIKGKSMXJLKOTGXJIKGPXASKMUPMKASMKPSMPJKGMKTKDSPMIKJTUZMXKGSKYSPMKXGUOXAIPGXJÑJSUSÑTUPAUAVKMJXKAÑATUZMXIPDPMSMXAJDPJUTUPAGXJÑAUIXIKJIKGSKYSPDGXAPJPATXLWUXIXJÑJXAIPÑAXPMIKAXTUPAIUZKMKASKHAPMLXGLKASKWXJSXASKTPLDGKCXDKMPGXJÑAUIXIKJKAJULUJLXJAPJPALPIUZUTXIXJDPMKGTPASMXMUPKAÑATUZMXIPDPMJÑJSUSÑTUPAGXJÑAUIXIKJIKGSKYSPDGXAPLXASUKAKAKGLUJLPPMIKAGPFÑKNXTKKJJÑJSUSÑUMGXJDMPDUXJÑAUIXIKJIKGSKYSPDGXAP"

Tamaño: 589 caracteres.

Clave empleada en el cifrado: "XWTIKZBNUCRGLAEPDFMJSÑVQYHO"

Tiempo de ejecución: 01:47

Mejor clave encontrada: "XWTIKZBNUCRGLAEPDFMJSÑVQYHO"

Comentarios tras el ataque realizado: La clave que se obtiene es la correcta, por lo que el criptograma se descifra correctamente al primer intento de ataque.

3.- Criptograma: "ZUSIXERYQIDHXDZÑSXHIDOYEYIWTWRXRTSXYUZWTUAZRYOYOZSXHIDOYEYIZÑBTZTUXODOZWOZRZPRYEÑDUYWYUWTWRXRTXODWSYURZPRYSXHIDOYWXQTXZUOYTUWXWRZADIZQTÑDIÑDWTUXODOZWETZOZUWZITUDWYÑDÑZRIDZÑSDWYADWSYATUEDIZWOZÑZRIDWRIXYWOZÑZRIDWAZMSÑDWOZÑYDURZIXYIZURIZYRIYWZÑIZSZERYIOZWSXHIDZÑRZPRYIZDÑXMDUOYÑDWTWRXRTSXYUXUNZIWD"

Tamaño: 294 caracteres.

Clave empleada en el cifrado: "DJSOZHQFXGKÑAULYEBIWRTNVPCM"

Tiempo de ejecución: 02:28

Mejor clave encontrada: "DFSOZHQCXKVÑAUJYEBIWRTNLGPM"

Comentarios tras el ataque realizado: La clave que se obtiene no es del todo correcta (hay varios caracteres que no se corresponden con la clave original que no tienen incidencia en el descifrado del criptograma por no aparecer en el texto en claro. El único carácter incorrecto que sí incide en que el texto plano obtenido no sea del todo correcto es el correspondiente a la "X", habiéndose obtenido en el texto en claro la "Y" en su lugar). No obstante lo dicho, el descifrado del criptograma es casi correcto al primer intento de ataque.

4.- Criptograma: "DZUHPWGAÑHMLPMDXUPLHMYAWAHNFNGPGFUPAZDNFZVDGAYAYDUPLHMYAWAHDXJFDFZPYMYDNYDGDTGAWXMZANAZNFNGPGFPYMNUAZGDTGAUPLHMYANPÑFPDZYAFZNPNGDVMHDÑFXMH"

Tamaño: 138 caracteres.

Clave empleada en el cifrado: "MKUYDLÑIPOCXVZEAWJHNGFSRTBQ"

Tiempo de ejecución: 02:26

Mejor clave encontrada: "AWUYDEÑOPBSXVZQMLJHNGFCRKTI"

Comentarios tras el ataque realizado: La clave que se obtiene no es la correcta, pero, tal y como se puede observar en la figura anterior, el texto en claro que se obtiene es bastante legible, por lo que es posible depurar manualmente la clave obtenida hasta dar con la correcta y descifrar el criptograma correctamente.

Tras estas pruebas y algunas más que he realizado, concluyo que este método de ataque es bastante eficaz, sobre todo con criptogramas no muy cortos, y eficiente (aunque seguro que se puede mejorar el algoritmo que he implementado). En cualquier caso, si no se obtuviera el texto en claro correcto tras un primer intento de ataque, tras reintentar éste, no hace falta que sea en muchas ocasiones, suele darse con el texto plano correcto o con uno parcialmente descifrado que nos permita hallar la clave correcta.

Quizás también te interese: