Criptografía (CXLVIII): Solución Reto picoCTF 2018 "Super Safe RSA 3"

Solución a otro reto de criptografía de la plataforma picoCTF 2018.

Continúo con la solución a otro de los retos en los que se ve involucrado el criptosistema de clave pública (criptografía asimétrica) más utilizado actualmente, RSA, y que, en mi opinión, presenta un nivel de dificultad medio (★★★☆☆).

Este reto es casi idéntico al que puse en este post.

- Super Safe RSA 3 - Points: 600:

Su enunciado dice lo siguiente: 'The more primes, the safer.. right.?.? Connect with nc 2018shell.picoctf. com 11423'.

Solución: se proporcionan un criptograma (c), el módulo (n) y el exponente de la clave pública (e).

A la vista del propio enunciado y de la pista que se da en la pestaña 'Hints' ('How would you find d if there are more than 2 prime factors of n?' ) entiendo que lo primero que tengo que hacer es factorizar el módulo (n) y que me voy a encontrar con que hay más de dos factores primos de éste (por cierto, esto no hace más seguro el cifrado, tal y como se pregunta en el enunciado, sino todo lo contrario :), pero esto sería un asunto para otro post).

Para factorizar el módulo utilizo una de las herramientas online existentes:

Y resulta, si no he contado mal, que el módulo tiene hasta 32 factores primos.

Para resolverlo utilizo el pequeño script en python que utilicé en el post al que he hecho referencia (ver la solución al reto que en él se plantea para entender el por qué):

import Crypto.Util.number

# Calcular phi(n)

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

phi = 1
factores = [2216626733,
                  2353728527,
                  2511152023,
                  2545724263,
                  2636909203,
                  2659594117,
                  2765632621,
                  2893811629,
                  3043075129,
                  3084958931,
                  3222720343,
                  3235936523,
                  3240465131,
                  3297624329,
                  3321331709,
                  3528885013,
                  3558467161,
                  3690452713,
                  3744592309,
                  3761351999,
                  3846388487,
                  3876840109,
                  3982662973,
                  3990696223,
                  3994358603,
                  4001015287,
                  4051529753,
                  4086522311,
                  4103446817,
                  4170069601,
                  4192976911,
                  4214479271]

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

# Descifrado

print''
print'*** Descifrado'

n = 80509034973844509812297937265661360684561413352339270954736583354448265929512999646346556793715073428645462173095582471194464571788380127342173367753073851265807020620003520076297734526712629978586121842783097553584649012129373054387923681508677017607274319694560401412399097625365979732185276180913771273
c = 6164443208635004519221715284526082234260704016333545712004585220881866974025844572374714570334142732026962449767936294097466517483445610420615526118394013991871936601963052473746227439195349769623342409498842941470919513138848059703355096031019287700960602193158738019243740897904868504011294753825176467

m = pow(c, d, n)

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

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

Lo ejecuto y obtengo lo siguiente:

Con lo que la solución a este reto es: picoCTF{p_&_q_n0_r_$_t!!_0954925}.