¿Cómo se rompe un cifrado sin la clave?

Para hacerlo completo trabajamos con el alfabeto de 26 letras, sin ñ, sin tildes y sin espacios: la ñ se escribe N y se quitan las tildes. Numeramos las letras de 0 (A) a 25 (Z). Cifrar con una clave $k_0 k_1\dots k_{m-1}$ de longitud $m$ es sumar módulo 26:

Nuestro ejemplo es un mensaje propio de 362 letras, cifrado con la clave PLATA ($m = 5$). Va en grupos de cinco, con 25 letras por línea:

FFEKI SZMTR XZLTR TFNBO COEFA
CLNTQ JPDTA EWASA SLHTS ILEEJ
JPVXS TWMXN HLJXQ JPRXC XMIKA
HNOGT XPNXL POIKE RNIHN SPLTL
BLCXN NWAAO GLDXL PPNMR TRAEL
TGAXL STNXR DPNNN HZBKE RPRKA
SZYGO WLBEE HNOGN POIXD TWAKE
JYIHN CTDXL BPNLA YPSBA ARUBE
CEEIR TRUGT PAOKE ALLFA RPNWI
FFEOA HLVXR PEUAE GXAGA RFAGD
DWLXG JPSTL PAUXR ILELP TCAAA
HEAJU TZIZA HWAVA BAAGA SPLTI
VWELI PJEGT DYCXS TYTKA HTNAA
RPRKU XOOJU TXAXS ILCTR ILDXS
EFELD TWEXR AL

Finge que no conoces ni la clave ni su longitud.

Paso 1: repeticiones y distancias (Kasiski)

Buscamos tramos de 4 o más letras que aparezcan dos veces. En este texto hay exactamente tres (ninguno de 5 letras), con sus posiciones (la primera letra es la posición 0):

Si una repetición viene de un mismo trozo de mensaje cifrado con las mismas letras de la clave, la distancia es un múltiplo de $m$. Si las tres repeticiones son de ese tipo, $m$ divide a las tres distancias, y por tanto a su máximo común divisor:

Así que $m$ es 1 o 5. Con $m = 1$ sería un César, cosa que el paso 2 descarta. La longitud de la clave es probablemente 5.

Hay que ir con cuidado, porque una repetición también puede salir por casualidad. Con tramos de 3 letras aparecen 20 repeticiones más. En 18 de ellas la distancia es múltiplo de 5: son trozos del mensaje que se repiten, como QUE, DEL o CERR. Pero dos son pura casualidad: BAA, a distancia 97, y AAR, a distancia 129. Es lo que cabe esperar: hay 17 576 tramos posibles de tres letras y unos 64 600 pares de posiciones, así que un texto al azar ya daría unas 3 o 4 coincidencias. Basta una de esas casualidades para que el mcd de todas las distancias sea 1. Por eso no se toma el mcd a ciegas: se mira qué divisor comparten casi todas las distancias. Aquí, de las 26 distancias que salen de los tramos de tres letras, 24 son múltiplos de 5. Y la conclusión se confirma con el paso siguiente.

Paso 2: el índice de coincidencia

William Friedman, en un folleto de los laboratorios Riverbank (Illinois) de principios de los años veinte, introdujo una medida que no necesita buscar repeticiones. El índice de coincidencia de un texto de $N$ letras, en el que la letra $x$ aparece $n_x$ veces, es la probabilidad de que dos letras tomadas al azar en dos posiciones distintas del texto sean iguales:

El denominador cuenta las formas de elegir la primera posición y luego otra distinta; el numerador, las que caen en la misma letra.

¿Cuánto vale para un idioma? Si cada letra del texto es la $x$ con probabilidad $p_x$, la probabilidad de que dos letras sean ambas la $x$ es $p_x \cdot p_x$, y sumando sobre todas las letras sale $\sum_x p_x^2$. Ese es el valor que el IC estima. Hay dos casos extremos:

