cifrado de Hill

En criptografía clásica , el cifrado de Hill es un cifrado de sustitución poligráfico basado en álgebra lineal . Inventado por Lester S. Hill en 1929, fue el primer cifrado poligráfico en el que resultaba práctico (aunque con dificultad) operar con más de tres símbolos a la vez.

La siguiente explicación presupone un conocimiento básico de matrices .

Cada letra está representada por un número módulo 26. Aunque esta no es una característica esencial del cifrado, este sencillo esquema se utiliza con frecuencia:

Para cifrar un mensaje, cada bloque de n letras (considerado como un vector de n componentes ) se multiplica por una matriz invertible de n × n , con módulo 26. Para descifrar el mensaje, cada bloque se multiplica por la inversa de la matriz utilizada para el cifrado.

La matriz utilizada para el cifrado es la clave de cifrado , y debe elegirse aleatoriamente del conjunto de matrices invertibles n × n ( módulo 26). El cifrado puede, por supuesto, adaptarse a un alfabeto con cualquier número de letras; simplemente, todas las operaciones aritméticas deben realizarse módulo el número de letras en lugar de módulo 26.

Considere el mensaje 'ACT' y la clave que aparece a continuación (o GYB / NQK / URP en letras):

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}}$

Dado que 'A' es 0, 'C' es 2 y 'T' es 19, el mensaje es el vector:

${\displaystyle {\begin{pmatrix}0\\2\\19\end{pmatrix}}}$

Por lo tanto, el vector cifrado viene dado por:

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}{\pmod {26}}}$

lo que corresponde a un texto cifrado de 'POH'. Ahora, supongamos que nuestro mensaje es 'CAT', o:

${\displaystyle {\begin{pmatrix}2\\0\\19\end{pmatrix}}}$

En esta ocasión, el vector cifrado viene dado por:

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}={\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}}$

lo que corresponde a un texto cifrado de 'FIN'. Cada letra ha cambiado. El cifrado de Hill ha alcanzado la difusión de Shannon , y un cifrado de Hill n -dimensional puede difundirse completamente a través de n símbolos a la vez.

Para descifrar, convertimos el texto cifrado de nuevo en un vector y luego simplemente lo multiplicamos por la matriz inversa de la matriz clave (IFK / VIV / VMI en letras). Encontramos que, módulo 26, la inversa de la matriz utilizada en el ejemplo anterior es:

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}{\pmod {26}}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}}$

Tomando el ejemplo anterior del texto cifrado 'POH', obtenemos:

${\displaystyle {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}}$

lo que nos lleva de nuevo a 'ACT', como era de esperar.

Existe una complicación al elegir la matriz de cifrado:

1. No todas las matrices tienen inversa . Una matriz tendrá inversa si y solo si su determinante es invertible módulo n, donde n es la base modular.

Así, si trabajamos módulo 26 como se indicó anteriormente, el determinante debe ser distinto de cero y no debe ser divisible por 2 ni por 13. Si el determinante es cero o tiene factores comunes con la base modular, la matriz no se puede utilizar en el cifrado de Hill y se debe elegir otra matriz (de lo contrario, no será posible descifrarla). Afortunadamente, las matrices que cumplen las condiciones para ser utilizadas en el cifrado de Hill son bastante comunes.

Para nuestra matriz de claves de ejemplo:

${\displaystyle {\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)=441\equiv 25{\pmod {26}}}$

Entonces, módulo 26, el determinante es 25. Dado que${\displaystyle 25=5^{2}}$y${\displaystyle 26=2\times 13}$, 25 no tiene factores comunes con 26, y esta matriz se puede utilizar para el cifrado de Hill.

El riesgo de que el determinante tenga factores comunes con el módulo se puede eliminar haciendo que el módulo sea primo . En consecuencia, una variante útil del cifrado de Hill añade 3 símbolos adicionales (como un espacio, un punto y un signo de interrogación) para aumentar el módulo a 29, ya que 27 es 3 al cubo y 28 es 2 veces 14 o 4 veces 7.

Dejar

${\displaystyle K={\begin{pmatrix}3&3\\2&5\end{pmatrix}}}$

Sea la clave y supongamos que el mensaje de texto plano es 'HELP'. Entonces este texto plano está representado por dos pares

${\displaystyle HELP\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to {\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}}$

Luego calculamos

${\displaystyle {\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}7\\4\end{pmatrix}}\equiv {\begin{pmatrix}7\\8\end{pmatrix}}{\pmod {26}},}$y

${\displaystyle {\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}11\\15\end{pmatrix}}\equiv {\begin{pmatrix}0\\19\end{pmatrix}}{\pmod {26}}}$

y continuar el cifrado de la siguiente manera:

${\displaystyle {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}}$

