El cifrado Vigenère y cómo lo rompió Charles Babbage

La forma más simple de cifrar un mensaje, esto es, de conseguir a partir del texto original otro texto encriptado con forma de galimatías según el cual quede expresado el texto inicial, ha sido, desde que existe la criptografía, el algoritmo de sustitución. Dicho algoritmo se basa en hacer corresponder a cada letra del texto llano otra letra o símbolo, de acuerdo con un convenio entre el emisor y el receptor del mensaje. Por lo tanto ambos deben poseer la tabla de equivalencias y aplicarla para cifrar y posteriormente descifrar el mensaje.

El problema del algoritmo de sustitución es que el mensaje encriptado es en cierto modo fácil de descifrar, aún no poseyendo la tabla de equivalencias. El método que se debe emplear para tal fin fue descrito por primera vez por un sabio nacido en Bagdad en el año 801, llamado Al-Kindi, y que se dedicaba a la astronomía, a la matemática y a la medicina, teniendo también intereses como lingüista. El método que este estudioso describió se conoce como análisis de frecuencias, y consiste en analizar un texto suficientemente grande en un determinado idioma y cuantificar en él la frecuencia de aparición de cada letra. Una vez obtenida esta estimación de lo probable que es la aparición de todas las letras, se puede aplicar este conocimiento para hacer suposiciones sobre los símbolos más frecuentes del texto cifrado, y una vez que éstos han sido asignados se siguen haciendo suposiciones sobre los restantes símbolos de dicho texto, teniendo en cuenta por ejemplo que lo más probable antes o después de una vocal es una consonante y otras apreciaciones en base al conocimiento de la lengua en la que fue redactado el mensaje llano, hasta llegar a un mensaje coherente semánticamente, que será el texto descifrado. El punto débil del algoritmo de sustitución simple que se ha descrito es que una determinada letra se sustituye siempre por el mismo símbolo, por lo que es evidente que las frecuencias de las letras originales, que son similares aproximadamente al del alfabeto de que proceden en el contexto de la lengua utilizada, coinciden con las frecuencias de los símbolos cifrados, y es éste el tendón de Aquiles que aprovecha el análisis de frecuencias.

En criptografía ha habido siempre una lucha sin cuartel entre cifradores y descifradores. Los primeros han intentado con el paso de los siglos perfeccionar los métodos de cifrado hasta aproximarse a un encriptado perfecto. Los segundos han hecho acopio de verdadero ingenio para lograr métodos eficientes a la hora de echar por tierra el trabajo de los primeros. Así pues, el caso de la simplicidad del algoritmo de sustitución y de lo sencillamente que se vino abajo no fue una excepción.

La solución criptográfica al uso del análisis de frecuencias por parte de los descifradores vino por cuenta de un genio del Renacimiento, el polifacético Leon Battista Alberti, más conocido en sus facetas de arquitecto, matemático y teórico de la perspectiva. Su aportación quedó en el olvido por no escribir ningún tratado sobre la misma, pero fue posteriormente desarrollada por dos académicos llamados Blaise de Vigenère y Johannes Trithemius. Esta aportación se conoce con el nombre de cifrado polialfabético y consiste en utilizar el mismo alfabeto de sustitución para letras cuyo ordinal en el mensaje difiere en la longitud de una palabra utilizada como clave y diferentes alfabetos de sustitución para letras que no cumplen esa propiedad, estando cada alfabeto de sustitución determinado por cada letra de la palabra clave. Así pues, la cifra Vigenère consiste en escribir el mensaje llano sin cifrar y colocar encima de cada letra, en orden sucesivo, las letras de la palabra clave, repitiendo dicha operación deslizando dicha palabra clave una y otra vez hasta cubrir todo el mensaje. A continuación para cada letra de la palabra clave se consulta su alfabeto de sustitución correspondiente y se codifica la letra original como el sustituto para ella hallado en el alfabeto de sustitución parejo a la letra clave empleada. De este modo se obtiene un galimatías ciertamente bastante más robusto que si se emplease sustitución simple.

Pero,…,¿es factible el romper este esquema de cifrado?. El cifrado Vigenère fue inexpugnable durante casi dos siglos, pero allá por el año 1854, uno de los pioneros del cálculo automático, sobre el que escribí un artículo en esta web, Charles Babbage, logró encontrar un método operativo para romper el cifrado Vigenère, aunque no publicó nunca sus resultados, siendo identificada su primicia mucho tiempo después al revisar sus notas.

¿Qué medio se le ocurrió a Babbage para esta tarea? Charles Babbage partió de que el número de letras de la palabra clave empleada determinaba el número de distintos alfabetos de sustitución usados. De esta manera, si por ejemplo dicha longitud era de cinco letras, ello significaba que cada carácter del mensaje original podía quedar cifrado de cinco maneras diferentes. Así pues, el primer paso a llevar a cabo era el determinar la longitud de la palabra clave. Suponiendo que se tenía un texto cifrado lo suficientemente largo, dicho primer paso se acometía aprovechando aquellas palabras que se cifraban de igual manera en el texto, me refiero por ejemplo a artículos o pronombres. Estas palabras aparecen cifradas con la misma equivalencia a lo largo del texto cuando los ordinales de sus letras constituyentes difieren en un múltiplo de la longitud de la palabra clave. De esta manera, viendo las palabras (cifradas) repetidas, determinando la diferencia entre los ordinales de sus letras en relación al inicio del texto y obteniendo los comunes divisores de dichas diferencias se podía obtener un conjunto de longitudes plausibles para la palabra clave. Se seguía el análisis usando la longitud más probable de entre las encontradas. El siguiente paso consistía en aplicar un análisis de frecuencias a aquellas letras del mensaje cifrado cuyo ordinal difiere en un múltiplo de dicha primera longitud supuesta. Como el cifrado polialfabético Vigenère con cinco letras en su palabra clave –por ejemplo- es equivalente a cinco cifrados monoalfabéticos (o cifrados simples de sustitución) que se van repitiendo en letras cuyo ordinal difiere en el mencionado múltiplo se tiene que para aplicar aquí el análisis de frecuencias basta con hacerlo cinco veces. Es algo similar a descifrar por análisis de frecuencias cinco mensajes que forman parte del total, y que son los formados por las letras con ordinales separados por la longitud de la clave. Evidentemente si con la primera longitud de clave bajo prueba no se obtenía nada coherente, se pasaba a la segunda más probable y se volvía a repetir el proceso hasta obtener con alguna de ellas el mensaje descifrado.

En realidad el cifrado polialfabético es un método robusto de criptografía, sobre todo si se usan claves muy largas. Casos particulares notables de este tipo de encriptación son el cifrado mediante la máquina Enigma, utilizado por el ejército nazi en la Segunda Guerra Mundial y el cifrado mediante libro de claves de único uso. Este segundo método que cito es el mecanismo perfecto de cifrado, ya que se basa en claves formadas por una secuencia aleatoria de letras de gran longitud, con lo que los mensajes pueden ser muy largos. Cada clave es de uso único y es conocida por emisor y receptor mediante un libro de claves. Aún así, el problema de la distribución de claves sigue vigente, ya que siempre es necesaria cierta logística para distribuir los libros entre los usuarios de este mecanismo, y por lo tanto en principio no es un método invulnerable. En la imagen superior de esta entrada aparece el sabio Al-Kindi. En la intermedia, Leon Battista Alberti, y en la inferior Blaise de Vigenère.