ALG: Criptografía con matrices

El cifrado matricial (conocido históricamente como una variante del Cifrado de Hill) es una aplicación directa del álgebra lineal donde la clave secreta es una matriz invertible.

¿Cómo funciona el Cifrado Matricial?

El proceso consta de cuatro pasos fundamentales:

1. Sustitución numérica: Convertimos cada letra del mensaje en un número siguiendo un diccionario prefijado.

2. Vectorización: Agrupamos la secuencia de números en vectores fila de tamaño $1 \times n$. Si la longitud total del texto no es múltiplo de $n$, añadimos letras de relleno (padding) al final.

3. Cifrado: Elegimos una matriz cuadrada $A$ de dimensión $n \times n$ que sea invertible ($\det(A) \neq 0$). Multiplicamos cada vector fila $X$ por la derecha por la matriz $A$:

$$Y = X \cdot A$$

4. Descifrado: El receptor multiplica cada vector cifrado $Y$ por la derecha por la matriz inversa $A^{-1}$ para recuperar el mensaje original:

$$Y \cdot A^{-1} = (X \cdot A) \cdot A^{-1} = X \cdot I = X$$

Ejemplo práctico: «Las matemáticas en criptografía»

1. Definición del Alfabeto

Utilizaremos el alfabeto castellano de 27 letras (A–Z incluyendo la Ñ), sin espacios, mapeado de 1 a 27:

2. Preparación y Vectorización del Texto

* Frase limpia: «LASMATEMATICASENCRIPTOGRAFIA»
* Longitud: 28 letras.
* Agrupación ($3 \times 3$): Para usar una matriz de $3 \times 3$, necesitamos que la longitud sea múltiplo de 3. Añadimos dos letras «X» (valor 25) al final para completar 30 caracteres.
* Texto final con relleno: «LASMATEMATICASENCRIPTOGRAFIAXX»

Agrupamos el texto en 10 bloques de 3 caracteres (vectores de $1 \times 3$):

1. «L A S» $\rightarrow [12, 1, 20]$
2. «M A T» $\rightarrow [13, 1, 21]$
3. «E M A» $\rightarrow [5, 13, 1]$
4. «T I C» $\rightarrow [21, 9, 3]$
5. «A S E» $\rightarrow [1, 20, 5]$
6. «N C R» $\rightarrow [14, 3, 19]$
7. «I P T» $\rightarrow [9, 17, 21]$
8. «O G R» $\rightarrow [16, 7, 19]$
9. «A F I» $\rightarrow [1, 6, 9]$
10. «A X X» $\rightarrow [1, 25, 25]$

3. Matriz Clave ($A$) y Multiplicación

Elegimos la matriz invertible $A$ de $3 \times 3$:

$$A = \begin{bmatrix} 1 & -2 & 2 \\ -1 & 1 & 3 \\ 1 & -1 & -4 \end{bmatrix}$$

Al realizar el producto matricial $Y_i = X_i \cdot A$ para cada bloque:

* $[12, 1, 20] \cdot A = [31, -43, -53]$
* $[13, 1, 21] \cdot A = [33, -46, -55]$
* $[5, 13, 1] \cdot A = [-7, 2, 45]$
* $[21, 9, 3] \cdot A = [15, -36, 57]$
* $[1, 20, 5] \cdot A = [-14, 13, 42]$
* $[14, 3, 19] \cdot A = [30, -44, -39]$
* $[9, 17, 21] \cdot A = [13, -22, -15]$
* $[16, 7, 19] \cdot A = [28, -44, -23]$
* $[1, 6, 9] \cdot A = [4, -5, -16]$
* $[1, 25, 25] \cdot A = [1, -2, -23]$

Criptograma final enviado por el canal de comunicación:
«31, -43, -53, 33, -46, -55, -7, 2, 45, 15, -36, 57, -14, 13, 42, 30, -44, -39, 13, -22, -15, 28, -44, -23, 4, -5, -16, 1, -2, -23»

Con maxima

\[{ }[ 12{,}1{,}3{,}12{,}1{,}23{,}5{,}5{,}20{,}21{,}1{,}5{,}14{,}19{,}5{,}2{,}5{,}3{,}1{,}25{,}25] \]

\[{ }\left[ \left[ 12{,}1{,}3\right] {,}\left[ 12{,}1{,}23\right] {,}\left[ 5{,}5{,}20\right] {,}\left[ 21{,}1{,}5\right] {,}\left[ 14{,}19{,}5\right] {,}\left[ 2{,}5{,}3\right] {,}\left[ 1{,}25{,}25\right] \right] \]

\[{ }\left[ \begin{bmatrix}11\\-20\\6\end{bmatrix}{,}\begin{bmatrix}11\\-80\\-14\end{bmatrix}{,}\begin{bmatrix}0\\-60\\-30\end{bmatrix}{,}\begin{bmatrix}20\\-35\\13\end{bmatrix}{,}\begin{bmatrix}-5\\-10\\-48\end{bmatrix}{,}\begin{bmatrix}-3\\-6\\-16\end{bmatrix}{,}\begin{bmatrix}-24\\-51\\-99\end{bmatrix}\right] \]

\[{ }[ 11{,}-20{,}6{,}11{,}-80{,}-14{,}0{,}-60{,}-30{,}20,\]\[\left.-35{,}13{,}-5{,}-10{,}-48{,}-3{,}-6{,}-16{,}-24{,}-51{,}-99\right] \]

\[{ }\left[ 12{,}1{,}3{,}12{,}1{,}23{,}5{,}5{,}20{,}21{,}1{,}5{,}14{,}19{,}5{,}2{,}5{,}3{,}1{,}25{,}25\right] \]

En búsqueda de la matriz de cifrado

Pensemos que tenemos un texto cifrado y sabemos cuál es el texto, pero no sabemos la matriz con la que se ha cifrado, pero sí su orden. Nuestro propósito: encontrar la matriz de cifrado.

Para plantear el proceso de hallazgo de la matriz clave $A$ mediante un sistema de ecuaciones lineales, convertimos el texto claro a su representación numérica usando el alfabeto español de 27 letras (donde A=1, B=2, …, Ñ=15, …, Z=27), ignorando espacios y tildes.

Qué sabemos:

• Texto original: «La clave está en Rebeca»
• Cifrado:[23,-35,-6,3,-21,20,5,-10,19,-39,-3,2,9,-23,8,-13,7,-12,-23,22]
• \(A\in\mathcal{M}_2(\mathbb{R})\)

1. Conversión de texto a vectores

El texto «La clave está en Rebeca» se procesa agrupando las letras en pares (columnas de 2 elementos) para coincidir con la matriz $A_{2 \times 2}$:

* Par 1: L (12), a (1)
* Par 2: c (3), l (12)
* Par 3: a (1), v (23)
* Par 4: e (5), e (5)
* …y así sucesivamente.

El texto cifrado proporcionado se organiza en columnas correspondientes:

$$C = \begin{bmatrix} 23 & -6 & -21 & 5 & \dots \\ -35 & 3 & 20 & -10 & \dots \end{bmatrix}$$

2. Planteamiento matricial $A \cdot t_i = C_i$

Definimos la matriz incógnita $A$ y la matriz de texto claro $P$:

$$\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} 12 \\ 1 \end{bmatrix} = \begin{bmatrix} 23 \\ 3 \end{bmatrix}$$

$$\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} 3 \\ 12 \end{bmatrix} = \begin{bmatrix} -6 \\ 3 \end{bmatrix}$$

Al multiplicar la matriz $A$ por las dos primeras columnas de texto claro, se generan las ecuaciones necesarias para determinar las 4 incógnitas.

3. Sistema de ecuaciones lineales

El sistema completo de 4 ecuaciones se descompone en dos sistemas independientes de $2 \times 2$:

Sistema para la primera fila de $A$ ($a_{11}$ y $a_{12}$):

$$\begin{cases} 12 a_{11} + 1 a_{12} = 23 \\ 3 a_{11} + 12 a_{12} = -6 \end{cases}$$

Sistema para la segunda fila de $A$ ($a_{21}$ y $a_{22}$):

$$\begin{cases} 12 a_{21} + 1 a_{22} = -35 \\ 3 a_{21} + 12 a_{22} = 3 \end{cases}$$

4. Resolución de los sistemas

Resolviendo el primer sistema:

1. De la primera ecuación: $a_{12} = 23 – 12 a_{11}$
2. Sustituyendo en la segunda ecuación:

$$3 a_{11} + 12(23 – 12 a_{11}) = -6$$

$$3 a_{11} + 276 – 144 a_{11} = -6$$

$$-141 a_{11} = -282 \implies a_{11} = 2$$

3. Sustituyendo el valor de $a_{11}$:

$$a_{12} = 23 – 12(2) = -1$$

Resolviendo el segundo sistema:

1. De la primera ecuación: $a_{22} = -35 – 12 a_{21}$
2. Sustituyendo en la segunda ecuación:

$$3 a_{21} + 12(-35 – 12 a_{21}) = 3$$

$$3 a_{21} – 420 – 144 a_{21} = 3$$

$$-141 a_{21} = 423 \implies a_{21} = -3$$

3. Sustituyendo el valor de $a_{21}$:

$$a_{22} = -35 – 12(-3) = 1$$

Matriz Clave $A$

La matriz de cifrado que satisface el sistema es:

$$A = \begin{bmatrix} 2 & -1 \\ -3 & 1 \end{bmatrix}$$

