• Author / Uploaded
• jhosep

Citation preview

Trabajo colaborativo Algebra lineal

Facultad de ingeniería y ciencias básicas

Integrantes Michael Andrey López cortes

cód. 1821022796

Luisa Fernanda Calle Gómez

cód. 1821025324

14 abril 2019.

Introducción Una de las aplicaciones del algebra es la criptografía, parte de la criptografía (es el estudio de lo oculto), que trata del diseño e implementación de sistemas secretos para cifrar mensajes. Existen diversas técnicas para cifrar y descifrar mensajes cuya complejidad depende de las herramientas matemáticas que se empleen en el diseño de los algoritmos de cifrado. Un sistema clásico es el sistema de Hill o cifrado en bloques que fue diseñado por el matemático Lister Hill en 1929 basado en ideas de algebra lineal, en particular, en algebra de matrices.

Objetivo general. Mediante el sistema de Lister Hill encriptar y desencriptar mensajes. Objetivos específicos. Consultar el sistema de Lister Hill. Describir el proceso de cifrado. Desencriptar mensajes mediante la matriz clave.

Desarrollo trabajo colaborativo Actividad 1. Consultar el sistema de Hill para encriptar y desencriptar mensajes. Luego, describa el proceso (paso a paso) para cifrar la palabra DEDICACION empleando la matriz 1 7 ) y la asignación numérica que aparece en el siguiente recuadro (en él, símbolo 0 1

clave(

“–“representa el espacio entre las palabras). A B C D E F GHI J K L M N Ñ O P Q R S T U V W X Y Z _

.

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8

De acorde lo citado en la consulta https://en.wikipedia.org/wiki/Lester_S._Hill (Enlaces a un sitio externo.)https://culturacientifica.com/2017/01/11/criptografia-matricescifrado-hill/, el sistema Hill es un sistema criptográfico de sustitución poli alfabético, para ocultar mensajes de manera de encriptación y des encriptación por medio de los siguientes pasos.

Encriptación: Primer paso: realizar la tabla alfanumérica. Segundo paso: diagnosticar matriz clave. Tercer paso: realizar sustitución del mensaje a enviar para crear matriz mensaje.

Cuarto paso: de acuerdo con el orden de la transformación lineal, agrupar en grupos (1,2,3, 4 ,, , n). Quinto paso: multiplicar la matriz clave por los grupos y así generar la matriz mensaje. Sexto paso: ordenar la matriz resultante y sustituir en la tabla. Séptimo paso: dictaminar mensaje encriptado el cual sería el que se envía, con la matriz clave Des encriptación: Octavo paso: se consulta la tabla alfanumérica con la cual fue encriptado el mensaje. Noveno paso: se realiza la sustitución del mensaje interceptado de acuerdo a la tabla alfanumérica. Y así sacar matriz mensaje. Decimo paso: de acuerdo con la matriz clave diagnosticada se le saca la inversa ( 𝐴−1). Onceavo paso: se multiplica la matriz mensaje por la matriz inversa de acuerdo con la agrupación correspondiente. Y se realiza modulación de acuerdo con la tabla. Doceavo paso: dada la matriz mensaje se ordena y luego se realiza sustitución de acorde a la tabla para ver que dice el mensaje el mensaje enviado por medio de encriptación.

Procediendo con la solución el cifrado de la palabra DEDICACION, omitimos los dos primeros pasos puesto que la actividad ya nos genera la tabla polialfabetica como la matriz clave y con ello pasamos al.

Tercer paso: sustitución. D

E

D

I

C

A

C

I

O

N

3

4

3

8

2

0

2

8

15

13

Matriz mensaje. ( 3 4 3 8 2 0 2 8 15 13 ) Cuarto paso: como la matriz que nos dan es de 2x2 entonces realizaremos agrupación por 2 así: (3 4), (3 8), (2,0), (2 8), (15, 13) Quinto paso: multiplicación matriz clave por matriz mensaje. (

1𝑥3 + 7𝑥4 1 7 3 31 𝑚𝑜𝑑 29 2 )| | = [ ]=‖ ‖= ( ) 0𝑥3 + 1𝑥4 0 1 4 4 4 𝑚𝑜𝑑 29

(

1𝑥3 + 7𝑥8 1 7 3 1 59 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0𝑥3 + 1𝑥8 0 1 8 8 8 𝑚𝑜𝑑 29

(

1𝑥2 + 7𝑥0 1 7 2 2 2 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0𝑥2 + 1𝑥0 0 1 0 0 0 𝑚𝑜𝑑 29

(

1𝑥2 + 7𝑥8 1 7 2 0 58 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0𝑥2 + 1𝑥8 0 1 8 8 8 𝑚𝑜𝑑 29

(

1 7 15 1𝑥15 + 7𝑥13 19 106 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0 1 13 13 0𝑥15 + 1𝑥13 13 𝑚𝑜𝑑 29

Sexto paso: ordenar y sustituir nuevamente. ( 2 4 1 8 2 0 0 8 19 13 )

C

E

B

I

C

A

A

I

S

N

2

4

1

8

2

0

0

8

19

13

Séptimo paso: dictaminando el mensaje encriptado y el cual se enviara queda así: C E B I C A A I S N. Desencriptación En este caso nos saltaremos los pasos 8 y 9, ya que seguiremos trabajando con la misma tabla polialfabetica y la de sustitución la encontramos en el sexto paso y continuando. Decimo paso: sacar la matriz inversa A-1. Recordemos que para saber si una matriz tiene inversa debemos saber que su determinante sea ≠ 0. Consultando determinante mediante ley de sarrus. (

1 7 ) = (1x1 – 7x0) = 1 DET. 0 1

Ya conociendo que el DET es 1 y al ser ≠ 0; concluimos que si tiene inversa, la cual realizaremos mediante sarrus que en una de sus propiedades nos dice que si A es invertible entonces. A-1 =

ADJ (A) DET (A)

1. Calcular matriz de cofactores. 2. Calcular matriz transpuesta de cofactores la cual es = a la Adjunta (Adj). 3. Calcular determinante matriz.

Calculando matriz de cofactores. Cij (

i+j (-1)

(Mij)

1 7 ) 0 1

C11 = 1 C12 = 0 C21 = ─7 C22 = 1 1 =| −7 Adj = [

0 | = matriz cofactores 1

1 −7 ] = recordar que la matriz adj. = transpuesta de cofactores 0 1

Y como ya sabemos que el DET = 1, entonces.

1 −7

1 −7 A-1 = 0 1 1 = A-1 = | | matriz inversa. 0 1

Onceavo paso: multiplicación de la matriz inversa por matriz mensaje agrupada y su respectiva modulación. (

1𝑥2 + (−7𝑥4) 1 −7 2 −26 𝑚𝑜𝑑 29 3 )| | = [ ]=‖ ‖= ( ) 0 1 4 4 4 𝑚𝑜𝑑 29 0𝑥2 + 1𝑥4

(

1𝑥1 + (−7𝑥8) 1 −7 1 3 −55 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0 1 8 8 8 𝑚𝑜𝑑 29 0𝑥1 + 1𝑥8

(

1𝑥2 + −7𝑥0 1 −7 2 2 2 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0𝑥2 + 1𝑥0 0 1 0 0 0 𝑚𝑜𝑑 29

(

1𝑥0 + −7𝑥8 1 −7 0 2 −56 𝑚𝑜𝑑 29 )| | = [ ]=‖ ‖= ( ) 0𝑥0 + 1𝑥8 0 1 8 8 8 𝑚𝑜𝑑 29

(

1𝑥19 + −7𝑥13 1 −7 19 −72 𝑚𝑜𝑑 29 15 )| | = [ ]=‖ ‖= ( ) 0𝑥19 + 1𝑥13 0 1 13 13 𝑚𝑜𝑑 29 13

Doceavo paso: ordenando y sustituyendo. ( 3 4 3 8 2 0 2 8 15 13 ) D

E

D

I

C

A

C

I

O

N

3

4

3

8

2

0

2

8

15

13

Y así concluimos que el mensaje desencriptado es: DEDICACION

Actividad 2. Suponga que se intercepta el mensaje NQÑTIJIQKSSEWNHRÑTYPIWADPHYEVNUHZEMQTEKHJQLLP Junto con 9 5 2 este mensaje encriptado, solo se logró obtener la matriz clave (5 4 3) 1 1 1

Desarrollo Octavo paso: se establece la tabla polialfabetica mediante la cual fue encriptado el mensaje.

Noveno paso: convertir las letras a números con la información que tenemos del valor de cada letra y la matriz clave Tabla.

N=13

S=19

Y=25

E=4

T=20

Q=17

S=19

P=16

V=22

E=4

Ñ=14

E=4

I=8

N=13

K=10

T=20

W=23

W=23

U=21

H=7

I=8

N=13

A=0

H=7

J=9

J=9

H=7

D=3

Z=26

Q=17

I=8

R=18

P=16

E=4

L=11

Q=17

Ñ=14

H=7

M=12

L=11

K=10

T=20

Y=25

Q=17

P=16

Decimo paso: Sacamos la matriz inversa de la matriz clave 9 5 (5 4 1 1

2 3) 𝐴−1 1

Para sacar la matriz inversa realizo los siguientes pasos mediante el método gauss Jordán. •

Escribo la matriz aumentada

2 1 3) ‖0 1 0

9 5 (5 4 1 1

•

0 0 1 0‖ 0 1

Encuentro el pivote en la columna # 1 y hago intercambio de la fila # 3 con la fila # 1

1 1 (5 4 9 5

•

1 0 3) ‖0 2 1

0 1 1 0‖ 0 0

Vuelvo cero la columna # 1 con las siguientes operaciones Multiplico por -5 la fila 2 y por -9 la fila 3 y así obtengo el 0 en ambas filas

1 1 1 0 0 (0 −1 −2) ‖0 1 0 −4 −7 1 0

1 −5‖ −9

•

Encuentro el pivote en la columna # 2 fila # 2 invirtiendo el signo de toda la fila

1 0 (0 1 0 0 •

−1 0 2 ) ‖0 1 1

1 −4 −1 5 ‖ −4 11

Elimino la columna # 3

1 0 (0 1 0 0

•

1 −4 −1 5 ‖ −4 11

Encuentro el pivote en la columna # 3 en la fila # 3

1 0 (0 1 0 0

•

−1 0 2 ) ‖0 1 1

0 1 0) ‖−2 1 1

−3 7 7 −17‖ −4 11

El resultado que nos queda al lado derecho es la matriz inversa

1 −3 7 ‖−2 7 −17‖ 1 −4 11

Onceavo paso: Para empezar a descifrar el mensaje debemos multiplicar matriz inversa por la matriz mensaje de acuerdo con su respectiva modulación y los resultados de esta multiplicación nos va a dar el mensaje queremos descifrar

1 −3 7 13 1 ∗ 13 (−2 7 −17) (17) = (−2 ∗ 13 1 −4 11 14 1 ∗ 13

−3 ∗ 17 7 ∗ 17 −4 ∗ 17

7 ∗ 14 60mod29 −17 ∗ 14) (−145mod29) 11 ∗ 14 99mod29

2 C =(0)A 12 M

1 −3 7 20 1 ∗ 20 (−2 7 −17) ( 8 ) = (−2 ∗ 20 1 −4 11 9 1 ∗ 20

−3 ∗ 8 7∗8 −4 ∗ 8

7∗9 59mod29 −17 ∗ 9) (−137mod29) 11 ∗ 9 87mod29

1 −3 7 8 1 ∗ 8 −3 ∗ 17 (−2 7 −17) (17) = (−2 ∗ 8 7 ∗ 17 1 −4 11 10 1 ∗ 8 −4 ∗ 17

7 ∗ 10 27 −17 ∗ 10) (−67mod29) 11 ∗ 10 50mod29

1 B = (8 ) I 0 A

27 − = (20) T 21 U

1 −3 7 19 1 ∗ 19 (−2 7 −17) (19) = (−2 ∗ 19 1 −4 11 4 1 ∗ 19 19 S = (27) − 16 P

−3 ∗ 19 7 ∗ 19 −4 ∗ 19

7∗4 −10mod29 ) −17 ∗ 4) ( 27 11 ∗ 4 −13mod29

1 −3 7 23 1 ∗ 23 (−2 7 −17) (13) = (−2 ∗ 23 1 −4 11 7 1 ∗ 23

−3 ∗ 13 7 ∗ 13 −4 ∗ 13

7∗7 33mod29 −17 ∗ 7) (−74mod29) 11 ∗ 7 48mod29

−3 ∗ 14 7 ∗ 14 −4 ∗ 14

7 ∗ 20 116mod29 −17 ∗ 20) (−278mod29) 11 ∗ 20 182mod29

−3 ∗ 16 7 ∗ 16 −4 ∗ 16

7∗8 33mod29 −17 ∗ 8) (−74mod29) 11 ∗ 8 49mod29

4 E = (13) N 19 S

1 −3 7 18 1 ∗ 18 (−2 7 −17) (14) = (−2 ∗ 18 1 −4 11 20 1 ∗ 18 O A = (12) M 8 I

1 −3 7 25 1 ∗ 25 (−2 7 −17) (16) = (−2 ∗ 25 1 −4 11 8 1 ∗ 25 4 E = (13) N 20 T

1 −3 7 23 1 ∗ 23 (−2 7 −17) ( 0 ) = (−2 ∗ 23 1 −4 11 3 1 ∗ 23 15 O = (19) S 27 −

−3 ∗ 0 7∗0 −4 ∗ 0

7∗3 44mod29 −17 ∗ 3) (−97mod29) 11 ∗ 3 56mod29

1 −3 7 16 1 ∗ 16 (−2 7 −17) ( 7 ) = (−2 ∗ 16 1 −4 11 25 1 ∗ 16

−3 ∗ 7 7∗7 −4 ∗ 7

7 ∗ 25 170mod29 −17 ∗ 25) (−408mod29) 11 ∗ 25 263mod29

25 Y = (27) − 2 C

4 1 −3 7 1 ∗ 4 −3 ∗ 22 (−2 7 −17) (22) = (−2 ∗ 4 7 ∗ 22 1 −4 11 13 1 ∗ 4 −4 ∗ 22

7 ∗ 13 29mod29 −17 ∗ 13) (−75mod29) 11 ∗ 13 59mod29

0 A = (12) M 1 B

1 −3 7 21 1 ∗ 21 (−2 7 −17) ( 7 ) = (−2 ∗ 21 1 −4 11 26 1 ∗ 21

−3 ∗ 7 7∗7 −4 ∗ 7

7 ∗ 26 182mod29 −17 ∗ 26) (−435mod29) 11 ∗ 26 279mod29

1 −3 7 4 1 ∗ 4 −3 ∗ 12 (−2 7 −17) (12) = (−2 ∗ 4 7 ∗ 12 1 −4 11 17 1 ∗ 4 −4 ∗ 12

7 ∗ 17 87mod29 −17 ∗ 17) (−213mod29) 11 ∗ 17 143mod29

8 I = ( 0 )A 18 R

0 A = (19) S 27 − 1 −3 (−2 7 1 −4

7 20 1 ∗ 20 ) ( ) = ( −17 4 −2 ∗ 20 11 10 1 ∗ 20

−3 ∗ 4 7 ∗ 10 20 T 78mod29 ) ( ) = ( 7 ∗ 4 −17 ∗ 10 −182mod29 21) U −4 ∗ 4 11 ∗ 10 27 − 114mod29

7 1 −3 7 1 ∗ 7 −3 ∗ 9 7 ∗ 17 99mod29 (−2 7 −17) ( 9 ) = (−2 ∗ 7 7 ∗ 9 −17 ∗ 17) (−240mod29) 1 −4 11 17 1 ∗ 7 −4 ∗ 9 11 ∗ 17 158mod29 12 M = (21) U 18 N

1 −3 7 11 1 ∗ 11 (−2 7 −17) (11) = (−2 ∗ 11 1 −4 11 16 1 ∗ 11

−3 ∗ 11 7 ∗ 11 −4 ∗ 11

7 ∗ 16 90mod29 −17 ∗ 16) (−217mod29) 11 ∗ 16 143mod29

3 D = (15) O 27 −

Doceavo paso: ya que se realizó en este caso directamente la sustitución damos por concluido que el mensaje interceptado significa lo siguiente. CAMBIA TUS PENSAMIENTOS Y CAMBIARAS TU MUNDO

Conclusiones El sistema de Hill nos permite descifrar mensajes de una manera efectiva mediante una secuencia de pasos ordenados. Mientras se desarrollen a cabalidad y forma ordenada los respectivos pasos del método Hill estos no harán más fácil la vida en cuestión de criptografía. Nos damos cuenta que la matriz clave es una parte esencial en el proceso de cifrado ya que si no se aplica la correcta con su respectiva inversa será muy difícil concluir un buen desarrollo.

Bibliografía

https://en.wikipedia.org/wiki/Lester_S._Hill (Enlaces a un sitio externo.)https://culturacientifica.com/2017/01/11/criptografia-matrices-cifrado-hill/.