• Author / Uploaded
• astrid

• Categories
• Criptografía
• Matriz (Matemáticas)
• Clave (Criptografía)
• Determinante
• Cifrado

Citation preview

TRABAJO COLABORATIVO

MENSAJES OCULTOS – SISTEMA DE HILL

MARCO TEÓRICO

EL CIFRADO DE HILL El sr. Lester s. Hill creó el cifrado de Hill en el año 1929, es un sistema criptográfico o (escrito en clave), que consiste en cambiar o reemplazar un mensaje que contenga números, signos o símbolos por una letra del alfabeto o una letra por un número. Autor: Raúl Ibáñez, Arthur Cayley, explorador victoriano del territorio matemático, RBA, 2017 (pendiente de publicación). Colaborador de la cátedra de cultura científica. Recuperado de: https://culturacientifica.com/2017/01/11/criptografia-matrices-cifrado-hill/

SISTEMAS DE ECUACIONES Y MATRICES Una matriz real de orden m x n siendo m y n números naturales es un conjunto de m x n números distribuidos en “m” filas y “n” columnas. La importancia de esta área radica en que las matrices constituyen una herramienta que nos permite saber rápidamente si un sistema de ecuaciones tiene soluciones y el tipo de soluciones. Recuperado de: https://www.matesfacil.com/matrices/matrices-sistemas.html OPERACIONES CON MATRICES El resultado de multiplicar dos matrices es otra matriz en la que el elemento que ocupa el lugar cij se obtiene sumando los productos parciales que se obtienen al multiplicar todos los elementos de la fila “i” de la primera matriz por los elementos de la columna “j” de la segunda matriz. Es decir, multiplicamos la primera fila por los elementos de la primera columna y el resultado será nuestro nuevo elemento. Para ello, el número de columnas de la primera matriz debe coincidir con el de filas de la segunda. Recuperado de: https://yosoytuprofe.com/2017/06/04/operaciones-con-matrices/ DETERMINANTES Llamamos determinante de A, det A, al número obtenido al sumar todos los diferentes productos de n elementos que se pueden formar con los elementos de dicha matriz, de modo que en cada producto figuren un elemento de cada distinta fila y uno de cada distinta columna, a cada producto se le asigna el signo (+) si la permutación de los subíndices de filas es del mismo orden que la permutación de los subíndices de columnas, y signo (-) si son de distinto orden. Recuperado de:http://www.ehu.eus/juancarlos.gorostizaga/apoyo/determinantes.htm

DESARROLLO DE LAS ACTIVIDADES

ACTIVIDAD 1 1.2. A partir de la consulta anterior, con sus propias palabras, describa el paso a paso para cifrar la palabra DEDICACIÓN empleando la matriz clave: 1 −5 0 1 Y la asignación numérica que aparece en el siguiente recuadro (en él, el símbolo “_” representa el espacio entre las palabras). ABCDEFGH I J 0123456 789

K L M N Ñ O P Q R S 10 11 12 13 14 15 16 17 18 19

T U V W X Y Z - . 20 21 22 23 24 25 26 27 28

Según la consulta, en el cifrado de Hill se utiliza como clave una matriz cuadrada de números A, y es ésta la que establece la transformación lineal y=A*x, donde y,x son vectores columna y A*x es una multiplicación de matrices. En este caso consideramos una matriz cuadrada de 2*2 y su transformación lineal y=A*x: 𝑦1 1 = 𝑦2 0

−5 𝑥1 * 1 𝑥2

𝑦1 = 1 ∗ 𝑥1 −5 ∗ 𝑥2 𝑦2 = 0 ∗ 𝑥1 +1 ∗ 𝑥2

La palabra que queremos cifrar es DEDICACIÓN

Primer paso: Realizar la transcripción numérica de la palabra en cuestión teniendo en cuenta la tabla de sustitución propuesta, es decir, reemplazamos cada letra de nuestro mensaje a cifrar por el número que le corresponda según la tabla de sustitución.

D 3

E 4

D 3

I 8

C 2

A 0

C 2

I 8

O N 15 13

Segundo paso: Recordemos que tenemos una transformación lineal de orden 2, por eso vamos a agrupar los números en duplas o pares, sobre las que aplicaremos, el siguiente paso, la transformación lineal. (3,4) (3,8) (2,0) (2,8) (15,13)

Tercer paso: Procedemos a transformar las duplas de números por medio de la transformación lineal dada por la clave, en las nuevas duplas, que serán el mensaje numérico cifrado. No podemos olvidar que estamos trabajando con los números enteros módulo 29, es decir 0, 1,2......28 el resto de números que lleguemos a obtener los identificamos con estos de manera cíclica, es decir 29=0, 30=1, 31=2 etc. Y con los números negativos hacemos lo mismo de manera que -1=28, -2=29,….. -29=0 Aquí debemos utilizar la ecuación anteriormente enunciada

𝑦1 1 −5 𝑥1 = * para cada una 𝑦2 0 1 𝑥2

de las duplas de números obtenidos en el segundo paso. (

3 1 −5 3 )∙( )=( 0 4 0 1

−20 −17 (−17 12 )=( ) + 29) = ( ) 4 4 4

Cuando el producto de la multiplicación de matrices es negativo, debemos identificarlos con el número que le corresponde según la tabla y lo hacemos sumándole el 29, como lo indica la operación que resaltamos anteriormente, que es nuestro sistema modular, y si aún nos da otro número negativo repetimos el proceso hasta que nos dé un número entero que esté en nuestra tabla de modular 29

Esto se puede comprobar usando la tabla de correspondencia donde podemos ver que −17 corresponde a 12, y lo hacemos así para el resto de números.

Continuamos: (

3 3 1 −5 )∙( )=( 0 8 0 1

−40 −37 (−37 21 )=( ) + 29 = −8 + 29 = 21) = ( ) +8 8 8

En este caso restamos −37+29 = −8, como no está dentro de nuestra correspondencia de números enteros módulo 29 se vuelve a restar de 29 como indicamos en la operación resaltada.

(

2 2 1 −5 )∙( )=( 0 0 0 1

0 2 )=( ) 0 0

(

2 2 1 −5 )∙( )=( 0 8 0 1

−40 −38 (−38 20 )=( ) + 29 = −9 + 29) = ( ) +8 8 8

(

15 −65 8 1 −5 15 −50 + 29 (−21 )∙( )=( )=( ) + 29 = 8) = ( ) 13 0 +13 0 1 13 13

4. Cuarto paso: con el producto final que obtenemos de cada una de las multiplicaciones de matrices que realizamos anteriormente, es decir la matriz resultante, tenemos los números para convertir el mensaje original en un mensaje cifrado y los escribimos

12, 4, 21, 8, 2, 0, 20, 8,8, 13

5. Quinto paso: transformar de nuevo los números en sus correspondientes letras de la tabla de correspondencia módulo 29, para convertirlo en el mensaje cifrado:

12, 4, 21, 8, 2, 0, 20, 8,8, 13 M E U I C A T I I N

1.3 Describir el proceso (paso a paso) para desencriptar el mensaje obtenido en el punto anterior.

PRIMER PASO: Para poder descifrar el mensaje cifrado mediante el método de Hill se necesita que la matriz de la transformación lineal utilizada, la clave, sea una matriz inversible. Vemos si la matriz de nuestro ejemplo lo es hallando su determinante, el cual debe ser diferente de 0, lo podemos hallar usando la fórmula Det A=(

𝑎 𝑐

𝑏 )=ad-cb 𝑑

1 −5 𝐴=( ) 0 1 𝐷𝑒𝑡 𝐴 = (1 ∙ 1) − (0 ∙ (−5)) = 1 − 0 = 1 𝐷𝑒𝑡 𝐴 = 1

SEGUNDO PASO: Hallar la matriz inversa de A, que es la necesaria para descifrar un mensaje. La inversa de una matriz 2*2 se puede calcular usando la fórmula 1 𝑙𝐴𝑙

𝑑 −𝑐

(

𝑎 Si A= ( 𝑐

−𝑏 ) Donde lAl es el determinante de A 𝑎

1 𝑏 𝑑 ) entonces A-1= 𝑙𝐴𝑙 ( 𝑑 −𝑐

Reemplazamos:

−𝑏 ) 𝑎

1 −5 𝐴=( ) 0 1 𝐴−1 =

1 1 −(−5) ∙( ) −(0) 1 1

𝐴−1 =

1 1 5 ∙( ) 1 0 1

Multiplicamos por cada elemento de la matriz

𝐴−1

1 ∙1 = (1 1 ∙0 1 1 0

𝐴−1 = (

1 ∙5 1 ) = (1 5 ) 1 0 1 ∙1 1

5 ) 1

TERCER PASO: Para descifrar el mensaje hay que utilizar nuevamente el cifrado de Hill, pero utilizando como clave la matriz inversa A-1 (módulo 29) de la matriz A de codificación. Por lo tanto, se empieza de nuevo transformando el mensaje en la sucesión de duplas numéricas asociada. Y entonces se transforman mediante la transformación lineal con matriz A 1, es decir, Y = A-1 ∙ X. M E U I C A T I I N 12 4 21 8 2 0 20 8 8 13 (12,4) (21,8) (2,0) (20,8) (8,13)

(

12 1 5 12 )∙( )=( 0 4 0 1

+20 32 3 ) = ( ) = (32 − 29 = 3) = ( ) +4 4 4

(

21 21 1 5 )∙( )=( 0 8 0 1

+40 61 3 ) = ( ) = (61 − 29 = 32 − 29 = 3) = ( ) +8 8 8

(

2 +0 2 2 1 5 )∙( )=( )=( ) 0 +0 0 0 0 1

(

20 20 1 5 )∙( )=( 0 8 0 1

+40 2 ) = (60 − 29 = 31 − 29 = 2) = ( ) +8 8

(

8 8 +65 1 5 15 )∙( )=( ) = (73 − 29 = 44 − 29 = 15) = ( ) 13 0 +13 0 1 13

CUARTO PASO: Tomando la matriz resultante de cada operación anterior nos quedan las duplas y procedemos a remplazar los números por su valor correspondiente en la tabla de conversión dada: 3 4 3 8 2 0 2 8 15 13 DE D I C A C I O N

Y de este modo desencriptamos el mensaje cifrado

Actividad 2 Suponga que se intercepta el mensaje FO_NOS_HKWOJTMJZRRSUUDFFLDY_AAHJF_LVRKVGCY y que de él se sabe lo siguiente. a. Las tres primeras letras del mensaje oculto son "SIN" y las tres últimas son "E_ _" 𝑎 b. La matriz clave es de la forma ( 3 1

𝑏 𝑐 4 1) 3 1

c. El determinante de la matriz clave es 1. 2.2 A partir de esta información, responda y realice lo que se muestra a continuación, según corresponda. 2.2.1 ¿Es posible descifrar el mensaje con la información dada? Justifique su respuesta con las explicaciones y procesos necesarios. 2.2.2 Si la respuesta al ítem anterior fue afirmativa, descifre el mensaje oculto.

Respuestas:



Lo primero que debemos hacer es convertir la matriz en una matriz triangular, para esto debajo de la diagonal principal debe haber puros ceros

𝑎 (3 1

𝑏 4 3

𝑐 1) 𝐹2 1

3 (𝑎 1

4 𝑏 3

1 𝑐) 1

3 (0 1 3 (0 0

𝐹1

Intercambiamos las filas 2 y 1

𝑎

𝐹2 − (3) ∙ 𝐹1

4

1

4∙𝑎−3∙𝑏

𝑎+3∙𝑐

3

3

3

1

𝐹2

𝑎

Multiplicamos 𝐹1 ∙ 3 y la restamos a 𝐹2

−1

−1

) 𝐹1 ∙ ( 3 ) Multiplicamos 𝐹1 ∙ ( 3 ) y la restamos a 𝐹3

4

1

4∙𝑎−3∙𝑏

𝑎+3∙𝑐

3 5

3 2

3

3

)

1. 4 ∙ 𝑎 − 3 ∙ 𝑏 ≠ 0

3 (0 0

4

1

4∙𝑎−3∙𝑏

𝑎+3∙𝑐

3 5

3 2

3

3

)

−5

−5

𝐹3 − (4∙𝑎−3∙𝑏) ∙ 𝐹2

𝐹3 Multiplicamos 𝐹2 ∙ 4∙𝑎−3∙𝑏 y la restamos a 𝐹3

4∙𝑎−3∙𝑏 ≠ 0

3 (0 0

4

1

4∙𝑎−3∙𝑏

𝑎+3∙𝑐

3

0

) 3 𝑎−2∙𝑏+5∙𝑐 4∙𝑎−3∙𝑏

Una vez convertida nuestra matriz en una matriz triangular hacemos la multiplicación de la diagonal principal y tenemos:

𝑎 (3 1

𝑏 4 3

3 𝑐 0 1)=( 1 0

4

1

4∙𝑎−3∙𝑏

𝑎+3∙𝑐

3

0

) 3 𝑎−2∙𝑏+5∙𝑐

4∙𝑎−3∙𝑏

=3 ∙ (

3

𝑎−2∙𝑏+5∙𝑐

)∙(

4∙𝑎−3∙𝑏

)

4∙𝑎−3∙𝑏

= 𝑎 − 2𝑏 + 5𝑐 = 1 (determinante) Esta es la primera ecuación que obtenemos para resolver el sistema

Ahora seguimos trabajando con nuestra tabla alfanumérica módulo 29 ABCDEFGHI J 0123 456 7 89

K L M N Ñ O P Q R S 10 11 12 13 14 15 16 17 18 19

T U V WX Y Z - . 20 21 22 23 24 25 26 27 28 Empezamos por reemplazar las tres primeras y las tres últimas letras que nos da el ejercicio S

I N

E _ _

19 8 13

4 27 27

Y realizar la multiplicación de estas en forma de vectores por nuestra matriz clave: 𝑎 (3 1

𝑏 4 3

𝑐 19 1) ( 8 )= (19𝑎 + 1 13

8𝑏

+13𝑐 )=5

𝑎 (3 1

𝑏 4 3

4 𝑐 1) (27)= (4𝑎 + 1 27

27𝑏

+27𝑐 )= 6

Ya tenemos nuestro sistema de ecuaciones, el cual resolvimos mediante la herramienta www.wolframcloud.com 𝑎 − 2𝑏 + 5𝑐 = 1

19𝑎 + 8𝑏 + 13𝑐 = 5 4𝑎 + 27𝑏 + 27𝑐 = 6 La solución del sistema (módulo 29) es: 𝑎=4 𝑏=4 𝑐=1 Teniendo ya despejadas nuestras incógnitas procedemos a remplazarlas en nuestra matriz clave: 4 (3 1

4 1 4 1) 3 1

Para descodificar el mensaje hay que utilizar el mismo método anterior, el cifrado de Hill, pero utilizando como clave la matriz inversa A-1 (módulo 29) de la matriz A de codificación. Por lo tanto, se empieza de nuevo reemplazando las letras del mensaje cifrado por los números correspondientes en módulo 29 y luego se transforma el mensaje cifrado en la sucesión de triplas numéricas asociada FO_NOS_HKWOJTMJZRRSUUDFFLDY_AAHJF_LVRKVGCY 5 15 27 13 15 19 27 7 10 23 15 9 20 13 9 26 18 18 19 21 21 3 5 5 11 3 25 27 0 0 7 9 5 27 11 22 18 10 22 6 2 25 (5,15,27)(13,15,19)(27,7,10)(23,15,9)(20,12,9)(26,18,18)(19,21,21)(3,5,5)(11,3,25)(27,0,0) (7,9,5)(27,11,22)(18,10,22)(6,2,25) Y entonces se transforman mediante la transformación lineal con matriz inversa A-1, es decir, Y = A-1 ∙ X 4 4 A= (3 4 1 3

1 1) 1

