Mind your Ps and Qs

Mind your Ps and Qs

On this post, we’ll break some RSA Crypto for the Challenge “Mind your Ps and Qs” from picoCTF.

The challenge description asks us “In RSA, a small e value can be problematic, but what about N?”

So, if you don’t know how RSA works or even what RSA is, let me give you a short introduction, but without going to deep into math:

RSA Basics

RSA is an asymetric cryptosystem which is named after its creators Ron Rivest, Adi Shamir and Leonard Adleman.
Asymetric cryptosystems are working with two different keys, the public key and the private key. If Alice wants to send Bob an encrypted message, she needs his public key to encrypt it so that Bob is able to decrypt the message with his private key.
To generate the two RSA keys, you need two prime numbers “p” and “q” which give the name to this challenge “Mind your Ps and Qs”. These two prime numbers multiplied together build one part of both the public and the private key, which is called “N”.
To get the other parts of the public and private key, we have to build φ(N) which is (p – 1) * (q – 1).
To complete the public key, we only have to choose an “e” which is a number between 1 and φ(N) that doesn’t have an other greatest common devisor than 1. Best suited for this is a prime number so that you only have to check if “e” is not a divisor of φ(N).
With this “e” we have our public key which is “N” and “e”.
Now it’s time to go a little wild with math. For our private key, we need another part called “d” which is the modular multiplicative inverse of “e” modulo φ(N). To get this “d”, you can use the extended Euclidean algorithm but I will showcase you how to get it with a single line of python code.
With “N” and “d” we have all we need for our private key.
To encrypt a cleartext m, we use the function c = m^e modulo N and to decrypt a cyphertext c we use the funktion m = c^d modulo N where m is the clear text and c is the cyher text.

RSA Example

1. First, we need two prime numbers. Lets take some small ones for this example:

p = 11, q = 13

2. To calculate N we have to build the product of p and q:

N = p * q = 143

3. Now we have to calculate φ(N) which is (p – 1) * (q – 1):

φ(N) = (11 – 1) * (13 – 1) = 10 * 12 = 120

4. We have to choose an e which is smaller than φ(N) and does not have a common divisor with φ(N) other than 1

e = 17; 17 is smaller than 120 and not a divisor of 120

5. To calculate d which is the multiplicative inverse of e modulo φ(N) we use the Python function pow:

d = pow(17, -1, 120) = 113

6. Now that we have our private and public key, we are able to encrypt and decrypt messages. Let’s encrypt the super secret message 100 with the same Python function pow:

c = m^e modulo N = 100¹⁷ % 143 = pow(100, 17, 143) = 133

133 is our encrypted message. To decrypt the message we use the pow function again:

m = c^d modulo N = 133¹¹³ % 143 = pow(133, 113, 143) = 100

We successfully encrypted and decrypted a message with RSA.

Solve the challenge

With this knowledge we are able to solve the challenge. The description gives us some values:
c: 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n: 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e: 65537

So c is our encrypted message. Additionally we have the public key which consists of N and e.
Ideally there is no easy way to calculate the private key out of the public key without an enormous amount of computing power if N is large enough. You have to find the two prime numbers which are the devisors of N as we have seen above. Here N is ‘only’ 81 digits long. So there is a good chance that we are able to find the two devisors in a web database called FactorDB.

I made a small python script which does all the work for us including looking up the prime factors, calulating the private key and decrypting the message:

import requests

c = 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n = 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e = 65537

# get devisors from factordb
def get_factor(n):
    f = requests.get('http://factordb.com/api', params={'query': str(n)}).json()
    return int(f['factors'][0][0]), int(f['factors'][1][0])

print(f"Getting factors of n = {n} ...")
f = get_factor(n)
print(f"p = {f[0]}, q = {f[1]}")
phi_n = (f[0]-1) * (f[1]-1)
print(f"phi(n) = {phi_n}")
d = pow(e, -1, phi_n)
print(f"d = {d}")
print("decrypting ...")
m = pow(c, d, n)
print("converting to text ...")
print(f"Result: {bytearray.fromhex(hex(m)[2:]).decode('ascii')}")

Please have a look at my other CTF-WriteUps.