# picoCTF: Mind your Ps and Qs

## Solution#

Three values are provided on the problem page -

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

Here is a step-by-step guide for RSA - https://www.cs.utexas.edu/~mitra/honors/soln.html

Our first task is to find factors for n. Using an online tool, we have derived two factors `p` and `q`.

``````p: 1461849912200000206276283741896701133693
q: 431899300006243611356963607089521499045809
``````

Using these values we can now compute `phi(n)`.

``````phi(n): (p-1)*(q-1) = 631371953793368771804570727896887140714061729769155038068711341335911329840163136
``````

Next step is to compute `d` using above computed values. There is an easy way to do that using Python. We need to come up with multiplicative inverse of `d * e mod phi(n) = 1`

``````d = pow(e, -1, phi_n)
``````

Now using `d` which is in reality is a private key, we can decrypt the ciphertext `c`.

``````plaintext = pow(c,d,n)
``````

Convert it to ASCII and the flag will be revealed.

``````print(bytearray.fromhex(hex(plaintext)[2:]).decode())
``````

To summarize, Here is the complete code -

``````# already given
c = 421345306292040663864066688931456845278496274597031632020995583473619804626233684
n = 631371953793368771804570727896887140714495090919073481680274581226742748040342637
e = 65537

# Find factors using - https://www.dcode.fr/prime-factors-decomposition
p = 1461849912200000206276283741896701133693
q = 431899300006243611356963607089521499045809

# compute
phi_n = (p-1)*(q-1)
d = pow(e, -1, phi_n)
plaintext = pow(c,d,n)

# print
print(bytearray.fromhex(hex(plaintext)[2:]).decode())
``````

## Flag#

Here is the flag -

``````picoCTF{sma11_N_n0_g0od_55304594}
``````