output.txt contains:

n: 228430203128652625114739053365339856393
e: 65537
c: 126721104148692049427127809839057445790

Most people would use the RsaCtfTool to do the decryption of the ciphertext (c), however during the CTF, I wasn't able to install it properly (idk why). So, I solved it manually instead. A lot of the help I got was from this writeup.

Note: Now that the CTF has ended, I have managed to install it (idk why). So, I will share both methods of solving it (manually and with RsaCtfTool).

Solution [Manually]

1. Figure out what is RSA.

   This is a good place to start. Summary:

   (n, e) is the Public Key, AKA the encryption key.
   (n, d) is the Private Key, AKA the decryption key.
   c is the ciphertext.
   n is made up of 2 prime numbers, p and q.
   e is the public exponent.
   d is the private exponent.
   n is the modulus.
   

2. Find the 2 primes, p and q.

   Using this tool, we can find the primes, such that p * q = n.

   p = 12546190522253739887
   q = 18207136478875858439
   n = 12546190522253739887 * 18207136478875858439
     = 228430203128652625114739053365339856393 (which is the same as in *output.txt*)
   

3. Find PHI.

   PHI is Euler's totient, which we can then use along with the public exponent (e) to find the private exponent (d).

   PHI = (p - 1) * (q - 1)
       = 12546190522253739886 * 18207136478875858438
       = 228430203128652625083985726364210258068
   

4. Find the private exponent (d).

   (d * e) mod PHI = 1
   (d *  65537) mod 228430203128652625083985726364210258068 = 1
   d = (1/65537) mod 228430203128652625083985726364210258068
   

   To calculate d, we need to find the inverse of e modulo PHI, which can be done using this tool.

   

   The result would be:

   d = 57678303879838009672243096264323227345
   

5. Decrypt the message.

   Public key = (n, e)
              = (228430203128652625114739053365339856393, 65537)
   Private key = (n, d)
               = (228430203128652625114739053365339856393, 57678303879838009672243096264323227345)
   

   With the decryption key (AKA private key), we can decrypt the ciphertext.

   plaintext = ciphertext^d (mod n)
             = 126721104148692049427127809839057445790^57678303879838009672243096264323227345 (mod 228430203128652625114739053365339856393)
             = 136143999223147678052546820270298707069
   
   *Note: Using python, use the function pow(c, d, n).*
   

   Thus, the plaintext/decrypted message would be:

   plaintext = 136143999223147678052546820270298707069
   

6. Convert the numbers to a readable string.

   The number itself was not the flag. While researching on how to decode it, I came across this forum where it was explained. Based on that, we would need to convert the decimal to hexadecimal and then to ASCII characters.

   Decimal to hexadecimal:

   136143999223147678052546820270298707069 --> 666C61677B363861623832646633347D
   

   Hexadecimal to text:

   666C61677B363861623832646633347D --> flag{68ab82df34}
   

   And with this long manual process, we have finally found the flag.

Flag: flag{68ab82df34}

Solution [RsaCtfTool]

1. Figure out the command.

   This should be doable with the help command. In a simplified manner, it should be:

   python3 ./RsaCtfTool.py -n <modulus> -e <public exponent> --uncipher <ciphertext>
   

2. Run the command.

   

   And the flag is displayed within a matter of seconds 😭