Criptografía (CLXXIII): Solución Reto TUCTF 2019 "Something in Common"

Continúo con las soluciones a los retos correspondientes a la categoría de criptografía de TUCTF 2019, competición tipo CTF de formato 'Jeopardy', en modalidad 'On-line' y por equipos.

En este post es el turno de uno de los retos en el que se ve involucrada la criptografía moderna y en concreto el criptosistema más utilizado actualmente, RSA.

En mi opinión este reto presenta un nivel de dificultad medio (★★★☆☆).

El título del reto es "Something in Common" y su enunciado es el siguiente:

Lo primero que hago es bajarme el archivo que se proporciona como recurso asociado al reto (rsa_details.txt), y veo que contiene lo siguiente:

Es decir, el módulo (n), dos exponentes (e1 y e2) correspondientes a sendas claves públicas y dos criptogramas (c1 y c2) obtenidos respectivamente con el mismo módulo (n) y su correspondiente exponente público (c1 = m1 ^ e1 mod n; c2 = m2 ^ e2 mod n).

A la vista del contenido del fichero proporcionado y considerando el título del reto, parece claro cuál es el ataque a emplear en este caso para romper el cifrado, el ataque mediante módulo común (ver este post donde lo explico).

Es decir, parece evidente que las dos claves RSA comparten el mismo módulo (n) y, si además, ambos criptogramas (c1 y c2) se corresponden con el mismo texto en claro (m = m1 = m2), entonces romper el cifrado (obtener el texto en claro, m) es un "juego de niños".

Compruebo si mi sospecha es correcta. Para ello creo el siguiente script de python:

import Crypto.Util.number

def inv(num1, num2):
global r0, s0, t0

r0 = num1
r1 = num2
s0 = 1
t0 = 0
s1 = 0
t1 = 1

while r1 != 0:
q = r0//r1
r = r0%r1
s = s0 - q * s1
t = t0 - q * t1
r0 = r1
r1 = r
s0 = s1
s1 = s
t0 = t1
t1 = t

return  r0, s0, t0

n = 5196832088920565976847626600109930685983685377698793940303688567224093844213838345196177721067370218315332090523532228920532139397652718602647376176214689
e1 = 15
e2 = 13
c1 = 2042084937526293083328581576825435106672034183860987592520636048680382212041801675344422421233222921527377650749831658168085014081281116990629250092000069
c2 = 199621218068987060560259773620211396108271911964032609729865342591708524675430090445150449567825472793342358513366241310112450278540477486174011171344408

inv(e1, e2)

print ""
if r0 != 1:
    print "No existe inverso"
    m =""
elif s0 < 0:
    s = t0
    t = s0
    inv(c1, n)
    m = ((c2 ** s)%n)*(s0 ** (-t))%n
else:
    s = s0
    t = t0
    inv(c2, n)
    m = ((c1 ** s)%n)*(s0 ** (-t))%n

print 'Flag:', Crypto.Util.number.long_to_bytes(m)

Lo ejecuto:

Y ya puedo ver la flag: TUCTF{Y0U_SH0ULDNT_R3US3_TH3_M0DULUS}.