Hallamos la matriz inversa de A (matriz clave), que es la necesaria para descodificar un mensaje cifrado Encontramos la matriz inversa por el método de eliminación de Gauss-Jordan usando las operaciones elementales. Para ello se aumenta la matriz dada con una matriz identidad y realizamos las operaciones de filas correspondientes (lo resolvimos con la herramienta https://matrixcalc.org/es/

4 4 (3 4 1 3

1 −1 1 −1 0 1) = (−2 3 −1) 1 5 −8 4

Ahora procedemos a realizar la transformación lineal de nuestro mensaje cifrado por medio de la multiplicación de la matriz inversa por las triplas formadas por las letras del mismo:

1 −1 0 5 5 (−2 3 −1) ∙ (15) = (−10 5 −8 4 27 25 1 −1 0 13 13 (−2 3 −1) ∙ (15) = (−26 5 −8 4 19 65

−10 19 𝑆 −15 0 45 −27) = ( 8 ) = ( 8 ) = ( 𝐼 ) 13 13 𝑁 −120 108 − −2 27 −45 0 𝐴) ) = ( ) = ( ) = ( 0 0 45 −19 𝑈 21 21 −120 76

1 −1 0 27 27 (−2 3 −1) ∙ ( 7 ) = (−54 5 −8 4 10 135

−7 0 20 20 𝑇 21 −10) = (−43) = (15) = (𝑂 ) −56 40 119 3 𝐷

1 −1 0 23 23 (−2 3 −1) ∙ (15) = (−46 5 −8 4 9 115

𝐼 8 8 −15 0 45 −9) = (−10) = (19) = ( 𝑆 ) 31 2 𝐶 −120 36

1 −1 0 20 20 (−2 3 −1) ∙ (12) = (−40 5 −8 4 9 100

−12 0 8 8 𝐼 36 −9) = (−13) = (16) = (𝑃) −96 36 40 11 𝐿

1 −1 0 26 26 (−2 3 −1) ∙ (18) = (−52 5 −8 4 18 130

−18 0 8 8 𝐼 54 −18) = (−16) = (13) = (𝑁 ) −144 72 58 20 𝐴 − −21 0 −2 27 63 −21) = ( 4 ) = ( 4 ) = ( 𝐸 ) 𝐿 −168 84 11 11

1 −1 0 19 19 (−2 3 −1) ∙ (21) = (−38 5 −8 4 21 95

− 1 −1 0 3 −2 27 3 −5 0 (−2 3 −1) ∙ (5) = (−6 15 −5) = ( 4 ) = ( 4 ) = ( 𝐸 ) 𝑋 5 −8 4 5 −5 24 15 −40 20

7 1 −1 0 7 (−2 3 −1) ∙ (9) = (−14 5 −8 4 5 35

𝐼 −3 0 8 8 9 −25) = (−38) = (20) = ( 𝑇 ) −24 100 131 15 𝑂 − 0 0 27 27 0 0) = (−54) = ( 4 ) = ( 𝐸 ) 𝑆 0 0 135 19 − −9 0 −2 27 27 −5) = ( 8 ) = ( 8 ) = ( 𝐼 ) 𝑀 −72 20 −17 12

1 −1 0 27 27 (−2 3 −1) ∙ (11) = (−54 5 −8 4 22 135

𝑃 −11 0 16 16 33 −22) = (−43) = (15) = (𝑂) −88 88 135 19 𝑆

1 −1 0 18 18 (−2 3 −1) ∙ (10) = (−36 5 −8 4 22 90

−10 0 8 8 𝐼 ) = ( ) = ( ) = ( 30 −22 −28 1 𝐵) −80 88 98 11 𝐿

1 −1 0 6 6 (−2 3 −1) ∙ ( 2 ) = (−12 5 −8 4 25 30

−2 0 4 4 𝐸 6 −25) = (−31) = (27) = (−) −16 100 114 27 −

