37997695
CIFRADO DE HILL
- El cifrado de Hill fue inventado, basándose en el álgebra
lineal, por el matemático norteamericano Lester S. Hill en
1929, y aparece explicado en su artículo Cryptography in an
Algebraic Alphabet, publicado en The American
Mathematical Monthly.
- Es un sistema criptográfico de sustitución polialfabético,
es decir, un mismo signo, en este caso una misma letra,
puede ser representado en un mismo mensaje con más
de un carácter. Así, en el ejemplo que vamos a analizar a
continuación, la letra A del mensaje original aparece
representada en el mensaje codificado de tres formas
distintas, como C, K e I.
- Como en la correspondencia anterior, entre letras/signos y números, solamente
aparecen 27 números, hay que trabajar con los números enteros “módulo 27”. Es
decir, se consideran los números enteros 0, 1, 2,… , 26 y el resto se identifica con
estos de forma cíclica. Así, el 27 es igual a 0, el 28 a 1, el 29 a 2, etcétera, y lo mismo
con los números negativos, de forma que – 1 es igual 26, – 2 es igual 25, etcétera.
Además, se reducen las operaciones aritméticas (suma, resta, multiplicación y
división) al conjunto de los números enteros módulo 27 de forma natural, es decir,
al operar dos números enteros (módulo 27) el resultado se considera también
módulo 27. Por ejemplo, si se realiza la multiplicación de los números 6 y 13,
módulo 27, el resultado dará 24 (módulo 27), puesto que 6 13 = 78 y 78 = 2 27 +
24. O el inverso de 2, es decir, el número a tal que 2 a es igual a 1 (módulo 27), es
14, puesto que 2 14 = 28, que es igual a 1, módulo 27. En el cifrado de Hill se utiliza
una
- “CUADERNO DE CULTURA CIENTIFICA”, cuya transcripción
numérica, teniendo en cuanta la tabla de sustitución anterior,
es “2, 21, 0, 3, 4, 18, 13, 15, 3, 4, 2, 21, 11, 20, 21, 18, 0, 2, 8, 4, 13,
20, 8, 5, 8, 2, 0”. Como la transformación lineal es de orden 3,
vamos a agrupar los números en grupos de tres, en ternas,
sobre las que luego aplicaremos la transformación lineal, (2, 21,
0), (3, 4, 18), (13, 15, 3), (4, 2, 21), (11, 20, 21), (18, 0, 2), (8, 4, 13),
(20, 8, 5), (8, 2, 0). A continuación, vamos a transformar las
ternas de números anteriores, mediante la transformación
lineal dada por la clave, en nuevas ternas, que serán el mensaje
numérico cifrado. ¡Ojo!, que en la transformación lineal no hay
que olvidar que seguimos trabajando con los números enteros
módulo 27.
- Aunque la transformación lineal de la
terna (2, 21, 0) es inicialmente (44, 84, 2),
como estamos trabajando con enteros
módulo 27, esta terna se convierte en (17,
3, 2), ya que 44 = 1 x 27 + 17 y 84 = 3 x 27 +
3. E igual para el resto.
- En consecuencia, la secuencia de ternas numéricas original
asociada al anterior mensaje codificado es (3, 8, 22), (21, 11, 6),
(0, 13, 3), (15, 11, 0), (19, 12, 0), (20, 4, 12), (0, 20, 8), (2, 0, 19). Y
traduciendo los números a sus correspondientes letras del
alfabeto se obtiene que el mensaje original enviado es
- “DIVULGANDO LAS
MATEMATICAS”
- Máquina de cifrado M-94 utilizada
por el ejército de los Estados
Unidos de América entre los años
1922 y 1945, que consta de 25
discos con las letras del alfabeto
- Sin embargo, el cifrado de Hill no es seguro. Utilizando métodos de álgebra lineal en un “ataque con
texto claro conocido” puede romperse el código y descubrir la matriz clave de encriptado. Un ataque
con texto claro conocido significa que el analista que quiere romper el código dispone de un ejemplo
de “texto en claro”, es decir, de un mensaje original, con el correspondiente mensaje cifrado. Veamos
cómo se puede romper este código. Supongamos que estamos utilizando la matriz clave anterior A =
(1 2 3 / 0 4 5 / 1 0 6), y que el analista “enemigo” ha conseguido obtener tanto un mensaje original
como el correspondiente mensaje cifrado. Por ejemplo, el primero de los utilizados en esta entrada
del Cuaderno de Cultura Científica. MENSAJE ORIGINAL: “CUADERNO DE CULTURA CIENTIFICA” (2, 21,
0), (3, 4, 18), (13, 15, 3), (4, 2, 21), (11, 20, 21), (18, 0, 2), (8, 4, 13), (20, 8, 5), (8, 2, 0) MENSAJE CIFRADO:
“QDCLYDYUEQFVGWCXKDBAFXDWMII” (17, 3, 2), (11, 25, 3), (25, 21, 4), (17, 5, 22), (
- Aunque esta última parte de la presente entrada es muy interesante, debido a que nos muestra una
aplicación del método de Gauss Jordan, también es un poco técnica, por lo que las personas que lo
deseen pueden saltársela y considerar simplemente que es posible romper el cifrado de Hill, mediante
técnicas de álgebra lineal. El método de Gauss Jordan consiste realizar una serie de operaciones sobre la
anterior matriz, que está dividida en dos partes, la correspondiente al mensaje original y la del mensaje
cifrado, para conseguir que en la parte de la izquierda quede la matriz identidad (1 0 0 / 0 1 0 / 0 0 1) en
tres de las filas, para considerar entonces la parte correspondiente de la derecha, como se mostrará
después. Esas operaciones consisten en sustituir cada fila de la matriz por el resultado de
sumarle/restarle a esa fila una combinación lineal de algunas de las otras filas. Como el elemento que
está en la primera fila y la primera columna tiene que ser un 1, para conseguir la ma
- Ahora queremos conseguir un 1 en la posición que se corresponde con la segunda fila y la segunda
columna, de nuevo buscando conseguir la matriz identidad en la parte de la izquierda. Como en esa
posición está el 13, debemos buscar su inverso módulo 27, que resulta que es 25 (ya que 13 x 25 =
325, que tomando módulo 27, es igual a 1). Es decir, hay que multiplicar la segunda fila por 25, de
manera que esta segunda fila (0 13 18 : 26 7 0) se transforma, al multiplicarla por 25 (módulo 27) en
(0 1 18 : 2 13 0). Y ahora buscamos obtener ceros en la segunda posición de las demás filas mediante
las siguientes sustituciones (método de Gauss Jordan): f) “1ª fila” se sustituye por “1ª fila” – 24 x “2ª
fila” (módulo 27) g) “4ª fila” se sustituye por “4ª fila” – 14 x “2ª fila” (módulo 27) h) “5ª fila” se sustituye
por “5ª fila” – 26 x “2ª fila” (módulo 27) quedando ahora la matriz como sigue
- El siguiente paso sería conseguir un 1 en la posición que se corresponde con la tercera fila y la tercera
columna, una vez más buscando conseguir la matriz identidad en la parte de la izquierda. Sin embargo,
en este momento nos encontramos con una primera anomalía por trabajar módulo 27, y es que los
números enteros módulo 27 admiten “divisores de cero”, como el 3 y el 9, ya que el producto de 3 por 9
es igual a 0 (módulo 27), y estos no tienen inverso. En consecuencia, no se puede conseguir un 1 en la
tercera columna de las filas 3, 4 y 5. Y al multiplicarlas por 9 se anulan todos sus elementos, luego esas
tres filas no nos interesan. Por lo tanto, vamos a intentar conseguir un 1 en la tercera columna de la
fila 6, para lo cual tenemos que multiplicar por el inverso de 2, que como ya sabemos es 14. Y al fila 6
pasa de (0 0 2 : 6 10 12) a (0 0 1 : 3 5 6), al multiplicarla por 14. Y para obtener la matriz identidad en la
parte de la izquierda solo nos falta convertir el 18 que está e
- Luego, tras el método de
Gauss Jordan (módulo 27), en
la parte de la derecha de la
matriz, correspondiéndose con
la matriz identidad de la
izquierda, nos queda la
siguiente matriz
- que es la matriz traspuesta (es decir, se cambian
las filas por columnas, y al revés) de la matriz clave
utilizada en el ejemplo que hemos visto de
encriptación de Hill. En consecuencia, el álgebra
lineal que ha servido para desarrollar el cifrado de
Hill, también sirve para romper su código.
- Una forma de evitar lo
anterior, es modificar el
algoritmo del cifrado de Hill
para que la matriz clave no
sea fija, sino que sea
dinámica.
- Una forma de evitar lo
anterior, es modificar el
algoritmo del cifrado de Hill
para que la matriz clave no
sea fija, sino que sea
dinámica.
- que es la matriz traspuesta (es decir, se cambian
las filas por columnas, y al revés) de la matriz clave
utilizada en el ejemplo que hemos visto de
encriptación de Hill. En consecuencia, el álgebra
lineal que ha servido para desarrollar el cifrado de
Hill, también sirve para romper su código.
- Luego, tras el método de
Gauss Jordan (módulo 27), en
la parte de la derecha de la
matriz, correspondiéndose con
la matriz identidad de la
izquierda, nos queda la
siguiente matriz
- El siguiente paso sería conseguir un 1 en la posición que se corresponde con la tercera fila y la tercera
columna, una vez más buscando conseguir la matriz identidad en la parte de la izquierda. Sin embargo,
en este momento nos encontramos con una primera anomalía por trabajar módulo 27, y es que los
números enteros módulo 27 admiten “divisores de cero”, como el 3 y el 9, ya que el producto de 3 por 9
es igual a 0 (módulo 27), y estos no tienen inverso. En consecuencia, no se puede conseguir un 1 en la
tercera columna de las filas 3, 4 y 5. Y al multiplicarlas por 9 se anulan todos sus elementos, luego esas
tres filas no nos interesan. Por lo tanto, vamos a intentar conseguir un 1 en la tercera columna de la
fila 6, para lo cual tenemos que multiplicar por el inverso de 2, que como ya sabemos es 14. Y al fila 6
pasa de (0 0 2 : 6 10 12) a (0 0 1 : 3 5 6), al multiplicarla por 14. Y para obtener la matriz identidad en la
parte de la izquierda solo nos falta convertir el 18 que está e
- Ahora queremos conseguir un 1 en la posición que se corresponde con la segunda fila y la segunda
columna, de nuevo buscando conseguir la matriz identidad en la parte de la izquierda. Como en esa
posición está el 13, debemos buscar su inverso módulo 27, que resulta que es 25 (ya que 13 x 25 =
325, que tomando módulo 27, es igual a 1). Es decir, hay que multiplicar la segunda fila por 25, de
manera que esta segunda fila (0 13 18 : 26 7 0) se transforma, al multiplicarla por 25 (módulo 27) en
(0 1 18 : 2 13 0). Y ahora buscamos obtener ceros en la segunda posición de las demás filas mediante
las siguientes sustituciones (método de Gauss Jordan): f) “1ª fila” se sustituye por “1ª fila” – 24 x “2ª
fila” (módulo 27) g) “4ª fila” se sustituye por “4ª fila” – 14 x “2ª fila” (módulo 27) h) “5ª fila” se sustituye
por “5ª fila” – 26 x “2ª fila” (módulo 27) quedando ahora la matriz como sigue
- Aunque esta última parte de la presente entrada es muy interesante, debido a que nos muestra una
aplicación del método de Gauss Jordan, también es un poco técnica, por lo que las personas que lo
deseen pueden saltársela y considerar simplemente que es posible romper el cifrado de Hill, mediante
técnicas de álgebra lineal. El método de Gauss Jordan consiste realizar una serie de operaciones sobre la
anterior matriz, que está dividida en dos partes, la correspondiente al mensaje original y la del mensaje
cifrado, para conseguir que en la parte de la izquierda quede la matriz identidad (1 0 0 / 0 1 0 / 0 0 1) en
tres de las filas, para considerar entonces la parte correspondiente de la derecha, como se mostrará
después. Esas operaciones consisten en sustituir cada fila de la matriz por el resultado de
sumarle/restarle a esa fila una combinación lineal de algunas de las otras filas. Como el elemento que
está en la primera fila y la primera columna tiene que ser un 1, para conseguir la ma
- Sin embargo, el cifrado de Hill no es seguro. Utilizando métodos de álgebra lineal en un “ataque con
texto claro conocido” puede romperse el código y descubrir la matriz clave de encriptado. Un ataque
con texto claro conocido significa que el analista que quiere romper el código dispone de un ejemplo
de “texto en claro”, es decir, de un mensaje original, con el correspondiente mensaje cifrado. Veamos
cómo se puede romper este código. Supongamos que estamos utilizando la matriz clave anterior A =
(1 2 3 / 0 4 5 / 1 0 6), y que el analista “enemigo” ha conseguido obtener tanto un mensaje original
como el correspondiente mensaje cifrado. Por ejemplo, el primero de los utilizados en esta entrada
del Cuaderno de Cultura Científica. MENSAJE ORIGINAL: “CUADERNO DE CULTURA CIENTIFICA” (2, 21,
0), (3, 4, 18), (13, 15, 3), (4, 2, 21), (11, 20, 21), (18, 0, 2), (8, 4, 13), (20, 8, 5), (8, 2, 0) MENSAJE CIFRADO:
“QDCLYDYUEQFVGWCXKDBAFXDWMII” (17, 3, 2), (11, 25, 3), (25, 21, 4), (17, 5, 22), (
- Máquina de cifrado M-94 utilizada
por el ejército de los Estados
Unidos de América entre los años
1922 y 1945, que consta de 25
discos con las letras del alfabeto
- “DIVULGANDO LAS
MATEMATICAS”
- En consecuencia, la secuencia de ternas numéricas original
asociada al anterior mensaje codificado es (3, 8, 22), (21, 11, 6),
(0, 13, 3), (15, 11, 0), (19, 12, 0), (20, 4, 12), (0, 20, 8), (2, 0, 19). Y
traduciendo los números a sus correspondientes letras del
alfabeto se obtiene que el mensaje original enviado es
- Aunque la transformación lineal de la
terna (2, 21, 0) es inicialmente (44, 84, 2),
como estamos trabajando con enteros
módulo 27, esta terna se convierte en (17,
3, 2), ya que 44 = 1 x 27 + 17 y 84 = 3 x 27 +
3. E igual para el resto.
- “CUADERNO DE CULTURA CIENTIFICA”, cuya transcripción
numérica, teniendo en cuanta la tabla de sustitución anterior,
es “2, 21, 0, 3, 4, 18, 13, 15, 3, 4, 2, 21, 11, 20, 21, 18, 0, 2, 8, 4, 13,
20, 8, 5, 8, 2, 0”. Como la transformación lineal es de orden 3,
vamos a agrupar los números en grupos de tres, en ternas,
sobre las que luego aplicaremos la transformación lineal, (2, 21,
0), (3, 4, 18), (13, 15, 3), (4, 2, 21), (11, 20, 21), (18, 0, 2), (8, 4, 13),
(20, 8, 5), (8, 2, 0). A continuación, vamos a transformar las
ternas de números anteriores, mediante la transformación
lineal dada por la clave, en nuevas ternas, que serán el mensaje
numérico cifrado. ¡Ojo!, que en la transformación lineal no hay
que olvidar que seguimos trabajando con los números enteros
módulo 27.
- Como en la correspondencia anterior, entre letras/signos y números, solamente
aparecen 27 números, hay que trabajar con los números enteros “módulo 27”. Es
decir, se consideran los números enteros 0, 1, 2,… , 26 y el resto se identifica con
estos de forma cíclica. Así, el 27 es igual a 0, el 28 a 1, el 29 a 2, etcétera, y lo mismo
con los números negativos, de forma que – 1 es igual 26, – 2 es igual 25, etcétera.
Además, se reducen las operaciones aritméticas (suma, resta, multiplicación y
división) al conjunto de los números enteros módulo 27 de forma natural, es decir,
al operar dos números enteros (módulo 27) el resultado se considera también
módulo 27. Por ejemplo, si se realiza la multiplicación de los números 6 y 13,
módulo 27, el resultado dará 24 (módulo 27), puesto que 6 13 = 78 y 78 = 2 27 +
24. O el inverso de 2, es decir, el número a tal que 2 a es igual a 1 (módulo 27), es
14, puesto que 2 14 = 28, que es igual a 1, módulo 27. En el cifrado de Hill se utiliza
una
- Es un sistema criptográfico de sustitución polialfabético,
es decir, un mismo signo, en este caso una misma letra,
puede ser representado en un mismo mensaje con más
de un carácter. Así, en el ejemplo que vamos a analizar a
continuación, la letra A del mensaje original aparece
representada en el mensaje codificado de tres formas
distintas, como C, K e I.
Media attachments
0 comments
Want to create your own Mind Maps for free with GoConqr? Learn more.