Cifrado Hill

En criptografía clásica, el Cifrado Hill es un cifrado de sustitución poligráfica basado en el álgebra lineal. Inventado por Lester S. Hill en 1929, fue el primer cifrado poligráfico que era práctico para operar sobre más de tres símbolos inmediatamente. El artículo siguiente supone un conocimiento elemental de matrices.

Operación

Cada letra está representada por un número. A menudo el esquema es sencillo A = 0, B = 1, ..., Z = 25 es utilizado, pero esto no es una característica esencial del cifrado. Para encriptar un mensaje, cada bloque de n letras (considerados como un vector) está multiplicado por una matriz invertible n×n (modular 26). Para desencriptar el mensaje, cada bloque es multiplicado por el inverso de la matriz usada para la encriptación.

La matriz usada para la encriptación es la llave de cifrado, y tiene que ser escogida aleatoriamente del conjunto de matrices invertibles n×n (modular 26). El cifrado puede naturalmente, ser adaptado a un alfabeto representado con cualquier orden numerico y/o cambiando el número (modular 26) siempre y cuando la matriz n×n (modular x) sea invertible.

Considerar el mensaje 'ACT', y la clave de abajo (Matriz en letras es GYBNQKURP):

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

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

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

Por ello el vector cifrado está dado por:

{\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}\equiv {\begin{pmatrix}67\\222\\319\end{pmatrix}}

{\begin{pmatrix}(67)mod(26)\\(222)mod(26)\\(319)mod(26)\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}

El cual corresponde al texto 'POH'. Ahora, suponemos que nuestro mensaje es 'CAT', su vector equivalente sería:

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

Esta vez, el vector cifrado está dado por:

{\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}\equiv {\begin{pmatrix}(31)mod(26)\\(216)mod(26)\\(325)mod(26)\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}

El cual corresponde al texto 'FIN'. Cada letra ha cambiado, obteniendo un vector completamente distinto. El cifrado de Hill ha conseguido la difusión de Shannon.

Descifrado

Para descifrar, transformamos el texto cifrado en un vector, entonces sólo tendrás que multiplicar por la matriz inversa de la matriz clave (IFKVIVVMI en letras). (Hay métodos estándares para calcular la matriz inversa; ver matriz invertible para detalles.). Encontramos que, módulo 26, el inverso de la matriz usada en el ejemplo anterior es:

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

Tomando el ejemplo anterior de texto cifrado 'POH', tenemos que :

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

El cual nos da como resultado 'ACT', tal y como esperábamos.

No hemos hablado todavía sobre las dos complicaciones que existen al elegir la matriz de encriptar. No todas las matrices tienen un inverso (ver matriz invertible). La matriz tendrá un inverso si y sólo si su determinante no es cero. También, en el caso del Cifrado de Hill, el determinante de la matriz de encriptar no tiene que tener ningún factor común con la base modular. Así, si trabajamos módulo 26 como arriba, el determinante tiene que ser no-cero, y no tiene que ser divisible por 2 o 13. Si el determinante es 0, o tiene factores comunes con la base modular, entonces la matriz no puede ser utilizada en el Cifrado de Hill y otra matriz tiene que ser escogida. Afortunadamente, las matrices que satisfacen las condiciones para ser utilizadas en el Cifrado de Hill son bastante comunes.

Para poder descifrar el cifrado Hill, debemos comprender que es una matriz traspuesta, adjunta, determinante y como se compone la inversa: La inversa es 1/determinante · (matriz adjunta de la matriz traspuesta)

Para nuestro ejemplo, la matriz clave:

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

Así que, módulo 26, el determinante es 25. Éste tiene no factores comunes con 26, así que esta matriz puede ser utilizada para el Cifrado de Hill.

El riesgo del determinante habiendo factores comunes con el módulo puede ser eliminado convirtiendo el módulo en primo. Consiguientemente una variante útil del Cifrado de Hill añade 3 símbolos extras (como un espacio, un punto y un signo de interrogación) para aumentar el módulo a 29.

Ejemplo

Sea

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

la clave y suponiendo que el mensaje es 'HELP'. Entonces este mensaje está representado por dos pares

$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}}$

Entonces computamos

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

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}11\\15\end{pmatrix}}\equiv {\begin{pmatrix}0\\19\end{pmatrix}}{\pmod {26}}$ y continuamos la encriptación así:

${\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 ello $K^{-1}$ existe tal que $KK^{-1}=K^{-1}K=I_{2}$ . El inverso de K puede ser computado usando la fórmula ${\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}$

Esta fórmula se mantiene después de una reducción modular si el inverso multiplicativo se usa para calcular $(ad-bc)^{-1}$ . En este caso, computamos

$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}}$

$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}}$

Entonces computamos

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

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

Por tanto:

${\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$ .

Véase también

Cifrado de Playfair

Advanced Encryption Standard

Referencias

Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June–July 1929, pp. 306–312. (PDF)
Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly Vol.38, 1931, pp. 135–154.
Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol.29, No.1, January 2005, pp59–72. (CiteSeerX) (PDF)

Aclaración

https://es.wikipedia.org/wiki/Usuario:Lbayo

Enlaces externos

"Hill Cipher, la aplicación web" implementa el Hill cipher y muestra las matrices implicadas
"Hill Cipher" ilustra el álgebra lineal detrás del Hill Cipher
"Hill Cipher, la calculadora" perfila el Hill Cipher con una Página web

Datos: Q2454939