Criptografía (CLXXIV): Solución Reto UTC-CTF 2019 "RSAcue"

Otra de las competiciones tipo CTF de formato 'Jeopardy', en modalidad 'On-line' y por equipos con la que me he entretenido durante estos fines de semana es UTC-CTF.

Comienzo en este post a poner algunas de las soluciones de los retos que he resuelto en esta competición. Empiezo por uno de criptografía, pero también tendrán cabida desafíos catalogados en otras categorías.

Al igual que en el último post correspondiente a un desafío de otra plataforma de este tipo que he puesto en este blog, se trata de un reto 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 bajo (★★☆☆☆).

El título del reto es "RSAcue" y su enunciado es el siguiente: 
Como siempre lo primero que hago es descargar los archivos asociado al reto: el primero de ellos (challenge_baby.py) es un script de python en el que se ve la forma en la que que se ha generado la clave pública (tercero de los archivos, publickey.pem) y cómo se ha obtenido el criptograma (segundo de los archivos, ciphertext) que supuestamente contiene la flag o solución al reto.

Fijándome en el contenido del primero de los citados archivos (challenge_baby.py) veo que los dos números primos ('p' y 'q') empleados cumplen con la condición de ser primos consecutivos a los que sólo les separa un número (necesariamente par y, por tanto, compuesto), es decir, q = p + 2.

La consecuencia de utilizar dos número primos muy cercanos es que el módulo será muy fácilmente factorizable al existir algoritmos muy eficientes para ello, con lo que el secreto queda "roto" (el texto en claro, 'm', correspondiente al criptograma, 'c', contenido en el archivo ciphertext).

Obtengo los valores correspondientes a la clave pública que contiene el archivo publickey.pem (el módulo, 'n', y el exponente público, 'e', aunque sé que este último es 65537, ya que se ve en el archivo challenge_baby.py), para lo que creo el siguiente script en python:

from Crypto.PublicKey import RSA

# Obtener parametros de la clave publica

pubkey = open('publickey.pem', 'r')
param_pubkey = RSA.importKey(pubkey.read())
print ''
print '   n  ...:', param_pubkey.n
print '   e  ...:', param_pubkey.e
pubkey.close()

Lo ejecuto:

Lo siguiente que hago es factorizar el módulo. Para ello utilizo una herramienta on-line y veo que los dos factores primos del mismo son:

152777516386350781880168612195788492071670529707183028442659731050780650246806687912093838064236073818693170025899623418576802777894452115885481025571017558984186236658002227671928033021500390743254563665432524870210224122180999810222908681626276290754278604538897819450533525723316529567703923553390398838723

y

152777516386350781880168612195788492071670529707183028442659731050780650246806687912093838064236073818693170025899623418576802777894452115885481025571017558984186236658002227671928033021500390743254563665432524870210224122180999810222908681626276290754278604538897819450533525723316529567703923553390398838721

Con lo que compruebo que, efectivamente, a ambos número primos únicamente les separa un número compuesto.

Una vez factorizado el módulo ('n') "romper" el cifrado es muy fácil, para lo que creo el siguiente script en python:

import Crypto.Util.number
import base64

n= 23340969513181681669886867124297366201945838538200009802685175918916975846804407564465991446659110587194498035612776912466980598231734891359851233259880511275720151718945837594008921478180856400092449301945615071348468948166726825972379205191078930318376444669315567445937802438802902489277773238394532264660179274909819475224351258216422153542290105609840561176158021408561703840207392844063034658892035606967061985331583041696160739791355387960973933646534405406373409762058896880070632898708609976063409024168659391417736541832207520205503452433935527234086203176945565493782067913785720671180939691807486166593283
print 'n ......', n

p = 152777516386350781880168612195788492071670529707183028442659731050780650246806687912093838064236073818693170025899623418576802777894452115885481025571017558984186236658002227671928033021500390743254563665432524870210224122180999810222908681626276290754278604538897819450533525723316529567703923553390398838723
q = 152777516386350781880168612195788492071670529707183028442659731050780650246806687912093838064236073818693170025899623418576802777894452115885481025571017558984186236658002227671928033021500390743254563665432524870210224122180999810222908681626276290754278604538897819450533525723316529567703923553390398838721
print 'p ......', p
print 'q ......', q

phi = (p-1)*(q-1)
print 'phi ....', phi

e = 65537
print 'e ......', e

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

ciphertext = open('ciphertext', 'rb')
c  = ciphertext.read()
c = base64.b64decode(c).encode('hex')
c = int(c,16)
ciphertext.close()

m = pow(c, d, n)

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

Lo ejecuto:

Y ya puedo ver la flag: utc{d0n7_k33p_pr1m35_cl053_by_2}.