Criptografía (XX): cifrado Vigenère y criptoanálisis IC (I)

Ya he escrito algunas entradas en este blog (ver primer post) sobre cifrados de sustitución polialfabética, entre otros sobre el cifrado de Vigenère, y también sobre el método Kasiski para atacar cifrados de este tipo, y en este post me propongo explicar lo que he entendido sobre el criptoanálisis basado en el Índice de Coincidencia (IC).

Este método de criptoanálisis fue desarrollado en 1920 por William Friedman para atacar cifrados de sustitución polialfabética con claves periódicas, sistemas criptograficos de los que el cifrado de Vigenère es un ejemplo.

Para explicar este método de criptoanálisis seguiré los siguientes puntos:

1.- Cifrados de sustitución polialfabética con claves periódicas.
2.- ¿Qué es el Índice de Coincidencia (IC)?.
3.- ¿Cómo se utiliza el Índice de Coincidencia (IC) para atacar este tipo de cifrados?.
4.- Ejemplo de ataque a un criptograma basado en el Índice de Coincidencia (IC), en un próximo post.

1.- Cifrados de sustitución polialfabética con claves periódicas:

Como ya sabemos, en estos sistemas de cifrado, de los que como digo el cifrado de Vigenère es un ejemplo, para cifrar un texto o mensaje en claro se utiliza una clave donde cada carácter de la misma se corresponde con un alfabeto, de tal forma que el primer carácter del texto en claro se cifra con el alfabeto correspondiente al primer carácter de la clave, el segundo carácter del texto en claro con el correspondiente al segundo y así hasta agotar todos los caracteres de la clave, momento en el cual el siguiente carácter del texto en claro se cifra nuevamente con el alfabeto correspondiente al primer carácter de la clave, y así sucesivamente, es decir:

Donde:
K: clave.
k_i: carácter i-ésimo de la clave (1 ≤ i ≤ t).
t: periodo o longitud de la clave o, lo que es lo mismo, número de alfabetos.
E: función de cifrado.
m_i: carácter i-ésimo del mensaje o texto en claro a cifrar.
D: función de descifrado.
c_i: carácter i-ésimo del criptograma o texto cifrado.
n: tamaño del alfabeto.

Veamos esto cifrando un texto en claro en español con el cifrado de Vigenère.

1.1.- En primer lugar establezcamos una relación entre las letras del alfabeto español y la posición que ocupa cada una de ellas en el mismo:

1.2.- Tamaño del alfabeto (n) = 27

1.3.- Texto en claro a cifrar: EJEMPLO.

1.4.- Clave (K): CLAVE.

1.5.- Longitud de la clave (t) = 5.

1.6.- Cifrado:

E_k(m₁) = (m₁ + k₁) mod n = (E + C) mod 27 = (4 + 2) mod 27 = 6 = G
E_k(m₂) = (m₂ + k₂) mod n = (J + L) mod 27 = (9 + 11) mod 27 = 20 = T
E_k(m₃) = (m₃ + k₃) mod n = (E + A) mod 27 = (4 + 0) mod 27 = 4 = E
E_k(m₄) = (m₄ + k₄) mod n = (M + V) mod 27 = (12 + 22) mod 27 = 7 = H
E_k(m₅) = (m₅ + k₅) mod n = (P + E) mod 27 = (16 + 4) mod 27 = 20 = T
E_k(m₆) = (m₆ + k₁) mod n = (L + C) mod 27 = (11 + 2) mod 27 = 13 = N
E_k(m₇) = (m₇ + k₂) mod n = (O + L) mod 27 = (15 + 11) mod 27 = 26 = Z

Texto cifrado o criptograma: GTEHTNZ.

1.7.- Descifrado:

D_k(c₁) = (c₁ - k₁) mod n = (G - C) mod 27 = (6 - 2) mod 27 = 4 = E
D_k(c₂) = (c₂ - k₂) mod n = (T - L) mod 27 = (20 - 11) mod 27 = 9 = J
D_k(c₃) = (c₃ - k₃) mod n = (E - A) mod 27 = (4 - 0) mod 27 = 4 = E
D_k(c₄) = (c₄ - k₄) mod n = (H - V) mod 27 = (7 - 22) mod 27 = 12 = M
D_k(c₅) = (c₅ - k₅) mod n = (T - E) mod 27 = (20 - 4) mod 27 = 16 = P
D_k(c₆) = (c₆ - k₁) mod n = (N - C) mod 27 = (13 - 2) mod 27 = 11 = L
D_k(c₇) = (c₇ - k₂) mod n = (Z - L) mod 27 = (26 - 11) mod 27 = 15 = O

Texto en claro: EJEMPLO.

En este tipo de cifrados su vulnerabilidad residía en su naturaleza cíclica, es decir, en la aplicación cíclica de t cifrados de sustitución monoalfabética y, por tanto, como en el método Kasiski (ver primer post al que he hecho referencia al principio), lo primero que hay que hacer para atacarlos es averiguar la longitud de la clave, para más tarde realizar un análisis de frecuencias sobre los caracteres del criptograma que han sido cifrados con el mismo carácter de la clave (mismo alfabeto) con objeto de obtener la clave y descifrarlo.

