Cifrados clásicos: Esconder letras: de César a Vigenère

El texto «cifrado» más antiguo que se conoce es una inscripción funeraria de Menet Jufu, en Egipto, de hacia el 1900 a. C., cuyo escriba usó jeroglíficos poco habituales, probablemente para dar solemnidad al texto más que para ocultarlo. El secreto de verdad aparece algo después: una tablilla mesopotámica de hacia el 1500 a. C. esconde una receta de esmalte para cerámica escribiendo sus palabras con signos raros, y los generales espartanos enrollaban una tira de cuero alrededor de un bastón de grosor fijo, la escítala, escribían a lo largo y enviaban la tira: desenrollada, las letras eran un revoltijo; enrollada en un bastón del mismo grosor, volvían a alinearse. La escítala transpone letras, cambia su orden. Este capítulo trata sobre todo de la otra gran familia: los cifrados que sustituyen letras.

El desplazamiento de César

Suetonio cuenta que Julio César escribía las cartas confidenciales «cambiando el orden de las letras del alfabeto de modo que no se pudiera entender ni una palabra», y que quien quisiera leerlas debía «sustituir la cuarta letra del alfabeto, es decir la D, por la A, y así con las demás». Numeremos las letras $A = 0, B = 1, \dots, Z = 25$ (el alfabeto latino de 26 letras, sin la Ñ). El cifrado de César con clave $k$ es

E_{k} (x) = (x + k) mod 26, D_{k} (y) = (y - k) mod 26 .

César usaba $k = 3$ ; Augusto, su sobrino, $k = 1$ . Los escribas hebreos tenían su propia variante, el atbash, que invierte el alfabeto ( $x \mapsto 25 - x$ ); aparece en el libro de Jeremías. ROT13, el desplazamiento de 13 con el que se escondían los finales de los chistes en Usenet, es su propio inverso porque $13 + 13 = 26$ .

El cifrado de César y cómo romperlo. Cambia el desplazamiento y cambia el texto cifrado. Debajo, lo que ve el atacante: el texto cifrado descifrado con todas las demás claves. Con solo 25 candidatos, el que se lee como el idioma salta a la vista, y la figura lo elige sola comparando frecuencias de letras (con el χ² que se explica más abajo).

Su debilidad es el tamaño del espacio de claves: 25 claves útiles se prueban a mano en minutos. La lección, que sigue vigente, es la primera regla del diseño de cifrados.

Principio (búsqueda exhaustiva)

Cualquier cifrado puede atacarse probando todas las claves y reconociendo el texto en claro correcto. Un cifrado con $K$ claves es como mucho tan fuerte como una búsqueda de $K$ intentos; para ser seguro, $K$ tiene que estar fuera del alcance del atacante. Hoy eso significa al menos $2^{128}$ .

Todas las permutaciones del alfabeto

El arreglo evidente es permitir cualquier reordenación del alfabeto, no solo desplazamientos: escribir las 26 letras en un orden revuelto, a menudo derivado de una palabra clave, y sustituir cada letra por la que tiene debajo. Esta sustitución monoalfabética fue el caballo de batalla de la diplomacia durante un milenio.

Proposición (el espacio de claves de la sustitución)

Las claves de una sustitución monoalfabética son las permutaciones de 26 letras, así que hay

26! = 403 291 461 126 605 635 584 000 000 \approx 4 \times 10^{26} \approx 2^{88.4}

Más que las claves de DES ( $2^{56}$ ), y demasiadas para probarlas una a una, incluso hoy.

Y sin embargo, una sustitución cae en minutos ante alguien con un lápiz. Un espacio de claves enorme es necesario pero no suficiente: además, el cifrado no debe dejar escapar estructura. Y la sustitución monoalfabética deja escapar la estructura más importante de todas.

Al-Kindi cuenta letras

En el Bagdad del siglo IX, en la Casa de la Sabiduría, el filósofo Abu Yusuf Yaqub ibn Ishaq al-Kindi escribió el Manuscrito para descifrar mensajes criptográficos, redescubierto en un archivo de Estambul en 1987. En él describe, por primera vez, el análisis de frecuencias:

Una manera de resolver un mensaje cifrado, si conocemos su lengua, es encontrar un texto distinto en esa lengua lo bastante largo para llenar una hoja, y contar cuántas veces aparece cada letra. […] Después miramos el texto cifrado que queremos resolver y clasificamos también sus símbolos.al-Kindi, h. 850

Las letras no aparecen con la misma frecuencia. En español, la E supone casi el 13,7 % de las letras y la A el 12,5 %, mientras que K y W apenas aparecen; en inglés manda la E (12,7 %), seguida de la T y la A. Una sustitución cambia el nombre de las letras pero conserva sus recuentos: el símbolo más frecuente de un texto cifrado largo es casi seguro la E. Para medir cuánto «se parece» al idioma un descifrado candidato, se comparan los recuentos observados $O_{i}$ con los esperados $E_{i} = N p_{i}$ :

χ^{2} = \sum_{i = 0}^{25} \frac{(O_{i} - E_{i})^{2}}{E_{i}} .

Un $χ^{2}$ pequeño indica que el texto tiene la estadística de letras del idioma. Este único número rompe automáticamente cualquier cifrado por desplazamiento: se descifra con los 26 desplazamientos y se queda el de menor $χ^{2}$ .

Análisis de frecuencias. Las barras oscuras son las frecuencias de las letras de un texto cifrado con un desplazamiento secreto; las claras, las del idioma. Mueve el desplazamiento hasta que los dos perfiles encajen (el χ² cae en picado): debajo aparece el texto en claro. El desplazamiento secreto se elige al azar cada vez que cargas la página.

Con una sustitución general, el atacante empareja primero los símbolos más frecuentes y luego usa las parejas de letras (DE, EN, EL, LA en español; TH, HE, IN en inglés), las letras dobles y las palabras cortas para fijar el resto. Edgar Allan Poe lo convirtió en culto con El escarabajo de oro (1843), y Arthur Conan Doyle hizo que Sherlock Holmes rompiera una sustitución de monigotes danzantes en 1903. En la vida real, el análisis de frecuencias llevó al cadalso a María Estuardo, reina de Escocia, en 1587: Thomas Phelippes rompió el nomenclátor que usaba para escribirse con los conspiradores de Babington.

El cifrado indescifrable

La defensa contra el recuento es hacer que cada letra del texto en claro vaya a muchas letras distintas del cifrado. Leon Battista Alberti, el arquitecto renacentista, construyó un disco de cifrado en 1467 y propuso girarlo cada pocas palabras. Johannes Trithemius tabuló los 26 desplazamientos en su tabula recta (Polygraphia, 1518). En 1553 Giovan Battista Bellaso añadió la idea decisiva: elegir el desplazamiento de cada letra a partir de una palabra clave que se repite. Blaise de Vigenère describió una variante más fuerte en 1586, y la historia le dio su nombre al cifrado de Bellaso. Con una palabra clave de longitud $L$ , $k_{0} k_{1} \dots k_{L - 1}$ :

c_{i} = (p_{i} + k_{i mod L}) mod 26, p_{i} = (c_{i} - k_{i mod L}) mod 26 .

Con la palabra clave LEMON, ATTACKATDAWN se convierte en LXFOPVEFRNHR: las dos T de ATTACK se vuelven X y F; las cuatro A, L, O, E y N. Los recuentos de letras se aplanan, y el cifrado se ganó el nombre de le chiffre indéchiffrable. Lo conservó trescientos años; todavía en 1917 Scientific American lo calificaba de «imposible de traducir». Llevaba sesenta años roto.

Romper Vigenère: Babbage, Kasiski, Friedman

La debilidad es que la palabra clave se repite. Si conociéramos su longitud $L$ , podríamos partir el texto cifrado en $L$ columnas (las letras $0, L, 2 L, \dots$ ; las letras $1, L + 1, \dots$ ), y cada columna sería un simple César, que cae con un análisis de frecuencias. Charles Babbage encontró la longitud hacia 1854, pero no lo publicó; el oficial prusiano Friedrich Kasiski publicó el método en 1863:

Método (examen de Kasiski)

Cuando el mismo fragmento del texto en claro cae en la misma posición de la palabra clave, se cifra igual. Así que las distancias entre fragmentos repetidos del texto cifrado tienden a ser múltiplos de $L$ , y su máximo común divisor suele ser $L$ o un múltiplo pequeño.

En 1922 William Friedman, fundador del criptoanálisis estadounidense, sustituyó la búsqueda de repeticiones por un estadístico que usa todas las letras del texto.

Definición (índice de coincidencia)

El índice de coincidencia de un texto de $N$ letras, con $n_{i}$ apariciones de la letra $i$ , es la probabilidad de que dos letras tomadas al azar de él sean iguales:

