Solucion Actividad 1 (4) b1p51

ACTIVIDAD 1

1.1 Consultar el sistema Hill para encriptar y desencritar mensajes. Escribir la bibliografía revisada. SISTEMA HILL El cifrado de Hill es un criptosistema polialfabetico que trabaja dividiendo el mensaje original en bloques de un tamaño fijo y transformando cada bloque de forma independiente en otro conjunto de letras distinto. Esta transformación viene definida por una aplicación del algebra lineal: la multiplicación matricial. Este sistema es polialfabetico pues puede darse que un mismo carácter en un mensaje a enviar se encripte en dos caracteres distintos en el mensaje encriptado. Lester Hill trato por primera vez este criptosistema en 1929 en ´ The American Mathematical Monthly, introduciendo así uno de las primeras aplicaciones del algebra lineal a la criptografía poligráfica. En 1931, volvió a escribir un artıculo sobre el cifrado en otra edición del mismo periódico. Hill, con ayuda de Louis Weisner, tuvieron la idea de construir una máquina que implementase el criptosistema. La llamaron the Message Protector y la patentaron. La máquina operaba con bloques de seis letras y se basaba en un sistema de engranajes y poleas. En primer lugar, en el cifrado de Hill, se asocia cada letra del alfabeto con un número. La forma más sencilla de hacerlo es con la asociación natural ordenada, aunque podrían realizarse otras asociaciones diferentes. Además, también podrán añadirse otros símbolos usuales, como el espacio en blanco “_”, el punto “.” o la coma “,”, la interrogación “?”, las 10 cifras básicas, entre otros.

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, entre otros. 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 matriz cuadrada de números A como clave, la cual determina la transformación lineal Y = A ∙ X, donde Y, X son vectores columna y A y X se multiplican, con la multiplicación de matrices. Consideremos como ejemplo la matriz cuadrada 3 x 3 (aunque en general pueden considerarse matrices cuadradas de cualquier tamaño) siguiente y la correspondiente transformación lineal Y = A ∙ X .

1.2 A partir de la consulta anterior, con sus propias palabras, describa el paso 1 5 a paso para cifrar la palabra DEDICACIÓN empleando la matriz clave ( ) 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 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 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

PASOS PARA ENCRIPTAR UN MENSAJE Palabra que se quiere encriptar: ¨DEDICACIÓN ¨ Matriz clave 2*2: (

1 5 ) 0 1

Paso 1. Se realiza transcripción numérica, teniendo en cuanta la tabla de sustitución anterior: “3,4,3,8,2,0,2,8,15,13”. Como la transformación lineal es de orden 2, vamos a agrupar los números en grupos de dos, en ternas, sobre las que luego aplicaremos la transformación lineal, (3,4), (3, 8), (2,0), (2,8), (15,13). Paso 2. Se transforman 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, es decir se multiplica la matriz clave con la terna calculada. Se debe tener en cuenta que en la transformación lineal se está trabajando con los números enteros módulo 29. (

(1 ∗ 3) + (5 ∗ 4) 1 5 3 23 )*( ) = ( )=( ) (0 ∗ 3) + (1 ∗ 4) 4 0 1 4

(

(1 ∗ 3) + (5 ∗ 8) 43 14 1 5 3 )*( ) = ( ) = ( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 3) + (1 ∗ 8) 8 8 0 1 8

(

(1 ∗ 2) + (5 ∗ 0) 2 1 5 2 )*( ) = ( )=( ) (0 ∗ 2) + (1 ∗ 0) 0 0 1 0

(

(1 ∗ 2) + (5 ∗ 8) 42 13 1 5 2 )*( ) = ( ) = ( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 2) + (1 ∗ 8) 8 8 0 1 8

(

(1 ∗ 15) + (5 ∗ 13) 80 22 1 5 15 )*( ) = ( ) = ( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 15) + (1 ∗ 13) 13 13 0 1 13

3 43 Aunque la transformación lineal de la terna ( ) es inicialmente ( ) y como se está 8 8 14 trabajando con enteros módulo 29, entonces esta terna se convierte en ( ) , este 8 valor se halló empleando el siguiente comando en Excel, =RESIDUO (47; 29) para escribir 47 en módulo 29.

Paso 3. Se toman los resultados de la transformación lineal de cada terna, teniendo así un mensaje numérico cifrado “23, 4, 14, 8, 2, 0, 13, 8, 22, 13”, que al transformar de nuevo los números en sus correspondientes letras, se convierte en el mensaje cifrado: “WE()ICANIVN”

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

PASOS PARA DESENCRIPTAR UN MENSAJE. Mensaje a Desencriptar: “WE()ICANIVN” Paso 1. Comprobar que la matriz de la transformación lineal utilizada, es decir, la clave, sea una matriz inversible. La matriz del ejercicio lo es, puesto que su determinante es no nulo, |A|= 1. 𝟏 𝟓 𝑨=( ) 𝟎 𝟏

1 5 𝑑𝑒𝑡 ( ) = |𝐴| = (1 ∗ 1) − (5 ∗ 0) = 1 0 1

Paso 2. Se debe hallar la inversa de la matriz clave, ya que es la necesaria para descodificar el mensaje cifrado. Para calcular la inversa de la matriz clave, se debe escribir la matriz aumentada (A│I) y se realiza la reducción por renglones para encontrar la forma escalonada reducida por renglones. 𝑨=(

𝟏 𝟎

𝟓𝟏 𝟎 | ) 𝟏𝟎 𝟏

𝑹𝟏 → −𝟓𝑹𝟐 + 𝑹𝟏 (

𝟏 𝟎

𝟎𝟏 | 𝟏𝟎 𝟏 𝟎

𝑴𝒂𝒕𝒓𝒊𝒛 𝒊𝒏𝒗𝒆𝒓𝒔𝒂 = 𝑨−𝟏 = (

−𝟓 ) 𝟏 −𝟓 ) 𝟏

Paso 3. Se debe recordar que debido a que se está trabajando con los enteros módulo 29 entonces se tiene que transformar la matriz inversa anterior en una matriz con números enteros módulo 29. 𝑨−𝟏 𝒎𝒐𝒅 𝟐𝟗 = (

𝟏 𝟎

𝟏 −𝟓 ) 𝒎𝒐𝒅 𝟐𝟗 = ( 𝟎 𝟏

𝟐𝟒 ) 𝟏

Paso 4. Se transforma el mensaje en la sucesión de ternas numéricas asociada, (23, 4), (206,8), (2,0), (205,8), (334,13). Para luego, transformarla nuevamente mediante la transformación lineal con matriz 𝐴−1 es decir, Y = 𝐴−1 *X (

𝟏 𝟎

(1 ∗ 23) + (24 ∗ 4) 𝟐𝟒 23 119 3 )*( ) = ( )=( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 23) + (1 ∗ 4) 𝟏 4 4 4

(

𝟏 𝟎

(1 ∗ 14) + (24 ∗ 8) 𝟐𝟒 14 206 3 )*( ) = ( )=( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 14) + (1 ∗ 8) 𝟏 8 8 8

(

𝟏 𝟎

(1 ∗ 2) + (24 ∗ 0) 𝟐𝟒 2 2 )*( ) = ( )=( ) (0 ∗ 2) + (1 ∗ 0) 𝟏 0 0

(

𝟏 𝟎

(1 ∗ 13) + (24 ∗ 8) 𝟐𝟒 13 2 205 )*( ) = ( )=( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 13) + (1 ∗ 8) 𝟏 8 8 8

(

𝟏 𝟎

(1 ∗ 22) + (24 ∗ 13) 𝟐𝟒 22 334 15 )*( ) = ( )=( ) 𝑐𝑜𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 29 ( ) (0 ∗ 22) + (1 ∗ 13) 𝟏 13 13 13

Paso 5. En consecuencia, la secuencia de ternas numéricas original asociada al anterior mensaje codificado es (3, 4), (3,8), (2,0), (2, 8), (15,13). Y al traducir los números a

sus correspondientes letras del alfabeto se obtiene el mensaje original: “DEDICACION”

ACTIVIDAD 2. 2.1 Suponga que se intercepta el mensaje HSÑQEQÑQBTDCL_TRUDNBUHÑV.ZWEAYZOZELHRACAZJCBC y que de él se sabe lo siguiente: a) Las tres primeras letras del mensaje oculto son “CAM” y las tres últimas son “DO_” 𝑎 𝑏 𝑐 b) La matriz clave es de la forma (6 7 3) 1 2 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. En mi opinión, el mensaje no se puede descifrar con la información dada, ya que, aunque se conozca la matriz clave y su determinante, esta matriz es alfanumérica (a, b, c, 6,7,3,1,2,1) y al calcular su inversa también quedara una matriz alfanumérica y así tendría más incógnitas.

