El álgebra lineal: un modelo matemático en criptografía


El mundo de las matrices y el álgebra lineal nos proporcionan diversos métodos criptográficos.

Cualquier texto lo podemos escribir en forma de números; basta sólo con hacer corresponder a cada carácter un número. Formalmente si tenemos un alfabeto de n caracteres podemos trabajar en

Para cifrar un mensaje basta que emisor y receptor se pongan de acuerdo con una matriz A y un vector b y hacer algo del estilo:

Si llaman x a una secuencia de números asociados a una secuencia de elementos del alfabeto, sólo hay que hacer: f(x) = A · x + b = y

El «hacker» verá que por la red circula y, para saber x será preciso conocer la matriz A (de hecho, la inversa de A: A-1).

Entonces y - b = A · x y por tanto A-1 · (y - b) = x.

Para poder hacer todo esto será necesaria la existencia de la matriz inversa en lo que se cumple si mcd (det (A), n) = 1.

El primer modelo sencillo lo encontramos en el llamado cifrado de Hill.

Lester S. Hill (1891-1961) realizó en el año 1929 una aportación fundamentada en combinar el álgebra lineal y la aritmética modular. Hill publica el artículo "Cryptography in an Algebraic Alphabet", en American Mathematical Monthly, vol. 36, nº 6 (junio-julio, 1929), pp. 306-312, en el que describe cómo un bloque de texto claro es cifrado a través de una operación con matrices. Es posible utilizar una matriz, en principio de orden dos, como herramienta para cifrar un mensaje en palabras, descomponiendo el texto en pares de letras y asociando a cada letra un valor numérico del alfabeto. La matriz para cifrar el texto llano la denotamos A, invertible, que para simplificar la consideraremos de determinante la unidad:

con det(A)= ad – bc = 1, siendo la inversa
Si disponemos de un alfabeto con n caracteres, el mecanismo para cifrar es usar la relación lineal de la forma en módulo n, siendo el texto plano

Para descifrar el mensaje bastará aplicar la matriz inversa en el vector Para ilustrar el funcionamiento consideremos el alfabeto español ampliado con el espacio blanco que designaremos con el símbolo @, cada carácter se identifica con un número –por sencillez, en el ejemplo, se toma el número de orden–.

Cada mensaje para cifrar se descompone en bloques de dos elementos. Cifremos la palabra MAT, para ello agrupamos MAT en bloques de dos elementos de la forma MA T@; a cada elemento se le asocia el número correspondiente, en nuestro caso MA se identificará con (12 0) y T@ con (20 27). Aplicaremos por ejemplo la clave conocida por el emisor y receptor, y preestablecida de mutuo acuerdo.

MA quedará en módulo 28 como
T@ quedará en módulo 28 como

Con ello se puede afirmar que la palabra MAT cifrada es IACW.

Las operaciones matriciales efectuadas tienen como modelo matemático el producto de matrices de la forma:



Para descifrar se considera la matriz inversa



También puede visualizarse el cálculo de la forma:

Como que basta multiplicar esta matriz por su inversa y se obtiene

En general si denotamos A a la matriz para cifrar y M a la matriz del texto llano y X a la matriz del mensaje cifrado, podemos establecer la relación:

A · M = X, es decir: A = X · M-1,

De esta forma, si se desea conocer la clave A bastará con interceptar un solo mensaje M y su traducción X, ya que solamente con estos datos y la ayuda del álgebra lineal podremos encontrar la clave A.

En el ejemplo hemos considerado pares de dos caracteres, con lo cual podemos realizar 228 parejas. Para disminuir la vulnerabilidad se puede agrupar en pares de tres caracteres, cuatro caracteres...; para ello sería necesario considerar matrices de 3x3, 4x4, ...respectivamente, hecho que provocaría mayor seguridad, pero a su vez un aumento de la dificultad de cálculos.

Volviendo al ejemplo observamos la restricción de que el determinante de la matriz debe ser 1, ¿por qué? En el cálculo de la matriz inversa aparece involucrado el determinante como denominador, hecho que induce a tomar el determinante 1 ya que en caso contrario no podemos garantizar la existencia de inverso en aritmética modular.

En general un cifrado de Hill en el alfabeto español se obtiene al transformar series de n caracteres en un texto cifrado a través de una relación de la forma:

C = Av + b (mód. 28), siendo A (la clave) una matriz de nxn, v y b vectores columna de n elementos con la condición de que mcd (det(A), 28)=1 para garantizar la existencia de la matriz inversa.

Cifrado Hill: un modelo matricial para criptografía

Sea n indica la cantidad de elementos de un alfabeto, para cada matriz invertible, y para cada vector formalmente el cifrado Hill consiste en una aplicación lineal f definida como:



La matriz A es la clave, nótese que tendremos tantas claves posibles como matrices invertibles. Se puede demostrar que A es invertible si mcd (det(A), n)=1. Nótese también que tendremos 2n posibles parejas, hecho que dificulta la vulnerabilidad.

Para descifrar basta con realizar:

De la expresión y = A·x + b nos interesa el valor de x, procedemos como: y - b= A · x
A-1 · (y - b) = x.

El cifrado Hill puede generalizarse para bloques formados por k caracteres (con k>2) con matrices de orden k. Con ello tendremos kn posibilidades.

Suscríbase al newsletter

© 2019 JUEGOS Y DESAFIOS MATEMÁTICOS