2.- ¿Qué es el Índice de Coincidencia (IC)?:

El Índice de Coincidencia (IC) es la probabilidad de que dos letras tomadas al azar de un texto sean iguales.

Para obtener la fórmula con la que calcularlo, consideremos lo siguiente:

2.1.- El número de pares de letras “AA” que podemos obtener tomando 2 letras al azar de un texto es:

Donde: f_A es la frecuencia o número de ocurrencias del carácter “A” en el texto.

Por tanto, el número de pares de letras iguales que podemos obtener tomando 2 letras al azar de un texto es:

2.2.- Por otra parte, el número de pares de letras tomadas al azar que podemos obtener de un total de N letras (tamaño del texto) es:

2.3.- Por lo que la probabilidad de que dos letras tomadas al azar de un texto con un tamaño de N letras sean iguales (IC) es:

3.- ¿Cómo se utiliza el Índice de Coincidencia (IC) para atacar cifrados de sustitución polialfabética con claves periódicas?:

Como ya he comentado, lo primero que hay que hacer para atacar este tipo de cifrados es averiguar la longitud de la clave, y para eso precisamente se utiliza el Índice de Coincidencia (IC).

Me explico: tal y como he leído por ahí, el IC obtenido a partir de un texto en el idioma español estará próximo a 0,0775 (lógicamente siempre y cuando el texto sea lo suficientemente grande, aunque ni siquiera hace falta que sea muy extenso para que el IC se aproxime a ese valor).

Cuando se cifra un texto empleando un sistema de sustitución monoalfabética el IC del idioma en el que está escrito el texto en claro se mantiene en el texto cifrado, mientras que si se utiliza un sistema de sustitución polialfabética el IC en el texto cifrado será significativamente menor que el del texto en claro, ya que las frecuencias más altas de las letras del texto en claro se reparten entre varias letras del criptograma.

De lo anterior se deduce que si calculamos el IC para las letras del criptograma que conforme a cada una de las posible longitudes de la clave hayan sido cifradas con el alfabeto correspondiente al mismo carácter de la clave sólo obtendremos valores próximo a 0,0775 para la longitud de la clave realmente usada en el cifrado. Es decir:

- Longitud de la clave (t) = 1: calculamos el IC de todo el texto cifrado. En este caso todos los caracteres del texto en claro habrían sido cifrados por el alfabeto correspondiente al único carácter de la clave y, por tanto, se habría utilizado un único alfabeto, es decir, se trataría realmente de una sustitución monoalfabética. Si el IC calculado está próximo a 0,0775 la clave empleada en el cifrado podría tener una longitud de 1.

- Longitud de la clave (t) = 2: formamos dos subcriptogramas (C₁ y C₂₎, el primero compuesto por los caracteres del criptograma 1º, 3º, 5º, 7º, 9º,... y el segundo por 2º, 4º, 6º, 8º, 10º,..., ya que los caracteres de C₁ habrían sido cifrados con el alfabeto correspondiente a la primera letra de la clave y los de C₂ con el alfabeto correspondiente a la segunda, y calculamos el IC de cada uno de estos dos subcriptogramas. Si ambos IC calculados están próximos a 0,0775 la clave empleada en el cifrado podría tener una longitud de 2.

- Longitud de la clave (t) = 3: formamos tres subcriptogramas (C₁, C₂, y C₃) el primero compuesto por los caracteres del criptograma 1º, 4º, 7º, 10º, 13º,..., el segundo por 2º, 5º, 8º, 11º, 14º,... y el tercero por 3º, 6º, 9º, 12º, 15º..., ya que los caracteres de C₁ habrían sido cifrados con el alfabeto correspondiente a la primera letra de la clave, los de C₂ con el alfabeto correspondiente a la segunda y los de C₃ con el alfabeto correspondiente a la tercera, y calculamos el IC de cada uno de estos tres subcriptogramas. Si los IC calculados están próximos a 0,0775 la clave empleada en el cifrado podría tener una longitud de 3.
...

Una vez averiguada la longitud de la clave, mediante el análisis de frecuencias de los caracteres de los subcriptogramas correspondientes a esa longitud, obtendríamos la clave utilizada y descifraríamos el mensaje.

En resumen y en mi opinión, un elegante método el propuesto por William Friedman, en 1920, para atacar cifrados de sustitución polialfabética con claves periódicas, pero que recomiendo utilizar en combinación con el método Kasiski, para una vez averiguada la longitud de la clave conforme a este último método confirmar que efectivamente es así, por los siguientes motivos principales:

- En textos pequeños el IC no es muy confiable.
- A medida que el tamaño de la clave aumenta llega un momento en el que el IC se aproxima al de una distribución uniforme, es decir, aquella en la que cada letra del alfabeto ocurre con la misma frecuencia (1/27), y por tanto el IC se aproxima a 0,0370, con lo que la información que este método nos aporta pierde valor.

4.- Ejemplo de ataque a un criptograma basado en el Índice de Coincidencia (IC):

En un próximo post.

Quizás también te interese: