En criptografía clásica , el cifrado de Hill es un cifrado de sustitución poligráfica basado en álgebra lineal . Inventado por Lester S. Hill en 1929, fue el primer cifrado poligráfico en el que fue práctico (aunque apenas) operar en más de tres símbolos a la vez.
La siguiente discusión asume un conocimiento elemental de matrices .
Cifrado
Cada letra está representada por un número módulo 26. Aunque esta no es una característica esencial del cifrado, este esquema simple se usa a menudo:
Letra | A | B | C | D | mi | F | GRAMO | H | I | J | K | L | METRO | norte | O | PAG | Q | R | S | T | U | V | W | X | Y | Z |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Número | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Para cifrar un mensaje, cada bloque de n cartas (considerado como un n componente z del vector ) se multiplica por un invertible n × n matriz , en contra de módulo 26. Para descifrar el mensaje, cada bloque se multiplica por el inverso de la matriz utilizada para cifrado.
La matriz utilizada para el cifrado es la clave de cifrado , y debe elegirse aleatoriamente del conjunto de matrices n × n invertibles ( módulo 26). El cifrado puede, por supuesto, adaptarse a un alfabeto con cualquier número de letras; toda la aritmética solo necesita hacerse 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):
Dado que 'A' es 0, 'C' es 2 y 'T' es 19, el mensaje es el vector:
Por tanto, el vector cifrado viene dado por:
que corresponde a un texto cifrado de 'POH'. Ahora, suponga que nuestro mensaje es en cambio 'CAT', o:
Esta vez, el vector cifrado viene dado por:
que corresponde a un texto cifrado de 'FIN'. Cada letra ha cambiado. El cifrado Hill ha logrado la difusión de Shannon , y un cifrado Hill n- dimensional puede difundirse completamente a través de n símbolos a la vez.
Descifrado
Para descifrar, volvemos el texto cifrado a un vector, 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:
Tomando el texto cifrado de ejemplo anterior de 'POH', obtenemos:
lo que nos devuelve a 'ACT', como se esperaba.
Existen dos complicaciones al elegir la matriz de cifrado:
- No todas las matrices tienen una inversa (ver matriz invertible ). La matriz tendrá una inversa si y solo si su determinante no es cero.
- El determinante de la matriz de cifrado no debe tener ningún factor común con la base modular.
Así, si trabajamos módulo 26 como arriba, 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 se puede usar en Hill. cifrado, y se debe elegir otra matriz (de lo contrario, no será posible descifrar). Afortunadamente, las matrices que satisfacen las condiciones para ser utilizadas en el cifrado Hill son bastante comunes.
Para nuestra matriz de claves de ejemplo:
Entonces, módulo 26, el determinante es 25. Dado que no tiene factores comunes con 26, esta matriz se puede utilizar para el cifrado 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 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
sea la clave y suponga que el mensaje de texto sin formato es 'AYUDA'. Entonces este texto plano está representado por dos pares
Entonces calculamos
- y
y continúe con el cifrado de la siguiente manera:
La matriz K es invertible, por lo tanto existe tal que . La inversa de K se puede calcular usando la fórmula
Esta fórmula aún se mantiene después de una reducción modular si se usa un inverso multiplicativo modular para calcular. Por lo tanto, en este caso, calculamos
Entonces calculamos
- y
Por lo tanto,
- .
Seguridad
El cifrado básico de Hill es vulnerable a un ataque de texto plano conocido porque es completamente lineal . Un oponente que interceptaLos pares de caracteres de texto plano / texto cifrado pueden configurar un sistema lineal que (normalmente) se puede resolver fácilmente; si sucede que este sistema es indeterminado, solo es necesario agregar algunos pares más de texto plano / texto cifrado. Calcular esta solución mediante algoritmos estándar de álgebra lineal lleva 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 , porque la multiplicación de matrices puede proporcionar difusión . Por ejemplo, una matriz elegida apropiadamente puede garantizar que pequeñas diferencias antes de la multiplicación de matrices resultarán en 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 cajas S no lineales con una multiplicación de matrices (MDS) cuidadosamente elegida.
Tamaño del espacio clave
El espacio clave es el conjunto de todas las claves posibles. El tamaño del espacio de clave es el número 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 la clave.
Existen matrices de dimensión n × n . Por lo tanto o sobre es un límite superior en el tamaño de la clave del cifrado Hill utilizando matrices n × n . Este 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 sólo 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 2 ). Es
Igualmente, el número de matrices invertibles módulo 13 (es decir, el orden de GL (n, Z 13 )) es
El número de matrices invertibles módulo 26 es el producto de esos dos números. Por lo tanto es
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.
Implementación mecánica
Cuando se opera con 2 símbolos a la vez, un cifrado Hill no ofrece ninguna ventaja particular sobre Playfair o el cifrado bífido y, de hecho, es más débil que cualquiera de los dos y un poco 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 de EE.UU. 1.845.947 ) para este dispositivo, que realizó una multiplicación de matriz de 6 × 6 módulo 26 utilizando un sistema de engranajes y cadenas.
Desafortunadamente, los arreglos de engranajes (y por lo tanto la clave) se arreglaron para cualquier máquina dada, por lo que se recomendó el cifrado triple por seguridad: un paso no lineal secreto, seguido por el paso amplio de difusión desde la máquina, seguido de un tercer paso no lineal secreto. (El cifrado Even-Mansour, mucho más tardío , también utiliza un paso intermedio difusivo no codificado). Tal combinación fue realmente muy poderosa para 1929 e indica que Hill aparentemente entendió los conceptos de un ataque de encuentro en el medio , así como confusión y difusión. Desafortunadamente, su máquina no se vendió. [ cita requerida ]
Ver también
Otros cifrados poligráficos prácticos de "lápiz y papel" incluyen:
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 cierto aparato de transformación lineal de la criptografía, The American Mathematical Monthly Vol.38, 1931, págs. 135-154.
- Jeffrey Overbey, William Traves y Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia , Vol.29, No.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
- " Hill Cipher Explained " ilustra el álgebra lineal detrás del Hill Cipher
- " Hill's Cipher Calculator " describe el Hill Cipher con una página web