Solucion Actividad 1.docx h5h35

ACTIVIDAD 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.1 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: ( Paso 1.

1 5 ) 0 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. Se debe tener en cuenta que en la transformación lineal se está trabajando con los números enteros módulo 27. (

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

(

(1 ∗ 3) + (5 ∗ 8) 43 16 1 5 3 )*( ) = ( )=( )≡( ) (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 1 5 2 15 )*( ) = ( )=( )≡( ) (0 ∗ 2) + (1 ∗ 8) 8 0 1 8 8

(

(1 ∗ 15) + (5 ∗ 13) 80 26 1 5 15 )*( ) = ( )=( )≡( ) (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 16 trabajando con enteros módulo 27, entonces esta terna se convierte en ( ) ya que 8 1 ∗ 27 + 𝟏𝟔 ( ) , de este modo se realiza para las otras ternas. 8 Paso 3. Se toman los resultados de la transformación lineal de cada terna, teniendo así un mensaje numérico cifrado “23, 4, 16, 8, 2, 0, 15, 8, 26, 13”, que al transformar de nuevo los números en sus correspondientes letras, se convierte en el mensaje cifrado: “WEPICAOIZN”

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

PASOS PARA DESENCRIPTAR UN MENSAJE. Mensaje a Desencriptar: “WEPICAOIZN” 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 A, ya que es la necesaria para descodificar el mensaje cifrado. Para calcular la inversa de la matriz A, se debe escribir la matriz aumentada (A│I) y se realiza la reducción por renglones para encontrar la forma escalonada reducida por renglones de A. 𝑨=(

𝟏 𝟎

𝟓𝟏 𝟎 | ) 𝟏𝟎 𝟏

𝑹𝟏 → −𝟓𝑹𝟐 + 𝑹𝟏 (

𝟏 𝟎

𝟎𝟏 | 𝟏𝟎 𝟏 𝟎

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

Paso 3.

−𝟓 ) 𝟏 −𝟓 ) 𝟏

Se debe recordar que debido a que se está trabajando con los enteros módulo 27 entonces se tiene que transformar la matriz inversa anterior en una matriz con números enteros módulo 27. 𝟏 𝟎

𝑨−𝟏 𝒎𝒐𝒅 𝟐𝟕 = (

−𝟐𝟔 −𝟓 ) 𝒎𝒐𝒅 𝟐𝟕 = ( −𝟐𝟕 𝟏

−𝟑𝟐 ) −𝟐𝟔

27 ∗ 1 − 𝟐𝟔 = 1 27 ∗ 1 − 𝟑𝟐 = −5 27 ∗ 1 − 𝟐𝟕 = 0 27 ∗ 1 − 𝟐𝟔 = 1 Paso 4. Se transforma el mensaje en la sucesión de ternas numéricas asociada, (23, 4), (16,8), (2,0), (15,8), (26,13). Para luego, transformarla nuevamente mediante la transformación lineal con matriz 𝐴−1 es decir, Y = 𝐴−1 *X (

(−26 ∗ 23) + (−32 ∗ 4) −𝟐𝟔 −𝟑𝟐 23 −726 3 )*( ) = ( )=( )≡( ) (−27 ∗ 23) + (−26 ∗ 4) −𝟐𝟕 −𝟐𝟔 −725 4 4

(

(−26 ∗ 16) + (−32 ∗ 8) −𝟐𝟔 −𝟑𝟐 16 −672 3 )*( ) = ( )=( )≡( ) (−27 ∗ 16) + (−26 ∗ 8) −𝟐𝟕 −𝟐𝟔 8 −640 8

(

(−26 ∗ 2) + (−32 ∗ 0) −𝟐𝟔 −𝟑𝟐 2 2 −52 )*( ) = ( )=( )≡( ) (−27 ∗ 2) + (−26 ∗ 0) −𝟐𝟕 −𝟐𝟔 0 0 −54

(

(−26 ∗ 15) + (−32 ∗ 8) −𝟐𝟔 −𝟑𝟐 15 −646 2 )*( ) = ( )=( )≡( ) (−27 ∗ 15) + (−26 ∗ 8) −𝟐𝟕 −𝟐𝟔 −613 8 8

(

(−26 ∗ 26) + (−32 ∗ 13) −𝟐𝟔 −𝟑𝟐 26 −1092 5 )*( ) = ( )=( )≡( ) (−27 ∗ 26) + (−26 ∗ 13) −𝟐𝟕 −𝟐𝟔 13 −1040 13

−726 23 ) es inicialmente ( ) y como se −725 4 3 está trabajando con enteros módulo 27, entonces esta terna se convierte en ( ) 4 27 ∗ (−27) + 𝟑 ya que ( ) , de este modo se realiza para las otras ternas. 27 ∗ (−27) + 𝟒 Aunque la transformación lineal de la terna (

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 𝑎 det 𝐴 = 𝑑𝑒𝑡 (6 1

𝑏 7 2

𝑐 3) 1 𝑏 7 2

𝑐 3) = 1 1

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

−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 



Criptografía con matrices, el cifrado de Hill. Tomado de: https://culturacientifica.com/2017/01/11/criptografia-matricescifrado-hill/ Criptografía desde el punto de vista de la programación funcional. Tomado de:https://idus.us.es/xmlui/bitstream/handle/11441/43818/Rodr%C3 %ADguez%20Chavarr%C3%ADa%2C%20Daniel%20TFG.pdf?seque nce=1&isAllowed=y