# Chosen plaintext attack on textbook RSA decryption

Let $(n,d)$ be an RSA private key and $(n,e)$ the corresponding public key.

1. Generate a secret random $r$ from $(\mathbb{Z}/n\mathbb{Z})^*$
2. Compute $C’ = C (r^e) \bmod n$
3. Submit $C’$ as a chosen ciphertext and receive back
$M’ = C’ ^ d \bmod n = M r$, since $C’ = (C \bmod n) \times (r^e \bmod n) = (M^e \bmod n) x (r^e \bmod n) = (M r)^e \bmod n$.
4. Deduce $M$ with a division modulo $n$ since $r$ is known: $(M r) r^{-1} \bmod n$.

I am trying to understand a chosen plaintext attack on textbook RSA decryption. If I follow the method above, I must generate a random $n$ from a range of $n-1$ values. How I am I going to know which of my $r$ values is the one I need, because the $n$ value very big? My $e$ value is 65537 and my ciphertext value is very big.

• I am using the java BigInteger to generate a random number from N range Aug 14 '14 at 16:27
• Can you update your question using MathJax? It will make the equations much more readable. Also, what have you tried? Where are you stuck in solving it yourself? Aug 14 '14 at 16:49
• What you are describing is a chosen ciphertext attack, as you are choosing the ciphertext $C'$, receive back the decryption, and you are able to compute $M$. Just pick any value for $r$. Aug 14 '14 at 23:14
• When you say "I must generate a random $n$ from a range of $n-1$ values" do you mean "I must generate a random $r$ from a range of $n-1$ values"? Aug 15 '14 at 14:13
• I will explain more clear the part I stuck ,For example, I randomly select r = 2 and use the formula to find c'. After that I use the C' mod n = M' and C = mod n = M. The purpose I do this because I don't know the Decryption key. So what I gonna do to compare the M' and M value in order to find out my pure plaintext ? Aug 15 '14 at 15:57

You seem to have some misconception here. Obviously, you are investigating chosen ciphertext attacks (CCAs) on textbook RSA instead of chosen plaintext attacks (CPAs). To help you with your understanding I am discussing CPA on textbook RSA first. To analyse all these kinds of attacks we formally model the attack as a game between an adversary (trying to break the property) played with a so called challenger.

CPA for textbook RSA

In a CPA game, an adversary can compute arbitrary encryptions of plaintexts of its choice as it is given the public key by the challenger and at some point submits two distinct plaintexts $m_0$ and $m_1$ to the challenger. The challenger then flips a coin to determine a bit $b$ and provides an encryption of $m_b$ (the challenge ciphertext $c^*$) to the attacker and the attacker has to output a guess $b^*$. The adversary wins if the probability that $Pr[b=b^*] -1/2$ is non negligible (in the security parameter). This means that the adversary needs to succeed significantly better than just guessing the bit.

Clearly, textbook RSA does not provide IND-CPA security, since it is deterministic. When the adversary receives the challenge ciphertext $c^*$, he simply encrypts e.g. $m_0$ and if the so obtained ciphertext matches $c^*$, then we have $b^*=0$ and $b^*=1$ otherwise. Note that the probability of winning this game for textbook RSA is 1.

CCA for textbook RSA

This notion is stronger than CPA and this is modelled by giving the adversary additional access to a decryption black-box (oracle) throughout the game, i.e., the adversary is allowed to submit ciphertexts and gets back the respective message, but does not get to hold the decryption key directly.

The only restriction is that the adversary is not allowed to ask the decryption oracle to decrypt the challenge ciphertext $c^*$.

Now lets look at your given procedure. What you describe is a strategy for winning the CCA game for textbook RSA. Note that if the adversary receives the challenge ciphertext $c^*$, he is not allowed to send $c^*$ to the decryption oracle directly. But what the adversary can do is to "blind" the challenge ciphertext with a "blinding value" $r\in \mathbb{Z}_n^*\setminus \{1\}$, i.e., it submits $c'=c^*r^e \pmod n$ to the decryption oracle (note that this is allowed as $c'\neq c^*$). Then the adversary gets back $m'$ from the decryption oracle which has performed a decryption to obtain $m'=(c^*r^e)^d=m_br \bmod n$. Now if the adversary has chosen $r$ as above, i.e., such that it is invertible in $\mathbb{Z}_n$ (which is the case iff $r$ is relatively prime to $n$, i.e., $gcd(r,n)=1$), then the adversary can compute $r^{-1}$ and compute $m_b=m'r^{-1}$ and wins the CCA game with probability 1.

There are subtle differences between IND-CCA1 and IND-CCA2 security, but this explanation should be sufficient here.

Note that when employing a proper padding scheme to textbook RSA such as OAEP, the decryption oracle will only return a decryption if the decryption works correctly, i.e., the decryption oracle checks if the padding of the message is proper. For a "good" padding scheme the probability of ciphertext $c'=c^*r^e \pmod n$ yields a proper decryption is negligible and thus RSA-OAEP provides IND-CCA security as the above discussed attack does not work (with overwhelming probability).

• "which is the case if $r$ is relatively prime to $n$", $gcd(r,n) \neq 1$ should actually be $gcd(r,n) = 1$. You could also clarify with "if and only if". :) Aug 17 '14 at 11:59
• @johnnycrab jup, typo. THX! Aug 17 '14 at 12:03

Simple, $r$ just needs to be co-prime to $n$. To test this check that $gcd(r,n)==1$. This is required since you need to "divide" by $r$, i.e., multiply by $r^{-1}$. $r$ is invertible iff $gcd(n,r)==1$.