RsaCtfTool

2 minutos de lectura

Se nos proporciona una clave pública de RSA en formato PEM (pubkey.pem):

Podemos abrirla con Python para ver qué valores tenemos:

$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> with open('pubkey.pem') as f:
...     key = RSA.import_key(f.read())
...
>>> key.e
65537
>>> key.n
1128137999850045612492145429133282716267233566834715456536184965477269592934207986950131365518741418540788596074115883774105736493742449131477464976858161587355643311888741515506653603321337485523828144179637379528510277430032789458804637543905426347328041281785616616421292879871785633181756858096548411753919440011378411476275900648915887370219369154688926914542233244450724820670256654513052812215949495598592852131398736567134556141744727764716053145639513031

Podemos tratar de factorizar el módulo $n$ para obtener los números primos privados $p$ y $q$ de un criptosistema RSA común. En SageMath:

$ sage -q
sage: factor(1128137999850045612492145429133282716267233566834715456536184965477269592934207986950131365518741418540788596074115883774105736493742449131477464  
....: 97685816158735564331188874151550665360332133748552382814417963737952851027743003278945880463754390542634732804128178561661642129287987178563318175685809
....: 65484117539194400113784114762759006489158873702193691546889269145422332444507248206702566545130528122159494955985928521313987365671345561417447277647160
....: 53145639513031)
10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911^3

O en Python usando el módulo primefac:

$ python3 -m primefac 1128137999850045612492145429133282716267233566834715456536184965477269592934207986950131365518741418540788596074115883774105736493742449131477464976858161587355643311888741515506653603321337485523828144179637379528510277430032789458804637543905426347328041281785616616421292879871785633181756858096548411753919440011378411476275900648915887370219369154688926914542233244450724820670256654513052812215949495598592852131398736567134556141744727764716053145639513031
1128137999850045612492145429133282716267233566834715456536184965477269592934207986950131365518741418540788596074115883774105736493742449131477464976858161587355643311888741515506653603321337485523828144179637379528510277430032789458804637543905426347328041281785616616421292879871785633181756858096548411753919440011378411476275900648915887370219369154688926914542233244450724820670256654513052812215949495598592852131398736567134556141744727764716053145639513031: 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911

Pero esto es raro, ya que $n = p^3$. No se trata de un criptosistema RSA habitual.

De todas formas, podemos aplicar los mismos conceptos. Ahora que tenemos la factorización de $n$, podemos calcular $\phi(n)$ (que es la función indicador de Euler).

Como $n = p^3$, entonces $\phi(n) = p^3 - p^2$.

Lo siguiente es calcular el exponente privado $d$, que es $e^{-1} \mod{\phi(n)}$.

Y finalmente $m = c^d \mod{n}$.

El texto cifrado $c$ está en otro archivo llamado key en formato hexadecimal:

13822f9028b100e2b345a1ad989d9cdedbacc3c706c9454ec7d63abb15b58bef8ba545bb0a3b883f91bf12ca12437eb42e26eff38d0bf4f31cf1ca21c080f11877a7bb5fa8ea97170c932226eab4812c821d082030100030d84ebc63fd8767cde994e0bd1a1f905c27fb0d7adb55e3a1f101d8b5b997ba6b1c09a5e1cc65a9206906ef5e01f13d7beeebdf389610fb54676f76ec0afc51a304403d44bb3c739fd8276f0895c3587a710d15e43fc67284070519e6e0810caf86b134f02ec54018

Vamos a hallar $m$:

>>> with open('key') as f:
...     c = int(f.read(), 16)
...
>>> p = 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911  
>>> phi_n = p ** 3 - p ** 2
>>> d = pow(key.e, -1, phi_n)
>>> m = pow(c, d, key.n)
>>> hex(m)
'0x7365637265746b6579961d57bec0393c'
>>> bytes.fromhex(hex(m)[2:])
b'secretkey\x96\x1dW\xbe\xc09<'

No es la flag. No obstante, tenemos otro archivo llamado flag.enc.aes:

$ xxd flag.txt.aes
00000000: 4845 da30 14a5 2429 e914 c311 7b1c 45a0  HE.0..$)....{.E.  
00000010: a68d 6454 e830 57af 6fca dada e011 814d  ..dT.0W.o......M
00000020: 0a

$ xxd -p flag.txt.aes
4845da3014a52429e914c3117b1c45a0a68d6454e83057af6fcadadae011
814d0a

Entonces, la clave anterior tiene que ser usada para el cifrado AES. Vamos a descifrarlo (nótese el uso de .strip() para quitar el carácter de salto de línea del final):

>>> from Crypto.Cipher import AES
>>> k = bytes.fromhex(hex(m)[2:])
>>> cipher = AES.new(k, AES.MODE_ECB)
>>> with open('flag.txt.aes', 'rb') as f:  
...     ct = f.read().strip()
...
>>> flag = cipher.decrypt(ct)
>>> flag
b'HTB{pl4y1ng_w1th_pr1m3s_1s_fun!}'