Criptografía (CCLXXI): El algoritmo 'Hill Climbing'

Tal y como nos cuenta wikipedia el algoritmo 'Hill Climbing', también llamado algoritmo de "ascenso de la colina" es un algoritmo iterativo que comienza con una solución arbitraria a un problema, un punto actual en un espacio de búsqueda, para luego intentar encontrar una mejor solución, un nuevo punto mejor en el espacio de búsqueda, variando incrementalmente un único elemento de la solución. Si el cambio produce una mejor solución, otro cambio incremental se realizará a la nueva solución, repitiendo este proceso hasta que no se puedan encontrar mejoras o se hayan alcanzado un número predefinido de iteraciones.

¿Podemos aplicar un algoritmo de este tipo para el criptoanálisis automatizado de criptogramas?

Pensemos en un cifrado de sustitución simple monoalfabética, en el que cada carácter del texto en claro o texto plano se sustituye siempre por un mismo carácter en el texto cifrado o criptograma.

En este tipo de cifrados, cuando el alfabeto de sustitución es aleatorio, tal y como dije en un post anterior, no es nada aconsejable realizar un ataque de fuerza bruta, ya que en el caso del alfabeto español con letras mayúsculas (27 caracteres) el tamaño del espacio de claves o alfabetos de sustitución posibles es de 27!, es decir, más de diez mil cuatrilllones, pero sí es posible realizar otro tipo de ataques.

Pues bien, sin conocer nada más que el criptograma, es decir, sin disponer de información adicional, como parte del texto claro ('cribs') o de otra clase, que podría posibilitar otro tipo de ataques, me propongo implementar un algoritmo de este tipo mediante 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.

La calificación de la aptitud de un texto consiste en determinar si éste se asemeja más o menos a un texto escrito en el idioma al que queremos comprobar si corresponde o no. Un texto que obtenga una calificación o puntuación alta tendrá una buena aptitud (buen 'fitness'), lo que significará que se asemeja mucho a un texto escrito en el idioma para el que queremos calificar ese texto, mientras que si la puntuación es baja (mal 'fitness') significará que no se parece (ver esta entrada donde puse un script en python para calificar la aptitud de un texto).

La idea para implementar este algoritmo es la siguiente:

1.- Se genera la clave a probar en el descifrado del criptograma, se califica la aptitud ('fitness') del texto descifrado que se obtiene y se almacena esa puntuación.
2.- Se cambia una letra de la clave y se vuelve a calificar la aptitud ('fitness') del texto descifrado que se obtiene con la nueva clave.
3.- Si la puntuación obtenida con la nueva clave es mayor que la puntuación almacenada, entonces se sustituye la clave con la nueva clave y la puntuación almacenada con la nueva puntuación.
4. Si no se obtiene una mejor puntuación tras un número de iteraciones prestablecido el algoritmo finaliza, en caso contrario se vuelve al punto 2.

A medida que el algoritmo va realizando iteraciones, el texto que se va obtenido con las nuevas claves va obtenido una aptitud ('fitness') mayor y la clave se va ajustando a la clave empleada en el cifrado, aunque puede que no se encuentre la verdadera solución, ya que este algoritmo sólo garantiza encontrar un óptimo local, no el óptimo global (la verdadera solución), es decir, la solución que se va a alcanzar depende del punto de partida (la clave inicial) en el espacio de búsqueda y posteriores iteraciones, con lo que podría ser necesario reiniciar el algoritmo.

Lo dicho, en posteriores post desarrollaré este algoritmo para atacar cifrados de sustitución simple monoalfabética y pondré un script en python para ello.

No obstante lo dicho, el algoritmo 'Hill Climbing' puede ser utilizado para atacar otros tipos de cifrados clásicos, para lo que pondré otras entradas con el desarrollo y las implementaciones correspondientes, e incluso tiene aplicación en multitud de otras materias, entre otras en inteligencia artificial.

Quizás también te interese: