RsaCtfTool
2 minutes to read
We are given an RSA public key in PEM format (pubkey.pem
):
-----BEGIN PUBLIC KEY-----
MIHeMA0GCSqGSIb3DQEBAQUAA4HMADCByAKBwHfR4yv+QfsHYSvLlS6LGW2cMDlB
3RlH1PteD7gN6nU4KhyMlRznOUQI7cgB082btMWs1usPYfUSrqkDs+1EDrzzw42M
G683YvLlJRfcO2syc+YNJTDqtVHW5V3SNJ2J+WKCw0A5+ab2qA+sfhRFhvPJ7gsL
vUj+blt5qweyGVheMOQvy+WXI+Vi/jwtlW3it25kBLZUoESDBg+HZKnxz3MgcJ6X
roMdjPPwTH2f8sOrCTI1jJzNUYxJ9JQ0QPTrxwIDAQAB
-----END PUBLIC KEY-----
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
$ 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
Anyway, we can apply the same concepts. Now that we have the factorization of
Since
Next is to find the private exponent
And finally
The ciphertext key
as a hexadecimal string:
13822f9028b100e2b345a1ad989d9cdedbacc3c706c9454ec7d63abb15b58bef8ba545bb0a3b883f91bf12ca12437eb42e26eff38d0bf4f31cf1ca21c080f11877a7bb5fa8ea97170c932226eab4812c821d082030100030d84ebc63fd8767cde994e0bd1a1f905c27fb0d7adb55e3a1f101d8b5b997ba6b1c09a5e1cc65a9206906ef5e01f13d7beeebdf389610fb54676f76ec0afc51a304403d44bb3c739fd8276f0895c3587a710d15e43fc67284070519e6e0810caf86b134f02ec54018
Let’s find
>>> 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!}'