# picoCTF 2014: RSA Mistakes

RSA Mistakes was a 200 points cryptography master challenge in picoCTF. The final objective was to recover the encrypted message.

• a traffic capture file in tcpdump format
• a python script

By looking at the pcap file we could notice that there are a bunch of request/responses, which by the problem statement were most likely encrypted using RSA.

Two of these streams, the first and the fourth, were extremely interesting, because two over the three parameters in the request were identical, while the third was not, and on the other side, the reply, which is supposed to be the encrypted message was completely different.

So, at this point, let’s give a look at the server python script and try to figure things out.

The interesting part is the following:

By looking at these instructions we can notice that

• the application accepts 3 parameters as imput, separated by a space
• the program splits them to generate N, e and user_id, where N is the modulus and e is the exponent
• and then it encrypts the message.

But if we look at the encryption function more closely, we can notice that the user_id plays a key role here, as it’s used to modify the supplied message before the RSA encryption is performed.

The encryption itself is done with a typical RSA equation where we have

but m in this specific case is

where t is the user supplied text

So, putting things togeder we have:

• two different encrypted messages
• a small public exponent: 3
• the same public key being used for both messages, because the public key (e, n) is the same in both encryption processes

Plus, we also have a user_id parameter which differs, and allows us to determine a linear relation between the two messages so that

This is a convenient situation, because there is an interesting theorem: the theorem of Franklin-Raiter that states:

Set $e = 3$ and let $(N, e)$ be an RSA public key. Let $M_1 \neq M2 \in \mathbb{Z}^*_N$ satisfy $M_1 \equiv f(M_2) \pmod{n}$ for some linear polynomial $f = \alpha x + \beta \in \mathbb{Z}_N[x]$ with $b \neq 0$ . Then, given $(N, e, C_1, C_2, f)$, the attacker can recover $M_1, M_2$ in time quadratic in $log_2 N$.

The original paper which can be found here: https://www.cs.unc.edu/~reiter/papers/1996/Eurocrypt.pdf

also provides us with all the mathematical functions we need to calculate the value of our plaintext message from the encrypted messages: so all we were left to do was to calculate $M_2$ in function of $M_1$ as shown above, and implement the formula in a python script to compute the values for us; once the plaintext for the message is recovered, it’s then just a matter of extracting $t$.

First let’s start by working on the messages and have them set in a proper way: since we need $\alpha$ and $\beta$ we procede as follows.

Given

• user_id1 as the first message userid
• user_id2 as the second message userid
• t as the plaintext we need to recover
• x as the modular multiplicative inverse of 37

Now that we have $\alpha$ and $\beta$ what remains to do is punch them in our python script with $C_1, C_2$ and $N$ to retrieve $M_1$

Running the above script returns the following output

0x576f772120596f757220666c61672069733a206469645f796f755f6b6e6f775f796f755f63616e5f736f6d6574696d65735f6763645f6f7574736964655f615f6575636c696465616e5f646f6d61696e0a


that converted to ASCII gives us the flag:

Wow! Your flag is: did_you_know_you_can_sometimes_gcd_outside_a_euclidean_domain