Veamos si hemos acertado:
$$\begin{bmatrix} 2 & -1 \\ -3 & 1 \end{bmatrix}\begin{bmatrix} 1 \\ 23 \end{bmatrix} = \begin{bmatrix} -21 \\ 20 \end{bmatrix}$$
$$\begin{bmatrix} 2 & -1 \\ -3 & 1 \end{bmatrix}\begin{bmatrix} 5 \\ 5 \end{bmatrix} = \begin{bmatrix} 5 \\ -10 \end{bmatrix}$$
$$\begin{bmatrix} 2 & -1 \\ -3 & 1 \end{bmatrix}\begin{bmatrix} 20 \\ 21 \end{bmatrix} = \begin{bmatrix} 19 \\ -39 \end{bmatrix}$$
Y así sucesivamente. Hemos probado que la matriz hallada es la buscada.

Aumentando la dificultad

Supongamos que no conocemos el orden de la matriz con la que hemos cifrado el texto.
Qué sabemos:

• Texto original: «Sol, sol y luna. Sol, sol y tierra quemada»
• Cifrado:[4, -40, -40, 4, -40, -40, 14, -80, -32, 13, -73, -9, 4, -64, -40, 4, -82, -46, 12, -27, -11, 0, -3, -39, -4, -11, -53, 12, -24, 6]
• \(A\in\mathcal{M}_n(\mathbb{R})\) (No sabemos el valor de \(n\))

Utilizaremos el alfabeto estándar de 27 letras ($A=1, B=2, \dots, Ñ=15, \dots, Z=27$). Limpiando espacios y signos de puntuación, las 30 letras del texto limpio se traducen numéricamente así: Secuencia: [20, 16, 12, 20, 16, 12, 26, 12, 22, 14, 1, 20, 16, 12, 20, 16, 12, 26, 21, 9, 5, 19, 19, 1, 18, 22, 5, 13, 1, 4].

Hipótesis: Supongamos que la matriz es de $2 \times 2$

Imaginemos que un analista asume que la matriz clave $A$ es de dimensión $2 \times 2$. En ese caso, dividimos el texto en bloques de 2 letras (vectores fila de $1 \times 2$):

1. Primer bloque «S O»: $[20, 16]$ $\rightarrow$ Cifrado interceptado: $[4, -40]$
2. Segundo bloque «L S»: $[12, 20]$ $\rightarrow$ Cifrado interceptado: $[-40, 4]$

Planteamos la multiplicación matricial para encontrar la matriz incógnita $A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}$:

$$\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}\begin{bmatrix} 20 \\ 12 \end{bmatrix} = \begin{bmatrix} 4 \\ 40 \end{bmatrix}$$
$$\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}\begin{bmatrix} 16 \\ 20 \end{bmatrix} = \begin{bmatrix} -40 \\ 1 \end{bmatrix}$$

Al resolver este sistema de 4 ecuaciones lineales con 4 incógnitas, obtenemos una solución matemática única:

$$A_{cand} = \begin{bmatrix} \frac{45}{13} & -\frac{54}{13} \\ -\frac{53}{13} & \frac{35}{13} \end{bmatrix} $$

Matemáticamente, esta matriz satisface de forma perfecta los dos primeros bloques. ¿Significa eso que hemos descubierto la clave secreta?

La prueba de fuego: Validación global

Para comprobar si $A_{cand}$ es válida, intentamos cifrar el tercer bloque del texto, «O L» $= [16, 12]$:

$$ \begin{bmatrix} \frac{45}{13} & -\frac{54}{13} \\ -\frac{53}{13} & \frac{35}{13} \end{bmatrix} \begin{bmatrix} 16 \\ 12 \end{bmatrix} = \begin{bmatrix} \frac{84}{13}\\ -\frac{444}{13} \end{bmatrix} \approx \begin{bmatrix} 6.46 \\ -34.15 \end{bmatrix}$$

Sin embargo, los números 5 y 6 que realmente aparecen en el texto cifrado interceptado son $[-40, -40]$.

El resultado obtenido no coincide en absoluto con el cifrado real (además de no ser siquiera valores enteros). La matriz $A_{cand}$ falla estrepitosamente al intentar codificar el resto del mensaje.

Este es un error conceptual muy común al intentar romper o descifrar un mensaje mediante un ataque de texto claro conocido.

A menudo, los alumnos asumen que, si logran plantear y resolver un sistema de ecuaciones para encontrar una matriz clave candidata, esa matriz es automáticamente la correcta.

En resumen, forzar la resolución de un sistema tomando solo los primeros datos nos dará una solución matemática para esos datos en concreto, pero no garantiza la validez global si la hipótesis de partida es falsa. En criptografía y en aprendizaje automático (machine learning), verificar la consistencia con todo el conjunto de datos es indispensable para validar cualquier modelo.

Independencia lineal en la práctica

Para resolver el problema anterior, vemos que una matriz de $2 \times 2$ no servía. El siguiente paso natural es probar si el mensaje fue cifrado mediante una matriz de $3 \times 3$.

Como una matriz de $3 \times 3$ tiene 9 incógnitas ($a_{11}, a_{12}, \dots, a_{33}$), la teoría nos dice que necesitaremos al menos 9 ecuaciones escalares para encontrarla. Dado que cada bloque de 3 letras nos genera 3 ecuaciones, parece que bastaría con tomar los 3 primeros bloques del texto.

Sin embargo, aquí es donde muchos estudiantes tropiezan con un concepto clave del álgebra lineal: no basta con tener 9 ecuaciones, tienen que ser linealmente independientes.

1. El problema de las 9 primeras ecuaciones

Escribamos el texto claro agrupado en bloques de 3 letras ($1 \times 3$) y sus correspondientes valores numéricos:

1. Bloque 1 «S O L»: $[20, 16, 12]$ $\rightarrow$ Cifrado: $[4, -40, -40]$
2. Bloque 2 «S O L»: $[20, 16, 12]$ $\rightarrow$ Cifrado: $[4, -40, -40]$
3. Bloque 3 «Y L U»: $[26, 12, 22]$ $\rightarrow$ Cifrado: $[14, -80, -32]$

Si intentamos plantear el sistema matricial $X \cdot A = Y$ tomando los 3 primeros bloques de texto claro para formar la matriz $X$:

$$X = \begin{bmatrix} 20 & 16 & 12 \\ 20 & 16 & 12 \\ 26 & 12 & 22 \end{bmatrix}$$
Observar que, en este ejemplo, estamos tomando el sistema traspuesto; es decir, $X \cdot A = Y$ en vez de $A \cdot X = Y$, donde pondríamos los vectores en columna en la matriz.

Al calcular el determinante de esta matriz de coeficientes: $$\det(X) = 0$$
El considerar el sistema traspuesto no afecta a este resultado, ya que \(\det(X)=\det(X^t)\)

¿Por qué el determinante es 0?
Porque la primera y la segunda fila son idénticas (corresponden a la palabra «SOL» repetida).

Conclusión matemática

El sistema de 9 ecuaciones resultante es compatible indeterminado. No nos falta información por cantidad de datos, sino por calidad (rango). La segunda fila no aporta ninguna información nueva sobre la matriz $A$; tenemos en realidad un sistema de rango 2 con infinitas soluciones.

2. Cómo descubrir la matriz de $3 \times 3$ real

Para poder calcular una matriz clave única $A$, necesitamos que las filas de la matriz de texto claro $X$ formen una base en $\mathbb{R}^3$ (es decir, que sean 3 vectores linealmente independientes).

Simplemente descartamos el bloque repetido y elegimos el siguiente bloque disponible en el texto que no sea combinación lineal de los anteriores, por ejemplo, el cuarto bloque «N A S» $= [14, 1, 20]$.

Construimos la nueva matriz de texto claro $X_{indep}$ y su correspondiente matriz cifrada $Y_{indep}$:

$$X_{indep} = \begin{bmatrix} 20 & 16 & 12 \\ 26 & 12 & 22 \\ 14 & 1 & 20 \end{bmatrix}, \quad Y_{indep} = \begin{bmatrix} 4 & -40 & -40 \\ 14 & -80 & -32 \\ 13 & -73 & -9 \end{bmatrix}$$

Comprobamos el determinante de $X_{indep}$:

$$\det(X_{indep}) = -736 \neq 0$$

Como el determinante es distinto de cero, el rango es 3 y la matriz $X_{indep}$ es invertible (o regular).

3. Cálculo de la clave secreta $A$

Multiplicando por la izquierda por la inversa de $X_{indep}$:

$$A = X_{indep}^{-1} \cdot Y_{indep}$$

Al realizar el cálculo (o resolver el sistema), obtenemos de forma única la matriz clave:

$$A = \begin{bmatrix} 1 & -1 & 1 \\ -1 & 1 & -3 \\ 0 & -3 & -1 \end{bmatrix}$$

Solo nos quedaría verificar que con esta matriz podemos cifrar el resto del mensaje y obtener los mismos resultados.

Lección a recordad

1. La dependencia lineal destruye la unicidad: Un sistema con el número «correcto» de ecuaciones puede ser no resoluble de forma única si los datos de entrada son redundantes.
2. Cuidado con los patrones en el texto claro: Las palabras repetidas en el mensaje original («SOL», «SOL») producen ecuaciones linealmente dependientes en el criptoanálisis.
3. Validación: La independencia lineal nos permite hallar la matriz, pero probar la matriz en bloques no usados es lo que nos confirma que el modelo de dimensión $3 \times 3$ era el correcto.