391192836-TRABAJO-COLABORATIVO-ALGEBRA-LINEAL-POLI

Vista previa del material en texto

Facultad de Ingeniería y Ciencias Básicas 
Departamento de Ciencias Básicas 
Trabajo 
Colaborativo 
–
 
Algebra Lineal
 
 
Facultad de Ingeniería y Ciencias Básicas 
Departamento de Ciencias Básicas 
Trabajo 
Colaborativo 
–
 
Algebra Lineal
 
 
Universidad Nacional Autónoma de México
Facultad de Estudios Superiores
Plantel Aragón
INGENIERIA INDUSTRIAL
CLASE: algebra lineal
Trabajo 
PRACTICA 
GRUPO:8105
NOMBRE DEL PROFESOR: ALBERTO HIGUERA GARCIA
NOMBRE DEL ALUMNO: CORTES HERNANDEZ RICARDO
 
FECHA DE ENTREGA: SEPTIEMBRE DEL 2021
SITUACIÓN PROBLEMA 
 
 
 Actividad 1. 
 
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 clave: 
	1 	-4 
	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). 
 
	A
	B
	C
	D
	E
	F
	G
	H
	I
	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
	10
	11
	12
	13
	14
	15
	16
	17
	18
	19
	20
	21
	22
	23
	24
	25
	26
	27
	28
 
Actividad 2. 
 
1. Suponga 	que 	se 	intercepta 	el 	mensaje HTQÑULUYXHBZPHXOTJHTQBADWIGPZH, junto con este mensaje encriptado, solo se logró obtener la matriz clave: 
 
4 2 	1 
5 3 	2 
	2 	1 	1 
 
La misión del grupo es: 
 
1. Descifrar tal mensaje. 
2. Detallar organizadamente todos los procedimientos que se realizaron para descifrar el mensaje. 
 
 
 
 
 
 
 
SISTEMA DE HILL PARA ENCRIPTAR 
Y DESENCRIPTAR MENSAJES 
 
Este sistema está basado en el álgebra lineal y ha sido importante en la historia de la criptografía. Fue Inventado por Lester S. Hill en 1929, y fue el primer sistema criptográfico polialfabético que era práctico para trabajar con más de tres símbolos simultáneamente. 
Este sistema es polialfabético pues puede darse que un mismo carácter en un mensaje a enviar se encripte en 2 caracteres distintos en el mensaje encriptado. 
Suponiendo que trabajamos con un alfabeto de 26 caracteres. 
Las letras se numeran en orden alfabético de forma tal que 
A=0, B=1,..., Z=25 
	A 
	B 
	C 
	D 
	E 
	F 
	G 
	H 
	I 
	J 
	K 
	L 
	M 
	0 
	1 
	2 
	3 
	4 
	5 
	6 
	7 
	8 
	9 
	10 
	11 
	12 
	N 
	O 
	P 
	Q 
	R 
	S 
	T 
	U 
	V 
	W 
	X 
	Y 
	Z 
	13 
	14 
	15 
	16 
	17 
	18 
	19 
	20 
	21 
	22 
	23 
	24 
	25 
 
Se elige un entero “X” que determina bloques de “X” elementos que son tratados como un vector de d dimensiones. Se elige de forma aleatoria una matriz de A × A elementos los cuales serán la clave a utilizar. Los elementos de la matriz de A × A serán enteros entre 0 y 26, además la matriz clave debe dejar ser inversible. 
Para la encriptación, el texto es dividido en bloques de “X” elementos los cuales se multiplican por la matriz A × A. Todas las operaciones aritméticas se realizan en la forma módulo que sea necesario ya que se le pueden agregar otros caracteres, es decir que 26=0, 27=1, 28=2 etc. 
Dado un mensaje a encriptar debemos tomar bloques del mensaje de "A" caracteres y aplicar: 
MATRIZ CLAVE × Pi = C, donde C es el código cifrado para el mensaje Pi 
 
Ejemplo: 
Si tomamos esta matriz como matriz clave. 
 
Para encriptar el mensaje "CODIGO" debemos encriptar los seis caracteres de "CODIGO" en bloques de 3 caracteres cada uno, el primer bloque 
 
 
 
El primer bloque "COD" se codificara como "WLP" 
 
El segundo bloque "IGO" se codificara como "GSE" Luego 'CODIGO' encriptado equivale a 'WLPGSE'. 
Observar que las dos "O" se codificaran de forma diferente. 
Para desencriptar el método es idéntico al anterior pero usando la matriz inversa de la usada para encriptar. 
 
CÁLCULO DE LA MATRIZ INVERSA 
 
Antes que nada debemos verificar que la matriz elegida sea invertible en módulo 26. Hay una forma relativamente sencilla de averiguar esto a través del cálculo del determinante. Si el determinante de la matriz es 0 o tiene factores comunes con el módulo (en el caso de 26 los factores son 2 y 13), entonces la matriz no puede utilizarse. Al ser 2 uno de los factores de 26 muchas matrices no podrán utilizarse (no servirán todas en las que su determinante sea 0, un múltiplo de 2 o un múltiplo de 13) 
 
Para ver si es invertible calculo el determinante de A 
 
5 (23 · 13 – 3 ·11) – 17 (9 · 13 – 3 · 2) + 20 (9 · 11 – 23 · 2) = 
1215 – 1734 + 1060 = 503 
503 = 9 mod 26 
La matriz A es invertible en módulo 26 ya que 26 y 9 son coprimos. Para hallar la inversa de la matriz módulo 26, utilizamos la formula 
 
Donde CT es la matriz de cofactores de A transpuesta. Hay que tener en cuenta que debe realizarse en módulo 26 dependiendo el número de caracteres que se asignen, por lo tanto para el ejemplo la inversa de 9 (mod 26) es 3 (mod 26) ya que 9 (mod 26) · 3 (mod 26) = 27 mod 26 = 1 (mod 26), por lo tanto 3 es la inversa multiplicativa de 9 en módulo 26. Para calcular C hay que calcular los cofactores de A 
 
 
 
 
 
 
Ahora aplicamos la fórmula de la inversa 
 
Esta última es la matriz que utilizamos para desencriptar. 
 
 
 
 
 
 
ACTIVIDAD 1º 
 
PASO 1º: Con la matriz clave y la tabla guía se realiza la asignación del mensaje “DEDICACION” a cada uno de los números correspondientes. 
 
TABLA GUÌA 
 
	A
	B
	C
	D
	E
	F
	G
	H
	I
	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
	10
	11
	12
	13
	14
	15
	16
	17
	18
	19
	20
	21
	22
	23
	24
	25
	26
	27
	28
 
MATRIZ CLAVE 
 
	1 	-4 
	0 	1 
 
	D 
	E 
	D 
	I 
	C 
	A 
	C 
	I 
	O 
	N 
	3 
	4 
	3 
	8 
	2 
	0 
	2 
	8 
	15 
	13 
 
PASO 2º: En este paso realizaremos agrupaciones de dos componentes ya que la matriz calve es de tamaño 2 x 2 así: 
 
 
[3,4] 
[3,8] 
[2,0] 
[2,8] 
[15,13] 
 
 
 
 
PASO 3º: Luego multiplicamos la matriz clave por cada uno de los grupos de esta forma. 
 
 
 
 PASO 4º: Ya que son 28 números + el "0" en total 
29, los resultados se deben reducir a módulo 29. 
 
 
 
(1	−4) . (3) = (−13) módulo 29 (16) (𝑃) 
0	1	4	 4	4	𝐸
 
(1	−4) . (3) = (−29) módulo 29 (0) (𝐴) 
0	1	8	 8	8	𝐼
 
 (1	−4) . (2) = (2) módulo 29 (2) (𝐶) 
0	1	0	 0	0	𝐴
 
10	−14 . (28) = (− 308 ) módulo 29 (288 ) (𝐼.) 
(	)
 
(1	−4) . (15) = (−37) módulo 29 (21) (𝑈) 
0	1	13	 13	13	𝑁
 
 
 PASO 5º: Luego, convertimos los números en letras para cifrar el mensaje, volviendo a ser la asignación con las letras del abecedario, para así obtener mensaje “PEAICA.IUN”. 
 
	P 
	E 
	A 
	I 
	C 
	A 
	. 
	I 
	U 
	N 
	16 
	4 
	0 
	8 
	2 
	0 
	28 
	8 
	21 
	13 
 
 
 
ACTIVIDAD 2º 
 
PASO 1º: Primero se debe hallar el determinante de la matriz clave que tiene que ser diferente de cero (0) y calcular el módulo de ese determinante. 
 
	 	MATRIZ CLAVE 	 
 	 	 	 	 
	4 
	2 
	1 
	5 
	3 
	2 
	2 
	1 
	1 
K= 
 
 
 
 
	DET(K)= 	1 	MÒDULO 29 	= 	1 
 
 
PASO 2º: Segundo es calcular la matriz inversa de la matriz clave. 
 
	1 
	-1 
	1 
	-1 
	2 
	-3 
	-1 
	0 
	2 
K-1= 
 
 
PASO 3º: Tercero convertir la matriz inversa a módulo 29 ya que según los caracteres son 29 a trabajar. 
 
	1 
	28 
	1 
	28 
	2 
	26 
	28 
	0 
	2 
MOD 29= 
 	 	 
 	 	 
 
PASO 4º: 
 
1) En este paso lo que realizamos es de la matriz inversa resultante del mod 29; agruparemos del mensaje inicial grupos de 3 ya que la matriz es de 3 x 3. 
 
	H
	T
	Q
	Ñ
	U
	L
	U
	Y
	X
	H
	B
	Z
	P
	H
	X
	O
	T
	J
	H
	T
	Q
	B
	A
	D
	W
	I
	G
	P
	Z
	H
	7
	20
	17
	14
	21
	11
	21
	25
	24
	7
	1
	26
	16
	7
	24
	15
	20
	9
	7
	20
	17
	1
	0
	3
	23
	8
	6
	16
	26
	7
X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 
 
2) Multiplicamos esa matriz mod 29 por cada grupo de 3 hasta completar todo el mensaje. 
 
3) Luego realizamos la conversión de cada uno de los resultados a mod 29. 
 
4) Finalmente reemplazamos los resultados por las letras correspondientes para encontrar el mensaje. 
 
	A
	B
	C
	D
	E
	F
	G
	H
	I
	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
	10
	11
	12
	13
	14
	15
	16
	17
	18
	19
	20
	21
	22
	23
	24
	25
	26
	27
	28