Cifrado de Hill
Este sistema está basado en el álgebra lineal y es muy importante en la historia de la criptografía. Fue Inventado por Lester S. Hill en 1929, y fue el primer sistema criptográfico polialfabético que trabajaba con más de tres símbolos simultáneamente
Este sistema es polialfabético pues puede darse que un mismo carácter en un mensaje a enviar se cifra en dos caracteres distintos en el mensaje encriptado
Quisiera empezar con un sistema muy sencillo que puede explicarse matemáticamente hablando mediante aritmética modular. A lo largo de este articulo usaré por simplicidad el alfabeto inglés estándar de 26 letras:
\tiny\begin{pmatrix} 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25 \\ A& B& C& D& E& F& G& H& I& J& K& L& M& N& O& P& Q& R& S& T& U& V& W& X& Y& Z \\ \end{pmatrix}
Se elige un entero d que determina bloques de d elementos que serán tratados como un vector de d dimensiones. De forma aleatoria, se elige una matriz de d × d elementos los cuales serán la clave a utilizar. Los elementos de la matriz d × d serán enteros entre 0 y 25, además la matriz M debe ser invertible en \mathbb{Z}^n_{26}
Para la encriptación, el texto es dividido en bloques de d elementos los cuales se multiplican por la matriz d × d. Así M\cdot P_i \equiv C \pmod{26} donde hemos asignado a la A el número 0 a la B el 1, … , a la Z el 25, y \pmod{26} indica que debemos tomar el resto de dividir por 26 (en lenguaje C utilizamos el operador % ) M es la matriz d x d, C es el texto cifrado y P el original
Ejemplo de cifrado de Hill
CODIGO rompemos la estructura en bloques de 3 caracteres cada uno (en este caso d = 3), eliminando signos ortográficos si los hubiera y obtenemos los equivalentes numéricos de estas letras
P_1=COD=\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}, P_2=IGO=\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}
Elegimos M=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix} como matriz de claves
Antes de aplicar el cifrado debemos asegurarnos de que M es invertible \mod{26}. Hay una forma relativamente sencilla de averiguar esto a través del cálculo del determinante. Si el determinante de la matriz es 0 o tiene factores comunes con el módulo (en el caso de 26 los factores son 2 y 13), entonces la matriz no puede utilizarse. Al ser 2 uno de los factores de 26 muchas matrices no podrán utilizarse (no servirán todas en las que su determinante sea 0, un múltiplo de 2 o un múltiplo de 13)
\det(M) = \begin{vmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{vmatrix} = 5 \cdot(23 \cdot 13 - 3 \cdot 11) - 17 \cdot (9 \cdot 13 - 3 \cdot 2) + 20 \cdot (9 \cdot 11 - 23 \cdot 2) =
= 1215 - 1734 + 1060 = 503
Ahora comprobamos \pmod{26}:
503 = 9\pmod{26}
La matriz A es invertible en \mod{26}, ya que 26 y 9 son coprimos
Calculamos el primer bloque:
M\cdot P_1=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = \begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix}
\begin{pmatrix} 308 \\ 349 \\ 197 \end{pmatrix} = \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix}\pmod{26}
\begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = WLP
Así el mensaje cifrado del bloque uno es:
C_1=WLP
Calculamos el segundo bloque:
M\cdot P_2=\begin{pmatrix} 5& 17& 20 \\ 9& 23& 3& \\ 2& 11& 13 \end{pmatrix}\cdot \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = \begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix}
\begin{pmatrix} 422 \\ 252 \\ 264 \end{pmatrix} = \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix}\pmod{26}
\begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = GSE
Así el mensaje cifrado del bloque uno es:
C_2=GSE
Unimos ambos mensajes cifrados para obtener el mensaje cifrado C:
C=WLPGSE
Desciframos el C anterior, el método es el mismo, pero necesitamos calcular M^{-1}. Para ello lo calculamos a partir de esta fórmula:
M^{-1}=C^t\cdot (\det(M))^{-1}
Donde C^t es la matriz de cofactores de M transpuesta y (\det(M))^{-1} debe realizarse como \mod{26}, que en este caso es 3 ya que:
9\pmod{26} \cdot 3\pmod{26}=27 \pmod{26}=1 \pmod{26}
Calculamos los cofactores de M
C_{1 1}= + \begin{vmatrix} 23& 3 \\ 11& 13 \end{vmatrix} C_{1 2}= - \begin{vmatrix} 9& 3 \\ 2& 13 \end{vmatrix} C_{1 3}= + \begin{vmatrix} 9& 23 \\ 2& 11 \end{vmatrix}
C_{2 1}= - \begin{vmatrix} 17& 20 \\ 11& 13 \end{vmatrix} C_{2 2}= + \begin{vmatrix} 5& 20 \\ 2& 13 \end{vmatrix} C_{2 3}= - \begin{vmatrix} 5& 17 \\ 2& 11 \end{vmatrix}
C_{3 1}= + \begin{vmatrix} 17& 20 \\ 23& 3 \end{vmatrix} C_{3 2}= - \begin{vmatrix} 5& 20 \\ 9& 3 \end{vmatrix} C_{3 3}= + \begin{vmatrix} 5& 17 \\ 9& 23 \end{vmatrix}
C=\begin{pmatrix} 266& -111& 53 \\ -1& 25& -21& \\ -409& 165& -38 \end{pmatrix} C^t= \begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix}
Ahora aplicamos la fórmula de la inversa:
M^{-1}=C^t\cdot (\det(M))^{-1}=\begin{pmatrix} 266& -1& -409 \\ -111& 25& 165 \\ 53& -21& -38 \end{pmatrix} \cdot 3=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix}
M^{-1}\pmod{26}=\begin{pmatrix} 798& -3& -1227 \\ -333& 75& 495 \\ 159& -63& -114 \end{pmatrix} \pmod{26} =\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1 \\ 3& 15& 16 \end{pmatrix}
Calculamos el primer bloque:
M\cdot P_1=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 22 \\ 11 \\ 15 \end{pmatrix} = \begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix}
\begin{pmatrix} 964 \\ 378 \\ 471 \end{pmatrix} = \begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix}\pmod{26}
\begin{pmatrix} 2 \\ 14 \\ 3 \end{pmatrix} = COD
Así el mensaje cifrado del bloque uno es:
P_1=COD
Calculamos el segundo bloque:
M\cdot P_2=\begin{pmatrix} 18& 23& 21 \\ 5& 23& 1& \\ 3& 15& 16 \end{pmatrix}\cdot \begin{pmatrix} 6 \\ 18 \\ 4 \end{pmatrix} = \begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix}
\begin{pmatrix} 606 \\ 448 \\ 352 \end{pmatrix} = \begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix}\pmod{26}
\begin{pmatrix} 8 \\ 6 \\ 14 \end{pmatrix} = IGO
Así el mensaje cifrado del bloque uno es:
P_2=IGO
Unimos ambos mensajes cifrados para obtener el mensaje cifrado C: