Cifrado de la colina

El cifrado de Hill es un cifrado de sustitución de poligramas basado en álgebra lineal y aritmética modular . Inventado por el matemático estadounidense Lester Hill en 1929. Fue el primer cifrado que hizo posible en la práctica (aunque con dificultad) operar simultáneamente con más de tres caracteres. El cifrado de Hill no ha encontrado aplicación práctica en criptografía debido a la débil resistencia al cracking ya la falta de una descripción de los algoritmos para generar grandes matrices directas e inversas.

Historia

El cifrado de Hill se describió por primera vez en el artículo "Criptografía en un alfabeto algebraico" [1] , publicado en The American Mathematical Monthly en junio-julio de 1929. En agosto de ese año, Hill amplió el tema y pronunció un discurso sobre criptografía ante la American Mathematical Society en Boulder, Colorado [2] . Su conferencia más tarde condujo a un segundo artículo, "Sobre ciertos aparatos de criptografía de transformación lineal" [3] , que se publicó en The American Mathematical Monthly en marzo de 1931. David Kahn , en su Code Breakers , describió el cifrado de Hill y su lugar en la historia de la criptografía [4] de la siguiente manera:

Hill fue uno de los que desarrollaron un método general y poderoso. Además, el cifrado de Hill transfirió por primera vez la criptografía mediante poligramas a la categoría de disciplinas prácticas.

Texto original (inglés)[ mostrarocultar] Pero solo Hill ideó un método de poder y generalidad. Además, su procedimiento de criptografía poligráfica es práctico por primera vez.

Descripción del cifrado de Hill

El cifrado de Hill es un cifrado de poligrama que puede usar bloques grandes usando álgebra lineal. A cada letra del alfabeto se le asigna un número módulo 26. Para el alfabeto latino, a menudo se usa el esquema más simple: A = 0, B = 1, ..., Z = 25, pero esta no es una propiedad esencial del cifrado. . Un bloque de n letras se trata como un vector n - dimensional y se multiplica módulo 26 por una matriz n  ×  n . Si se usa un número mayor que 26 como base del módulo, entonces se puede usar un esquema numérico diferente para hacer coincidir las letras de los números y agregar espacios y puntuación [5] . Los elementos de la matriz son la clave. La matriz debe ser invertible para que la operación de descifrado sea posible [6] [7] . ${\matemáticas {Z}}_{{26}}^{n}$

Para n = 3, el sistema se puede describir de la siguiente manera:

{\begin{casos}c_{1}=k_{11}p_{1}+k_{12}p_{2}+k_{13}p_{3}{\pmod {26)),\\ c_{2}=k_{21}p_{1}+k_{22}p_{2}+k_{23}p_{3}{\pmod {26)),\\c_{3}=k_{31} p_{1}+k_{32}p_{2}+k_{33}p_{3}{\pmod {26}},\\\end{casos}}

o en forma matricial:

{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix))={\begin{bmatrix}k_{11}&k_{12}&k_{13} \\k_{21}&k_{22}&k_{23}\\k_{31}&k_{32}&k_{33}\end{bmatrix}}{\begin{bmatrix}p_{1}\\p_{2} \\p_{3}\end{bmatriz}}{\pmod {26}},

C=KP{\pmod {26)),

donde y son vectores de columna de altura 3 que representan el texto sin formato y el texto cifrado, respectivamente, y es una matriz de 3 × 3 que representa la clave de cifrado. Las operaciones se realizan módulo 26. $PAGS$ $C$ $k$

Para descifrar el mensaje, se requiere obtener la matriz de clave inversa . Existen métodos estándar para calcular matrices inversas (ver formas de encontrar una matriz inversa ), pero no todas las matrices tienen una inversa (ver matriz inversa ). Una matriz tendrá una inversa si y solo si su determinante es distinto de cero y no tiene divisores comunes con el módulo base [8] . Si el determinante de una matriz es cero o tiene un divisor común con el módulo base, entonces esa matriz no se puede usar en un cifrado de Hill, y se debe elegir otra matriz (de lo contrario, el texto cifrado será indescifrable). Sin embargo, las matrices que satisfacen las condiciones anteriores existen en abundancia [6] . $K^{-1}$

En general, el algoritmo de cifrado se puede expresar de la siguiente manera [6] [9] :

Cifrado: . $C=E(K,P)=KP{\pmod {26))$

Descifrado: . $P=D(K,C)=K^{-1}C{\pmod {26}}=K^{-1}KP{\pmod {26}}=P$

Ejemplo

En el siguiente ejemplo [7] , se utilizan letras latinas de la A a la Z, los valores numéricos correspondientes se dan en la tabla.

