• Author / Uploaded
• Jean Pierre

Citation preview

APLICACIÓN DEL ÁLGEBRA LINEAL EN LA CODIFICACIÓN DE MENSAJES MEDIANTE EL MÉTODO DE HILL Saray Consuegra, Yuleisy Rivera, Jean Pierre Vera

Objetivos: Demostrar la importancia del Álgebra Lineal en la vida real Mostrar la utilidad del método de Hill en la codificación y decodificación de mensajes

REPORTE TÉCNICO N° ESPOL-FCNM-AL-2019-IIS-PAR 9

DE LA FACULTAD DE CIENCIAS NATURALES Y MATEMÁTICAS DOCENTE: MARGARITA MARTÍNEZ TÉCNICO DOCENTE: ISAAC MANCERO Enero 2020

Índice Índice ...................................................................................................................................................... 2 Introducción ............................................................................................................................................ 3 Marco teórico .......................................................................................................................................... 4 Ejercicio I ................................................................................................................................................ 5 Ejercicio II .............................................................................................................................................. 5 1 .............................................................................................................................................................. 5 2. Si modificamos el espacio 𝒁𝒌 para incluir caracteres mayúsculos, minúsculos, diez dígitos y el espacio, ¿Cuántos modos de construir H existen? De estas, ¿qué porcentaje es invertible? .................. 6 3. ............................................................................................................................................................. 8 4. ............................................................................................................................................................. 9 5. ........................................................................................................................................................... 13 6. Diseñe un diagrama de flujo de trabajo para un codificador ............................................................ 14 7. Basado en la información dada, y en información adicional investigada. ¿Cuán factible es para usted construir o programar un codificador de Hill? ............................................................................ 16 Conclusiones ......................................................................................................................................... 16 Recomendaciones ................................................................................................................................. 16 Bibliografía .............................................................................................. Error! Bookmark not defined.

Página 2 de 17

Introducción El diccionario define a la criptografía como “el arte de escribir con clave secreta o de modo enigmático”, pero lo cierto es que abarca todo el proceso de técnicas, que, en principio tratan sobre la protección o ocultamiento de información a personas no autorizadas. La criptografía tiene aplicaciones en ámbitos militares e informáticos, aunque ha visto un desarrollo en empresas y organizaciones dedicadas a actividades comerciales. Actualmente, existen un sinnúmero de maneras de encriptar la información, algunas mejores que otras, pero estas suponen un grado de complejidad mayor y requieren del dominio de campos de estudios superiores como Álgebra Modular o Matemáticas Discretas. Entre todos estos sistemas, nos encontramos con uno tradicional y que es práctico para la criptografía, refiriéndonos al cifrado de Hill. El cifrado de Hill está íntegramente basado en el álgebra lineal y ha sido importante en la historia de la criptografía. Fue inventado 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 como (Matemoción, 2017) explica. Este 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 y es conocido como el método más sencillo y famoso de criptografía clásica. A lo largo de este trabajo, se utilizará esta herramienta para el descifrado de un mensaje, poniendo en evidencia la importancia que tiene el álgebra lineal para la criptografía junto a las ventajas y desventajas de este método en específico. Durante el trabajo se discutirá las bases del método y las operaciones relacionadas al álgebra lineal elemental que son necesarias para el descifrado de un mensaje e ilustrándolo mediante un mensaje simple; además de las bondades y debilidades que usar este sistema de cifrado implica.

Página 3 de 17

Marco teórico Lester S. Hill publica en 1929 su libro Cryptography in an Algebraic Alphabet, en el cual un bloque de texto claro se cifra a través de una operación con matrices. Originariamente, Hill trabajaba módulo 26 (usaba alfabeto inglés), con el alfabeto de cifrado arbitrario.

A B 5



C D

23 2

E

G

H

I

20 10 15 8

4

18 25 0

16 13

U

V

Y

N O

P

Q

7

1

19 6

3

F

R

S

T

J

K

W X

L

M

Z

12 24 21 17 14 22 11 9

Se elige un entero d que determina bloques de d elementos que son tratados como un vector de d dimensiones.



Se elige de forma aleatoria una matriz de d × d elementos los cuales serán la clave a utilizar.



