# The Data Life # CTF - Mind your Ps and Qs (picoCTF - RSA Cryptography)

Now we go to the area of cryptography.

This problem was taken from the picoCTF 2021 and the solution will be discussed below. So proceed with caution. The problem provides the following a values file containing the following:

``````Decrypt my super sick RSA:
c: 421345306292040663864066688931456845278496274597031632020995583473619804626233684
n: 631371953793368771804570727896887140714495090919073481680274581226742748040342637
e: 65537
``````

It is clearly stated that the problem is related to RSA encryption. The problem wants us to decrypt a message.

What are the variables `c`, `n` and `e`?

To proceed we need to understand that in RSA encryption the following should exist:

• `c` is the cyphertext. This is the encrypted message we have to decrypt. (given in the problem)

• A public key that is composed of two parts:

• `n` called the modulus (given in the problem), is the product of two large prime numbers `p` and `q`.

• `e` is a public exponent in which the value is chosen relative to `ϕ(pq)`, more on this later. In practice, the value chosen is usually 65537, consistent with the `e` in the problem.

• `ϕ(pq)` or `ϕ(n)` which is called totient.

• `d` private key which solved by modular inverse `d` of `e` modulo `ϕ(pq)` . `de≡1(modϕ(pq))`

• `m` which is the original message. We are trying to find this out.

So according to the above, we are missing the following `p`, `q`, `ϕ(pq)`, `d` to solve `m` which is the decrypted message.

So let's first solve `p` and `q` which are needed to solve `ϕ(pq)`

It is important to know that the difficulty of factoring large intergers as a product of two large prime numbers `p` and `q` is what makes RSA encryption secure. Even supercomputers will take a lot of time factoring, the larger `n` is.

Addressing the problem's question, a small `N` makes the encryption less secure similar to a small `e`. A small `N` will make factoring of two prime numbers easier and faster.

I decided to use a prime factor decomposition website used called dcode.fr to quickly solve for `p` and `q`. There are a lot of other factor database available online.

``````p = 1461849912200000206276283741896701133693
q = 431899300006243611356963607089521499045809
``````

Next, we solve for the totient `ϕ(pq)` by the formula `(p-1)*(q-1)`

``````totient = 631371953793368771804570727896887140714061729769155038068711341335911329840163136
``````

To solve the private key `d` we need to compute the modular inverse `de≡1(modϕ(pq))`. According to stackoverflow.com/questions/4798654/modular.., we can solve the modular inverse using `pow` function in Python.

``````d = pow(e, -1, totient)
print(d)
# 86820026055294556838164569629472617179839240561509150603097892917271661878321409
``````

Now that we have solved the private key we can now decrypt the message with the formula. `c^d %n`. Using the same `pow` Python function we can decrypt the message.

``````m = pow(c,d,n)
print(m)
# 13016382529449106065927291425342535437996222135352905256639647889241102700065917
``````

We have decoded the integer value of the encrypted message. Now we convert back the integer to bytes and then convert the bytes to its equivalent text (ASCII) for the flag.

Using Python we can use two ways.

``````decrypted_m = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode('ascii')
print(decrypted_m)
# picoCTF{sma11_N_n0_g0od_55304594}
``````
``````decrypted_m = bytes.fromhex(hex(m)[2:]).decode('ascii'))
print(decrypted_m)
# picoCTF{sma11_N_n0_g0od_55304594}
``````

There we have found the flag : `picoCTF{sma11_N_n0_g0od_55304594}`

Until next time. Keep learning.

Stay stoked and code.