Criptografía (CCL): Ataque de fuerza bruta al cifrado afín 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 afín. 

Pues bien, ahora le toca el turno a un script para atacar un criptograma cifrado utilizando este criptosistema sin saber ni la constante de decimación ni la de desplazamiento empleadas en el cifrado.

El tipo de ataque a realizar mediante este script se denomina ataque de fuerza bruta, y consiste en probar todas las posibles claves (en este caso, la constante de decimación y la constante de desplazamiento) 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; lo que en este caso, recorrer el espacio de claves hasta encontrar la clave correcta, es perfectamente factible porque, aunque el espacio de claves es muy superior al del cifrado César, es una tarea que queda al alcance de cualquier ordenador en un tiempo muy pequeño.

Para hacernos una idea del tamaño del espacio de claves a recorrer: para un alfabeto de 26 caracteres ("Ñ" excluida), éste sería de: (nº de posibles constantes de decimación * nº de posibles constantes de desplazamiento) - (nº de constantes de decimación no coprimas con el tamaño del alfabeto * 26) = (26 * 26)  - (nº de constantes de decimación pares * 26) - (constante de decimación 13 * 26) = (26 * 26) - (13 * 26) - (1 * 26) = 676 - 338 - 26 = 312, y para un alfabeto de 27 caracteres ("Ñ" incluida), éste sería de: (nº de posibles constantes de decimación * nº de posibles constantes de desplazamiento) - (nº de constantes de decimación no coprimas con el tamaño del alfabeto * 27) = (27 * 27)  - (constante de decimación 3,6,9,12,15,18,21,24,27 * 27) = (27 *27) - (9 * 27) = 729 - 243 = 486.

Por tanto, como ya he dicho, un ordenado tardará muy poco tiempo en descifrar ese número de criptogramas probando todas las claves, y su comprobación visual, para ver cuál arroja un texto inteligible, tampoco será muy costosa.

No obstante lo último indicado, para facilitar la comprobación visual, el script utiliza para cada uno de los idiomas a los que podría corresponderse el criptograma conforme al alfabeto utilizado (si se excluye la "Ñ" supone que el idioma es el inglés, y si se incluye supone que es el español) 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), de tal forma que se asigna una puntuación a cada texto en claro obtenido en función de si en el descifrado se hallan trigramas y/o palabras del idioma en el que se supone se realizó el cifrado, y muestra los resultados ordenados descendentemente por la puntuación obtenida por cada uno de ellos.

El script es el siguiente:

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

# ATAQUE DE FUERZA BRUTA AL CIFRADO AFÍN:
#
# Ataque de fuerza bruta a un criptograma cifrado
# mediante el cifrado afín probando todas las
# constantes de decimación y desplazamiento posibles.
#
# http://mikelgarcialarragan.blogspot.com/

import re
from unicodedata import normalize
import math

# ATAQUE DE FUERZA BRUTA:
# La función de descifrado es: Da,b(ci) = (inv(a) * (ci - b)) mod n
def descifrar(alfabeto,criptograma,a,b):
    texto_claro = ''
    for caracter in criptograma:
        texto_claro = texto_claro + alfabeto[(pow(int(a), -1, len(alfabeto)) * (alfabeto.find(caracter) - int(b))) % len(alfabeto)]
    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 una opcion: ")
        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 fuerza bruta al cifrado afín.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- ATAQUE DE FUERZA BRUTA:")
            # 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 alfabeto_seleccionado == "1":
                    criptograma = criptograma.replace('Ñ','N')
                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)
                    if alfabeto_seleccionado == "1":
                        f_trigramas = open("english_trig.txt")
                        f_palabras = open("english_word.txt")
                    else:
                        f_trigramas = open("espanol_trig.txt")
                        f_palabras = open("espanol.pala.txt")
                    trigramas = f_trigramas.readlines()
                    palabras = f_palabras.readlines()
                    textos_descifrados = []
                    for a in range(0,len(alfabeto)):
                        if math.gcd(a,len(alfabeto)) == 1:
                            for b  in range(0,len(alfabeto)):
                                for caracter in criptograma:
                                    texto_claro = descifrar(alfabeto,criptograma,a,b)
                                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)
                                textos_descifrados.append([puntos, a, b, texto_claro])
                                b+=1
                        a+=1
                    textos_descifrados.sort(key=lambda x:x[0], reverse=True)
                    for texto_descifrado in range(0,len(textos_descifrados)):
                        print(texto_descifrado+1, ".- Constante de decimación: ", textos_descifrados[texto_descifrado][1],
                                                              "Constante de desplazamiento: ", textos_descifrados[texto_descifrado][2],
                                                              "--> Texto en claro: ", textos_descifrados[texto_descifrado][3])
                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: