Criptografía (CCLXXII): Ataque 'Hill Climbing' a la sustitución simple monoalfabética

Decía en este post que iba a desarrollar el algoritmo 'Hill Climbing' para atacar criptogramas cifrados mediante sustitución simple monoalfabética 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 con las sucesivas claves a probar. Todo ello, con objeto de obtener la clave correcta empleada en el cifrado.

El algoritmo que voy a implementar puede representarse gráficamente de la siguiente manera:

1.- En primer lugar, se generará la clave con la que se iniciará la secuencia de descifrados, pero no será aleatoria, sino que como clave inicial se generará aquella conforme a la frecuencia relativa de los caracteres (monogramas) del criptograma con respecto a las letras del idioma en el que esté escrito el texto en claro.

Es decir, si el idioma es el español, la letra "E" de la clave (el alfabeto de sustitución) será la que aparezca con mayor frecuencia en el criptograma, la letra "A" del alfabeto de la clave se corresponderá con la segunda con mayor frecuencia de aparición en el criptograma, y así sucesivamente.

El orden de frecuencia de aparición de las letras (de mayor a menor) considerado para el español e inglés es el siguiente (ver este post):

a) Español:

['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']

b) Inglés:

['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']

además, se inicializarán: la mejor calificación o puntuación de la aptitud del texto descifrado ('fitness') y el límite máximo de iteraciones sin mejora a realizar antes de dar por finalizada la ejecución del algoritmo.

2.- Se obtiene el texto descifrado y se califica su aptitud ('fitness').

3.- Si se ha obtenido una mejora, es decir, el 'fitness' del texto descifrado es mayor que el mejor 'fitness' obtenido hasta el momento, entonces se pondrá como mejor clave la utilizada en el descifrado del texto y como mejor 'fitness' el obtenido en este descifrado, y se pondrá a cero el número de iteraciones sin mejora. Nótese que la primera vez siempre habrá mejora, ya que el mejor 'fitness' se ha inicializado con un número negativo grande.

Mientras que si no ha habido mejora se incrementará en una unidad el número de iteraciones sin mejora y en el caso de que éste haya superado el límite prestablecido el algoritmo finalizará.

4.- La nueva clave (alfabeto de sustitución) a utilizar en el siguiente descifrado será la mejor clave hasta el momento en la que se permutarán (intercambiarán) dos letras al azar.

En un próximo post pondré un script en python con esta implementación, lo ejecutaré con varios criptogramas de diferentes tamaños, para comprobar su eficacia y eficiencia, y comentaré los resultados obtenidos.

Quizás también te interese: