Criptografía (XXIII): cifrado de Hill (I)

En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill, propuesto por el matemático Lester S. Hill, en 1929, y que se basa en emplear una matriz como clave para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente.

Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice Dani, amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasatiempo: como resolver crucigramas, acertijos, etc.; y la tercera es que, por deformación profesional, tiendo a automatizar dichos procesos (cifrado, descifrado y criptoanálisis), lo que también me sirve para no olvidar los principios de programación aprendidos hace también mucho tiempo.

Pero, volvamos al cifrado de Hill:

1.- Cifra el texto en claro considerando bloques de k símbolos del mismo (bigramas, trigramas, etc.).

2.- Propone un criptosistema utilizando como clave (K) una matriz cuadrada de orden k, es decir, una matriz con el mismo número de filas (k) y de columnas (k), de tal forma que los caracteres de la clave se disponen en filas y columnas (de izquierda a derecha y de arriba a abajo), y el algoritmo de cifrado para el primer bloque de k símbolos del texto en claro sería el siguiente:

Donde:
kij: carácter de la fila i columna j de la matriz (K) que se utilizará como clave para cifrar el texto en claro.
mi: carácter i-ésimo del mensaje a cifrar o texto en claro.
ci: carácter i-ésimo del mensaje cifrado o criptograma.
n: tamaño del alfabeto.

3.- Conforme a este criptosistema, la matriz K debe tener inversa K^-1 mod n, que será la que se use en el descifrado del criptograma.

Para comprender mejor este criptosistema, repasemos ahora algunos conceptos de álgebra lineal:

3.1..- Dadas dos matrices K y M éstas se pueden multiplicar sí y sólo sí el número de columnas de K es igual al número de filas de M (como es nuestro caso) y el elemento cij de la matriz producto (C) se obtiene como el sumatorio de los productos de cada elemento de la fila i de la matriz K por cada elemento de la columna j de la matriz M. Es decir:

En nuestro caso, como la matriz K tiene k filas y k columnas, y la matriz M tiene k filas y 1 columna, la matriz producto (C) tendrá k filas y 1 columna:

3.2.- Por otra parte, para que la matriz K tenga inversa (K^-1) se debe cumplir la siguiente condición (necesaria pero no suficiente):

Donde:
K: matriz que se utilizará como clave para cifrar el texto en claro.
K^-1: matriz inversa de K, que se utilizará para descifrar el mensaje cifrado o criptograma.
I_n: matriz identidad de orden n.

Como sabemos la matriz identidad es aquella en la que todos sus elementos son 0 excepto los de la diagonal principal que son todos ellos 1:

Por lo que esto impone una condición (tal y como he dicho necesaria pero no suficiente): sólo las matrices cuadradas tienen matriz inversa y, por tanto, la matriz K que se utilice como clave debe ser cuadrada (mismo número de filas que de columnas), como también es nuestro caso.

3.3.- La inversa de una matriz K, si existe (K^-1), es única.

3.4.- Si  K^-1 es la matriz inversa de K, entonces: (K^-1)^-1 = K.

3.5.- Para que una matriz cuadrada (K) tenga inversa (K^-1) se debe cumplir como condición adicional (en este caso necesaria y, además, suficiente) que su determinante (det K = |K|) sea distinto de cero, y su cálculo (K^-1) puede realizarse aplicando la siguiente fórmula:

Donde:
K^-1: matriz inversa de K.
C^T: matriz de cofactores de K transpuesta.
|K|: determinante de la matriz K.

3.6.- Y, por último y para terminar este repaso de matemáticas, me tengo que referir a los números primos entre sí (coprimos o primos relativos), es decir, aquellos cuyo máximo común divisor (mcd) es 1 o -1, o, lo que es lo mismo, aquellos que no tienen un divisor en común diferente de 1 y -1, ya que |K| y n (tamaño del alfabeto) deben ser coprimos para que la matriz K sea invertible en módulo n.  

4.- Veamos un ejemplo de cifrado y de descifrado:

4.1.- Cifrado:

Texto en claro: "EJEMPLO DE CIFRADO HILL".
Longitud texto en claro = 20.
Clave de cifrado: "CLAVEEJEM".
Longitud de la clave: 9.

Considerando el alfabeto español:

 Tamaño del alfabeto (n) = 27

Como clave (K) vamos a utilizar una matriz cuadrada de orden k = 3 (3 filas y 3 columnas), para lo que distribuimos las letras de la clave en tres filas de tres caracteres cada una y sustituimos cada uno de los caracteres por el número correspondiente a la posición que ocupa en el alfabeto español, de la siguiente manera:

Antes que nada, vamos a comprobar si esta matriz (K) tiene inversa (K^-1) mod 27, ya que si no es así no se podría utilizar como clave:

Para ello, calculamos su determinante: det K = |K| = 2 x 4 x 12 +  11 x 4 x 9 + 0 x 22 x 4 - 9 x 4 x 0 - 4 x 4 x 2 - 12 x 22 x 11 = 96 + 396 + 0 - 0 - 32 - 2.904 = -2.444.

det K mod 27= |K| mod 27 = -2.444 mod 27 = -14, por lo que la matriz K es invertible en módulo 27, ya que su determinante es distinto de cero y -14 y 27 son coprimos.

Posteriormente, como la longitud del texto en claro no es múltiplo de k (3), rellenamos el texto en claro con caracteres sin sentido en él (por ejemplo "X"), hasta que lo sea:

Texto en claro: "EJEMPLO DE CIFRADO HILLX".
Longitud texto en claro = 21 (múltiplo de 3).

Después troceamos el texto en claro en bloques de k (3) caracteres (trigramas):

