1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Hint: what if we compute $B^e$, what could we do with that? $\endgroup$
    – poncho
    Dec 1, 2015 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, 2015 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, 2015 at 21:40

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2015 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.