Criptografía con matrices, el cifrado de Hill

El cifrado de Hill fue inventado, basándose en el álgebra lineal, por el matemático

norteamericano Lester S. Hill en 1929, y aparece explicado en su artículo Cryptography in
an Algebraic Alphabet, publicado en The American Mathematical Monthly.

Es un sistema criptográfico de sustitución polialfabético, es decir, un mismo signo, en este

caso una misma letra, puede ser representado en un mismo mensaje con más de un
carácter. Así, en el ejemplo que vamos a analizar a continuación, la letra A del mensaje
original aparece representada en el mensaje codificado de tres formas distintas, como C, K
e I.

Expliquemos en qué consiste el cifrado de Hill. En primer lugar, se asocia cada letra del
alfabeto con un número. La forma más sencilla de hacerlo es con la asociación natural
ordenada, aunque podrían realizarse otras asociaciones diferentes. Además, en este
ejemplo solamente vamos a utilizar las 27 letras del alfabeto, pero también podrían
añadirse otros símbolos usuales, como el espacio en blanco “_”, el punto “.” o la coma “,”,
la interrogación “?”, las 10 cifras básicas, etcétera.

Como en la correspondencia anterior, entre letras/signos y números, solamente aparecen

27 números, hay que trabajar con los números enteros “módulo 27”. Es decir, se
consideran los números enteros 0, 1, 2,… , 26 y 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étera, y lo mismo con los números
negativos, de forma que – 1 es igual 26, – 2 es igual 25, etcétera. Además, se reducen las
operaciones aritméticas (suma, resta, multiplicación y división) al conjunto de los números
enteros módulo 27 de forma natural, es decir, al operar dos números enteros (módulo 27)
el resultado se considera también módulo 27. Por ejemplo, si se realiza la multiplicación
de los números 6 y 13, módulo 27, el resultado dará 24 (módulo 27), puesto que 6  13 =
78 y 78 = 2  27 + 24. O el inverso de 2, es decir, el número a tal que 2  a es igual a 1
(módulo 27), es 14, puesto que 2  14 = 28, que es igual a 1, módulo 27.

En el cifrado de Hill se utiliza una matriz cuadrada de números A como clave, la cual
determina la transformación lineal Y = A ∙ X, donde Y, X son vectores columna y A y X se
multiplican con la multiplicación de matrices (véase la siguiente imagen). Veamos un
ejemplo. Consideremos la matriz cuadrada 3 x 3 (aunque en general pueden considerarse
matrices cuadradas de cualquier tamaño) siguiente y la correspondiente transformación
lineal Y = A ∙ X:

Supongamos que el mensaje que se quiere enviar encriptado es

“CUADERNO DE CULTURA CIENTIFICA”,

cuya transcripción numérica, teniendo en cuanta la tabla de sustitución 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ón lineal es de orden 3, vamos a agrupar los números en grupos de tres, en
ternas, sobre las que luego aplicaremos la transformación 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ón, vamos a transformar las ternas de números anteriores, mediante la

transformación lineal dada por la clave, en nuevas ternas, que serán el mensaje numérico
cifrado. ¡Ojo!, que en la transformación lineal no hay que olvidar que seguimos trabajando
con los números enteros módulo 27.
 .

Aunque la transformación lineal de la terna (2, 21, 0) es inicialmente (44, 84, 2), como
estamos trabajando con enteros módulo 27, esta terna se convierte en (17, 3, 2), ya que
44 = 1 x 27 + 17 y 84 = 3 x 27 + 3. E igual para el resto.
 .

Por lo tanto, el mensaje numérico 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úmeros en sus
correspondientes letras, se convierte en el mensaje cifrado
“QDCLYDYUEQFVGWCXKDBAFXDWMII”.

Y este es el mensaje que se envía para que no sea comprendido por el “enemigo” aunque
este lo intercepte en el camino.

Imágenes de la patente US 1.845.947 presentada por Lester S. Hill y Louis Weisner,

quienes diseñaron una máquina que implementaba el cifrado de Hill de orden 6

Para poder descodificar los mensajes cifrados mediante el método de Hill se necesita que
la matriz de la transformación 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ás, la
matriz inversa de A, que es la necesaria para descodificar un mensaje cifrado, es