• Texto aleatorio en 26 letras, todas con probabilidad $1/26$: $\sum_x p_x^2 = 26\cdot\frac{1}{26^2} = \frac{1}{26} \approx 0{,}0385$. Es el valor más pequeño posible: cualquier reparto desigual da más.
• Texto en español: las letras están muy desigualmente repartidas, y como los cuadrados premian a las grandes, $\sum_x p_x^2$ sube. Contado sobre el texto completo del Quijote (1 651 361 letras, normalizadas igual), sale $0{,}0750$; solo la E (14 %), la A (12 %), la O, la S y la N ya aportan $0{,}055$. Con la tabla de frecuencias de Pratt (1939), reducida a 26 letras, sale $0{,}0753$. El español ronda $0{,}075$, casi el doble que el azar.

Un cifrado de César o cualquier sustitución con un solo alfabeto conserva el IC, porque solo cambia el nombre de las letras. Un Vigenère, en cambio, lo acerca a $0{,}0385$ porque mezcla alfabetos: nuestro texto cifrado completo da $0{,}0514$.

Aquí llega la idea clave. Si la clave tiene longitud $m$ y reparto el texto en $m$ columnas (las letras de las posiciones $0, m, 2m,\dots$; las de $1, m+1, 2m+1,\dots$; etc.), cada columna está cifrada con un único desplazamiento, es decir, es un César. Si he acertado con $m$, cada columna tiene un IC parecido al del español. Si me equivoco, las columnas mezclan alfabetos y su IC baja. Calculo el IC medio de las columnas para cada $m$:

Se ven dos picos, $m=5$ y $m=10$: si 5 es la longitud, con 10 también cada columna es un César (es dar la clave dos veces). Nos quedamos con la menor. Esto confirma a Kasiski: $m=5$. El valor $0{,}0873$ supera el $0{,}075$ por dos motivos. El mensaje sin cifrar ya tiene un IC de $0{,}0837$, porque es corto y repite palabras. Y cada columna tiene solo unas 72 letras, así que su IC baila mucho: en trozos de 72 letras del Quijote, nueve de cada diez tienen un IC entre $0{,}063$ y $0{,}087$.

Paso 3: recuperar cada letra de la clave

Ya tenemos cinco Césares. Para la columna 1 (las letras de las posiciones 0, 5, 10, …) hay 73 letras y las más frecuentes son T (11 veces), H (8), P (7) y S (6). Como la letra más frecuente del español es la E, probamos que la T sea una E desplazada: de E (4) a T (19) hay 15 puestos, y la letra que lleva el número 15 es la P. Primera letra de la clave: P. Es una pista, no una prueba, así que lo hacemos de forma sistemática.

Para cada desplazamiento $s$ posible de una columna de $n$ letras, deshacemos el desplazamiento y comparamos lo que sale con el español. Si el español tiene frecuencias $f_j$ (las del Quijote), esperaríamos ver $E_j = n\,f_j$ veces la letra $j$ del mensaje, es decir, la letra $j+s$ del texto cifrado. Llamamos $O_{j+s}$ a las veces que aparece de verdad (con los índices módulo 26) y medimos el desajuste con el estadístico $\chi^2$ de Pearson:

Cada sumando compara lo observado con lo esperado y lo divide por lo esperado, para que un desajuste en una letra rara pese más que el mismo desajuste en la E. La suma es pequeña cuando el desplazamiento $s$ deja las letras repartidas como en español. (La K y la W casi no aparecen en el Quijote; les damos una frecuencia mínima de 0,0005 para no dividir por casi cero. Cambiar ese mínimo no cambia el resultado.) Elegimos el $s$ que minimiza $\chi^2$:

La clave es PLATA. Restando esas letras en cada posición, se recupera el mensaje: «Querido Mario: la reunión de mañana queda aplazada hasta el jueves. El mensaje que recibirás…». La diferencia entre el mejor desplazamiento y el segundo es enorme en todas las columnas, y por eso el ataque no deja duda con 72 letras por columna. Con menos letras por columna el ataque se vuelve ambiguo, y por eso conviene probarlo con textos de varios cientos de letras.