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. :)

---

I hope you can voluntarily Buy Me A Coffee if you found this article useful and give additional support for me to continue sharing more content for the community. :)

Thank you very much. :)