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.

  • 2
    $\begingroup$ Hint: what if we compute $B^e$, what could we do with that? $\endgroup$
    – poncho
    Dec 1 '15 at 20:36
  • $\begingroup$ 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$ $\endgroup$ Dec 1 '15 at 20:41
  • $\begingroup$ @Timo Junolainen Yes, it is different. Still $(A,B)$ pair is calculated for the same $r$. So, division is available. Thanx poncho. $\endgroup$ Dec 1 '15 at 21:40

I think i got it.


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


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.

  • $\begingroup$ 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 $\endgroup$
    – poncho
    Dec 1 '15 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.