Los elementos de la matriz de d × d serán enteros entre 0 y 25, además la matriz M debe 𝑛 ser invertible en 𝑍26



Para la encriptación, el texto es dividido en bloques de d elementos los cuales se multiplican por la matriz d × d



Todas las operaciones aritméticas se realizan en la forma módulo 26, es decir que 26=0, 27=1, 28=2 etc.



Dado un mensaje a encriptar debemos tomar bloques del mensaje de "d" caracteres y aplicar:



M×Pi=C, donde C es el código cifrado para el mensaje Pi (Textos Científicos, 2005)

Página 4 de 17

Ejercicio I Demuestre la validez de la proposición dada: Para demostrar la validez de la proposición, probamos que con las condiciones definidas el conjunto 𝒁𝒌 es un espacio vectorial. De modo que: Si tomamos dos elementos cercanos al límite de 𝒁𝒌 y los sumamos, el resultado ya no va a estar en 𝒁𝒌 . Por lo tanto, 𝑍𝑘 no constituye un espacio vectorial.

Ejercicio II Investigue como se soluciona el inconveniente de una palabra que no tiene un número par de letras, si la matriz H2x2 puede codificar pares ordenados de letras.

Dado que el que codifica el mensaje puede agrupar los caracteres como se desee, podría elegirse que hayan ceros en los conjuntos en donde haya más de dos caracteres y que el cero no esté asociado a ningún carácter (como se hará más adelante en el ejercicio 4), lo cual aseguraría que el cifrado sea igual sin importar si hay tres caracteres.

1. Calcular las condiciones que debe cumplir la matriz H para que sea invertible, considerando que sus elementos provienen de 𝒁𝒌 . 𝑎𝑖𝑗 ∈ [0,26] ⊆ 𝑍 𝑥 ≡ 𝑦 ↔ ∃𝑘 ∈ 𝑍 |𝑥 − 𝑦| = 27𝑘, De manera que x e y son coprimos. Construyamos una matriz A: 𝑎11 𝐴=[ ⋮ 𝑎𝑛1

⋯ ⋱ …

𝑎1𝑛 ⋮ ] 𝑎𝑛𝑛

Para que A sea invertible en mod (27):

1. det (A) > 0 2. det(A) no debe ser múltiplos de los factores de 27 Consideremos que: det’(A) = determinante de A y múltiplos de los factores de 27 n= múltiplo de 27 Expresemos det’(A) en módulo 27: Página 5 de 17

′

′

det(A) ≡ 𝑦 ↔ ∃𝑘 ∈ 𝑍 |det(A) − 𝑦| = 27𝑘 Trabajando con la segunda parte del bicondicional, si se la divide para |n|: ′

|det(A) − 𝑦| =

| 𝑛|

27

| 𝑛|

𝑘

′

det(A) − 𝑦

27

𝑛

| 𝑛|

|

|=

𝑘

Con |n| siempre positivo:

′

det(A) − 𝑦

|

𝑛

|=

27 𝑛

𝑘

′

det(A)

|

′

det(A) 𝑛

y

27 𝑛

𝑛

𝑦 27 − |= 𝑘 𝑛 𝑛

son enteros ′

det(A)

| ′

Entonces

det(A) 𝑛

′

𝑦

det(A)

𝑛

𝑛

≡ mod (27) pero

𝑛

𝑦 𝑘 − | = 27 𝑛 𝑛

𝑦

y no son coprimos, porque aunque alguno de los dos sea 𝑛

primo, el otro es múltiplo del primero.

2. Si modificamos el espacio 𝒁𝒌 para incluir caracteres mayúsculos, minúsculos, diez dígitos y el espacio, ¿Cuántos modos de construir H existen? De estas, ¿qué porcentaje es invertible? Mayúsculos

Página 6 de 17

Minúsculos Carácter Posición

a b c 2 2 2 7 8 9

d e 3 3 0 1

f 3 2

g 3 3

h i 3 3 4 5

j 3 6

k 3 7

l 3 8

m n ñ o p q r 3 4 4 4 4 4 4 9 0 1 2 3 4 5

s 4 6

t 4 7

u v 4 4 8 9

w x 5 5 0 1

Dígitos Carácter 0 Posición 54

1 55

2 56

3 57

Carácter Posición

4 58

5 59

6 60

