Ir al contenido principal

Criptografía (CCLXXIV): Ataque de diccionario a la sustitución simple monoalfabética en python

Imagen
De

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:

Etiquetas:

Comentarios

Publicar un comentario

Entradas populares de este blog

Criptografía (I): cifrado Vigenère y criptoanálisis Kasiski

De
Hace unos días mi amigo Iñaki Regidor ( @Inaki_Regidor ), a quien dedico esta entrada :), compartió en las redes sociales un post titulado "Criptografía: el arte de esconder mensajes"  publicado en uno de los blogs de EiTB . En ese post se explican ciertos métodos clásicos para cifrar mensajes , entre ellos el cifrado de Vigenère , y , al final del mismo, se propone un reto consistente en descifrar un mensaje , lo que me ha animado a escribir este post sobre el método Kasiski  para atacar un cifrado polialfabético ( conociendo la clave descifrar el mensaje es muy fácil, pero lo que contaré en este post es la forma de hacerlo sin saberla ). El mensaje a descifrar es el siguiente: LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC Como ya he dicho el método de Vigenère es un sistema de sustitución polialfabético , lo que significa que, al contrario que en un sistema de
103 comentarios
Leer más

Criptografía (XXIII): cifrado de Hill (I)

De
En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill , propuesto por el matemático Lester S. Hill , en 1929, y que se basa en emplear una matriz como clave  para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente . Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice  Dani , amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasat
5 comentarios
Leer más

¿Qué significa el emblema de la profesión informática? (I)

De
Todas o muchas profesiones tienen un emblema que las representa simbólicamente y en el caso de la  informática: " es el establecido en la resolución de 11 de noviembre de 1977  para las titulaciones universitarias superiores de informática, y  está constituido por una figura representando en su parte central  un  núcleo toroidal de ferrita , atravesado por  hilos de lectura,  escritura e inhibición . El núcleo está rodeado por  dos ramas : una  de  laurel , como símbolo de recompensa, y la otra, de  olivo , como  símbolo de sabiduría. La  corona  será la  de la casa real  española,  y bajo el escudo se inscribirá el acrónimo de la organización. ". Veamos los diferentes elementos tomando como ejemplo el emblema del COIIE/EIIEO (Colegio Oficial de Ingenieros en Informática del País Vasco/ Euskadiko Informatikako Ingeniarien Elkargo Ofiziala ) . Pero no sólo el COIIE/EIIEO adopta el emblema establecido en dicha resolución, sino que éste se adopta también como im
Publicar un comentario
Leer más