El Cifrado de Hill

El cifrado de Hill es un método de cifrado de bloque que utiliza matrices para cifrar y descifrar mensajes. Es un método de cifrado simétrico, lo que significa que la misma clave se utiliza tanto para cifrar como para descifrar el mensaje.

Lester Hill

Matemático norteamericano que propone en el año 1929 el uso de matrices para la cifra de dos o más letras del texto en claro Hill patenta su invento con claves de 6 letras, pero como dicha clave debe ser fija para cada máquina, no puede competir con otras máquinas de la época como Enigma, Lorenz o Purple

Procedimiento de cifrado

Para cifrar un mensaje con el cifrado de Hill, primero se divide el mensaje en bloques de tamaño n, donde n es el tamaño de la matriz de cifrado. Cada bloque se representa como un vector de n elementos. A continuación, se multiplica cada vector por la matriz de cifrado utilizando la regla de multiplicación de matrices. El resultado es otro vector de tamaño n que representa el mensaje cifrado.

Para descifrar el mensaje, se realiza el mismo proceso, pero en lugar de utilizar la matriz de cifrado se utiliza su inversa. La inversa de una matriz es una matriz que, cuando se multiplica por la matriz original, produce la matriz identidad.

Es importante tener en cuenta que la matriz de cifrado debe cumplir ciertas propiedades para que el cifrado de Hill sea seguro. En particular, la matriz debe ser invertible y debe tener un tamaño adecuado (por lo general, se utilizan matrices de 2×2 o 3×3). Además, la clave de cifrado debe ser mantenida en secreto para evitar que los mensajes puedan ser descifrados por personas no autorizadas.

Desarollo

$Cifrado=\begin{pmatrix} K_{11} & K_{12} & K_{13} & K_{14} \\ K_{21} & K_{22} & K_{23} & K_{24} \\ K_{31} & K_{32} & K_{33} & K_{34} \\ K_{41} & K_{42} & K_{43} & K_{44}\end{pmatrix}\begin{pmatrix} m_{1} \\ m_{2} \\ m_{3} \\ m_{4}\end{pmatrix}=\begin{pmatrix} c_{1} \\ c_{2} \\ c_{3} \\ c_{4}\end{pmatrix}$

Algoritmo de mutiplicación.
* $(K_{11} . m_{1}) + (K_{12} . m_{2}) + (K_{13} . m_{3}) + (K_{14} . m_{4}) = c_{1}$
* $(K_{21} . m_{1}) + (K_{22} . m_{2}) + (K_{23} . m_{3}) + (K_{24} . m_{4}) = c_{2}$
* $(K_{31} . m_{1}) + (K_{32} . m_{2}) + (K_{33} . m_{3}) + (K_{34} . m_{4}) = c_{3}$
* $(K_{41} . m_{1}) + (K_{42} . m_{2}) + (K_{43} . m_{3}) + (K_{44} . m_{4}) = c_{4}$

$Descifrado=\begin{pmatrix} K^{-1}_{11} & K^{-1}_{12} & K^{-1}_{13} & K^{-1}_{14} \\ K^{-1}_{21} & K^{-1}_{22} & K^{-1}_{23} & K_{24} \\ K^{-1}_{31} & K^{-1}_{32} & K^{-1}_{33} & K^{-1}_{34} \\ K^{-1}_{41} & K^{-1}_{42} & K^{-1}_{43} & K^{-1}_{44}\end{pmatrix}\begin{pmatrix}c_{1} \\ c_{2} \\ c_{3} \\ c_{4}\end{pmatrix}=\begin{pmatrix} m_{1} \\ m_{2} \\ m_{3} \\ m_{4}\end{pmatrix}$

Condiciones Matriz Clave

* La matriz clave K debe tener inversa $K^{-1}$ en el módulo de cifra n
* Como $K^{-1}=\frac{T_{Adj(k)}}{|K|}$ mod n, en donde ADJ(K) es la matriz adjunta, $T_{Adj(K)}$ es la transpuesta y |K| el determinante. Este último valor |K| no podrá ser cero ni tener factores en común con n (condición de inversos)
* Si el texto en claro no es múltiplo del bloque de N letras, el último bloque se rellenará con una letra predeterminada de poco uso

Hagamos un ejemplo.

* Usaremos una matriz de 4×4 que cumpla con las condiciones antes explicadas. Por ejemplo

$Clave=\begin{pmatrix} 38 & 7 & 14 & 14 \\ 17 & 3 & 43 & 44 \\ 45 & 6 & 1 & 20 \\ 17 & 14 & 45 & 43\end{pmatrix}$

El determinante es: 288470

El determinante en mod(27) es: 2

Clave valida

* El mensaja a cifrar será: atacaremos al amanecer
* Haremos el digrama del mensaje en función a la dimensión de mi clave, en este caso 4

[ATAC][AREM][OSAL][AMAN][ECERX]. Rellenamos con una X si fuera necesario y suprimimos espacios en blanco

Cada digrama es un vector con la dimensión de la clave en $R^1$
La estructura queda:

$\begin{pmatrix} 38 & 7 & 14 & 14 \\ 17 & 3 & 43 & 44 \\ 45 & 6 & 1 & 20 \\ 17 & 14 & 45 & 43\end{pmatrix}.\begin{pmatrix} A \\ T \\ A \\ C \end{pmatrix}$

Relacionamos cada palabra del digrama con el valor correspondiente del alfabeto.

$\begin{pmatrix} 38 & 7 & 14 & 14 \\ 17 & 3 & 43 & 44 \\ 45 & 6 & 1 & 20 \\ 17 & 14 & 45 & 43\end{pmatrix}.\begin{pmatrix} 0 \\ 20 \\ 0 \\ 2 \end{pmatrix}=\begin{pmatrix} 6 \\ 13 \\ 25 \\ 15 \end{pmatrix} => \begin{pmatrix} G \\ N \\ Y \\ O \end{pmatrix}$

Desciframos

Usamos la clave para calcular la adjunta de la clave

$Clave(K)=\begin{pmatrix} 38 & 7 & 14 & 14 \\ 17 & 3 & 43 & 44 \\ 45 & 6 & 1 & 20 \\ 17 & 14 & 45 & 43\end{pmatrix} => Adj(K)=\begin{pmatrix} 9639 & -5198 & 18073 & -21032 \\ 2107 & -26784 & 4609 & 3064 \\ -637 & 4264 & -15769 & 15366 \\ -4998 & 27116 & -3266 & 3274\end{pmatrix}$

Para sacar la matrix inversa de K, debemos multiplicar cada valor de la matriz **traspuesta** por el inverso de su determinante en modulo 27. Por lo tanto **el inverso de 2 en modulo 27 es 14**

$K.T'=\begin{pmatrix} 9639*14 & 2107*14 & -637*14 & -4998*14 \\ -5198*14 & -26784*14 & 4264*14 & 27116*14 \\ 18073*14 & 4609*14 & -15769*14 & -3266*14 \\ -21032*14 & 3064*14 & 15366*14 & 3274*14\end{pmatrix} mod(27) => K'=\begin{pmatrix} 0 & 14 & 19 & 12 \\ 20 & 0 & 26 & 4 \\ 5 & 23 & 13 & 14 \\ 14 & 20 & 15 & 17\end{pmatrix}$

Una vez que tenemos la matriz inversa podemos descifrar el mensaje:

$\begin{pmatrix} 0 & 14 & 19 & 12 \\ 20 & 0 & 26 & 4 \\ 5 & 23 & 13 & 14 \\ 14 & 20 & 15 & 17\end{pmatrix}.\begin{pmatrix} G \\ N \\ Y \\ O\end{pmatrix}=\begin{pmatrix} A \\ T \\ A \\ C \end{pmatrix}$

Fortaleza de la clave

Si n = primo, el número de matrices válidas K tiende al máximo $p^{2n}$

Ejemplo

Si hacemos una cifra con bloques de 8 letras (n=8= y usamos como módulo p = 29 (por ejemplo las mayúsculas y los signos +y -), el número de matrices válidas K= $29^{64} \approx 2^{310}$ .Este espacio de claves será muy superior (254 veces mayor) a la del algoritmo AES 256, que tiene $22^{56}$ claves posibles .Si p = 191 (un subconjunto imprimible del código ASCII), con un bloque de 8 caracteres, el número de matrices válidas se eleva a K= $191^{64} \approx 2^{485}$ .Pero este sistema será muy vulnerable ante un criptoanálisis por texto en claro conocido, mediante el método de Gauss-Jordan

Romper Cifrado de Hill

Vectores unitarios

Se conoce como vector unitario a la fila de una matriz que contiene un uno en la columna que le corresponde en una matriz identidad y los demás valores son ceros.

$I=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$

Si un bloque de texto se cifra con una matriz identidad, es decir con los vectores unitarios, se obtiene el mismo texto en claro

$I=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}.\begin{pmatrix} S \\ O \\ L\end{pmatrix}mod 27 ==> \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}.\begin{pmatrix} 19 \\ 15 \\ 11\end{pmatrix}mod 27$

$C_1 =1*19 + 0*15 + 0*11 \ mod (27) = 19 = S$ 
$C_2 =0*19 + 1*15 + 0*11 \ mod (27) = 15 = O$ 
$C_3 =0*19 + 0*15 + 1*11 \ mod (27) = 11 = L$

Si la matriz clave K es de 2×2 no es tan difícil encontrar los vectores unitarios **AB (0 1)** y **BA (1 0)** en el texto en claro.
Veamos en ejemplo:

* Texto a cifrar: M=»ES OS AV IO NE SV OL **AB** AN MU YA **BA** JO»
* Texto cifrado: C=»WB YV NY ÑJ QV ÑV II **SV** EP GU HG **KX** XG»
* clave $(K)=\begin{pmatrix} 37 & 46 \\ 24 & 49 \end{pmatrix}$