Criptografía (CXXXII): Solución Reto 28

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

"Dados (ver archivo asociado al reto) los valores en decimal correspondientes al módulo (n) y al exponente público (e), ¿puedes descifrar el criptograma (c)?".

Solución: En el archivo asociado al reto (reto_28.txt) no veo nada raro en los valores decimales que se proporcionan y que me pueda dar una pista sobre utilizar un ataque concreto, lo único que el tamaño del módulo es pequeño con respecto a lo habitual. Por tanto, en primer lugar intento factorizar n. Para ello utilizo una herramienta online y obtengo lo siguiente:

Es decir, frente a lo habitual, que es que el módulo sea el producto de dos número primos, en este caso hay 5 factores primos.

Esto es raro, ya que en RSA el módulo (n) es el producto de dos números primos (p y q), pero, en principio, podría serlo de más (en este reto, tal y como digo, hay cinco: p, q, r, s, t):

p = 13;
q = 557;
r  = 58163923;
s = 31509957423978419;
t = 508221080740664699289019787936896001840798152657080678401919878890044322662379008195318884737419792416128150567708788354217048821519803

Tal y como decía en este post, para descifrar el criptograma (c) necesito conocer el exponente de la clave privada (d), que se calcula como el inverso mutiplicativo del exponente la clave pública (e) módulo j(n).

Por tanto, si calculo j(n) o phi(n) podré calcular el exponente de la clave privada (d) y descifrar el criptograma (c) sin ningún problema, pero ¿cómo calculo phi(n)?.

La función phi(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n, es decir, el número de dichos enteros cuyo máximo común divisor con n es igual a 1.

En la primera pista que puse para ayudar a resolver este reto decía que si p es primo entonces phi(p) = p-1, ya que un número primo no tiene más divisores comunes con ninguno de sus anteriores que el número 1, es decir, un número primo es coprimo con todos sus anteriores.

Sabemos también que para dos números primos (p, q) phi(pq) = phi(p) phi(q) = (p-1) (q-1), lo que podemos generalizar, ya que phi es una función multiplicativa, es decir, si varios números (en nuestro caso p, q, r, s, t) son coprimos (en nuestro caso al ser primos, evidentemente, son también primos entre sí), entonces phi(pqrst) = phi(p) phi(q) phi(r) phi(s) phi(t) = (p-1) (q-1) (r-1) (s-1) (t-1).

Dicho todo lo anterior, para obtener el mensaje en claro (m) creo el siguiente script en python:

import Crypto.Util.number

print''
print'*** Calcular phi(n)'

phi = 1
factores = [13, 557, 58163923, 31509957423978419,  508221080740664699289019787936896001840798152657080678401919878890044322662379008195318884737419792416128150567708788354217048821519803]

for primo in factores:
      phi *= primo - 1

print 'phi(n) .......:', phi

print''
print'*** Calcular d'

e = 65537

d = Crypto.Util.number.inverse(e,phi)

print 'd ...........:', d

print''
print'*** Descifrado'

n = 6744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451
c = 4981417018549801962431447642124325650931495730884909753071458271804946544002258604206443185260750428256778937027399957032405875914321337784313001520933520120133065

m = pow(c, d, n)

print 'c ...........:', c
print''
print 'm ...........:', m

print''
print'*** Solucion'
print 'm (ascii) ...:', Crypto.Util.number.long_to_bytes(m)

Y tras ejecutar este script:

Ya puedo ver la solución al reto: Mu17ip13_Prim3_R54.

******** PRÓXIMO RETO
Reto 29: "¡Descíflalo!".