2.5: Aplicación de Matrices en Criptografía
- Page ID
- 113856
En esta sección, aprenderemos a encontrar la inversa de una matriz, si existe. Posteriormente, utilizaremos inversión matricial para resolver sistemas lineales. En esta sección aprenderás a
- codificar un mensaje usando la multiplicación matricial.
- decodificar un mensaje codificado usando la matriz inversa y la multiplicación matricial
El cifrado se remonta aproximadamente a 4000 años. Los relatos históricos indican que los chinos, egipcios, indios y griegos cifraron mensajes de alguna manera para diversos fines. Un famoso esquema de cifrado se llama el cifrado César, también llamado cifrado de sustitución, utilizado por Julio César, implicaba el desplazamiento de letras en el alfabeto, como reemplazar A por C, B por D, C por E, etc, para codificar un mensaje. Los cifrados de sustitución son demasiado simples en su diseño para ser considerados seguros hoy en día.
En la edad media, las naciones europeas comenzaron a utilizar el cifrado. Una variedad de métodos de encriptación se utilizaron en Estados Unidos desde la Guerra Revolucionaria, pasando por la Guerra Civil, y hasta los tiempos modernos.
Las aplicaciones de la teoría matemática y los métodos al cifrado se generalizaron en el uso militar en el siglo XX. Los militares codificarían los mensajes antes de enviar y el destinatario decodificaría el mensaje, a fin de enviar información sobre las operaciones militares de manera que mantuviera la información segura si el mensaje fuera interceptado. En la Segunda Guerra Mundial, el cifrado jugó un papel importante, ya que tanto los poderes Aliados como los del Eje enviaron mensajes cifrados y dedicaron importantes recursos a fortalecer su propio cifrado al mismo tiempo que intentaban romper el cifrado de la oposición.
En esta sección examinaremos un método de cifrado que utiliza multiplicación matricial e inversos matriciales. Este método, conocido como el Algoritmo de Hill, fue creado por Lester Hill, un profesor de matemáticas que enseñó en varias universidades estadounidenses y además estuvo involucrado con el cifrado militar. El algoritmo Hill marca la introducción de la teoría matemática moderna y los métodos al campo de la criptografía.
En estos días, el Algoritmo Hill no se considera un método de cifrado seguro; es relativamente fácil romper con la tecnología moderna. Sin embargo, en 1929 cuando se desarrolló, la tecnología informática moderna no existía. Este método, que podemos manejar fácilmente con la tecnología actual, era demasiado engorroso para usarlo con cálculos manuales. Hill ideó una máquina de cifrado mecánico para ayudar con las matemáticas; su máquina se basó en engranajes y palancas, pero nunca ganó un uso generalizado. El método de Hill fue considerado sofisticado y poderoso en su tiempo y es uno de los muchos métodos que influyen en las técnicas en uso hoy en día. Otros métodos de cifrado en ese momento también utilizaban máquinas de codificación especiales. Alan Turing, un informático pionero en el campo de la inteligencia artificial, inventó una máquina que era capaz de descifrar mensajes cifrados por la máquina alemana Enigma, ayudando a cambiar el rumbo de la Segunda Guerra Mundial.
Con el advenimiento de la era informática y la comunicación por Internet, el uso del cifrado se ha generalizado en la comunicación y en la seguridad de los datos privados; ya no se limita a usos militares. Los métodos modernos de cifrado son más complicados, a menudo combinando varios pasos o métodos para cifrar datos para mantenerlos más seguros y más difíciles de romper. Algunos métodos modernos hacen uso de matrices como parte del proceso de cifrado y descifrado; otros campos de las matemáticas como la teoría de números juegan un papel importante en la criptografía moderna.
Para utilizar matrices en la codificación y decodificación de mensajes secretos, nuestro procedimiento es el siguiente.
Primero convertimos el mensaje secreto en una cadena de números asignando arbitrariamente un número a cada letra del mensaje. A continuación convertimos esta cadena de números en un nuevo conjunto de números multiplicando la cadena por una matriz cuadrada de nuestra elección que tiene una inversa. Este nuevo conjunto de números representa el mensaje codificado.
Para decodificar el mensaje, tomamos la cadena de números codificados y la multiplicamos por la inversa de la matriz para obtener la cadena original de números. Finalmente, asociando los números con sus letras correspondientes, obtenemos el mensaje original.
En esta sección, utilizaremos la correspondencia que se muestra a continuación donde las letras de la A a la Z corresponden a los números del 1 al 26, un espacio es representado por el número 27, y se ignora la puntuación.
\ [\ begin {array} {cccccccccccc}
\ mathrm {A} &\ mathrm {B} &\ mathrm {C} &\ mathrm {D} &\ mathrm {E} &\ mathrm {F} &\ mathrm {G} &\ mathrm {H} &\ mathrm {I} &\ mathrm {J} &\ mathrm {K} &\ mathrm {K} &\ mathrm {K} &\ mathrm {L} &\ mathrm {M}\\
1 y 2 y 3 y 4 y 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\
\ hline\ mathrm {N} &\ mathrm {O} &\ mathrm {P} &\ mathrm {Q} &\ mathrm {R} &\ mathrm {S} &\ mathrm {T} &\ mathrm {U} &\ mathrm {V} &\ mathrm {W} &\ mathrm {X} &\ mathrm {Y} &\ mathrm {Z}\\
14 y 15 y 16 y 17 y 18 y 19 y 20 y 21 y 22 y 23 y 24 y 25 y 26
\ end {array}\ nonumber\]
Usa matrix\ (A=\ left [\ begin {array} {ll}
1 & 2\\
1 & 3
\ end {array}\ right]\) para codificar el mensaje: ¡ATAQUE AHORA!
Solución
Dividimos las letras del mensaje en grupos de dos.
\[\begin{array}{lllll}\text { AT } & \text { TA } & \text { CK } & \text { -N } & \text { OW }\end{array} \nonumber \]
Asignamos los números a estas letras de la tabla anterior, y convertimos cada par de números en\(2 \times 1\) matrices. En el caso de que quede una sola letra al final, se agrega un espacio para convertirla en pareja.
\ [\ left [\ begin {array} {c}
\ mathrm {A}\\
\ mathrm {T}
\ end {array}\ right] =\ left [\ begin {array} {c}
1\\
20
\ end {array}\ right]\ quad\ left [\ begin {array} {l}
\ mathrm {T}\
\ mathrm {A}
\ end { array}\ derecha] =\ left [\ begin {array} {c}
20\\
1
\ end {array}\ right]\ quad\ left [\ begin {array} {l}
\ mathrm {C}\
\ mathrm {K}
\ end {array}\ right] =\ left [\ begin {array} {l}
3\\
11
\ fin {matriz}\ derecha]\ nonumber\]
\ [\ left [\ begin {array} {c}
-\\
\ mathrm {N}
\ end {array}\ right] =\ left [\ begin {array} {l}
27\\
14
\ end {array}\ right]\ quad\ left [\ begin {array} {l}
\ mathrm {O}\\ mathrm {W}
\ end {array}
\ end {array}\ derecha] =\ izquierda [\ begin {array} {l}
15\\
23
\ end {array}\ derecha]\ nonumber\]
Entonces, en esta etapa, nuestro mensaje expresado como\(2 \times 1\) matrices es el siguiente.
\ [\ left [\ begin {array} {c}
1\\
20
\ end {array}\ right]\ left [\ begin {array} {c}
20\\
1
\ end {array}\ right]\ left [\ begin {array} {c}
3\\
11
\ end {array}\ right]\ left [\ begin {array} {c}
27\\
14
\ end {array}\ right]\ left [\ begin {array} {c}
15\\
23
\ end {array}\ derecha]\ quad\ bf {(I)}\ nonumber\]
Ahora para codificar, multiplicamos, a la izquierda, cada matriz de nuestro mensaje por la matriz\(A\). Por ejemplo, el producto de\(A\) con nuestra primera matriz es:\ (\ left [\ begin {array} {ll}
1 & 2\\
1 & 3
\ end {array}\ right]\ left [\ begin {array} {c}
1\\
20
\ end {array}\ right] =\ left [\ begin {array} {l}
41 \\
61
\ fin {matriz}\ derecha]\)
Y el producto de\(A\) con nuestra segunda matriz es:\ (\ left [\ begin {array} {ll}
1 & 2\\
1 & 3
\ end {array}\ right]\ left [\ begin {array} {l}
20\\
1
\ end {array}\ right] =\ left [\ begin {array} {l}
22\\
23
\ end {array}\ derecha]\)
Multiplicar cada matriz\(\bf{(I)}\) por matriz\(A\), a su vez, da el mensaje codificado deseado:
\ [\ left [\ begin {array} {l}
41\\
61
\ end {array}\ right]\ left [\ begin {array} {l}
22\\
23
\ end {array}\ right]\ left [\ begin {array} {l}
25\
36
\ end {array}\ right]\ left [\ begin {array} {l}
55\\
69
\ end {array}\ right]\ left [\ begin {array} {l}
61\\
84
\ end {array}\ right]\ nonumber\]
Decodifica el siguiente mensaje que fue codificado usando matrix\ (A=\ left [\ begin {array} {ll}
1 & 2\\
1 & 3
\ end {array}\ right]\).
\ [\ left [\ begin {array} {l}
21\\
26
\ end {array}\ right]\ left [\ begin {array} {l}
37\\
53
\ end {array}\ right]\ left [\ begin {array} {l}
45\
54
\ end {array}\ right]\ left [\ begin {array} {c}
74\\
101
\ end {array}\ right]\ left [\ begin {array} {l}
53\\
69
\ end {array}\ right]\ quad (\ bf {II})\ nonumber\]
Solución
Dado que este mensaje fue codificado multiplicando por la matriz\(A\) en Ejemplo\(\PageIndex{1}\), decodificamos este mensaje multiplicando primero cada matriz, a la izquierda, por la inversa de matriz\(A\) dada a continuación.
\ [A^ {-1} =\ left [\ begin {array} {cc}
3 & -2\\
-1 & 1
\ end {array}\ right]\ nonumber\]
Por ejemplo:\ (\ left [\ begin {array} {cc}
3 & -2\\
-1 & 1
\ end {array}\ right]\ left [\ begin {array} {c} {c}
21\
\
26\ end {array}\ right] =\ left [\ begin {array} {c}
11\\
5
\ end {array}\ derecha]\)
Al multiplicar cada una de las matrices\(\bf{(II)}\) por la matriz\(A^{-1}\), obtenemos lo siguiente.
\ [\ left [\ begin {array} {c}
11\\
5
\ end {array}\ right]\ left [\ begin {array} {c}
5\\
16
\ end {array}\ right]\ left [\ begin {array} {c}
27\\
9
\ end {array}\ right]\ left [\ begin {array} {c}
20\\
27
\ end {array}\ right]\ left [\ begin {array} {c}
21\\
16
\ end {array}\ right]\ nonumber\]
Finalmente, asociando los números con sus letras correspondientes, obtenemos:
\ [\ left [\ begin {array} {l}
\ mathrm {K}\
\ mathrm {E}
\ end {array}\ right]\ left [\ begin {array} {l}
\ mathrm {E}\
\ mathrm {P}
\ end {array}\ right]\ left [\ begin {array} {l}
-\\
\ mathrm {I}
\ end { array}\ derecha]\ left [\ begin {array} {l}
\ mathrm {T}\\
-
\ end {array}\ right]\ left [\ begin {array} {l}
\ mathrm {U}\
\ mathrm {P}
\ end {array}\ right]\ nonumber\]
Y el mensaje dice: MANTENERLO ARRENDADO.
Ahora supongamos que queríamos usar una\(3 \times 3\) matriz para codificar un mensaje, entonces en vez de dividir las letras en grupos de dos, las dividiríamos en grupos de tres.
Usando la matriz\ (B=\ left [\ begin {array} {ccc}
1 & 1 & -1\\
1 & 0 & 1\\
2 & 1 & 1 & 1
\ end {array}\ right]\ nonumber\), codifica el mensaje: ¡ATAQUE AHORA!
Solución
Dividimos las letras del mensaje en grupos de tres.
ATT ACK -NO W- -
Tenga en cuenta que como la sola letra “W” quedaba al final, agregamos dos espacios para convertirla en un triplete.
Ahora asignamos a los números sus letras correspondientes de la tabla, y convertimos cada triplete de números en\(3 \times 1\) matrices. Obtenemos
\ [\ left [\ begin {array} {l}
\ mathrm {A}\
\ mathrm {T}\
\ mathrm {T}
\ end {array}\ right] =\ left [\ begin {array} {c}
1\\
20
\ end {array}\ right]\ left [\ begin {array} {l}
\ mathrm {A}\\
\ mathrm {C}\\
\ mathrm {K}
\ end {array}\ right] =\ left [\ begin {array} {l}
1\\
3\
11\ end {array}
\ right]\ left [\ begin {array} {l}
-\\\ mathrm {N}\
\\ mathrm {N}\
\\ mathrm {O}
\ end {array}\ right] =\ left [\ begin {array} {l}
27\\
14\\
15
\ end {array}\ right]\ left [\ begin {array} {l}
\ mathrm {W}\
-\
-
\ end {array}\ right] =\ left [\ begin {array} {l}
23\\
27\\
27
\ end {array}\ derecha]\ nonumber\]
Hasta el momento tenemos,
\ [\ left [\ begin {array} {c}
1\\
20\
20
\ end {array}\ right]\ left [\ begin {array} {c}
1\\
3\
11
\ end {array}\ right]\ left [\ begin {array} {c}
27\\
14\\
15
\ end {array}\ derecha]\ left [\ begin {array} {c}
23\\
27\\
27
\ end {array}\ derecha]\ quad\ bf {(III)}\ nonumber\]
Multiplicamos, a la izquierda, cada matriz de nuestro mensaje por la matriz\(B\). Por ejemplo,
\ [\ left [\ begin {array} {ccc}
1 & 1 & -1\\
1 & 0 & 1\\
2 & 1 & 1
\ end {array}\ right]\ left [\ begin {array} {c}
1\\
20
\ end {array}\ right] =\ left [\ begin {array} {c}
1\\
21\\
42
\ end {array}\ derecha]\ nonumber\]
Al multiplicar cada una de las matrices\(\bf{(III)}\) por la matriz\(B\), obtenemos el mensaje codificado deseado de la siguiente manera:
\ [\ left [\ begin {array} {c}
1\\
21\
42
\ end {array}\ right]\ left [\ begin {array} {c}
-7\\
12\
16
\ end {array}\ right]\ left [\ begin {array} {c}
26\\
42\\
83
\ end {array}\ right]\ left [\ begin {array} {c}
23\\
50\
100
\ end {array}\ right]\ nonumber\]
Si necesitamos decodificar este mensaje, simplemente multiplicamos el mensaje codificado por\(B^{-1}\), y asociamos los números con las letras correspondientes del alfabeto.
En Ejemplo\(\PageIndex{4}\) demostraremos cómo usar matrix\(B^{-1}\) para decodificar un mensaje cifrado.
Decodifica el siguiente mensaje que fue codificado usando matrix\ (B=\ left [\ begin {array} {lll}
1 & 1 & -1\\
1 & 0 & 1\\
2 & 1 & 1 & 1
\ end {array}\ right]\).
\ [\ left [\ begin {array} {l}
11\\
20\
43
\ end {array}\ right]\ left [\ begin {array} {l}
25\\
10\
41
\ end {array}\ right]\ left [\ begin {array} {l}
22\\
14\\
41
\ end {array}\ derecha]\ quad\ bf {(IV)}\ nonumber\]
Solución
Ya que este mensaje se codificaba multiplicando por la matriz\(B\). Primero determinamos la inversa de\(B\).
\ [\ mathrm {B} ^ {-1} =\ left [\ begin {array} {ccc}
1 & 2 & -1\\
-1 & -3 & 2\\
-1 & -1 & 1
\ end {array}\ derecha]\ nonumber\]
Para decodificar el mensaje, multiplicamos cada matriz, a la izquierda, por\(B^{-1}\). Por ejemplo,
\ [\ left [\ begin {array} {ccc}
1 & 2 & -1\\
-1 & -3 & 2\\
-1 & -1 & 1
\ end {array}\ right]\ left [\ begin {array} {c}
11\\
20\
43
\ end {array}\ right] =\ left [\ begin {array} {c}
8\\
15\\
12
\ end {array}\ derecha]\ nonumber\]
Multiplicar cada una de las matrices\(\bf{(IV)}\) por la matriz\(B^{-1}\) da lo siguiente.
\ [\ left [\ begin {array} {c}
8\\
15\
12
\ end {array}\ right]\ left [\ begin {array} {c}
4\\
27\\
6
\ end {array}\ right]\ left [\ begin {array} {c}
9\\
18\\
5
\ end {array}\ derecha]\ nonumber\]
Finalmente, asociando los números con sus letras correspondientes, obtenemos
\ [\ left [\ begin {array} {l}
\ mathrm {H}\
\ mathrm {O}\
\ mathrm {L}
\ end {array}\ right]\ left [\ begin {array} {l}
\ mathrm {D}\
-\\ mathrm {F}
\ end {array}
\ end {array}\ right]\ left [\ begin {array} {l}
\ mathrm {I}\\
\ mathrm {R}\\
\ mathrm {E}
\ end {array}\ derecha]\ quad\ text {El mensaje dice:}\ mathrm {HOLD}\ text {FUEGO}\ nonumber\]
El mensaje dice: MANTENER FUEGO.
Resumimos:
Para codificar un mensaje
1. Divida las letras del mensaje en grupos de dos o tres.
2. Convierte cada grupo en una cadena de números asignando un número a cada letra del mensaje. Recuerda asignar letras a espacios en blanco.
3. Convierte cada grupo de números en matrices de columna.
3. Convierta estas matrices de columna en un nuevo conjunto de matrices de columna multiplicándolas por una matriz cuadrada compatible de su elección que tenga una inversa. Este nuevo conjunto de números o matrices representa el mensaje codificado.
DECODIFICAR UN MENSAJE
1. Toma la cadena de números codificados y multiplícalo por la inversa de la matriz que se utilizó para codificar el mensaje.
2. Asociar los números con sus letras correspondientes.