Criptografía (CXXIX): Solución Reto 27

El  enunciado del reto de criptografía que puse en este post era el siguiente:

"Como en otros retos que he puesto en este blog, la persona que aparece en la imagen que ilustra este post nos dirá qué criptosistema se ve involucrado, lo que además confirmaremos con la pista dada al inicio. Una vez que hayas averiguado lo anterior, supón que interceptas el siguiente criptograma:

"ZVMVCWQKXVUNPOHOKUOJTSZLGIULKCBQALFQFGBFILXIBWGC",

y que además sabes o infieres que el inicio del mismo se corresponde con el siguiente texto en claro: “THESOLUTION”.¿Puedes descifrar el criptograma y obtener así la solución de este reto?".

Solución: En el enunciado decía que si sabes o averiguas quién es la persona que aparece en la imagen que ilustra este post entonces también sabrás el criptosistema involucrado en este reto. Pues bien, busco con 'Google imágenes' y obtengo:

Este resultado coincide con lo que se dice al inicio del post en el que se enunció este reto respecto a que el criptosistema involucrado fue inventando por un matemático americano, y la Wikipedia nos cuenta que entre las notables aportaciones de Lester S. Hill se encuentra el conocido como cifrado de Hill.

Una vez que hemos averiguado que el texto en claro se ha cifrado utilizando el criptosistema ideado por Hill en 1929 y suponiendo, por lo que conocemos de él y por el criptograma, que está escrito en inglés y que el alfabeto utilizado se reduce a las letras mayúsculas de dicho idioma (A = 0, B = 1, C = 2, ..., Z = 25), implemento el ataque de 3 maneras diferentes:

1.- Mediante "lápiz y papel", es decir, manualmente.
2.- Utilizando una herramienta especializada.
3.- Creando un pequeño script en python para resolver el reto.

Pero antes que nada recordar que el cifrado de Hill funciona multiplicando una matriz (K) cuadrada de orden k (k filas y k columnas), que se utiliza como clave para cifrar, por cada uno de los bloques de longitud k del texto en claro (M), mientras que el descifrado se realiza multiplicando la matriz inversa de la que se ha empleado como clave en el cifrado (K⁻¹)  por cada uno de los bloques de longitud k del mensaje cifrado o criptograma (C).

Tanto el cifrado como el descifrado se producen en el módulo (n) correspondiente al tamaño del alfabeto (en nuestro caso el número de caracteres en mayúsculas del idioma inglés, es decir, 26).

Dicho lo anterior, si conocemos parte del texto en claro y su correspondiente texto cifrado, siempre que podamos conocer el alfabeto utilizado, es decir, el módulo (n), y determinar el orden (k) de la matriz cuadrada empleada como clave (K), o lo que es lo mismo el tamaño del bloque (número de símbolos del texto en claro / criptograma que se cifran / descifran de forma simultánea - bigramas, trigramas, etc.), a partir de una matriz con el texto claro conocido (M) podemos calcular la matriz K⁻¹ con la que descifrar el criptograma (C), de la siguiente manera:

C = K M

K = M^-1 C

K^-1 sería la matriz de descifrado

1.- Solución manual ("Lápiz y papel"):

Tal y como he dicho, para implementar este ataque es necesario conocer el orden (k) de la matriz cuadrada empleada como clave (K) o, lo que es lo mismo, el tamaño del bloque, y sabemos que éste tiene que ser un factor del número de caracteres del texto cifrado (C). Es decir, en nuestro caso 48, tamaño del criptograma, tiene que ser múltiplo de k. Así que nuestros posibles valores de tamaño de bloque son: 2, 3, 4, 6, 8, 12, 16, 24, 48.

También sabemos que, debido a que la matriz utilizada como clave (K) es cuadrada (k x k), para que este ataque pueda prosperar necesitamos tener al menos k² letras de texto plano conocido (en nuestro caso conocemos 11 caracteres, “THESOLUTION”). Por tanto:

2² = 4; 4 < 11

3² = 9; 9 < 11
4² = 16; 16 > 11
...

Esto significa que para que podamos tener éxito con este ataque, se debe haber utilizado un tamaño de bloque de 2 ó 3, ya que si éste fuera mayor no conoceríamos los suficientes caracteres del texto en claro para resolver este reto y esto no tendría ninguna gracia :).

Cuatro caracteres como clave me parecen pocos, por lo que voy a suponer inicialmente que la clave utilizada tiene 9 caracteres (3 x 3), y si no consigo nada probaré con 4.

Ya que estamos trabajando con una matriz de 3 × 3, nuestro texto claro conocido, "THESOLUTION", se reduce a una longitud de bloque 9 (3 x 3): "THESOLUTI".

Por tanto, la matriz (M) con el texto claro conocido sería:

O utilizando la posición relativa de cada uno de esos caracteres en el alfabeto inglés (A = 0, B = 1, C = 2, ..., Z = 25):

Lo primero que hay que hacer es obtener la matriz inversa (M^-1) de la matriz con el texto claro conocido (M). Para ello utilizo la siguiente fórmula:

Donde:

M^-1: matriz inversa de M (matriz con el texto claro conocido).
C^T: matriz de cofactores de M transpuesta.

|M|: determinante de M, que debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 26.
(|M|)^-1: inverso del determinante de la matriz M. Debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 26.

Por tanto:

Por otra parte, la matriz (C) con la parte del criptograma correspondiente al texto claro conocido sería:

O utilizando la posición relativa de cada uno de esos caracteres en el alfabeto inglés (A = 0, B = 1, C = 2, ..., Z = 25):

Ahora calculamos (M^-1 C) mod 26:

(11 x 25 + 24 x 21 +   7 x 16) mod 26 = (275 + 504 + 112) mod 26 = 891 mod 26 = 7
(11 x 21 + 24 x   2 +   7 x 10) mod 26 = (231 +   48 +   70) mod 26 = 349 mod 26 = 11
(11 x 12 + 24 x 22 +   7 x 23) mod 26 = (132 + 528 + 161) mod 26 = 821 mod 26 = 15
(8   x 25 + 24 x 21 + 15 x 16) mod 26 = (200 + 504 + 240) mod 26 = 944 mod 26 = 8
(8   x 21 + 24 x   2 + 15 x 10) mod 26 = (168 +   48 + 150) mod 26 = 366 mod 26 = 2
(8   x 12 + 24 x 22 + 15 x 23) mod 26 = (  96 + 528 + 345) mod 26 = 969 mod 26 = 7
(12 x 25 + 13 x 21 + 12 x 16) mod 26 = (300 + 273 + 192) mod 26 = 765 mod 26 = 11
(12 x 21 + 13 x   2 + 12 x 10) mod 26 = (252 +   26 + 120) mod 26 = 398 mod 26 = 8
(12 x 12 + 13 x 22 + 12 x 23) mod 26 = (144 + 286 + 276) mod 26 = 706 mod 26 = 4

Y he obtenido la matriz transpuesta (K^T) de la utilizada como clave (K) en el cifrado, por lo que esta última sería:

Y ahora estoy ya en disposición de calcular la matriz de descifrado, que es la inversa (K^-1) de esta última matriz obtenida.

Donde:

K^-1: matriz inversa de K (matriz con la clave utilizada en el cifrado).
C^T: matriz de cofactores de K transpuesta.

|K|: determinante de K, que debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 26.
(|K|)^-1: inverso del determinante de la matriz K. Debe calcularse en mod n (tamaño del alfabeto), en nuestro caso en módulo 26.

El proceso para realizar este cálculo es el mismo que el desarrollado más arriba para obtener M^-1, por lo que me limito a indicar únicamente el resultado que se obtiene:

Y, finalmente, desciframos el criptograma. Como k = 3 procedo por bloques de 3 caracteres del criptograma.

Para el primer grupo de tres caracteres:

m1 = (12 x 25 +   5 x 21 + 22 x 12) mod 26 = 300 + 105 + 264 = 669 mod 26 = 19 =  T
m2 = (20 x 25 +   5 x 21 + 13 x 12) mod 26 = 500 + 105 + 156 = 761 mod 26 =   7 =  H
m3 = (11 x 25 +   5 x 21 + 12 x 12) mod 26 = 275 + 105 + 144 = 524 mod 26 =   4 =  E

Y así sucesivamente con el resto de bloques o grupos de tres caracteres del criptograma:

m4 = (12 x 21 +   5 x   2 + 22 x 22) mod 26 = 252 +   10 + 484 = 746 mod 26 = 18 =  S
m5 = (20 x 21 +   5 x   2 + 13 x 22) mod 26 = 420 +   10 + 286 = 716 mod 26 = 14 =  O
m6 = (11 x 21 +   5 x   2 + 12 x 22) mod 26 = 231 +   10 + 264 = 505 mod 26 = 11 =  L

m7 = (12 x 16 +   5 x 10 + 22 x 23) mod 26 = 192 +   50 + 506 = 748 mod 26 = 20 = U
m8 = (20 x 16 +   5 x 10 + 13 x 23) mod 26 = 320 +   50 + 299 = 669 mod 26 = 19 = T
m9 = (11 x 16 +   5 x 10 + 12 x 23) mod 26 = 176 +   50 + 276 = 502 mod 26 =   8 = I

m10 = (12 x 21 + 5 x 20 + 22 x 13) mod 26 = 252 + 100 + 286 = 638 mod 26 = 14 = O
m11 = (20 x 21 + 5 x 20 + 13 x 13) mod 26 = 420 + 100 + 169 = 689 mod 26 = 13 = N
m12 = (11 x 21 + 5 x 20 + 12 x 13) mod 26 = 231 + 100 + 156 = 487 mod 26 = 19 = T

m13 = (12 x 15 + 5 x 14 + 22 x   7) mod 26 = 180 +   70 + 154 = 404 mod 26 = 14 = O
m14 = (20 x 15 + 5 x 14 + 13 x   7) mod 26 = 300 +   70 +   91 = 461 mod 26 = 19 = T
m15 = (11 x 15 + 5 x 14 + 12 x   7) mod 26 = 165 +   70  +  84 = 319 mod 26 =   7 = H

m16 = (12 x 14 + 5 x 10 + 22 x 20) mod 26 = 168 +   50 + 440 = 658 mod 26 =   8 = I
m17 = (20 x 14 + 5 x 10 + 13 x 20) mod 26 = 280 +   50 + 260 = 590 mod 26 = 18 = S
m18 = (11 x 14 + 5 x 10 + 12 x 20) mod 26 = 154 +   50 + 240 = 444 mod 26 =   2 = C

m19 = (12 x 14 + 5 x  9 + 22 x 19) mod 26 = 168 +    45 + 418 = 631 mod 26 =  7 = H
m20 = (20 x 14 + 5 x  9 + 13 x 19) mod 26 = 280 +    45 + 247 = 572 mod 26 =  0 = A
m21 = (11 x 14 + 5 x  9 + 12 x 19) mod 26 = 154 +    45 + 228 = 427 mod 26 = 11 = L

m22 = (12 x 18 + 5 x 25 + 22 x 11) mod 26 = 216 + 125 + 242 = 583 mod 26 = 11 = L
m23 = (20 x 18 + 5 x 25 + 13 x 11) mod 26 = 360 + 125 + 143 = 628 mod 26 =   4 = E
m24 = (11 x 18 + 5 x 25 + 12 x 11) mod 26 = 198 + 125 + 132 = 455 mod 26 = 13 = N

m25 = (12 x   6 + 5 x  8 + 22 x 20) mod 26 =   72 +    40 + 440 = 552 mod 26 =   6 = G
m26 = (20 x   6 + 5 x  8 + 13 x 20) mod 26 = 120 +    40 + 260 = 420 mod 26 =   4 = E
m27 = (11 x   6 + 5 x  8 + 12 x 20) mod 26 =   66 +    40 + 240 = 346 mod 26 =   8 = I

m28 = (12 x 11 + 5 x 10 + 22 x   2) mod 26 = 132 +   50 +   44 = 226 mod 26 = 18 = S
m29 = (20 x 11 + 5 x 10 + 13 x   2) mod 26 = 220 +   50 +   26 = 296 mod 26 = 10 = K
m30 = (11 x 11 + 5 x 10 + 12 x   2) mod 26 = 121 +   50 +   24 = 195 mod 26 = 13 = N

m31 = (12 x   1 + 5 x 16 + 22 x   0) mod 26 =   12 +   80 +     0 =   92 mod 26 = 14 = O
m32 = (20 x   1 + 5 x 16 + 13 x   0) mod 26 =   20 +   80 +     0 = 100 mod 26 = 22 = W
m33 = (11 x   1 + 5 x 16 + 12 x   0) mod 26 =   11 +   80 +     0 =   91 mod 26 = 13 = N

m34 = (12 x 11 + 5 x  5 + 22 x 16) mod 26 = 132 +   25  + 352 = 509 mod 26 = 15 = P
m35 = (20 x 11 + 5 x  5 + 13 x 16) mod 26 = 220 +   25  + 208 = 453 mod 26 = 11 = L
m36 = (11 x 11 + 5 x  5 + 12 x 16) mod 26 = 121 +   25  + 192 = 338 mod 26 =   0 = A

m37 = (12 x   5 + 5 x  6 + 22 x   1) mod 26 =   60 +   30  +   22 = 112 mod 26 =   8 = I
m38 = (20 x   5 + 5 x  6 + 13 x   1) mod 26 = 100 +   30  +   13 = 143 mod 26 = 13 = N
m39 = (11 x   5 + 5 x  6 + 12 x   1) mod 26 =   55 +   30  +   12 =   97 mod 26 = 19 = T

