# Probabilistic RSA, IND CPA

Suppose we have classic RSA scheme. Let $n=pq$, $e$ public, $d$ secret.

Then message(M), not empty(not 0), is encrypted by choosing random $r$ and computing $A=(r^e)^e$ and $B=(Mr)^e$

$(A,B)$ is then cipher text.

Why is this not IND-CPA secure? Have trouble grasping IND-CPA concept.. well concept is clear, but how to prove it?

Given above scheme, my thoughts are, since we are able to feed $M=1$ to oracle, we receive $r^{e^2}$ and $(r^2)^e$, but that thought leeds me absolutely nowhere.

• Hint: what if we compute $B^e$, what could we do with that? – poncho Dec 1 '15 at 20:36
• Would give $(Mr^e)^e$, which is different/not $(r^e)^e$ if $M_1=1$ and $M_2\neq 1$ but! $(A,B)$ is calculated each time with different $r$ – Timo Junolainen Dec 1 '15 at 20:41
• @Timo Junolainen Yes, it is different. Still $(A,B)$ pair is calculated for the same $r$. So, division is available. Thanx poncho. – Vadym Fedyukovych Dec 1 '15 at 21:40

I think i got it.

Query:

Let $m={1,2}$, and query $oracle(m)=(A,B)$

Checking:

Lets compute $s=B^e=(m^er^e)^e=m^{e^2}A$

Lets compute $sA^{-1}=\frac{m^{e^2}r^{e^2}}{r^{e^2}}=m^{e^2}$

if $s=1$ then $m=1$, $m\neq 1$ otherwise

Hopefully logic holds.

• Pretty much it. Actually, if you want to make it a bit simpler, you can just compute $M^{e^2}A - B^e$; that's 0 for any $M$ with this method. However, your observation suffices for showing that this is not IND-CPA – poncho Dec 1 '15 at 22:45