El script que puse en el segundo de los citados posts utilizaba un tipo de ataque denominado ataque de fuerza bruta, que consiste en probar todas las posibles claves (en este caso, desplazamientos) 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 el caso de este criptosistema, recorrer el espacio de claves hasta encontrar la clave correcta, es perfectamente posible realizar 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.
Pues bien, en este post pongo un script en python para atacar criptogramas cifrados mediante el cifrado afín utilizando el análisis de frecuencias de los caracteres del criptograma.
Decía en el post anterior refiriéndome al cifrado César, que en un criptosistema de sustitución simple monoalfabética, como también lo es el cifrado afín, las frecuencias de aparición de las letras en el idioma en que se escribió el texto en claro se trasladan al criptograma, es decir, si la letra más frecuente en el idioma en que se escribió el texto en claro es la "E" (como así ocurre en español, con un porcentaje teórico de aparición en un texto de aproximadamente un 13,68%, y en inglés, con un 12,702%), en un criptograma un poco largo, aunque no es necesario que sea de mucho tamaño, podremos sospechar sin mucho riesgo a equivocarnos que la letra que más aparezca en él sea precisamente la "E", máxime teniendo en cuenta que la letra "E" es significativamente la letra más frecuente en ambos idiomas, y que la siguiente letra que más aparezca se corresponda en el texto en claro con la "A", caso del español, o la "T", caso del inglés. Y, si nos equivocamos, porque la estadística del lenguaje nos "juega una mala pasada" en el criptograma concreto, y no obtenemos en el descifrado un texto en claro inteligible, siempre podremos asociar las dos letras más frecuentes en el criptograma a otras letras muy frecuentes en el idioma correspondiente hasta obtener un texto en claro legible.
En el primero de los posts que he citado al principio decía que las funciones de cifrado y descifrado de este criptosistema son:
Donde:
mi: carácter i-ésimo del mensaje o texto en claro a cifrar.
D: función de descifrado.
ci: carácter i-ésimo del criptograma o texto cifrado.
n: tamaño del alfabeto.
Y pongo como ejemplo de criptograma a atacar el siguiente:
GÑWZLVNBHNLZXGAKXFZMHBGWZLVNBHMHVAKAFZFKWZHXGXGÑQKGWNBNAZSRHÑHBGÑNÑLNRGFHBGÑFGYFHGXWÑNVHGAAKAFZFKZBHMHVKXAZSRHÑHBGÑNÑLNRGFHBGÑFGYFHWZLVNBHAZGXBHGÑXKSGVHBGAZSRHÑHABGÑNÑLNRGFHGXWÑNVHZPKNÑQKGGÑXKSGVHBGAZSRHÑHABGÑNÑLNRGFHWZLVNBHMNVNUNÑÑNVGÑAZSRHÑHBGÑNÑLNRGFHWZLVNBHQKGAKAFZFKDGNKXBGFGVSZXNBHAZSRHÑHBGÑNÑLNRGFHGXWÑNVHAGKANKXNLKXWZHXSNFGSNFZWNNLZXGXNVZFSGFZWNSHBKÑNV
Al igual que el que puse de ejemplo en el post anterior, el criptograma ya nos da alguna pista: el alfabeto empleado en la sustitución es el de letras mayúsculas en español (27 letras), y si contamos la frecuencia de aparición de cada una de las letras en el criptograma podemos ver que la "G" es la que más aparece; un total de 43 veces, lo que supone un porcentaje de aparición del 11,94% sobre el total de las letras del criptograma (360), resultado que está cerca del esperado para la letra "E" en español, y la "H" es la segunda letra que más aparece; un total de 39 veces, lo que supone un porcentaje de aparición del 10,83% sobre el total de las letras del criptograma (360), resultado que está cerca del esperado para la letra "A" en español, Por tanto:
Cifrado "A": (a * "A" + b) mod 27 = "H"; (a * 0 + b) mod 27 = 7; b = 7
Y, aplicando la función de descifrado indicada antes, el descifrado se realizaría de la siguiente manera:
El texto claro que se obtiene con a = 20 y b = 7 no es inteligible, por lo que se probaría suponiendo que la "G" en el criptograma es la "E" en el texto en claro y que la "H" es la "O":
Cifrado "O": (a * "O" + b) mod 27 = "H"; (a * 15 + b) mod 27 = 7
El script es el siguiente:
#!/usr/bin/env python # -*- coding: utf-8 -*- # ATAQUE MEDIANTE ANÁLISIS DE FRECUENCIAS AL CIFRADO AFÍN: # # Ataque mediante análisis de frecuencias a un criptograma cifrado # mediante el cifrado afín. # # http://mikelgarcialarragan.blogspot.com/ import re from unicodedata import normalize import math # Obtener las constantes de decimación (a) y desplazamiento (b). def decimación_desplazamiento(alfabeto,letra_texto_claro_1,letra_criptograma_1,letra_texto_claro_2,letra_criptograma_2): if math.gcd(alfabeto.find(letra_texto_claro_2) - alfabeto.find(letra_texto_claro_1), len(alfabeto)) == 1: a = ((alfabeto.find(letra_criptograma_2) - alfabeto.find(letra_criptograma_1)) * pow(alfabeto.find(letra_texto_claro_2) - alfabeto.find(letra_texto_claro_1), -1, len(alfabeto)))%len(alfabeto) if math.gcd(a, len(alfabeto)) == 1: b = (alfabeto.find(letra_criptograma_2) - a * alfabeto.find(letra_texto_claro_2))%len(alfabeto) else: a = b = 0 else: a = b = 0 return a,b # 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(a, -1, len(alfabeto)) * (alfabeto.find(caracter) - b)) % len(alfabeto)] return texto_claro def main(): # SELECCIÓN DE IDIOMA: # Se solicita que se indique el idioma en el que se supone que se cifró 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 se cifró el texto en claro: ") if opcion == "1": idioma = "Inglés" elif opcion == "2": idioma = "Español" else: print ("*** ERROR: Opción no válida.") print ("") print ("[+] Idioma:", idioma) # SELECCIÓN DE ALFABETO: # Se solicita que se indique el alfabeto a emplear. if idioma == "Inglés": opcion = "1" 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'] else: alfabeto = "" while alfabeto == "": print ("") print ("*** SELECCIÓN DE ALFABETO ************************") print ('1. Alfabeto de 26 caracteres ("Ñ" excluida).') print ('2. Alfabeto de 27 caracteres ("Ñ" incluida).') print ("") opcion = input("Por favor, seleccione el alfabeto a utilizar: ") if opcion == "1": alfabeto = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 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'] elif opcion == "2": 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 ("") 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 mediante análisis de frecuencias al cifrado afín.") print ("2. Salir.") print ("") opcion = input("Por favor, seleccione una opción: ") if opcion == "1": print ("") print ("--- ATAQUE MEDIANTE ANÁLISIS DE FRECUENCIAS:") # 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) print("[+] Tamaño del criptograma:", len(criptograma), "caracteres.") frecuencia_relativa=[] for caracter in alfabeto: frecuencia_relativa.append([caracter,criptograma.count(caracter),criptograma.count(caracter)/len(criptograma)*100]) frecuencia_relativa.sort(key=lambda x:x[1], reverse=True) print("[+] Caracteres del alfabeto con mayor frecuencia de aparición en el criptograma, frecuencia relativa y porcentaje de aparición:") print(frecuencia_relativa[0][0], frecuencia_relativa[0][1], frecuencia_relativa[0][2],"%") print(frecuencia_relativa[1][0], frecuencia_relativa[1][1], frecuencia_relativa[1][2],"%") print("[+] Probando con los dos caracteres de frecuencia más alta en", idioma, ":", monogramas[0], monogramas[1]) a,b = decimación_desplazamiento(alfabeto,monogramas[0],frecuencia_relativa[0][0],monogramas[1],frecuencia_relativa[1][0]) if a != 0: texto_claro = descifrar(alfabeto,criptograma,a,b) print("[+] Texto claro:", texto_claro) fin = "*" caracter1_siguiente = 0 caracter2_siguiente = 2 while fin != "S": if caracter1_siguiente <= 7: if a != 0: fin = input('¿Es inteligible el texto en claro obtenido (S)í?: ').upper() if fin != "S": if caracter2_siguiente <= 7: if caracter1_siguiente != caracter2_siguiente: print("[+] Probando con otros dos caracteres de frecuencia alta en", idioma, ":", monogramas[caracter1_siguiente], monogramas[caracter2_siguiente]) a,b = decimación_desplazamiento(alfabeto,monogramas[caracter1_siguiente],frecuencia_relativa[0][0],monogramas[caracter2_siguiente],frecuencia_relativa[1][0]) if a != 0: texto_claro = descifrar(alfabeto,criptograma,a,b) print("[+] Texto claro:", texto_claro) else: print("[+] No se ha podido obtener texto en claro con los dos caracteres probados.") else: a = b = 0 caracter2_siguiente+=1 else: caracter1_siguiente+=1 caracter2_siguiente = 0 a = b = 0 else: fin = "S" print("[+] No quedan más posibilidades a probar con caracteres de frecuencia alta.") 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:
Quizás también te interese:
Comentarios
Publicar un comentario