Criptografía (XXIV): cifrado de Hill y criptoanálisis Gauss Jordan (II)

En un post anterior expliqué brevemente el cifrado de Hill, propuesto por el matemático Lester S. Hill en 1929, y en éste intento explicar, como siempre de la forma más comprensible de la que sea capaz, lo que he entendido sobre su vulnerabilidad y, por consiguiente, sobre el criptoanálisis de mensajes cifrados con este criptosistema.

La gran vulnerabilidad de este criptosistema radica en que es muy débil ante un ataque con texto claro conocido, es decir, si el criptoanalista conoce parte del texto en claro correspondiente al texto cifrado del que dispone no tendrá mayor problema para obtener la matriz K con la que se cifró esa parte del texto en claro y, por tanto, estaría en disposición de descifrar todos los mensajes cifrados con dicha clave (K). Esta vulnerabilidad se debe a la linealidad de este criptosistema, por lo que con texto claro conocido y empleando el método de Gauss Jordan no es muy difícil obtener la matriz clave (K).

Veamos un ejemplo: supongamos que un criptoanalista se hace con un pequeño fragmento de texto en claro y su correspondiente texto cifrado, los del ejemplo del post anterior, es decir:

Texto en claro: "EJEMPLODECIFRADOHILLX".
Criptograma: "ZFMLUHJHGLOCJDJZMPIEZ".

Supongamos también que el croptoanalista sabe o sospecha que el cifrado se ha realizado sobre trigramas del texto en claro, es decir, utilizando como clave una matriz cuadrada (K) de orden 3 (tres filas y tres columnas). Por tanto, sustituyendo cada una de las letras, tanto del texto en claro como del criptograma, por la posición que ocupa cada una de ellas en el alfabeto español, tendría el siguiente sistema de ecuaciones lineales:

(4 x k11 + 9 x k12 + 4 x k13) mod 27 = 26.
(4 x k21 + 9 x k22 + 4 x k23) mod 27 = 5.
(4 x k31 + 9 x k32 + 4 x k33) mod 27 = 12.
(12 x k11 + 16 x k12 + 11 x k13) mod 27 = 11.
(12 x k21 + 16 x k22 + 11 x k23) mod 27 = 21.
(12 x k31 + 16 x k32 + 11 x k33) mod 27 = 7.
...
(11 x k11 + 11 x k12 + 24 x k13) mod 27 = 8.
(11 x k21 + 11 x k22 + 24 x k23) mod 27 = 4.
(11 x k31 + 11 x k32 + 24 x k33) mod 27 = 26.

Sistema de ecuaciones lineales que en notación matricial podría expresarse de la siguiente manera (M · K = C):

Y para resolverlo, el criptoanalista podría crear la matriz aumentada o ampliada (M|C) combinando ambas matrices, siendo M la matriz de coeficientes y C la matriz de términos independientes, de la siguiente manera:

Ahora, el criptoanalista aplicando operaciones elementales a esta matriz aumentada o ampliada iría obteniendo sistemas equivalentes, que no alteran las soluciones del sistema lineal de ecuaciones, hasta transformar las tres primeras líneas de la matriz M en la matriz identidad de orden 3 (I3), aquella en la que todos sus elementos son 0 excepto los de la diagonal principal que son todos ellos 1, con lo que obtendría la matriz (K) que se utilizó como clave en el cifrado.

Antes que nada, comentar que la operaciones elementales que se pueden realizar sobre una matriz ampliada y que no alteran las soluciones de un sistema lineal de ecuaciones son las siguientes:

- Intercambiar entre sí dos filas de la matriz ampliada (equivale a intercambiar entre sí dos ecuaciones).
- Multiplicar una fila de la matriz ampliada por un número distinto de cero (equivale a multiplicar una ecuación por ese número).
- Sumar a una fila de la matriz ampliada una combinación lineal de otra (equivale a sumar a una ecuación otra multiplicada por un número cualquiera).

Dicho lo cual, el criptoanalista actuaría de la siguiente forma (las operaciones las realizaría siempre en módulo 27):

1.- Partiendo de la matriz ampliada (M|C):

Multiplicaría la primera fila por el inverso de 4 mod 27 = 7, para obtener un 1 en la primera columna de la primera fila:

(4 x 7) mod 27 = 28 mod 27 = 1.
(9 x 7) mod 27 = 63 mod 27 = 9.
(4 x 7) mod 27 = 28 mod 27 = 1.
(26 x 7) mod 27 = 182 mod 27 = 20.
(5 x 7) mod 27 = 35 mod 27 = 8.
(12 x 7) mod 27 = 84 mod 27 = 3.

Obteniéndose:

2.- Sumaría a cada una del resto de las filas la primera fila multiplicada por el opuesto del primer elemento (primera columna) de cada una de ellas, para obtener un cero en la primera columna del resto de filas:

2ª fila = (2ª fila + (-12) x 1ª fila) mod 27.
3ª fila = (3ª fila + (-15) x 1ª fila) mod 27.
...
7ª fila = (7ª fila + (-11) x 1ª fila) mod 27.

Obteniéndose:

3.- Intercambiaría entre sí las filas 2ª y 6ª:

4.- Multiplicaría la segunda fila por el inverso de 7 mod 27 = 4, para obtener un 1 en la segunda columna de la segunda fila:

5.- Sumaría a cada una del resto de las filas la segunda fila multiplicada por el opuesto del segundo elemento (segunda columna) de cada una de ellas, para obtener un cero en la segunda columna del resto de filas:

1ª fila = (1ª fila + (-9) x 2ª fila) mod 27.
3ª fila = (3ª fila + (-3) x 2ª fila) mod 27.
...
7ª fila = (7ª fila + (-20) x 2ª fila) mod 27.

Obteniéndose:

6.- Restaría a la 3ª la 6ª fila (3ª fila = 3ª fila + (-1) x 6ª fila):

7.- Multiplicaría la tercera fila por el inverso de 4 mod 27 = 7, para obtener un 1 en la tercera columna de la tercera fila:

8.- Y finalmente, sumaría a cada una del resto de las filas la tercera fila multiplicada por el opuesto del tercer elemento (tercera columna) de cada una de ellas, para obtener un cero en la tercera columna del resto de filas:

1ª fila = (1ª fila + (-10) x 3ª fila) mod 27.
2ª fila = (2ª fila + (-26) x 3ª fila) mod 27.
...
7ª fila = (7ª fila + (-6) x 3ª fila) mod 27.

Obteniéndose:

Con lo que el criptoanalista obtendría que:

1 x k11 + 0 x k12 + 0 x k13 = 2; k11 = 2.
1 x k21 + 0 x k22 + 0 x k23 = 22; k21 = 22.
1 x k31 + 0 x k32 + 0 x k33 = 9; k31 = 9.
0 x k11 + 1 x k12 + 0 x k13 = 11; k12 = 11.
0 x k21 + 1 x k22 + 0 x k23 = 4; k22 = 4.
0 x k31 + 1 x k32 + 0 x k33 = 4; k32 = 4.
0 x k11 + 0 x k12 + 1 x k13 = 0; k13 = 0.
0 x k21 + 0 x k22 + 1 x k23 = 4; k23 = 4.
0 x k31 + 0 x k32 + 1 x k33 = 12; k33 = 12.

Es decir, la parte derecha de la matriz ampliada que corresponde a la parte izquierda con la matriz identidad de orden 3 (I3) nos revela la matriz transpuesta de la matriz (K) que se utilizó como clave para cifrar el texto en claro. Por tanto, la matriz K sería:

Que como se puede ver en el post anterior es efectivamente la matriz utilizada como clave en el ejemplo.