1 −1 0 11 11 (−2 3 −1) ∙ ( 3 ) = (−22 5 −8 4 25 55 1 −1 0 27 27 (−2 3 −1) ∙ ( 0 ) = (−54 5 −8 4 0 135

Tenemos que el mensaje oculto es: SIN_AUTODISCIPLINA _EL _EXITO _ES _IMPOSIBLE_ _

Desde el inicio del lenguaje escrito, la humanidad ha buscado comunicarse de manera secreta. Y el objetivo de la criptografía es el estudio de las técnicas para proteger las comunicaciones sensibles por medio de encriptación de datos y su posterior descifrado.

Síntesis de las ideas obtenidas en el foro: sistema de Hill para encriptar y desencriptar mensajes

El cifrado consiste en transformar los datos en una forma ilegible, de manera que aunque se puedan ver los datos cifrados, no se pueda entender la información oculta. El descifrado es lo contrario a este proceso; es la transformación de los datos cifrados de nuevo en una forma comprensible.

- Cifrado: El procedimiento que generará un mensaje ininteligible para el receptor. También se usa para recrear el mensaje original, según el mecanismo de cifrado que se utilice.

- Texto Plano: El mensaje o información que se va a codificar.

- Texto cifrado: El mensaje o información que se obtiene después que se ha utilizado el Cifrado.

El sistema de Hill es un criptográfico de reemplazo 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.

También permite el descifrado de un mensaje oculto utilizando métodos de álgebra lineal que en un “ataque con texto claro conocido” puede romperse el código y ser descubierta 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.

CONCLUSIONES Por medio de la realización de este trabajo nos dimos cuenta que el álgebra lineal realmente tiene aplicaciones muy prácticas para la vida, nos llevó a aplicar los conceptos y procesos aprendidos durante el desarrollo del módulo mediante ejercicios prácticos y provechosos, aunque no fue nada fácil llegar a la solución de los problemas, sobretodo en la segunda actividad, tuvimos la oportunidad de pensar, de razonar, de investigar, consultar hasta llegar a la solución correcta. Concluimos que para encriptar un mensaje por medio del sistema de Hill hay que tener claros los conceptos de matrices y sus operaciones, es necesario contar con una matriz cuadrada que será la clave para encriptar el mensaje con éxito realizando la transformación lineal del mensaje al nuevo mensaje secreto. Se debe realizar la transcripción de las letras del mensaje a cifrar a los números correspondientes según el módulo que el problema plantee, agrupar los números en duplas o triplas dependiendo de la forma de nuestra matriz clave y proceder a su transformación lineal por medio de la multiplicación de cada grupo de números convertidos ahora en un vector por la matriz clave y de acuerdo al sistema modular que se esté trabajando. Para descifrar un mensaje es imprescindible que la matriz clave sea inversible, se debe hallar el determinante de la matriz que debe ser diferente de cero y la inversa de la matriz, que ahora será la matriz clave por la cual se deben multiplicar los vectores del mensaje cifrado y encontrar así el mensaje original. Teniendo la matriz clave, el determinante de la misma y una pista con las tres primeras y las tres últimas letras del mensaje cifrado, se puede descifrar un mensaje incluso si esta matriz contiene elementos alfanuméricos o variables en ella, esto se hace triangulando la matriz clave para poder hallar la primera ecuación del sistema de ecuaciones necesario producto de la multiplicación de la diagonal principal. Las otras dos ecuaciones del sistema se hallan del producto de las variables de la matriz clave por los vectores formados por el correspondiente numérico de las tres primeras y las tres últimas letras del mensaje cifrado. Una vez halladas las ecuaciones del sistema se igualan a la primera y antepenúltima letra del mensaje cifrado respectivamente y se resuelve sistema de ecuaciones para despejar las variables. Lo que nos queda de ahí en adelante es hallar la inversa de la matriz clave y proceder a descifrar el mensaje por medio de la transformación lineal.

BIBLIOGRAFÍA

Recursos de aprendizaje: La criptografía y el álgebra lineal © Nibcode Solutions. Recuperado de: http://www.nibcode.com/es/blog/7/cryptography-andlinear-algebra (Enlaces a un sitio externo.)Enlaces a un sitio externo. Criptosistema Hill: Textos científicos.com Dom, 26/06/2005 – 21:18. Recuperado de: www.textoscientificos.com/criptografia/hill (Enlaces a un sitio externo.)Enlaces a un sitio externo. Criptografía con matrices, el cifrado de Hill: Autor: Raúl Ibáñez, profesor del Departamento de Matemáticas de la UPV/EHU y colaborador de la Cátedra de Cultura Científica. Recuperado de: https://culturacientifica.com/2017/01/11/criptografia-matrices-cifrado-hill http://www.aldaba.com/cursos/Criptografia%20y%20Cifrado%20-%20VP.pdf

DETERMINANTES Hugo Eduardo Ramírez, Cartilla semana 3, módulo álgebra lineal, Politécnico gran Colombiano:

Encontrar inversas y determinantes https://es.khanacademy.org/math/linear-algebra/matrix-transformations/inverse-ofmatrices/v/linear-algebra-example-of-finding-matrix-inverse: