Criptografía (CCLXVIII): Criptoanálisis mediante análisis de frecuencias (III)

Decía en el post anterior sobre el análisis de frecuencias que conocer la frecuencia relativa de los monogramas (letras), bigramas (grupos de dos letras), trigramas (grupos de tres letras) y tetragramas (grupos de cuatro letras) en un determinado idioma puede ayudarnos a determinar cuánto se parece un texto descifrado a un texto escrito en ese idioma y, por tanto, que nos puede servir para automatizar el criptoanálisis, por ejemplo, de los cifrados por sustitución simple monoalfabética.

Para romper un cifrado de este tipo mediante la técnica del análisis de frecuencias iremos descifrando el criptograma objeto de análisis con diferentes claves (alfabetos de sustitución) y comprobando si los textos que se van produciendo se van pareciendo cada vez más a un texto escrito en el idioma en el que se escribió el mensaje. Si esto ocurre vamos por el buen camino y continuaremos probando más claves hasta encontrar un texto en claro total o parcialmente descifrado (para ello utilizaré el algoritmo 'hill climbing') y, por tanto, la clave correcta o una que se aproxime bastante a ésta.

Para llevar a cabo este enfoque de criptoanálisis automatizado necesitamos calificar o puntuar la aptitud ('fitness') de los textos que se vayan obtenido como consecuencia del descifrado, es decir, determinar si son similares o no al idioma en el que se escribió el texto en claro. Un texto parecido al idioma en el que se escribió el texto en claro obtendrá una calificación o puntuación alta (buen 'fitness'), mientras que un texto de caracteres sin sentido obtendrá una calificación o puntuación baja (mal fitness').

Para la medida de la aptitud de un texto se suelen utilizar las estadísticas de tetragramas (grupos de 4 caracteres).

Pongo un ejemplo:

Como paso previo, utilizando el mismo corpus de diez obras de literatura española que en el post anterior, se cuentan el número de ocurrencias de cada tetragrama existente en el corpus (de un total de aproximadamente 7.000.000 de caracteres) y se divide esa cantidad entre el total de tetragramas para calcular la probabilidad de aparición de cada uno de ellos.

Para hacerse una idea del resultado (se han obtenido 49.781 tetragramas) indicar que los 30 más frecuentes son los siguientes (número de ocurrencias y frecuencia relativa de aparición):

AQUE 20616 0.0029814022453360273
OQUE 20116 0.00290909427469827
DELA 15679 0.0022674333432588074
QUEL 14634 0.0021163096846258935
ESTA 14460 0.002091146510843954
ANDO 13802 0.001995989221484665
SQUE 12240 0.0017700991212123097
ENTE 12188 0.0017625790922659828
QUEE 11243 0.0016259170277606208
COMO 10411 0.0015055965646193917
QUES 10006 0.001447027108402808
PARA 9552 0.001381371471063724
EQUE 9411 0.0013609806233438762
ABIA 9090 0.0013145589061944359
ELLA 9069 0.00131152197142765
CION 8813 0.001274500290461118
HABI 8704 0.001258737152862087
RQUE 8465 0.0012241739428972386
OSDE 8291 0.001199010769115299
ENTO 8272 0.0011962630662310642
ADEL 8061 0.0011657491026219305
ODEL 7916 0.0011447797911369806
ESDE 7886 0.0011404413128987153
ASDE 7793 0.0011269920303600923
ACON 7642 0.0011051550232274894
TABA 7637 0.0011044319435211118
ANTE 7466 0.0010797026175629987
PERO 7317 0.0010581548423129468
IENT 7249 0.0010483209583062119
SDEL 7233 0.0010460071032458037

Ahora, supongamos un texto formado por una sola palabra: "CIFRADO", los tetragramas serían los siguientes: "CIFR", "IFRA", "FRAD", "RADO". Luego la probabilidad de aparición de "CIFRADO" sería:

p("CIFRADO") = p("CIFR") x p("IFRA") x p("FRAD") x p("RADO")

Donde la probabilidad de aparición de cada tetragrama sería la probabilidad de aparición de cada uno de ellos obtenida en el corpus. Y, finalmente, expresamos la probabilidad de aparición como:

log(p("CIFRADO")) = log(p("CIFR")) + log(p("IFRA")) + log(p("FRAD")) + log(p("RADO"))

Con lo que ya podemos implementar nuestra función para calificar o puntuar la aptitud ('fitness') de un texto: se divide éste en tetragramas y se suman los logaritmos de las probabilidades de aparición de cada uno de ellos que se hayan obtenido en nuestro corpus. Cuanto mayor sea el valor obtenido mayor probabilidad de que el texto sea del idioma al que queremos saber si corresponde, en nuestro caso el español.

Voy a hacer una prueba. Cifro un texto mediante sustitución simple monoalfabética: genero una clave aleatoria ("BLTGPVSZUCOJDNRXAQWKHMFÑIYE") y obtengo el siguiente criptograma: "HPIHXGPAWMPLBABWBFPWJBAMNHMBTUXNQMPXLHUPNPBJTBJUVUTBWKMBAHUHMG".

Creo un pequeño script en python para calificar la aptitud de este texto y obtengo una puntuación de -512.7892552378945.

Voy a ver qué ocurre si ahora califico la aptitud del texto en claro con cuyo cifrado obtuve el criptograma anterior, que es: "TEXTODEPRUEBAPARAVERLAPUNTUACIONQUEOBTIENEALCALIFICARSUAPTITUD", y obtengo una puntuación de -259.91637182026096.

Como se ve, la mayor puntuación obtenida se corresponde con el texto en claro, lo que indica que este texto es más similar a un texto escrito en español que el criptograma (un galimatías sin ningún sentido); esto se debe a que, por ejemplo, tetragramas muy frecuentes en español como "PARA" y "CION" contribuyen a la puntuación en mayor medida que "HPIH" y "PIHX", que son muy poco frecuentes o ni siquiera existen español.

Esta forma de calificar la aptitud de un texto me servirá en un próximo post para, utilizando el algoritmo de escalado de la colina ('hill climbing') junto con esta función de puntuar la aptitud de un texto a partir de las estadísticas de tetragramas, poner un script en python con el objetivo de romper cifrados de sustitución simple monoalfabética.

Quizás también te interese: