Posted on April 14, 2017 as PicoCTF 2017.
4 minutes
read.

WeirdRSA - 90 PTS

We recovered some data. It was labeled as RSA, but what in the world are "dq" and "dp"? Can you decrypt the ciphertext for us?

Firstly let's take a quick look at the Wikipedia page about RSA cryptosystem. We can easily see that values named as dp and dq are used in the Chinese Remainder algorithm, which is used as the algorithm in many popular crypto libraries, due to it's efficiency. Let's view the equations.

Great, we have everything right in the provided data. The only thing that concernes me is the qInv variable, which proved by this paper states to be modular inverse, and can be calculated using Euclidean Algorithm.

Quick google for the Python code calculating modular inverse, gives us this code.

Now we can add the modular inverse code, and calculate all the missing parts. We can also use Python's pow which will speed up the calculations as stated in the documentation:

pow(x, y[, z]) - return x to the power y; if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z).

We have the message. Last thing will be to turn it into a hexadecimal number, and calculate the ASCII characters, as we know we have to decrypt the ciphertext.