RsaCtfTool

2 minutes to read

We are given an RSA public key in PEM format (pubkey.pem):

We can open it in Python and see what values we have:

$ 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

We can try to factor the modulus $n$ so that we get the private prime numbers $p$ and $q$ of a common RSA cryptosystem. In SageMath:

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

Or in Python using primefac module:

$ python3 -m primefac 1128137999850045612492145429133282716267233566834715456536184965477269592934207986950131365518741418540788596074115883774105736493742449131477464976858161587355643311888741515506653603321337485523828144179637379528510277430032789458804637543905426347328041281785616616421292879871785633181756858096548411753919440011378411476275900648915887370219369154688926914542233244450724820670256654513052812215949495598592852131398736567134556141744727764716053145639513031
1128137999850045612492145429133282716267233566834715456536184965477269592934207986950131365518741418540788596074115883774105736493742449131477464976858161587355643311888741515506653603321337485523828144179637379528510277430032789458804637543905426347328041281785616616421292879871785633181756858096548411753919440011378411476275900648915887370219369154688926914542233244450724820670256654513052812215949495598592852131398736567134556141744727764716053145639513031: 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911 10410080216253956216713537817182443360779235033823514652866757961082890116671874771565125457104853470727423173827404139905383330210096904014560996952285911

But this is weird, since $n = p^3$. It is not the usual RSA cryptosystem.

Anyway, we can apply the same concepts. Now that we have the factorization of $n$, we can compute $\phi(n)$ (which is Euler’s totient function).

Since $n = p^3$, then $\phi(n) = p^3 - p^2$.

Next is to find the private exponent $d$, which is $e^{-1} \mod{\phi(n)}$.

And finally $m = c^d \mod{n}$.

The ciphertext $c$ is in another file called key as a hexadecimal string:

13822f9028b100e2b345a1ad989d9cdedbacc3c706c9454ec7d63abb15b58bef8ba545bb0a3b883f91bf12ca12437eb42e26eff38d0bf4f31cf1ca21c080f11877a7bb5fa8ea97170c932226eab4812c821d082030100030d84ebc63fd8767cde994e0bd1a1f905c27fb0d7adb55e3a1f101d8b5b997ba6b1c09a5e1cc65a9206906ef5e01f13d7beeebdf389610fb54676f76ec0afc51a304403d44bb3c739fd8276f0895c3587a710d15e43fc67284070519e6e0810caf86b134f02ec54018

Let’s find $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<'

It is not the flag. However, we are given another file called 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

So the key must be used for an AES encryption. Let’s decrypt it (notice the use of .strip() to remove the new line character at the end):

>>> 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!}'