IC = \sum_{i = 0}^{25} \frac{n_{i} (n_{i} - 1)}{N (N - 1)} .

Proposición (Friedman)

Si las letras de un texto tienen probabilidades $p_{i}$ , entonces $IC \to \sum_{i} p_{i}^{2}$ cuando $N$ crece. Para letras uniformemente aleatorias es $26 \cdot (1 / 26)^{2} = 1 / 26 \approx 0, 038$ ; para el inglés, unos $0, 066$ , y para el español, unos $0, 072$ . El IC no cambia con ninguna sustitución, porque una sustitución solo cambia el nombre de las letras.

Por qué el IC no cambia con una sustitución

$\sum_{i} n_{i} (n_{i} - 1)$ solo depende del multiconjunto de recuentos ${n_{i}}$ , no de qué letra tiene qué recuento. Una sustitución es una biyección del alfabeto, así que permuta los recuentos y deja la suma igual. En una columna de Vigenère construida con la $L$ correcta, todas las letras se desplazaron lo mismo: la columna es una sustitución del idioma, y su IC es el del idioma. Con una $L$ equivocada, la columna mezcla varios desplazamientos, su distribución de letras es más plana y su IC baja hacia $1 / 26$ .

El ataque es, por tanto, mecánico: para cada longitud candidata $L = 1, 2, 3, \dots$ , se corta el texto cifrado en $L$ columnas y se promedia su IC. La primera $L$ cuyo promedio salta al valor del idioma es la longitud de la clave. Después, cada columna es un César, y el $χ^{2}$ del apartado anterior recupera cada letra de la palabra clave.

Romper Vigenère a partir solo del texto cifrado. Cambia el texto o la palabra clave. Las barras son el índice de coincidencia medio de las columnas para cada longitud de clave candidata: se disparan en la longitud verdadera (y en sus múltiplos). Luego la figura rompe cada columna como un César con χ² y escribe la clave que ha recuperado. Los textos cortos o las claves muy largas la derrotan: cada columna necesita letras suficientes para que se note su estadística.

Playfair y los digramas

Otra forma de aplanar las frecuencias es cifrar parejas de letras: hay $26^{2} = 676$ parejas, y sus frecuencias son mucho más planas que las de las letras sueltas. Charles Wheatstone inventó un cifrado así en 1854; su amigo lord Playfair lo promovió tan bien que lleva su nombre. La clave es un cuadrado de 5×5 con las letras de una palabra clave seguidas del resto del alfabeto (la I y la J comparten casilla). El texto en claro se parte en parejas, con una X entre letras dobles; cada pareja se sustituye por las otras dos esquinas de su rectángulo en el cuadrado, o por las letras de su derecha (misma fila) o de debajo (misma columna). El ejército británico lo usó en la guerra de los bóers y en la Primera Guerra Mundial, para mensajes tácticos que solo tenían que ser secretos unas horas; se sigue pudiendo romper a mano, usando las frecuencias de las parejas. La aplicación de escritorio lo incluye con el ejemplo clásico de la Wikipedia.

Lo que enseñan los clásicos

El espacio de claves debe ser enorme, o gana la búsqueda exhaustiva (César).
Un espacio de claves enorme no basta: el texto cifrado no debe dejar escapar la estadística del texto en claro (la sustitución y al-Kindi).
Todo lo que se repite es un asidero: una clave que se repite convierte un cifrado difícil en varios fáciles (Vigenère y Kasiski).
La estadística vence al secreto: el IC de Friedman no necesita ninguna conjetura sobre el texto en claro.

El siguiente paso fue mecánico: una clave que en la práctica no se repite nunca, producida por una máquina. Esa máquina fue Enigma.

Para saber más

David Kahn, The Codebreakers (1967; revisado en 1996). La historia clásica, de Egipto a la era del ordenador.
Simon Singh, Los códigos secretos (1999). Los capítulos 1 y 2 tratan de María Estuardo, el análisis de frecuencias y Babbage.
Ibrahim A. Al-Kadi, «Origins of cryptology: the Arab contributions», Cryptologia 16(2), 1992.
William F. Friedman, The Index of Coincidence and Its Applications in Cryptography (1922).

§El desplazamiento de César

§Todas las permutaciones del alfabeto

§Al-Kindi cuenta letras

§El cifrado indescifrable

§Romper Vigenère: Babbage, Kasiski, Friedman

§Playfair y los digramas

§Lo que enseñan los clásicos

§Para saber más