RSA is a cryptographic method. It is based on prime numbers and have a way to construct those primes in to values which is used later on in the encryption/decryption-process. The following is my notes regarding RSA-basics in a CTF (capture the flag)-perspective.

The most common variables is:

p - First factor of the RSA modulus
q - Second factor of the RSA modulus
N - RSA modulus
phi - Multiplicative function
d - RSA private exponent
c - Ciphertext
e - RSA public exponent
m - Message/plaintext

N, p, q

The value of N is the product of the two primes p * q. It is possible for N to be the product of more then just two primes, but the conscept is the same by just adding them togheter.

If we have N and either por q, we can find the missing value like this:

p = N/q
q = N/p
N = p*q

In some cases we can stumble upon variations of the RSA where the primes like pand qand other ones may be reused in calculating other N values. In those cases it might be smart to try some basic equations with unkowns. This might give you the solution without knowing all the factors.

There is also databases with factorized numbers, like factordb. The website alpertron might also be handy.
   

Keys

In RSA we need keys for the encryption and decryption.

The public key is the pair of N and the public exponent e. e is a prime number (often 3 or 65537)

The private key is the pair of N and the private exponent d. In order to find d we need phi. To find the value of phiwe can use python and calculate phi = (p-1)*(q-1).

d can then be calculated with python by using this two methods:

import gmpy2
import Mod

d = gmpy2.invert(e, phi)
#or
d = int(Mod(e, phi).inverse)

 

Encryption/decryption

Encryption If we have a plaintext/message (m) then we can encrypt it to a Ciphertext (c) with python by typing c = pow(m**e %N), which is the same as Ciphertext = (Message^e) modulus N. Given we need numbers to do math, we first have to convert the message/plaintext in to a number value.

Decryption If we gave a ciphertext we can decrypt it by typing m = pow(c**d %N), which is the same as Message = (Ciphertext^d) modulus N. The returned value can then be converted in to string in order to be viewed as plaintext.

Low public exponent attack In some cases the eis only 3. We can then try to find the correct cube root, in order to print out the outcome as UTF-8. eg.

while True:
    root, excact = gmpy2.iroot(c, e)
    if excact:
        print(long_to_bytes(root).decode('utf-8'))
        exit(0)

>>> some text

Getting the correct output
In order to get the long decrypted integer back into text, just use:

from Crypto.Util.number import long_to_bytes
print(long_to_bytes("the long number").decode('utf-8'))
>>> Some text

Tools

RsaCtfTool - RsaCtfTool There will be many challenges where RsaCtfTool can crack the encryption for you. Feed the tool with values and watch it have a go at the cryptographic with well known methods. RsaCtfTool can also read, write and combine values which might be usefull in RSA. This tool might also be used with certifications and keys in a ppm-format.

   

GMPY2 - Python interface If you are about to work on RSA with Python it might be usefull to do some reading about the possibilities within Python and publicly available interfaces. GMPY2 gives can for example give you the possibility to work with large numbers with the gmpy2.mpz() function. Read more about it in the documentation on their site!

Math - issqrt() This can be an usefull tool. It finds the square root and rounds it down to the nearest integer.

> import math
> math.isqrt(10)

>>> 3

Wikipedia - RSA, wikipedia
We can find almost everything on Wikipedia. Use it when you are trying to learn something new.

PicoCTF - picoCTF
At picoCTF they have multiply RSA-challenges with various diffucality. This is a good place to learn more about RSA and other Crypto-challenges. picoCTF usally has a lot of writeups accessible within a quick google search, and it will ensure that you have progression if you have been stuck for too long.

pwntools - My post about pwntools
pwntools is a must have when it comes to working with CTF-challenges over the Internet. Use it to recive and send information to the server and carve out usefull values in order to assign it to your Python-code.