La matriz K es invertible, por lo tanto${\displaystyle K^{-1}}$existe tal que${\displaystyle KK^{-1}=K^{-1}K=I_{2}}$El inverso de K se puede calcular utilizando la fórmula${\displaystyle {\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}}$

Esta fórmula sigue siendo válida después de una reducción modular si se utiliza un inverso multiplicativo modular para calcular${\displaystyle (ad-bc)^{-1}}$Por lo tanto , en este caso, calculamos

${\displaystyle K^{-1}\equiv 9^{-1}{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv 3{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\pmod {26}}}$

${\displaystyle HIAT\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}\to {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}}$

Luego calculamos

${\displaystyle {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}7\\8\end{pmatrix}}={\begin{pmatrix}241\\212\end{pmatrix}}\equiv {\begin{pmatrix}7\\4\end{pmatrix}}{\pmod {26}},}$y

${\displaystyle {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}0\\19\end{pmatrix}}={\begin{pmatrix}323\\171\end{pmatrix}}\equiv {\begin{pmatrix}11\\15\end{pmatrix}}{\pmod {26}}}$

Por lo tanto,

${\displaystyle {\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to HELP}$.

El cifrado básico de Hill es vulnerable a un ataque de texto plano conocido porque es completamente lineal . Un oponente que intercepta${\displaystyle n^{2}}$Los pares de caracteres de texto plano/texto cifrado pueden configurar un sistema lineal que (generalmente) se puede resolver fácilmente; si este sistema resulta indeterminado, basta con añadir algunos pares más de texto plano/texto cifrado. Calcular esta solución mediante algoritmos estándar de álgebra lineal requiere muy poco tiempo.

Si bien la multiplicación de matrices por sí sola no da como resultado un cifrado seguro, sigue siendo un paso útil cuando se combina con otras operaciones no lineales , ya que puede proporcionar difusión . Por ejemplo, una matriz elegida adecuadamente puede garantizar que pequeñas diferencias antes de la multiplicación de matrices resulten en grandes diferencias después de la misma. De hecho, algunos cifrados modernos utilizan un paso de multiplicación de matrices para proporcionar difusión. Por ejemplo, el paso MixColumns en AES es una multiplicación de matrices. La función g en Twofish es una combinación de cajas S no lineales con una multiplicación de matrices (MDS) cuidadosamente seleccionada.

Al operar con dos símbolos simultáneamente, el cifrado de Hill no ofrece ninguna ventaja particular sobre el cifrado de Playfair o el cifrado bífido ; de hecho, es más débil que ambos y ligeramente más laborioso de realizar con lápiz y papel. A medida que aumenta la dimensión, el cifrado se vuelve rápidamente inviable para que un ser humano lo realice manualmente.

Se implementó mecánicamente un cifrado de Hill de dimensión 6. Hill y un socio obtuvieron una patente ( patente estadounidense 1.845.947 ) para este dispositivo, que realizaba una multiplicación de matrices de 6 × 6 módulo 26 mediante un sistema de engranajes y cadenas.

Desafortunadamente, la configuración de los engranajes (y, por lo tanto, la clave) era fija para cada máquina, por lo que se recomendaba el cifrado triple para mayor seguridad: un paso no lineal secreto, seguido del paso difusivo amplio de la máquina, seguido de un tercer paso no lineal secreto. (El cifrado Even-Mansour, mucho posterior , también utiliza un paso intermedio difusivo sin clave). Esta combinación era realmente muy potente para 1929 e indica que Hill aparentemente comprendía los conceptos de un ataque de encuentro en el medio, así como la confusión y la difusión. Lamentablemente, su máquina no se vendió.

Otros cifrados poligráficos prácticos que se pueden realizar con lápiz y papel incluyen:

• cifrado Playfair
• Cifrado bífido
• Cifrado trifido

• Lester S. Hill, Criptografía en un alfabeto algebraico, The American Mathematical Monthly, vol. 36, junio-julio de 1929, págs.  306-312 . ( PDF )
• Lester S. Hill, Sobre ciertos aparatos de transformación lineal de criptografía, The American Mathematical Monthly Vol. 38 , 1931, págs.  135-154 .
• Jeffrey Overbey, William Traves y Jerzy Wojdylo, Sobre el espacio de claves del cifrado Hill, Cryptologia , vol. 29, n.º 1, enero de 2005, págs. 59-72 . ( CiteSeerX ) ( PDF )

• La aplicación web " Hill Cipher " implementa el cifrado de Hill y muestra las matrices involucradas.
• " El cifrado de Hill explicado " ilustra el álgebra lineal que hay detrás del cifrado de Hill.
• La " Calculadora del Cifrado de Hill " describe el Cifrado de Hill en una página web.