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