𝑨−𝟏 =

𝟏 ∗ 𝑨𝒅𝒋𝒖𝒏𝒕𝒂 𝒅𝒆 𝑨 𝒅𝒆𝒕

𝑎 𝐴 = (6 1

𝑏 7 2

𝑐 3) 1

𝑎 det 𝐴 = 𝑑𝑒𝑡 (6 1 1 𝐴𝑑𝑗𝑢𝑛𝑡𝑎 𝐴 = ( −𝑏 + 𝑐 3𝑏 − 7𝑐

𝑏 7 2

𝑐 3) = 1 1

−3 𝑎−𝑐 −3𝑎 + 6𝑐

5 −2𝑎 + 𝑏) 7𝑎 − 6𝑏

7 2

3 ) = (1) ∗ ((7 ∗ 1) − (3 ∗ 2)) = 1 1 6 3 𝐴12 = (−1)1+2 ∗ ( ) = (−1) ∗ ((6 ∗ 1) − (3 ∗ 1)) = −3 1 1 6 7 𝐴13 = (−1)1+3 ∗ ( ) = (1) ∗ ((6 ∗ 2) − (7 ∗ 1)) = 5 1 2 𝑏 𝑐 𝐴21 = (−1)1+4 ∗ ( ) = (−1) ∗ ((𝑏 ∗ 1) − (𝑐 ∗ 2)) = −𝑏 + 𝑐 2 1 𝑎 𝑐 𝐴22 = (−1)1+5 ∗ ( ) = (1) ∗ ((𝑎 ∗ 1) − (𝑐 ∗ 1)) = 𝑎 − 𝑐 1 1 𝑎 𝑏 𝐴23 = (−1)1+6 ∗ ( ) = (−1) ∗ ((𝑎 ∗ 2) − (𝑏 ∗ 1)) = −2𝑎 + 𝑏 1 2 𝑏 𝑐 𝐴31 = (−1)1+7 ∗ ( ) = (1) ∗ ((𝑏 ∗ 3) − (𝑐 ∗ 7)) = 3𝑏 − 7𝑐 7 3 𝑎 𝑐 𝐴32 = (−1)1+8 ∗ ( ) = (−1) ∗ ((𝑎 ∗ 3) − (𝑐 ∗ 6)) = −3𝑎 + 6𝑐 6 3 𝑎 𝑏 𝐴33 = (−1)1+9 ∗ ( ) = (1) ∗ ((𝑎 ∗ 7) − (𝑏 ∗ 6)) = 7𝑎 − 6𝑏 6 7 𝐴11 = (−1)1+1 ∗ (

−𝟏

𝑨

1 𝟏 = ∗ ( −𝑏 + 𝑐 𝟏 3𝑏 − 7𝑐

1 𝑨−𝟏 = ( −𝑏 + 𝑐 3𝑏 − 7𝑐

−3 𝑎−𝑐 −3𝑎 + 6𝑐 −3 𝑎−𝑐 −3𝑎 + 6𝑐

5 −2𝑎 + 𝑏) 7𝑎 − 6𝑏 5 −2𝑎 + 𝑏) 7𝑎 − 6𝑏

2.2.2 Si la respuesta al ítem anterior fue afirmativa, descifre el mensaje oculto.

BIBLIOGRAFÍA 

Universidad del País Vasco. (2017). Criptografía con matrices, el cifrado de Hill. Bilbao: Cultura científica. Recuperado de https://culturacientifica.com/2017/01/11/criptografia-matrices-cifrado-hill/ Comentario: en este texto se describe la historia y el proceso de cifrado y descifrado empleando operaciones entre matrices. Se presenta un ejemplo de cómo realizar de manera organizada el paso a paso del proceso.



Rodríguez Chavarría Daniel (2016). Criptografía desde el punto de vista de la programación funcional. Recuperado de:https://idus.us.es/xmlui/bitstream/handle/11441/43818/Rodr%C3%AD guez%20Chavarr%C3%ADa%2C%20Daniel%20TFG.pdf?sequence=1&i sAllowed=y