"EJE MPL ODE CIF RAD OHI LLX".

Y distribuimos los caracteres del primer trigrama ("EJE") en una columna de 3 filas (k) y los sustituimos por el número correspondiente a la posición que ocupa cada uno de ellos en el alfabeto español, de tal forma que el cifrado se realizaría de la siguiente manera:

O, lo que es lo mismo, la función de cifrado (EK) seria:

Es decir, para el primer trigrama del texto en claro:

c1 = (k11 x m1 + k12 x m2 + k13 x m3) mod 27 = (2 x 4 + 11 x 9 + 0 x 4) mod 27 = 107 mod 27 = 26 = Z.
c2 = (k21 x m1 + k22 x m2 + k23 x m3) mod 27 = (22 x 4 + 4 x 9 + 4 x 4) mod 27 = 140 mod 27 = 5 = F.
c3 = (k31 x m1 + k32 x m2 + k33 x m3) mod 27 = (9 x 4 + 4 x 9 + 12 x 4) mod 27 = 120 mod 27 = 12 = M.

Después repetimos lo mismo con el segundo trigrama del texto en claro ("MPL"), de tal forma que el cifrado se realizaría de la siguiente manera:

Es decir, para el segundo trigrama del texto en claro:

c4 = (k11 x m4 + k12 x m5 + k13 x m6) mod 27 = (2 x 12 + 11 x 16 + 0 x 11) mod 27 = 200 mod 27 = 11 = L.
c5 = (k21 x m4 + k22 x m5 + k23 x m6) mod 27 = (22 x 12 + 4 x 16 + 4 x 11) mod 27 = 372 mod 27 = 21 = U.
c6 = (k31 x m4 + k32 x m5 + k33 x m6) mod 27 = (9 x 12 + 4 x 16 + 12 x 11) mod 27 = 304 mod 27 = 7 = H.

Y así sucesivamente, obteniéndose el siguiente texto cifrado o criptograma:

"ZFMLUHJHGLOCJDJZMPIEZ".

4.2.- Descifrado:

Criptograma: "ZFMLUHJHGLOCJDJZMPIEZ".
Clave de descifrado: matriz inversa (K^-1) mod 27. La calculamos con la fórmula ya vista anteriormente:

Donde:
K^-1: matriz inversa de K.
C^T: matriz de cofactores de K transpuesta.

|K|: determinante de K, que debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 27, y que tal y como hemos calculado antes, en nuestro ejemplo, es -14.
(|K|)^-1: inverso del determinante de la matriz K, es decir: 1/|K|. Debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 27, y que sería -2, ya que -2 es el inverso multiplicativo de -14 en módulo 27.

Por tanto:

Y una vez hecho estos cálculos obtenemos la matriz de descifrado:

Y ahora ya sólo nos queda descifrar el criptograma:

La función de descifrado (DK) sería:

Es decir, para el primer trigrama del criptograma:

m1 = (k^-1₁₁ x c1 + k^-1₁₂ x c2 + k^-1₁₃ x c3) mod 27 = (17 x 26 + 21 x 5 + 20 x 12) mod 27 = 787 mod 27 = 4 = E.

m2 = (k^-1₂₁ x c1 + k^-1₂₂ x c2 + k^-1₂₃ x c3) mod 27 = (24 x 26 + 6 x 5 + 16 x 12) mod 27 = 846 mod 27 = 9 = J.
m3 = (k^-1₃₁ x c1 + k^-1₃₂ x c2 + k^-1₃₃ x c3) mod 27 = (4 x 26 + 7 x 5 + 9 x 12) mod 27 = 247 mod 27 = 4 = E.

Después repetimos lo mismo con el segundo trigrama del criptograma ("LUH"), de tal forma que el descifrado se realizaría de la siguiente manera:

Es decir, para el segundo trigrama del texto en claro:

m4 = (k^-1₁₁ x c4 + k^-1₁₂ x c5 + k^-1₁₃ x c6) mod 27 = (17 x 11 + 21 x 21 + 20 x 7) mod 27 = 768 mod 27 = 12 = M.
m5 = (k^-1₂₁ x c4 + k^-1₂₂ x c5 + k^-1₂₃ x c6) mod 27 = (24 x 11 + 6 x 21 + 16 x 7) mod 27 = 502 mod 27 = 16 = P.
m6 = (k^-1₃₁ x c4 + k^-1₃₂ x c5 + k^-1₃₃ x c6) mod 27 = (4 x 11 + 7 x 21 + 9 x 7) mod 27 =  254 mod 27 = 11 = L.

Y así sucesivamente, obteniéndose el siguiente mensaje descifrado o texto en claro:

"EJEMPLODECIFRADOHILLX".

Conforme a las definiciones dadas en esta serie de post, en cuanto a la clasificación de los sistemas criptográficos, podemos decir que el cifrado de Hill es un sistema de sustitución monoalfabética, ya que cada bloque de k símbolos del mensaje en claro (bigramas, trigramas,...) se sustituye siempre por el mismo bloque de k símbolos en el texto cifrado, pero debido a que la clave que se emplea para descifrar (K^-1) es diferente de la que se usa para cifrar (K): ¿podríamos decir que se trata de un sistema asimétrico?. Pues no, ya que en este post comenté que en los criptosistemas simétricos la clave para descifrar un criptograma es la misma o se calcula a partir de la clave que se utiliza para cifrar el texto en claro, y viceversa, y, por tanto, estaríamos en el caso de un sistema criptográfico simétrico.

En un próximo post hablaré de la vulnerabilidad de este sistema criptográfico y de su criptoanálisis.