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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Dec 1, 2015 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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