Pero ojo, estamos trabajando con los enteros módulo 27 y vamos a transformar la matriz
inversa anterior en una matriz con números enteros módulo 27. Para empezar se necesita
el inverso del número 22. Se ve fácilmente que 22  16 = 352, que es igual a 1, módulo 27,
luego 1/22 = 16. Y la matriz inversa se transforma, módulo 27, en

Expliquemos ahora el proceso de descodificación de un mensaje. Imaginemos que el

receptor recibe el siguiente mensaje

“EHAHTDINRKQOPUSKVLKMUFÑG”,
y quiere conocer su significado. Para descodificar el mensaje hay que utilizar el mismo
método anterior, el cifrado de Hill, pero utilizando como clave la matriz inversa A -1
(módulo 27) de la matriz A de codificación.

Por lo tanto, se empieza de nuevo transformando el mensaje en la sucesión de ternas

numéricas 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ón lineal con
matriz A-1, es decir, Y = A-1 ∙ X.
.

.
 .

En consecuencia, la secuencia de ternas numéricas 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úmeros a sus correspondientes letras del alfabeto se obtiene
que el mensaje original enviado es

“DIVULGANDO LAS MATEMATICAS”.

Máquina de cifrado M-94 utilizada por el ejército de los Estados Unidos de América entre
los años 1922 y 1945, que consta de 25 discos con las letras del alfabeto. Imagen de la
página Cipher MachinesSin embargo, el cifrado de Hill no es seguro. Utilizando métodos
de álgebra lineal en un “ataque con texto claro conocido” puede romperse el código y
descubrir la matriz clave de encriptado. Un ataque con texto claro conocido significa que
el analista que quiere romper el código dispone de un ejemplo de “texto en claro”, es
decir, de un mensaje original, con el correspondiente mensaje cifrado.

Veamos cómo se puede romper este código. Supongamos que estamos utilizando la
matriz clave anterior A = (1 2 3 / 0 4 5 / 1 0 6), y que el analista “enemigo” ha conseguido
obtener tanto un mensaje original como el correspondiente mensaje cifrado. Por ejemplo,
el primero de los utilizados en esta entrada del Cuaderno de Cultura Científica.

MENSAJE ORIGINAL: “CUADERNO DE CULTURA CIENTIFICA”

(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)

MENSAJE CIFRADO: “QDCLYDYUEQFVGWCXKDBAFXDWMII”

(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)

Para romper el código se utiliza el “método de Gauss Jordan” (pero módulo 27) con la
matriz asociada al mensaje original y la matriz del mensaje cifrado:

Aunque esta última parte de la presente entrada es muy interesante, debido a que nos
muestra una aplicación del método de Gauss Jordan, también es un poco técnica, por lo
que las personas que lo deseen pueden saltársela y considerar simplemente que es
posible romper el cifrado de Hill, mediante técnicas de álgebra lineal.

El método de Gauss Jordan consiste realizar una serie de operaciones sobre la anterior
matriz, que está dividida en dos partes, la correspondiente al mensaje original y la del
mensaje cifrado, para conseguir que en la parte de la izquierda quede la matriz identidad
(1 0 0 / 0 1 0 / 0 0 1) en tres de las filas, para considerar entonces la parte correspondiente
de la derecha, como se mostrará después. Esas operaciones consisten en sustituir cada fila
de la matriz por el resultado de sumarle/restarle a esa fila una combinación lineal de
algunas de las otras filas.

Como el elemento que está en la primera fila y la primera columna tiene que ser un 1,
para conseguir la matriz identidad, y resulta que es un 2, debemos dividir por 2 (módulo
27) la primera fila. Ya hemos comentado al principio que el inverso de 2 (módulo 27) es
14, luego dividir por 2 es igual a multiplicar por 14 (módulo 27).

Al multiplicar la primera fila (2 21 0 : 17 3 2) por 14 (módulo 27) se transforma en (1 24 0 :

22 15 1). Ahora, para conseguir un 0 en la primera posición de cada fila se realiza las
siguientes sustituciones (método de Gauss Jordan):

a) “2ª fila” se sustituye por “2ª fila” – 3 x “1ª fila” (módulo 27)

b) “3ª fila” se sustituye por “3ª fila” – 13 x “1ª fila” (módulo 27)

c) “4ª fila” se sustituye por “4ª fila” – 4 x “1ª fila” (módulo 27)

d) “5ª fila” se sustituye por “5ª fila” – 11 x “1ª fila” (módulo 27)

