EVEN RSA CAN BE BROKEN

Challenge

Link	Difficulty	Status
https://play.picoctf.org/practice/challenge/470?category=2&originalEvent=74&page=1

Note

Description

This service provides you an encrypted flag. Can you decrypt it with just N & e? Connect to the program with netcat: $ nc verbal-sleep.picoctf.net 60565

Solution

Let us connect to the server and see what it gives us. We have a RSA cipher text(from the title of the challenge). We also have $N$ and $e$.

Read RSA to understand how it works and what $N$ and $e$ are and then continue with this writeup. It basically depends on the difficulty of finding out the two prime numbers used to compute the public and private key.

As seen in RSA, $N=p\times q$.

If we observe the value of N from the challenge interface above, we can find something interesting. It is ending with an $8$. We know that when a number ends in an even number it’s divisible by $2$ which is s prime number. Now we know both $p=N/2$ and $q$ = 2. Now that we have both $p$ and $q$. We can break the cipher text.

From the challenge we have $N$ and $e$. As seen in RSA, $(N,e)$ forms the public key. The private key on the other hand is $(N,d)$. The above ciphertext is obtained by encrypting the plaintext using the public key(which we have from the components provided). All we need is the corresponding private key. We already have $N$, all we need to compute is $d$.

$$d=e^{-}1\times (\mathrm{mod}\varphi N)$$

By plugging the given components into the equation above we can compute $d$ which then gives us our private key. Now that we have the private key we can use it to decrypt the ciphertext.

Alternatively

You can use https://www.dcode.fr/rsa-cipher to decrypt the text. Enter everything we know into the fields. ciphertext, e, N and q(q=2) and let the tool compute the rest and decrypt the ciphertext. The plaintext we get is the flag.