ALG: Criptografía basada en matrices

En criptografía clásica, el Cifrado Hill es un cifrado de sustitución poligráfica basado en el álgebra lineal. Inventado por Lester S. Hill en 1929, fue el primer cifrado poligráfico que era práctico para operar sobre más de tres símbolos inmediatamente. El artículo siguiente supone un conocimiento elemental de matrices.

Método

Cada letra está representada por un número. A menudo el esquema más sencillo es A = 1, B = 2, …, Z = 26 (o Z=27 si incluimos Ñ), pero esto no es una característica esencial del cifrado. Para encriptar un mensaje, cada bloque de n letras (considerados como un vector) está multiplicado por una matriz invertible n×n (modular 26). Para desencriptar el mensaje, cada bloque es multiplicado por el inverso de la matriz usada para la encriptación.

La matriz usada para la encriptación es la llave de cifrado, y tiene que ser escogida aleatoriamente del conjunto de matrices invertibles n×n (modular 26). El cifrado puede, naturalmente, ser adaptado a un alfabeto representado con cualquier orden numérico y/o cambiando el número (modular 26) siempre y cuando la matriz n×n (modular x) sea invertible.

En nuestro caso, y para facilitar el trabajo, consideraremos una matriz invertible sin tener en cuenta el paso a módulo 26. Veámoslo con un ejemplo.

Proceso de cifrado

\[{ }[ 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] \]

Subespacio generador

Hoy veremos cómo utilizamos maxima para tratar espacios vectoriales. Por ejemplo, podemos determinar la relación lineal de un conjunto de vectores haciendo transformaciones elementales.

Comencemos con un ejercicio que hicimos anteriormente:

Ejercicio: Determinar si \(\begin{bmatrix}-3&2&8\\ -1&9&3\end{bmatrix}\) pertenece al subesapcio \(S=\mathbf{Gen}\left\{\begin{bmatrix}-1&0&4\\ 1&1&5\end{bmatrix},\begin{bmatrix}0&1&-2\\ -2&3&-6\end{bmatrix}\right\}\).

Solución:

Sabemos que un conjunto de vectores \(\textbf{v}_1,\textbf{v}_2,\ldots,\textbf{v}_n\) son linealmente independientes si \(\textbf{rank}([\textbf{v}_1,\textbf{v}_2,\ldots,\textbf{v}_n])=n\), luego \(\textbf{u}\in \textbf{Gen}\{\textbf{v}_1,\textbf{v}_2,\ldots,\textbf{v}_n\}\) si \(\textbf{rank}([\textbf{v}_1,\textbf{v}_2,\ldots,\textbf{v}_n,\textbf{u}])=n\).

De este modo, si consideramos \(A\in\mathcal{M}_{(n+1)\times m}\) la matriz cuyas filas son \([\textbf{v}_1,\textbf{v}_2,\ldots,\textbf{v}_n,\textbf{u}]\) y mediante transformaciones elementales obtenemos \[[I_{n+1}\, |\, A] \sim [P\, |\, E],\] donde \(E\) es una matriz con la última fila todo ceros, entonces, si \(P=[p_{ij}]\), \[p_{(n+1)1}\textbf{v}_1+p_{(n+1)2}\textbf{v}_2+\ldots+p_{(n+1)n}\textbf{v}_n=-\textbf{u}.\]

Este procedimiento es ampliable a un conjunto \(\textbf{u}_i\in \textbf{Gen}\{\textbf{v}_1,\textbf{v}_2,\ldots,\textbf{v}_n\}\), \(i\in I=\{1,\ldots,k\}\): si \[[I_{n+k}\, |\, A] \sim [P\, |\, E],\] donde \(E\) es una matriz con las filas \(i>n\) todas ceros, entonces, \[-\textbf{u}_i=\sum_{j=1}^{n}p_{(n+i)j}\textbf{v}_j.\]

Veámoslo con algunos de los ejercicio realizados.

Ejercicio: ¿Quienes serían \(a\) y \(b\),números reales, tales que \(7X^3-3X^2-X-4\) es combinación lineal de \(-3X^3+X^2-X+2\), y, \(-X^3-2X+1\)?

Solución:

Ejercicio: Sea \(\textbf{u}=[7,11,20,-9]\in Gen\{[-1,-3,0,1],[3,5,8,-3],[0,-1,2,1]\}\), ¿cuál es la suma de las coordenadas de \(\textbf{u}\) respecto de los vectores del espacio generador al que pertenece?.

Solución:

Solución: