Cifrado de colina

Cifrado por sustitución basado en álgebra lineal

Máquina de cifrado de Hill, de la figura 4 de la patente

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 en el que era práctico (aunque difícilmente) operar con más de tres símbolos a la vez.

La siguiente discusión supone un conocimiento elemental de matrices .

Encriptación

Cada letra está representada por un número módulo 26. Aunque no es una característica esencial del sistema de cifrado, se suele utilizar este sencillo esquema:

Para cifrar un mensaje, cada bloque de n letras (considerado como un vector de n componentes ) se multiplica por una matriz invertible n × n , contra 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). Por supuesto, el cifrado puede adaptarse a un alfabeto con cualquier número de letras; toda la aritmética solo debe realizarse módulo el número de letras en lugar de módulo 26.

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

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

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

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

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

Esta vez, 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}}}$

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

Descifrado

Para descifrarlo, volvemos a convertir el texto cifrado 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 de texto cifrado de '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 se esperaba.

Existe una complicación a la hora de elegir la matriz de cifrado:

1. No todas las matrices tienen inversa . La matriz tendrá inversa si y sólo si su determinante es inversible módulo n, donde n es la base modular.

Así, si trabajamos módulo 26 como se ha indicado anteriormente, el determinante debe ser distinto de cero y no debe ser divisible por 2 o 13. Si el determinante es 0 o tiene factores comunes con la base modular, entonces la matriz no puede utilizarse en el cifrado de Hill y debe elegirse otra matriz (de lo contrario no será posible descifrarla). Afortunadamente, las matrices que satisfacen 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. Como y , 25 no tiene factores comunes con 26, y esta matriz se puede utilizar para el cifrado de Hill. ${\displaystyle 25=5^{2}}$ ${\displaystyle 26=2\times 13}$

El riesgo de que el determinante tenga factores comunes con el módulo se puede eliminar haciendo que el módulo sea primo . Por consiguiente, una variante útil del cifrado de Hill agrega 3 símbolos adicionales (como un espacio, un punto y un signo de interrogación) para aumentar el módulo a 29.

Ejemplo

Dejar

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

sea ​​la clave y supongamos que el mensaje de texto simple es 'AYUDA'. Entonces, este texto simple 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 con 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 existe tal que . La inversa de K se puede calcular utilizando la fórmula ${\displaystyle K^{-1}}$ ${\displaystyle KK^{-1}=K^{-1}K=I_{2}}$ ${\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 . Por lo tanto, en este caso, calculamos ${\displaystyle (ad-bc)^{-1}}$

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

Seguridad

El cifrado Hill básico es vulnerable a un ataque de texto plano conocido porque es completamente lineal . Un oponente que intercepte pares de caracteres de texto plano/texto cifrado puede configurar un sistema lineal que (normalmente) puede resolverse fácilmente; si sucede que este sistema es indeterminado, solo es necesario agregar algunos pares de caracteres de texto plano/texto cifrado más. Calcular esta solución mediante algoritmos de álgebra lineal estándar requiere muy poco tiempo. ${\displaystyle n^{2}}$

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 , porque la multiplicación de matrices puede proporcionar difusión . Por ejemplo, una matriz elegida adecuadamente puede garantizar que pequeñas diferencias antes de la multiplicación de matrices darán como resultado grandes diferencias después de la multiplicación de matrices. 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 S-boxes no lineales con una multiplicación de matrices (MDS) cuidadosamente elegida.

Tamaño del espacio clave

El espacio de claves es el conjunto de todas las claves posibles. El tamaño del espacio de claves es la cantidad de claves posibles. El tamaño efectivo de la clave , en número de bits, es el logaritmo binario del tamaño del espacio de claves.

Existen matrices de dimensión n × n . Por lo tanto, o aproximadamente es un límite superior para el tamaño de la clave del cifrado de Hill que utiliza matrices n × n . Esto es solo un límite superior porque no todas las matrices son invertibles y, por lo tanto, se pueden usar como clave. El número de matrices invertibles se puede calcular mediante el teorema del resto chino . Es decir, una matriz es invertible módulo 26 si y solo si es invertible tanto módulo 2 como módulo 13. El número de matrices n × n invertibles módulo 2 es igual al orden del grupo lineal general GL(n, Z ₂ ). Es ${\displaystyle 26^{n^{2}}}$ ${\displaystyle \log _{2}(26^{n^{2}})}$ ${\displaystyle 4.7n^{2}}$

${\displaystyle 2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n}).}$

Igualmente, el número de matrices invertibles módulo 13 (es decir, el orden de GL(n, Z ₁₃ )) es

${\displaystyle 13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).}$

El número de matrices invertibles módulo 26 es el producto de esos dos números. Por lo tanto, es

${\displaystyle 26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).}$

Además, parece prudente evitar demasiados ceros en la matriz de claves, ya que reducen la difusión. El efecto neto es que el espacio de claves efectivo de un cifrado Hill básico es de aproximadamente . Para un cifrado Hill de 5 × 5, eso es aproximadamente 114 bits. Por supuesto, la búsqueda de claves no es el ataque conocido más eficiente. ${\displaystyle 4.64n^{2}-1.7}$

Implementación mecánica

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

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

Lamentablemente, los mecanismos de transmisión (y, por lo tanto, la clave) eran fijos para cada máquina, por lo que se recomendaba una triple encriptación por razones de seguridad: un paso no lineal secreto, seguido por el paso difusivo amplio de la máquina, seguido por un tercer paso no lineal secreto (el cifrado Even-Mansour, mucho más tardío, también utiliza un paso intermedio difusivo sin clave). Esta combinación era realmente muy poderosa para 1929, e indica que Hill aparentemente entendía los conceptos de un ataque de encuentro en el medio, así como los de confusión y difusión. Lamentablemente, su máquina no se vendió. ^{[ cita requerida ]}

Véase también

Otros cifrados poligráficos prácticos de "lápiz y papel" incluyen:

• Cifrado de Playfair
• Cifra bífida
• Cifra trífida

Referencias

• 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)

Enlaces externos

• "Hill Cipher Web App" implementa el cifrado Hill y muestra las matrices involucradas
• "El cifrado de Hill explicado" ilustra el álgebra lineal detrás del cifrado de Hill
• "Calculadora de cifrado de Hill" describe el cifrado de Hill con una página web