m40 = (12 x   5 + 5 x  8 + 22 x 11) mod 26 =   60 +   40  + 242 = 342 mod 26 =   4 = E
m41 = (20 x   5 + 5 x  8 + 13 x 11) mod 26 = 100 +   40  + 143 = 283 mod 26 = 23 = X
m42 = (11 x   5 + 5 x  8 + 12 x 11) mod 26 =   55 +   40  + 132 = 227 mod 26 = 19 = T

m43 = (12 x 23 + 5 x 8 + 22 x    1) mod 26 = 276 +   40  +   22 = 338 mod 26 =   0 = A
m44 = (20 x 23 + 5 x 8 + 13 x    1) mod 26 = 460 +   40  +   13 = 513 mod 26 = 19 = T
m45 = (11 x 23 + 5 x 8 + 12 x    1) mod 26 = 253 +   40  +   12 = 305 mod 26 = 19 = T

m46 = (12 x 22 + 5 x 6 + 22 x    2) mod 26 = 264 +   30  +   44 = 338 mod 26 =   0 = A
m47 = (20 x 22 + 5 x 6 + 13 x    2) mod 26 = 440 +   30  +   26 = 496 mod 26 =   2 = C
m48 = (11 x 22 + 5 x 6 + 12 x    2) mod 26 = 242 +   30  +   24 = 296 mod 26 = 10 = K

Es decir, el texto en claro es:

THESOLUTIONTOTHISCHALLENGEISKNOWNPLAINTEXTATTACK

O, lo que es lo mismo:

THE SOLUTION TO THIS CHALLENGE IS KNOWN PLAINTEXT ATTACK

Por tanto, la solución a este reto es: KNOWN PLAINTEXT ATTACK.

2.- Solución mediante una herramienta especializada:

Utilizo la herramienta CrypTool (versión 1.4.40).

Tras introducir el criptograma realizo un ataque con texto claro conocido (introduciendo "THESOLUTI" como texto claro y "ZVMVCWQKX" como su correspondiente texto cifrado):

Como se observa en la figura anterior, la herramienta nos devuelve la matriz con la clave utilizada (tanto con los caracteres del alfabeto como con sus correspondientes valores numéricos).

Finalmente, desciframos el criptograma:

Por tanto, la solución a este reto es: KNOWN PLAINTEXT ATTACK.

3.- Solución creando un script de python:

from sympy import Matrix, pprint

alfabeto='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

n=len(alfabeto)
print ''
print '[+] Modulo (n):', n

M = Matrix([
  [ 19,  7,  4 ],
  [ 18, 14, 11 ],
  [ 20, 19,  8 ]
])
print '[+] Matriz con texto claro conocido (M):'
pprint(M)

M_inv = M.inv_mod(26)
print "[+] Matriz inversa de M (M'):"
pprint(M_inv)

C = Matrix([
  [ 25, 21, 12 ],
  [ 21,  2, 22 ],
  [ 16, 10, 23 ]
])
print '[+] Matriz con criptograma correspondiente a texto claro conocido (C):'
pprint(C)

K = M_inv * C
for i in range(len(K)):
   K[i]=K[i]%n
print '[+] Matriz transpuesta de la utilizada como clave en el cifrado (Kt):'
pprint(K)

K = K.transpose()
print '[+] Matriz con la clave utilizada en el cifrado (K):'
pprint(K)

K_inv = K.inv_mod(26)
print "[+] Matriz inversa de K (K'):"
pprint(K_inv)

C = Matrix([
[25, 21, 12, 21, 2, 22, 16, 10, 23, 21, 20, 13, 15, 14, 7, 14, 10, 20,
 14, 9, 19, 18, 25, 11, 6, 8, 20, 11, 10, 2, 1, 16, 0, 11, 5, 16, 5, 6,
 1, 5, 8, 11, 23, 8, 1, 22, 6, 2]
])
print '[+] Criptograma (C):'
pprint(C)

texto_claro=''
i=0
while i  < len(C):
   Ci = Matrix([C[i],C[i+1],C[i+2]])
   Mi = K_inv * Ci
   for j in range(len(Mi)):
      texto_claro = texto_claro + alfabeto[Mi[j]%n:Mi[j]%n+1]
   i+=3
print '[+] Texto en claro (M):', texto_claro

Y tras ejecutar este script ya puedo ver que la solución a este reto es: KNOWN PLAINTEXT ATTACK.

******** PRÓXIMO RETO
Reto 28: "¿Más seguro cuantos más primos?".