Solución Kriptojuego 20080131: La vergüenza española (II)

Tal y como comenté en la entrega anterior, y por sorprendente que parezca, la resolución por fuerza bruta de un simple cifrado de sustitución con clave (como el de nuestro kriptojuego) resultaría impracticable incluso haciendo uso de los recursos computacionales de que hoy en día disponemos. Sin embargo, algunos de nuestros lectores lo reventaron en pocos minutos. ¿Cómo puede ser esto?

La "culpa" de todo la tienen los criptoanalistas árabes del califato abbasí, iniciado hacia el año 750 y que dio paso a la Edad de Oro de la civilización islámica, que por entonces dominaba la mitad del mundo conocido. Estos califas estaban menos interesados en la conquista que en el establecimiento de una sociedad civil pacífica y próspera, donde florecieron las matemáticas y otras ciencias, como la medicina o la propia criptografía. Así, se ha documentado que en esta época se protegían las declaraciones de impuestos mediante criptografía, en concreto con un sistema de sustitución monoalfabética con alfabeto mixto.

Sin embargo el mayor mérito de estos antecesores árabes es el descubrimiento del criptoanálisis, es decir, la rama de la criptología que se encarga de reventar los mensajes cifrados sin necesidad de contar con la clave...

Curiosamente, el origen de la invención es religioso, ya que los teólogos de Bagdag y Basora (ciudades de triste fama actualmente, pero que en aquella época constituían auténticos centros del saber y la erudición) se dedicaron a analizar en profundidad la escritura de las revelaciones atribuidas a Mahoma, a fin de poder establecer su autenticidad y clasificarlas según su cronología. Para ello estudiaban minuciosamente la estructura de palabras y frases, buscando patrones de coincidencia con los escritos disponibles atribuidos al Profeta. No tardaron mucho en darse cuenta de que algunas letras del idioma árabe eran mucho más frecuentes que otras, revelando un patrón de frecuencias que también se conservaba en los textos cifrados.

El origen del criptoanálisis estaba así servido en bandeja y el primer tratado del que se tiene constancia lo firma Al-Kindi, un científico "todoterreno" del siglo IX, autor de cientos de obras relevantes en varias disciplinas diferentes. El texto clave de Al-Kindi se titula "Sobre descifrar mensajes criptográficos" y fue redescubierto en Estambul en 1987. Su revolucionario método de criptoanálisis está resumido en dos párrafos, cuya traducción al castellano (ver Simon Singh, "Los Códigos Secretos", Ed. Debate) dice:

Una manera de resolver un mensaje cifrado, si sabemos en qué lengua está escrito, es encontrar un texto llano diferente escrito en la misma lengua y que sea lo suficientemente largo para llenar una hoja, y luego contar cuántas veces aparece cada letra. A la letra que aparece con más frecuencia la llamamos "primera", a la siguiente en frecuencia la llamamos "segunda", a la siguiente la llamamos "tercera", y así sucesivamente, hasta que hayamos cubierto todas las letras que aparecen en la muestra de texto llano.

Luego observamos el texto cifrado que queremos resolver y clasificamos sus símbolos de la misma manera. Encontramos el símbolo que aparece con más frecuencia y lo sustituimos con la forma de la letra "primera" de la muestra de texto llano, el siguiente símbolo más corriente lo sistituimos por la forma de la letra "segunda", y el siguiente en frecuencia lo cambiamos por la forma de la letra "tercera", y así sucesivamente, hasta que hayamos cubierto todos los símbolos del criptograma que queremos resolver."

Este texto describe perfectamente la técnica de criptoanálisis denominada Análisis de Frecuencias, que es necesario utilizar para resolver nuestro kriptojuego 20080131.

Como es de suponer, en la actualidad esta técnica está perfectamente implementada mediante programas de ordenador (ejemplos: un analizador on-line, código fuente de un contador de caracteres en C y otro en Java, un completo analizador freeware para Windows cuyo pantallazo muestro más abajo...), lo que sin duda nos evita la parte más tediosa (contar letras y símbolos), pero debido a la diferencia existente entre los textos llanos utilizados para establecer las frecuencias características del lenguaje (aquí una tabla de frecuencias de caracteres en español) y los textos llanos que se cifran, no cabe esperar una solución totalmente automática mediante software. Por ejemplo: si ciframos un texto breve, donde aparezca varias veces el término "Kriptópolis" es muy probable que haya una proporción de letras K anormalmente alta en relación a lo esperable en un texto estándar en castellano. Como consecuencia tenemos siempre que contar con la necesidad de realizar unos cuantos ajustes "a mano" sobre el resultado que nos proporcione la mera sustitución de unos caracteres por otros en función de sus frecuencias de aparición.

