RSA-256 was a challenge at the UTCTF 2024 where participants were provided with the values of e, N, and a ciphertext, all part of an RSA scheme. With this information, we needed to find a way to brute-force the key in order to decrypt the message.
Description
The challenge originally weighed 1000 points, but since many people did already solve it at the time I did, I could only get 100 points from it. In this challenge, the info we are given is clear in the image above, the file vals.txt. Let’s see its content:
1
2
3
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
e = 65537
c = 43711206624343807006656378470987868686365943634542525258065694164173101323321
RSA Theory
We can identify two main parameters: N, which represents the RSA public key modulus, calculated as the product of two large prime numbers, p and q; and e, which denotes the RSA public key exponent, a positive integer that is coprime with the value of (p-1) * (q-1), where p and q are the prime factors of N. It’s worth noting that c refers to the ciphertext, which represents the encrypted flag.
For more information on RSA-256, you can check its Wikipedia article and this CTF101 explanation.
Getting the flag
Key cracking
Having this info is useless, since with the public key we can only encrypt; we need the private key with the which the flag was encrypted in order to obtain the desired plaintext.
RSA, which is an abbreviation of the author’s names (Rivest–Shamir–Adleman), is a cryptosystem which allows for asymmetric encryption. Asymmetric cryptosystems are alos commonly referred to as Public Key Cryptography where a public key is used to encrypt data and only a secret, private key can be used to decrypt the data. - OSIRIS Lab & CTFd, Source
Diagram from Abhisheyk Gaur
Since we are not provided with the private key, we will have to brute-force it in order to deduce it. Brute-forcing a private key is a challenging process, as it involves finding the prime factors of N (p and q). Once the prime factors are found, we can calculate the private key, d, using the following mathematical relation:
\[d = e^{-1} \mod ((p-1) (q-1))\]Where d is the private key, e is the public key exponent and p and q are the prime factors of N.
Use of RsaCtfTool
Creating our own script to crack RSA encryption could take a long time and might not yield good results. That’s why it would really be helpful to use a tool that automates this process for us. Fortunately, with a simple Google search we can find an incredible and powerful tool called RsaCtfTool, which does exactly what we need. You can find it here.
I won’t explain all the options that this tool offers this time, as it’s not necessary. With the data we have, we can simply use the following command:
1
~$ ./RsaCtfTool.py -n <our_n> -e <our_e> --decrypt <our_c>
This command would look like this with our parameters:
1
~$ ./RsaCtfTool.py -n 77483692467084448965814418730866278616923517800664484047176015901835675610073 -e 65537 --decrypt 43711206624343807006656378470987868686365943634542525258065694164173101323321
Actually getting the flag
And just like that, our output will look like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
~$ ./RsaCtfTool.py -n 77483692467084448965814418730866278616923517800664484047176015901835675610073 -e 65537 --decrypt 43711206624343807006656378470987868686365943634542525258065694164173101323321
private argument is not set, the private key will not be displayed, even if recovered.
['/tmp/tmpj5vi9ry_']
[*] Testing key /tmp/tmpj5vi9ry_.
attack initialized...
attack initialized...
[*] Performing factordb attack on /tmp/tmpj5vi9ry_.
[*] Attack success with factordb method !
Results for /tmp/tmpj5vi9ry_:
Decrypted data :
HEX : 0x00000000007574666c61677b6a7573745f73656e645f706c61696e746578747d
INT (big endian) : 48318056036638095126835825247330138638677839744287146849712239741
INT (little endian) : 56744891277200465927677691769438839148620997683319332003939796345463196614656
utf-8 : utflag{just_send_plaintext}
utf-16 : 甀晴慬筧番瑳獟湥彤汰楡瑮硥絴
STR : b'\x00\x00\x00\x00\x00utflag{just_send_plaintext}'
And there we have it, our beautiful and desired: utflag{just_send_plaintext}
Considerations
While this challenge was relatively simple and brief, it was enjoyable to revisit RSA. It may not have been my favorite challenge, but it was certainly interesting.
- wh0crypt