Intro to RSA

Challenge

In [9]: p = getPrime(128)
In [10]: q = getPrime(128)
In [11]: N = p*q
In [12]: bytes_to_long(flag) < N
Out[12]: True
In [13]: print(pow(bytes_to_long(flag), 65537, N), N)
9015202564552492364962954854291908723653545972440223723318311631007329746475 51328431690246050000196200646927542588629192646276628974445855970986472407007

Solution

First, we need to find out the values of p and q. You could try making a small Python script for this, using SymPy's factorint for example. But considering N is such a huge number, it will take some time to run (at least it did for me). So I tried to find an online calculator and ended up once again, on dCode.

Now that we know p and q, we can calculate phi and also d. And then we can decrypt the message !

This is what my Python code looks like:

p = 186574907923363749257839451561965615541
q = 275108975057510790219027682719040831427
N = 51328431690246050000196200646927542588629192646276628974445855970986472407007
ciphertext = 9015202564552492364962954854291908723653545972440223723318311631007329746475

phi_N = (p - 1) * (q - 1)
d = pow(65537, -1, phi_N)
decrypted_message = pow(ciphertext, d, N)
flag_bytes = decrypted_message.to_bytes(50, byteorder='big')

print(flag_bytes.decode())