Criptografia - APLICACION DE MATRICES PDF

Preview

Summary

APLICACION DE MATRICES...

Description

Criptograf´ıa con matrices, el cifrado de Hill Zu˜ niga Naquiche Gerson 1, Lopez Flores Freddy Eduardo 2, Quenta Huanaco Royer Franco 3 Facultad de Ciencias 1, Universidad Nacional de Ingenier´ıa 1, e-mail: [email protected] Facultad de Ciencias 2, Universidad Nacional de Ingenier´ıa 2, e-mail: royer 95 [email protected] Facultad de Ciencias 3, Universidad Nacional de Ingenier´ıa 3, e-mail: [email protected] Veremos la aplicaci´ on y el funcionamiento de las matrices del a´ lgebra lineal en la criptograf´ıa de Hill, por ello hallaremos una matriz compatible con el algoritmo del cifrado de Hill para luego, mediante una transformaci´ on lineal y la multiplicaci´ on de matrices, encriptar y desencriptar un mensa je. Palabras Claves: criptograf´ıa, transformaci´ on lineal, encriptar y desencriptar,

We will see the application and the operation of the matrices of linear algebra in Hill’s cryptography, so we will find a matrix compatible with Hill’s encryption algorithm and then, through a linear transformation and matrix multiplication, encrypt and decrypt a message. Keywords: cryptography, linear transformation encrypt and decrypt

´ 1. INTRODUCCION Las personas se comunican digitalmente a trav´es de aparatos electr´ onicos intercambiando informaci´on pero, ¿Qu´e pasa cuando esa informaci´on es intersectada ? Nos topamos con el problema de la confidencialidad de nuestra informaci´on. Para este fin, se utiliza la criptograf´ıa que se encarga de alterar las representaciones ling¨ u´ısticas de los mensajes sensibles con el fin de hacerlos ininteligibles a receptores no autorizados.

2. CONCEPTOS PREVIOS Expliquemos en qu´e consiste el cifrado de Hill. Asociaci´ on natural ordenada .-

En primer lugar, se asocia cada letra del alfabeto con un n´ umero. La

forma m´as sencilla de hacerlo es con la asociaci´on natural ordenada, aunque podr´ıan realizarse otras asociaciones diferentes.

Numeros enteros modulo n .-

Como en la correspondencia anterior, entre letras/signos y n´ umeros,

solamente aparecen 27 n´ umeros, hay que trabajar con los n´ umeros enteros “m´odulo 27”. Es decir, se consideran los n´ umeros enteros 0, 1, 2, . . . , 26y 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´etera, y lo mismo con los n´ umeros negativos, de forma que – 1 es igual 26, – 2 es igual 25, etc´etera. Operaciones arimeticas en modulo n .-

Adem´as, se reducen las operaciones aritm´eticas (suma, resta,

multiplicaci´on y divisi´on) al conjunto de los n´ umeros enteros m´ odulo 27 de forma natural, es decir, al operar dos n´ umeros enteros (m´ odulo 27) el resultado se considera tambi´en m´ odulo 27. Por ejemplo, si se realiza la multiplicaci´on de los n´ umeros 6 y 13, m´odulo 27, el resultado dar´a 24 (m´odulo 27), puesto que 6 × 13 = 78 y 78 = 2 × 27 + 24. O el inverso de 2, es decir, el n´ umero a tal que 2 × a es igual a 1 (m´odulo 27), es 14, puesto que 2 × 14 = 28, que es igual a 1, m´odulo 27. Transformaci´ on lineal de encriptamiento y desencriptamiento.-

En el cifrado de Hill se utiliza una

matriz cuadrada de n´ umeros A como clave, la cual determina la transformaci´on lineal Y = A.X, donde Y, X son vectores columna y A y X se multiplican con la multiplicaci´ on de matrices (v´ease la siguiente imagen). Veamos un ejemplo. Consideremos la matriz cuadrada 3 × 3 (aunque en general pueden considerarse matrices cuadradas de cualquier tama˜ no) siguiente y la correspondiente transformaci´on lineal Y = A.X :

´ 3. ANALISIS Codificaci´ on

Supongamos que el mensaje que se quiere enviar encriptado es

”CU ADERN ODECU LT URACIEN T IF ICA” cuya transcripci´on num´erica, teniendo en cuanta la tabla de sustituci´on anterior, es ”2, 21, 0, 3, 4, 18, 13, 15, 3, 4, 2, 21, 11, 20, 21, 18, 0, 2, 8, 4, 13, 20, 8, 5, 8, 2, 0”. Como la transformaci´on lineal es de orden 3, vamos a agrupar los n´ umeros en grupos de tres, en ternas, sobre las que luego aplicaremos la transformaci´on lineal, (2, 21, 0), (3, 4, 18), (13, 15, 3), (4, 2, 21), (11, 20, 21), (18, 0, 2), (8, 4, 13), (20, 8, 5), (8, 2, 0). A continuaci´ on, vamos a transformar las ternas de n´ umeros anteriores, mediante la transformaci´on lineal dada por la clave, en nuevas ternas, que ser´an el mensaje num´erico cifrado. ¡Ojo!, que en la transformaci´on lineal no hay que olvidar que seguimos trabajando con los n´ umeros enteros m´odulo 27.