7 61

8 62

9 63

{} 64

Texto en claro: “CodificAdor d3 11LL” Longitud texto cifrado: 18 Clave de cifrado: “CLAveo123” Longitud de la clave: 9

Tamaño de Zk: 65

Antes que nada, vamos a comprobar si esta matriz (K) tiene inversa (K-1) mod 65, por lo contrario no se podría utilizar como clave:

Página 7 de 17

y 5 2

z 5 3

det K mod 65= |K| mod 65 = -6.483 mod 65 = -48, por lo que la matriz K es invertible en módulo 65, ya que su determinante es distinto de cero y -48 y 65 son coprimos. Por lo tanto habrán 659 formas de construir H

3. Si un cliente le pide que diseñe un codificador de Hill pero utilizando una matriz H3x3, ¿considera usted más seguro o menos seguro que con una matriz H2x2? Justifique su respuesta. Cuanta más dimensión posee la matriz más segura será su codificación, puesto que aumentará el grado de dificultad tanto para hallar su inversa (para codificar) o romper el código (calculando mediante gauss). Por lo tanto se asegura que la matriz H3x3 es más segura que una codificación con una matriz cuadrado de orden 2.

Página 8 de 17

4. Diseñe un ejemplo de codificador de Hill con H2x2 y con H3x3, y codifique en ambos casos la frase: Hola mundo Y utilice las respectivas inversas para decodificar el resultado. 0 N 14

A 1 O 15

B 2 P 16

C 3 Q 17

D 4 R 18

E 5 S 19

F 6 T 20

G 7 U 21

H 8 V 22

I 9 W 23

J 10 X 24

K 11 Y 25

L 12 Z 26

M 13

MATRIZ H2x2

det(H) >0 Distribuimos en pares de letras la frase.

HO -

UN -

LA –

DO -

M–

Procedemos a hallar el texto codificado.

En módulo 27:

En módulo 27:

En módulo 27:

En módulo 27:

En módulo 27: Página 9 de 17

Texto codificado: HZWOZLDISV 8 H

26 Z

23 W

15 O

26 Z

12 L

4 D

9 I

19 S

22 V

Para decodificar el mensaje haremos uso de la inversa.

Calculando el inverso aditivo del modulo 27. k-1 = (det (k)-1).

= 10 modulo 27 * X modulo 27 = 190 modulo 27 = 1 modulo 27 X= 19

Matriz inversa con números enteros módulo 27.

k-1

=

En módulo 27: Multiplicamos la matriz para decodificar el mensaje.

En módulo 27:

En módulo 27:

Página 10 de 17

En módulo 27:

En módulo 27:

En módulo 27: Descifrando el mensaje: HOLA MUNDO

H 8

O 15

L 12

A 1

0

M 13

U 21

N 14

D 4

O 15

MATRIZ 3x3

con determinante mayor a 0, por lo tanto es invertible Separamos la oración en tripletas, obtenemos el número equivalente y procedemos a multiplicar por la matriz

En módulo 27:

En módulo 27:

En

módulo

27:

En módulo 27: Texto codificado:

FXGLXNOGPDGG Página 11 de 17

F X G L X N O G 6 24 7 12 24 14 15 7 Para decodificar el mensaje haremos uso de la inversa.

P 16

D 4

G 7

G 7

Calculando el inverso aditivo del modulo 27. I= 29 modulo27. X modulo 27= 406 modulo 27 I=14 Matriz inversa con números enteros módulo 27.

Procedemos a decodificar el mensaje con la matriz anterior:

En módulo 27:

En módulo 27:

En módulo 27:

En módulo 27:

Mensaje Decodificado:

0

H 8

O 15

HOLA MUNDO

L 12

A 1

0

M 13

U 21

N 14

D 4

O 15

0

Página 12 de 17

5. Suponga que usted conoce la frase original “Hola mundo” y también conoce su codificación, pero no conoce la matriz H, ¿es posible determinar H utilizando esa información? Es posible conocer la matriz H por medio del método de Gauss Jordan para todas las matrices, sin embargo este se vuelve más tedioso cuando las matrices son de mayor dimensión. Para demostrar que es posible determinar H, escogeremos el caso de la matriz 2x2 usada en la anterior pregunta. Adjuntamos los pares por filas, realizamos una matriz aumentada tanto con los códigos numéricos del mensaje codificado como el decodificado.