A	B	C	D	mi	F	GRAMO	H	yo	j	k	L	METRO	norte	O	PAGS	q	R	S	T	tu	V	W	X	Y	Z
0	una	2	3	cuatro	5	6	7	ocho	9	diez	once	12	13	catorce	quince	dieciséis	17	Dieciocho	19	veinte	21	22	23	24	25

Cifrado

Considere el mensaje "ACT" y la siguiente clave (GYBNQKURP en forma literal):

K={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix)).

Esta matriz es invertible, ya que su determinante no es igual a cero y no tiene divisores comunes con el módulo base. El peligro de que el determinante de la matriz clave tenga divisores comunes con la base del módulo puede eliminarse eligiendo un número primo como base del módulo. Por ejemplo, en una variante más conveniente del cifrado de Hill, se agregan 3 caracteres adicionales ( espacio , punto y signo de interrogación) al alfabeto para aumentar la base del módulo a 29 [5] .

Dado que la letra "A" corresponde al número 0, "C" - 2, "T" - 19, el mensaje es un vector

P_{1}={\begin{bmatrix}0\\2\\19\end{bmatrix}}.

Entonces el vector encriptado será

C_{1}=KP_{1}{\pmod {26}}={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix}}{\begin{bmatrix}0\\2\ \19\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}15\\14\\7\end{bmatrix}}.

El vector corresponde al texto cifrado "POH". Ahora supongamos que nuestro mensaje fuera "CAT":

P_{2}={\begin{bmatrix}2\\0\\19\end{bmatrix}}.

Ahora el vector encriptado será

C_{2}=KP_{2}{\pmod {26}}={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix}}{\begin{bmatrix}2\\0\ \19\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}5\\8\\13\end{bmatrix}}.

Este vector corresponde al texto cifrado "FIN". Se puede ver que cada letra del texto cifrado ha cambiado. El cifrado de Hill logró la difusión según Shannon , y un cifrado de Hill n -dimensional puede lograr la difusión de n caracteres a la vez.

Descifrado

Matriz de clave inversa:

K^{-1}{\pmod {26}}={\begin{bmatrix}8&5&10\\21&8&21\\21&12&8\end{bmatrix}}.

Tomemos el texto cifrado del ejemplo "POH" anterior:

P_{1}=K^{-1}C_{1}{\pmod {26}}={\begin{bmatrix}8&5&10\\21&8&21\\21&12&8\end{bmatrix}}{\begin{bmatrix }}{\begin{bmatrix} }15\\14\\7\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}0\\2\\19\end{bmatrix}}.

Este vector corresponde al mensaje "ACT".

Seguridad

El cifrado Hill estándar es vulnerable a un ataque de texto sin formato elegido porque utiliza operaciones lineales. Un criptoanalista que intercepte el par símbolo del mensaje/símbolo del texto cifrado podrá componer un sistema de ecuaciones lineales , que normalmente no es difícil de resolver. Si resulta que el sistema no tiene solución, solo necesita agregar algunos pares más de caracteres de mensaje/carácter de texto cifrado. Tales cálculos por medio de algoritmos de álgebra lineal convencionales requieren muy poco tiempo. En este sentido, para aumentar la fuerza criptográfica , habría que añadirle algunas operaciones no lineales. La combinación de operaciones lineales, como en el cifrado de Hill, y pasos no lineales condujo a la creación de una red de permutación-permutación (como la red de Feistel ). Por lo tanto, desde cierto punto de vista, los cifrados de bloques modernos pueden considerarse como un tipo de cifrados de poligramas [7] [8] . $n^{2}$

Longitud de clave

La longitud de la clave es el logaritmo binario del número de todas las claves posibles. Hay matrices de n  ×  n . Por lo tanto, es el límite superior de la longitud de la clave para un cifrado de Hill que utiliza matrices n  ×  n . Este es solo un límite superior, ya que no todas las matrices son invertibles, y solo esas matrices pueden ser una clave. El número de matrices invertibles se puede calcular utilizando el teorema chino del resto . Una matriz es invertible módulo 26 si y solo si es invertible módulo 2 y módulo 13 [8] . $26^{{n^{2}}}$ $\log _{2}(26^{n^{2}})\aproximadamente 4{,}7n^{2}$

El número de matrices n  ×  n invertibles módulo 2 y 13 es igual al orden del grupo lineal GL( n ,  Z 2 ) y GL( n ,  Z 13 ) respectivamente:

|K_{1}|=2^{n^{2}}(1-1/2)(1-1/2^{2})\puntos (1-1/2^{n}) ,

|K_{2}|=13^{n^{2}}(1-1/13)(1-1/13^{2})\puntos (1-1/13^{n}) .

El número de matrices invertibles módulo 26 es igual al producto de estos números:

|K|=26^{n^{2}}(1-1/2)(1-1/2^{2})\dots (1-1/2^{n})(1- 1/13)(1-1/13^{2})\puntos (1-1/13^{n}).

Además, sería prudente evitar demasiados ceros en la matriz clave, ya que reducen la difusión. Como resultado, resulta que el espacio de claves efectivo del cifrado estándar de Hill es de aproximadamente . Para un cifrado Hill de 5×5, esto sería de aproximadamente 114 bits. Obviamente, la fuerza bruta no es el ataque más eficaz contra el cifrado de Hill [7] . ${\ estilo de visualización 4{,}64n^{2}-1{,}7}$

Implementación mecánica

Cuando se trabaja con dos caracteres a la vez, el cifrado de Hill no proporciona ninguna ventaja específica sobre el cifrado de Playfair e incluso es inferior en términos de fuerza criptográfica y facilidad de cálculo en papel. A medida que aumenta el tamaño de la clave, el cifrado rápidamente se vuelve inaccesible para los cálculos humanos en papel. El cifrado Hill de dimensión 6 se implementó mecánicamente. Hill y un socio recibieron una patente para un dispositivo ( Patente de EE. UU. 1,845,947 ) que realizaba una multiplicación de matrices de 6 × 6 módulo 26 utilizando un sistema de engranajes y cadenas. La ubicación de los engranajes (y, por lo tanto, la clave) no se podía cambiar para un dispositivo en particular, por lo que se recomendó el triple cifrado por razones de seguridad. Esta combinación fue muy fuerte para 1929 y muestra que Hill ciertamente entendió los conceptos de confusión y difusión. Sin embargo, el dispositivo era bastante lento, por lo que en la Segunda Guerra Mundial , las máquinas de Hill se usaron solo para cifrar el código de tres caracteres de las señales de radio [10] .

Notas

↑ Lester S. Hill. Criptografía en un Alfabeto Algebraico : Artículo . - 1929. - S. 7 .
↑ Chris Christensen. Lester Hill Revisited // Taylor & Francis Group, LLC: Artículo. - 2014. - S. 297 . — ISSN 0161-1194 .
↑ Lester S. Hill. Acerca de ciertos aparatos de criptografía de transformación lineal (inglés) // The American Mathematical Monthly. - 1931. - Marzo. - S. 135-154 .
↑ David Khan. Los descifradores de códigos: la historia completa de la comunicación secreta desde la antigüedad hasta Internet . — Simón y Schuster. - Nueva York: Scribner, 1996. - Pág . 405 . — 723 pág. — ISBN 0-684-83130-9 .
↑ 1 2 Murray Eisenberg. Hill Ciphers: un proyecto de álgebra lineal con Mathematica .
↑ 1 2 3 William Stallings. Criptografía y seguridad de redes: principios y prácticas. - 5. - Educación Pearson, 2011. - S. 46-49. - ISBN 978-0-13-609704-4 .
↑ 1 2 3 4 A. VN Krishna, Dra. A. Vinaya Babu. Un algoritmo de cifrado Hill modificado para el cifrado de datos en la transmisión de datos (inglés) // Ciencias de la computación y telecomunicaciones: Revista científica electrónica de Georgia. - 2007. - Nº 3 (14) . - S. 78-83 . — ISSN 1512-1232 .
↑ 1 2 3 A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheryomushkin. Fundamentos de criptografía. - 2ª ed. - Helios ARV, 2002. - S. 115-119. — 480 s. — ISBN 5-85438-137-0 .
↑ Dorothy Elizabeth Robling Denning. Criptografía y Seguridad de Datos . - Londres: Addison-Wesley Publishing Company, 1982. - S. 88 -89. — 400 s. — ISBN 0-201-10150-5 .
↑ Friedrich L. Bauer. Secretos descifrados: métodos y máximas de criptología. - Springer, 2002. - S. 85. - 474 p. - ISBN 978-3-662-04738-5 .

Literatura

Guillermo Stallings. Criptografía y seguridad de redes: principios y prácticas. - Pearson, 2011. - Págs. 46-49. — 711 pág. - ISBN 978-0-13-609704-4 .
David Khan. Los descifradores de códigos: la historia completa de la comunicación secreta desde la antigüedad hasta Internet. - Simon y Schuster, 1996. - Pág. 405. - 723 p. - ISBN 978-0-13-609704-4 .
Jeffrey Overbey, William Traves, Jerzy Wojdylo. En el Keyspace del Hill Cipher. - 2005. - T. 29 . — págs. 59–72. -doi : 10.1080/ 0161-110591893771 .
Wade Trappe, Lawrence C. Washington. Introducción a la criptografía: con la teoría de la codificación . - Pearson Prentice Hall, 2006. - P. 34-38 . — 577 pág. — ISBN 0-13-198199-5 .
Craig P. Bauer. Historia secreta: la historia de la criptología. - Prensa CRC, 2013. - Pág. 227-228. — 575 pág. — ISBN 978-1-4665-6187-8 .