Aunque la transformaci´on lineal de la terna (2, 21, 0) es inicialmente (44, 84, 2), como estamos trabajando con enteros m´ odulo 27, esta terna se convierte en (17, 3, 2), ya que 44 = 1 × 27 + 17 y 84 = 3 × 27 + 3.

E igual para el resto.

Por lo tanto, el mensaje num´erico cifrado es ”17, 3, 2, 11, 25, 3, 25, 21, 4, 17, 5, 22, 6, 23, 2, 24, 10, 3, 1, 0, 5, 24, 3, 23, 12, 8, 8”, que al transformar de nuevo los n´ umeros en sus correspondientes letras, se convierte en el mensaje cifrado

”QDCLY DY U EQF V GW CX KDBAF XDW M II ” Y este es el mensaje que se env´ıa para que no sea comprendido por el “enemigo” aunque este lo intercepte en el camino.

Decodificaci´ on

Para poder descodificar los mensajes cifrados mediante el m´etodo de Hill se necesita que

la matriz de la transformaci´on lineal utilizada, la clave, sea una matriz inversible. La matriz de nuestro ejemplo lo es, puesto que su determinante es no nulo, |A| = 22. Adem´as, la matriz inversa de A, que es la necesaria para descodificar un mensaje cifrado, es

Pero ojo, estamos trabajando con los enteros m´odulo 27 y vamos a transformar la matriz inversa anterior en una matriz con n´ umeros enteros m´ odulo 27. Para empezar se necesita el inverso del n´ umero 22. Se ve f´acilmente que 22 × 16 = 352, que es igual a 1, m´odulo 27, luego m´odulo 27, en

1 22

= 16. Y la matriz inversa se transforma,

Expliquemos ahora el proceso de descodificaci´on de un mensaje. Imaginemos que el receptor recibe el siguiente mensaje

”EHAHT DIN RKQOP U SKV LKM UF nG” y quiere conocer su significado. Para descodificar el mensaje hay que utilizar el mismo m´etodo anterior, el cifrado de Hill, pero utilizando como clave la matriz inversa A−1 (m´odulo 27) de la matriz A de codificaci´on. Por lo tanto, se empieza de nuevo transformando el mensaje en la sucesi´on de ternas num´ericas asociada, (4, 7, 0), (7, 20, 3), (8, 13, 18), (10, 17, 15), (16, 21, 19), (10, 22, 11), (10, 12, 21), (5, 14, 6). Y entonces se transforman mediante la transformaci´ on lineal con matriz A−1 , es decir, Y = A−1 .X .

En consecuencia, la secuencia de ternas num´ericas original asociada al anterior mensaje codificado es (3, 8, 22), (21, 11, 6), (0, 13, 3), (15, 11, 0), (19, 12, 0), (20, 4, 12), (0, 20, 8), (2, 0, 19). Y traduciendo los n´ umeros a sus correspondientes letras del alfabeto se obtiene que el mensaje original enviado es

”DIV U LGANDOLASM AT EM AT ICAS”

4. OBSERVACIONES Nos percatamos que la determinante de la matriz clave debe ser primo entre s´ı con el modulo de encriptaci´on puesto que de no ser as´ı encontrar la matriz inversa modulo n no s´era posible, esto se debe a que :

A−1 .A = I |A−1 |.|A| = |I| = 1(mod 27) Sea A = 3˙ (multiplo de 3), tendremos ˙ = 1 + 3˙ |A−1 | × 3˙ = |I| = 1(mod27) = 1 + 27 |A−1 | × 3˙ = 1 + 3˙ 3˙ = 1 + 3˙ Lo que resulta en una contradicci´ on y de ello probamos que |A| debe ser primo entre s´ı con el m´ odulo de encriptaci´on, en otras palabras M CD(|A|, n) = 1.

5. CONCLUSIONES 1. Se determin´o que la determinante de la matriz debe ser mayor a 0 y primo entre s´con el m´odulo de cifrado. 2. Se determin´o que la matriz de descifrado es la matriz inversa de la matriz clave, la cual la calculamos con la f´ormula A−1 =

adj(A) detA

—————————————————————————– 1. Ra´ ul Ib´ an ˜ez, Arthur Cayley, explorador victoriano del

3. Lester S. Hill, Cryptography in an Algebraic Alpha-

territorio matem´ a tico, RBA, 2017 (pendiente de pu-

bet, The American Mathematical Monthly, vol. 36, n.

blicaci´ on).

6 (1929). p. 306-312.

2. Marie-Jos´ e Pestel, Paul Kichilov, de la gravure a` la

4. Jorge Rami´ o Aguirre, Seguridad Inform´ a tica y cripto-

anamorphose, Tangente Hors-serie 23: Maths et arts

graf´ıa (libro electr´ onico), Universidad Polit´ ecnica de

plastiques, p. 142-147.

Madrid, 2006....