Solución de nuestro Kriptojuego mediante CrypTool

Por supuesto CrypTool representa una importante ayuda en el criptoanálisis de un texto cifrado por sustitución, realizando por nosotros un análisis de frecuencia detallado, tanto del texto llano de referencia como de nuestro texto cifrado, y mostrando correlaciones e histogramas con los resultados. Además realiza automáticamente la sustitución de los caracteres y trata de adivinar la clave, por lo que el resultado que nos proporciona sólo suele necesitar algunos ajustes manuales por nuestra parte hasta convertirse en el texto llano original.

Para resolver nuestro kriptojuego empezaremos por proporcionar al programa un texto llano es español que pueda utilizar como referencia. Nos podemos arreglar con uno que viene con CrypTool, en el fichero genesis-es.txt de la carpeta references. Hay que cargarlo desde el menú Options -> Text Options -> Reference file for statistical applications. Pulsar luego Apply.

Vamos ahora a File -> Open y cargamos el fichero (o copi-pegamos) con el texto cifrado del kriptojuego:

Vamos ahora al menú Analysis -> Symmetric Encryption (classic) -> Ciphertext-only -> Substitution:

En la siguiente pantalla dejamos la opción por defecto: un análisis de frecuencia de digramas (es decir, basado en pares de caracteres y la posibilidad de que aparezcan juntos o no en nuestro lenguaje):

Dejamos sin marcar las dos opciones que nos ofrece el siguiente cuadro de diálogo:

Como podemos observar, el resultado ya es bastante bueno:

Nos basta retocar algunos defectos y reordenar las palabras para evitar su confusa (e intencionada ;) agrupación de cinco en cinco para obtener el resultado buscado. El resultado no es exacto porque el alfabeto de cifrado adivinado por CrypTool no es exacto (ya comentamos antes por qué). Basta fijarse en la sección "Current substitution Key". La clave correcta debería ser:

K R Y P T O S A B C D E F G H I J L M N Q U V W X Z

y no la que se muestra.

Si el resultado fuera aún incomprensible y quisiéramos mejorarlo, podríamos jugar con diferentes opciones sin más que pulsar ahora el botón "Manual Analysis" de esta misma pantalla. Como, por el contrario, lo consideramos bastante aceptable, pulsamos "Accept Substitution", lo que nos lleva a un cuadro de edición donde podemos retocar a mano el resultado hasta que tenga pleno sentido (he remarcado en rojo los pocos errores que aún existen):

Muestro a continuación el comienzo del trabajo:

El texto final que resuelve el criptograma es el siguiente:

Aunque los sistemas clasicos estén en desuso, no por ello deben
ser pasados por alto por el criptoanalista. En realidad, sería 
bastante poco agradable perder horas de esfuerzo en la intención 
de romper una cifra, suponiendo de antemano que el criptosistema 
en cuestión empleado es de los denominados modernos, para luego 
caer en la cuenta que aquel complicado enigma se trataba simplemente 
de un cifrado elemental, que puede romperse facilmente con herramientas 
básicas. No quedaríamos muy bien ante nuestros superiores. Por lo tanto
la primera acción que realizará todo criptoanalista será la de 
contabilizar los caracteres que aparecen en el criptograma para obtener 
información sobre el tipo de cifra monoalfabético o polialfabético e 
intentar aplicar las técnicas que describiremos más adelante para 
romper dicha cifra. Si esto no entrega los resultados esperados 
buscará otros caminos, yendo como es lógico siempre desde la dificultad
menor a la mayor.

Se trata de un instructivo párrafo (el resaltado es mío) del libro del Dr. Ramió, que recomiendo de nuevo para los que queráis profundizar en éste y otros criptosistemas, y no tengáis demasiado miedo a un tratamiento matemático de los mismos a un nivel universitario.

Como me he extendido más de lo previsto, queda para una última entrega el remate histórico que os había prometido. Mis disculpas.

Continuará...