AlexCTF - CR3 What is this encryption? (150pts)

Otro writeup relacionado con RSA de AlexCTF, esta vez corresponde al tercer reto de crypto.

.0x00. Intro

En esta ocasión la propia descripción del reto ofrecia la siguiente información:

Fady assumed this time that you will be so n00b to tell what encryption he is using he send the following note to his friend in plain sight :

p=0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9
 
q=0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307
 
e=0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41
 
c=0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520

He is underestimating our crypto skills!

.0x01. RSA 101

En RSA son importantes 6 variables:

Por otro lado, la clave pública se forma por (e,n) y la clave privada por (d,n). Así que las operaciones para cifrar/descifrar serían las siguientes:

Cifrado Descifrado
c = msg ^ e (mod n) msg = c ^ d (mod n)

Por lo tanto, necesitamos encontrar n y d para descifrar el mensaje con la clave privada.

.0x02. AND THE FLAG IS…

Para calcular d utilizamos la librería gmpy y para descifrar el mensaje, pycrypto. Al final nos quedó el siguiente script:

#!/usr/bin/env python
from Crypto.PublicKey import RSA
import gmpy

c = long("0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520", 16)
e = long("0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41", 16)
p = long("0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9", 16)
q = long("0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307", 16)

phi = (p-1)*(q-1)
n = p * q
d = long(gmpy.invert(e, phi))

print "[+] Exponente d --> {}\n".format(hex(d))
print "[+] Modulo n --> {}\n".format(hex(n))

key = RSA.construct((n, e, d))
plaintext = key.decrypt(c)

flag = hex(plaintext)[2:-1].decode('hex')
print flag

Y la flag dice así:

ALEXCTF{RS4_I5_E55ENT1AL_T0_D0_BY_H4ND}

Made with lots of coffee and Hugo.