e) “6ª fila” se sustituye por “6ª fila” – 18 x “1ª fila” (módulo 27)

y así podría seguirse con el resto, aunque no necesitamos las tres últimas filas para
conseguir nuestro objetivo. En cualquier caso, después de las sustituciones anteriores, la
matriz se ha transformado en la siguiente matriz

.
Ahora queremos conseguir un 1 en la posición que se corresponde con la segunda fila y la
segunda columna, de nuevo buscando conseguir la matriz identidad en la parte de la
izquierda. Como en esa posición está el 13, debemos buscar su inverso módulo 27, que
resulta que es 25 (ya que 13 x 25 = 325, que tomando módulo 27, es igual a 1). Es decir,
hay que multiplicar la segunda fila por 25, de manera que esta segunda fila (0 13 18 : 26 7
0) se transforma, al multiplicarla por 25 (módulo 27) en (0 1 18 : 2 13 0). Y ahora
buscamos obtener ceros en la segunda posición de las demás filas mediante las siguientes
sustituciones (método de Gauss Jordan):

f) “1ª fila” se sustituye por “1ª fila” – 24 x “2ª fila” (módulo 27)

g) “4ª fila” se sustituye por “4ª fila” – 14 x “2ª fila” (módulo 27)

h) “5ª fila” se sustituye por “5ª fila” – 26 x “2ª fila” (módulo 27)

quedando ahora la matriz como sigue

El siguiente paso sería conseguir un 1 en la posición que se corresponde con la tercera fila
y la tercera columna, una vez más buscando conseguir la matriz identidad en la parte de la
izquierda. Sin embargo, en este momento nos encontramos con una primera anomalía por
trabajar módulo 27, y es que los números enteros módulo 27 admiten “divisores de cero”,
como el 3 y el 9, ya que el producto de 3 por 9 es igual a 0 (módulo 27), y estos no tienen
inverso.

En consecuencia, no se puede conseguir un 1 en la tercera columna de las filas 3, 4 y 5. Y

al multiplicarlas por 9 se anulan todos sus elementos, luego esas tres filas no nos
interesan.

Por lo tanto, vamos a intentar conseguir un 1 en la tercera columna de la fila 6, para lo

cual tenemos que multiplicar por el inverso de 2, que como ya sabemos es 14. Y al fila 6
pasa de (0 0 2 : 6 10 12) a (0 0 1 : 3 5 6), al multiplicarla por 14.

Y para obtener la matriz identidad en la parte de la izquierda solo nos falta convertir el 18
que está en la tercera columna de la segunda fila en un cero, para lo cual realizamos la
siguiente sustitución

i) “2ª fila” se sustituye por “2ª fila” – 18 x “6ª fila” (módulo 27)

y la matriz queda finalmente, después de todo este proceso de Gauss Jordan,

.
Luego, tras el método de Gauss Jordan (módulo 27), en la parte de la derecha de la matriz,
correspondiéndose con la matriz identidad de la izquierda, nos queda la siguiente matriz

Que es la matriz traspuesta (es decir, se cambian las filas por columnas, y al revés) de la
matriz clave utilizada en el ejemplo que hemos visto de encriptación de Hill.

En consecuencia, el álgebra lineal que ha servido para desarrollar el cifrado de Hill,

también sirve para romper su código.

Una forma de evitar lo anterior, es modificar el algoritmo del cifrado de Hill para que la
matriz clave no sea fija, sino que sea dinámica.
Bibliografía

1.- Raúl Ibáñez, Arthur Cayley, explorador victoriano del territorio matemático, RBA, 2017
(pendiente de publicación).

2.- Marie-José Pestel, Paul Kichilov, de la gravure à la anamorphose, Tangente Hors-serie

23: Maths et arts plastiques, p. 142-147.

3.- Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical

Monthly, vol. 36, n. 6 (1929). p. 306-312.

4.- Jorge Ramió Aguirre, Seguridad Informática y criptografía (libro electrónico),

Universidad Politécnica de Madrid, 2006.

5.- OnlineMSchool, Online calculadoras para solucionar problemas matemáticas

6.- Calculadora de los números enteros modulares

Sobre el autor: Raúl Ibáñez es profesor del Departamento de Matemáticas de la UPV/EHU

y colaborador de la Cátedra de Cultura Científica