Calculamos el inverso aditivos de 8 modulo 27 para obtener el 1 en primer pivote I= 8 modulo27. X modulo 27= 109 modulo 27 I=17 Multiplicamos el mismo para todos los elementos en la fila y calculamos su respectivo modulo 27. 136 modulo 27= 1 255 modulo 27= 12 136 modulo 27= 1 442 modulo 27= 10

Realizar gauss con las demás filas y luego calcular su módulo 27. Fila 2

Fila 4

Fila 5

12+(-12)(1)=0 /0

21+(-21)(1)=0 / 0

4+(-4)(1)=0 / 0

1+(-12)(12)= -143 /19

14+(-21)(12)= -238 / 5

15+(-4)(12)= -33 / 21

23+(-12)(1)=11 / 11

4+(-21)(1)= -17 / 10

19+(-4)(1)=15 / 15

15+(-12)(10)= -108 / 3

9+(-21)(10)= -201 / 15

22+(-4)(10)= -18 / 9

Página 13 de 17

f2 ↔ f4

Calculamos el inverso aditivos de 5 modulo 27 para obtener el 1 en el segundo pivote. I= 5 modulo27. X modulo 27= 55 modulo 27 I=11 Multiplicamos el mismo para todos los elementos en la fila y calculamos su respectivo modulo 27. 55 modulo 27= 1 110 modulo 27= 2 162 modulo 27= 3 Realizar gauss con las demás filas y luego calcular su módulo 27. Realizando gauss :

Fila 3 13+(-13)(1)=0 /0

Fila 5

26+(-13)(2)=0 /0

21+(-21)(1)=0 / 0

12+(-13)(3)= -27 / 0

15+(-21)(2)= -27 / 0 9+(-21)(3)= -54/ 0

Fila 4 19+(-19)(1)=0 / 0

Finalmente la transpuesta de esta matriz es la matriz H que utilizamos anteriormente para codificar el mensaje.

11+(-19)(2)= -27 / 0 3+(-19)(3)= -54/ 0

6. Diseñe un diagrama de flujo de trabajo para un codificador

Página 14 de 17

Página 15 de 17

7. Basado en la información dada, y en información adicional investigada. ¿Cuán factible es para usted construir o programar un codificador de Hill? Es poco factible ya que el cifrado de Hill es una sustitución poligrámica por grupos de caracteres formados por un sistema criptográfico (bigramas, trigramas, etc...) o también conocido como sustitución mono alfabética. Aunque el sistema de cifrado de Hill puede llegar a tener espacios de claves potencialmente grandes, posee una gran vulnerabilidad, convirtiendo su criptosistema en uno no seguro, ya que 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 por tanto, estaría en disposición de descifrar todos los mensajes cifrados con dicha clave (K). (Matemoción, 2017) Esta vulnerabilidad se debe a la linealidad de este criptosistema, por lo que con texto claro conocido y empleando el método de Gauss Jordan no es muy difícil obtener la matriz clave (K), volviéndose un sistema muy débil ante el conocimiento de una cadena de texto original y su correspondiente texto codificado. (Larragan, 2016)

Conclusiones -

El método de Hill es extremadamente útil y fácil reproducir para la codificación y decodificación de mensajes.

-

El uso del álgebra lineal en aplicaciones de la vida real proporciona métodos sencillos para la resolución de ciertos problemas.

Recomendaciones

Bibliografía

Larragan, M. G. (26 de Julio de 2016). EL BLOG DE GARCÍA LARRAGAN Y CÍA. Obtenido de EL BLOG DE GARCÍA LARRAGAN Y CÍA: https://mikelgarcialarragan.blogspot.com/2016/07/criptografia-xxiv-cifrado-de-hilly.html Matemoción. (11 de Enero de 2017). CUADERNO DE CULTURA CIENTIFICA. Obtenido de CUADERNO DE CULTURA CIENTIFICA: https://culturacientifica.com/2017/01/11/criptografia-matrices-cifrado-hill/ Textos Científicos. (26 de Junio de 2005). Obtenido de Textos Científicos: https://www.textoscientificos.com/criptografia/hill

Página 17 de 17