viernes, 15 de febrero de 2019

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ónEn 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−1)  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−1 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 k2 letras de texto plano conocido (en nuestro caso conocemos 11 caracteres, “THESOLUTION”). Por tanto:
22 = 4; 4 < 11
32 = 9; 9 < 11
42 = 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).
CT: 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 (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 (KT) 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).
CT: 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 (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: Por publicar.

lunes, 11 de febrero de 2019

Criptografía (CXXVIII): Reto 27

En esta ocasión un reto de dificultad media sobre criptografía en el que se ve involucrado un criptosistema clásico inventado a finales de la década de los años veinte del siglo pasado por un matemático y criptógrafo estadounidense.

Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 27: "Un poco de ti es mucho".

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?.

Dificultad:
Tipo:           Criptografía.

******** 12/02/2019
Pista 1:     Ya sabrás que la persona que aparece en la imagen que ilustra este post es el matemático y criptógrafo estadounidense Lester S. Hill, inventor en 1929 del conocido como cifrado de Hill. Este criptosistema de sustitución poligráfica era muy robusto, pero tenía una vulnerabilidad importante: su "talón de Aquiles" eran los ataques con texto claro conocido, y precisamente de esto es de lo que se trata en este reto.

******** 13/02/2019
Pista 2:     Por el  texto claro conocido parece que el mensaje en claro está escrito en inglés y por el criptograma que el alfabeto se reduce a las letras mayúsculas de dicho idioma. Por tanto, el tamaño (n) del alfabeto sería 26 (A=0, B=1, ..., Z=25).

******** 14/02/2019
Pista 3:     Adelanto que el orden de la matriz cuadrada (K) empleada como clave en el cifrado es 3  (3 filas x 3 columnas). A partir de una matriz cuadrada (M) con texto claro conocido de orden 3, necesitamos 3 x 3 = 9 caracteres de texto en claro, si obtenemos su inversa (M-1) y multiplicamos ésta por la matriz cuadrada (C) de orden 3 con el texto cifrado que se corresponde con el texto en claro obtenemos la matriz empleada como clave en el cifrado (K), y calculando su inversa (K-1) podemos descifrar todo el criptograma. Es decir:
C = K M
K = M-1 C
K-1 es la matriz con la que desciframos el criptograma.

******** 15/02/2019
Solución.

******** PRÓXIMO RETO
Reto 28:   Por publicar.

lunes, 28 de enero de 2019

Criptografía (CXXVII): Solución Reto 26

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

"Y como no hay dos sin tres, otro reto en el que se nos viene a recordar que el tamaño sí importa. Supón que interceptas tres criptogramas, que sabes que se corresponden con un mismo texto en claro (m) y que dichos criptogramas han sido enviados a tres personas diferentes, ¿puedes obtener el texto en claro (m)?.

Nota: en el archivo asociado al reto se indican los valores en decimal correspondientes al módulo (n) y al exponente público (e) de las respectivas claves de las tres personas y los valores en decimal de los criptogramas remitidos a éstas".


Solución: Decía en la primera pista que puse para ayudar a resolver este reto que como en el enunciado se establece que los tres criptogramas se corresponden con un mismo texto en claro (m1 = m2 = m3 = m) y en el archivo asociado al reto (reto_26.txt) vemos que los tres exponentes públicos son iguales a 3 (e1 = e2 = e3 = 3), si los módulos (n1, n2, n3) son primos entre sí, coprimos o primos relativos dos a dos, es decir, si el mcd(ni, nj) = 1 para todo i distinto de j, entonces quizás el teorema chino del resto pueda ayudarnos a calcular m.

Por tanto, en primer lugar lugar creo un script en python para comprobar si los módulos (n1, n2 y n3) son coprimos dos a dos, es decir, si el máximo común divisor de ellos tomados de dos en dos es igual a 1:

import gmpy2

n1 = gmpy2.mpz("141237893326188574204627692926236597832923906875563312407296586270187098500830977089086198296698274977259945744931269328582013379088128599997921784764795876512664274811704263719810554438911212375275389637307533676792707072305650179551138270208913948697352662887831274626962574428552932203244712293494591555511")
n2 = gmpy2.mpz("123540448208108190442413152518982095069440783769340903005935077787457590335172518758985701753251638030875882695636036396466435248787871355571628582178196705443476117178179250809139797395693806996196479271907692595838139580204715620363875721843078735275575567535802910937573265882011978734919390275028927498651")
n3 = gmpy2.mpz("129764663185510756371105783443119016055267527773132919526587344357374102887540763282339924512254838799749899518844225166115902370305244996180768430247896711901844141296135907974189994271244431528747412109545908983450918905491684446582713912788850397046516711871065128208507799172858171575837210017773451264069")

print ''
if gmpy2.gcd(n1, n2)!=1 or gmpy2.gcd(n1, n3)!=1 or gmpy2.gcd(n2, n3)!=1:
   print '[-] Los modulos n1, n2 y n3 no son primos entre si, coprimos o primos relativos dos a dos.'
else:
   print '[+] Los modulos n1, n2 y n3 son primos entre si, coprimos o primos relativos dos a dos.'

Tras ejecutar este script, podemos afirmar que, efectivamente, los módulos de las claves son coprimos dos a dos:
Y, por tanto, el teorema chino del resto nos puede ayudar a obtener el texto en claro (m) que se corresponde con los tres criptogramas (c1, c2 y c3) que se enviaron, respectivamente, a las tres personas.

En este caso, como el texto en claro correspondiente a los tres criptogramas es el mismo (m1 = m2 = m3 = m) y los exponentes públicos de las tres claves son iguales a 3 (e1 = e2 = e3 = 3), el cifrado se ha realizado de la siguiente manera:

c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

Por tanto, tengo el siguiente sistema de congruencias simultáneas:

m^3   c1 mod n1
m^3 ≡ c2 mod n2
m^3 ≡ c3 mod n3

Es decir, se trata de hallar un número (m^3) que dividido entre n1 dé como resto c1, que dividido entre n2 dé como resto c2 y que dividido entre n3 dé como resto c3, y esto puede resolverse utilizando el teorema chino del resto (ver ejemplo en este post).

Una vez que calculo ese número (m^3), lógicamente, el mensaje en claro (m) es la raíz cúbica del mismo.

Para obtener m creo el siguiente script en python:

import gmpy2
import binascii

e = 3
c1 = gmpy2.mpz("37050595107607215425728862670311169686501715648529655096852022500961331010583163575464647323975465331340563969499827140101447214847555787027687021816122499851981434087708434429330112796102295773537370473348683587834276525448296670045256125366626288277440736754846403151338632769822829343206702099866719381340")
n1 = gmpy2.mpz("141237893326188574204627692926236597832923906875563312407296586270187098500830977089086198296698274977259945744931269328582013379088128599997921784764795876512664274811704263719810554438911212375275389637307533676792707072305650179551138270208913948697352662887831274626962574428552932203244712293494591555511")
c2 = gmpy2.mpz("29448590570339337019846906819372551561193767416448894862618308297222578491963152380884360258445115263084004692906639292433283570505453988598060990964248465596120682287756617715751129758488463897763244247700203105329378047389157194907729114086283485641777376575040271414336675879220483713989496496481639193284")
n2 = gmpy2.mpz("123540448208108190442413152518982095069440783769340903005935077787457590335172518758985701753251638030875882695636036396466435248787871355571628582178196705443476117178179250809139797395693806996196479271907692595838139580204715620363875721843078735275575567535802910937573265882011978734919390275028927498651")
c3 = gmpy2.mpz("59230107217036032019940650579150530277946966690389133886396754469356281025902289554077581971768082168768214384534406164927205095184494909622994804896955185141556382755419648502790626246194221204969871419277083672288347576620879291907671233882681829121454526629083136356495332711948312285534940375019766634305")
n3 = gmpy2.mpz("129764663185510756371105783443119016055267527773132919526587344357374102887540763282339924512254838799749899518844225166115902370305244996180768430247896711901844141296135907974189994271244431528747412109545908983450918905491684446582713912788850397046516711871065128208507799172858171575837210017773451264069")

N = n1*n2*n3
mcubo = (c1 * N/n1 * gmpy2.invert(N/n1,n1) + c2 * N/n2 * gmpy2.invert(N/n2,n2) + c3 * N/n3 * gmpy2.invert(N/n3,n3)) % N

m, exact = gmpy2.iroot(mcubo,e)
if exact:
   print ''
   print '[+] Texto en claro (m) ............', binascii.unhexlify(gmpy2.digits(m,16))

Y tras ejecutar este script:
Ya puedo ver la solución al reto: H4574D5 BR04DC457 4774CK.

******** PRÓXIMO RETO
Reto 27: "Un poco de ti es mucho".

sábado, 26 de enero de 2019

Gimnasia mental (XXXII): los siete ladrones

Siete ladrones roban un cargamento de lingotes de oro y a la hora de repartir el botín a partes iguales sobran 6 lingotes.

Como no se ponen de acuerdo en la forma de repartir los lingotes sobrantes, se pelean entre ellos y mueren dos ladrones. Tras realizar de nuevo el reparto entre los supervivientes sobran dos lingotes, por lo que se vuelve a desatar una pelea entre ellos y muere otro ladrón. Ahora sí, el reparto de los lingotes se realiza a partes iguales entre los ladrones que quedan vivos.

a) ¿Cuál es el número mínimo de lingotes que han robado los ladrones para que pueda ser cierto el enunciado?.
b) ¿Cuál es el siguiente número de lingotes que podría hacer cierto el enunciado?. 

Si eres capaz de resolver este problema, sin duda, podrás resolver también este reto de criptografía.


Solución: utilizo lo que he entendido del teorema chino del resto para resolver este problema.

Tenemos el siguiente sistema de congruencias lineales simultáneas:

X ≡ 6 (mod 7)
X ≡ 2 (mod 5)
X ≡ 0 (mod 4)

Es decir, buscamos el número X que dividido entre 7 da como resto 6, que dividido entre 5 da como resto 2 y que dividido entre 4 da como resto 0.

Como los módulos son primos entre sí dos a dos, es decir, el máximo común divisor de ellos tomados dos a dos es igual a 1, podemos utilizar el teorema chino del resto para resolverlo:

mcd(7, 5) = 1
mcd(7, 4) = 1
mcd(5, 4) = 1

Lo primero que tenemos que hacer para calcular X es obtener el módulo (N), que sería el producto de los módulos de las tres congruencias:

N = 7 * 5 * 4 = 140

Lo segundo que tenemos que hacer es dividir el nuevo módulo (N) entre los módulos de las tres congruencias:

N1 = 140 / 7 = 20
N2 = 140/ 5 = 28
N3 = 140 / 4 = 35

Lo tercero que tenemos que hacer es calcular el inverso mutiplicativo modular de los valores obtenidos en el paso anterior, es decir:

20 * s1 ≡ 1 (mod 7)
28 * s2 ≡ 1 (mod 5)
35 * s3 ≡ 1 (mod 4)

Cuando los números son pequeños, como es el caso, podemos utilizar la fuerza bruta para calcular el inverso multiplicativo modular, es decir, basta con ir probando todos los números (1, 2, …), uno detrás de otro, hasta encontrarlo.

s1 = 6
s2 = 2
s3 = 3

Finalmente encontramos la solución particular:

6 * 20 * 6 + 2 * 28 * 2 + 0 * 35 * 3 = 720 + 112 + 0 = 832

832 X (mod 140)

X = 132

Y la solución general sería:

X = 132 + 140 Y

Para Y = 1: X = 132 + 140 * 1= 272
Para Y = 2: X = 132 + 140 * 2= 412

Por tanto, la respuesta a la primera pregunta es que los ladrones han robado como mínimo 132 lingotes de oro y a la segunda, es decir, el siguiente número de lingotes robados que podría hacer cierto el enunciado, es 272.


Este mismo teorema se puede utilizar para resolver también este reto de criptografía.

Dejo un pequeño script en python que resuelve el problema planteado en este post y que puede servir, con pequeñas variaciones, para resolver el citado reto de criptografía.

import gmpy2

a1 = 6
n1 = 7
a2 = 2
n2 = 5
a3 = 0
n3 = 4

N = n1*n2*n3
X = (a1 * N/n1 * gmpy2.invert(N/n1,n1) + a2 * N/n2 * gmpy2.invert(N/n2,n2) + a3 * N/n3 * gmpy2.invert(N/n3,n3)) % N

print ''
print '[+] Respuesta pregunta 1: los ladrones han robado como minimo', X, 'lingotes de oro.'
print ''
print '[+] Respuesta pregunta 2: el siguiente numero de lingotes robados que podria hacer cierto el enunciado es', X+N,'.'

miércoles, 23 de enero de 2019

Criptografía (CXXVI): Reto 26

Otro reto de dificultad media sobre criptografía, relacionado con el anterior y, por tanto, en el que también se ve involucrado el criptosistema RSA.

Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 26: "El tamaño sí importa (III)".

Y como no hay dos sin tres, otro reto en el que se nos viene a recordar que el tamaño sí importa. Supón que interceptas tres criptogramas, que sabes que se corresponden con un mismo texto en claro (m) y que dichos criptogramas han sido enviados a tres personas diferentes, ¿puedes obtener el texto en claro (m)?.

Nota: en el archivo asociado al reto se indican los valores en decimal correspondientes al módulo (n) y al exponente público (e) de las respectivas claves de las tres personas y los valores en decimal de los criptogramas remitidos a éstas.

Dificultad:
Tipo:           Criptografía.

Recursos:   reto_26.txt.

******** 26/01/2019
Pista 1:     Como en el enunciado se dice que los tres criptogramas se corresponden con un mismo texto en claro (m1 = m2 = m3 = m) y en el archivo asociado al reto vemos que los tres exponentes públicos son iguales a 3 (e1 = e2 = e3 = 3), si los módulos (n1, n2, n3) son primos entre sí, coprimos o primos relativos dos a dos, es decir, si el mcd(ni, nj) = 1 para todo i distinto de j, entonces quizás el teorema chino del resto pueda ayudarnos a calcular m.

******** 27/01/2019
Pista 2:     Ver este post donde se explica un ejemplo de aplicación del teorema chino del resto y se deja un pequeño script en python que, con pequeñas modificaciones, puede servir para resolver este reto.

******** 28/01/2019
Solución.

******** PRÓXIMO RETO
Reto 27:   "Un poco de ti es mucho".