6
$\begingroup$

Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed.

So I use the fact that the decryption function is multiplicative: $d_K(y_1)d_K(y_2)= d_K(y_1y_2)$.

Thus we have $d_k(y\hat{y})=x\hat{x}$.

Now if $y\in \mathbb{Z}_n$ is a unit then we set $\hat{y}=y^{-1}$ and thus $x\hat{x}=1$ implying that $x=(\hat{x})^{-1}$

And if $y\in\mathbb{Z}_n$ is a zero divisor then we choose $\hat{y}$ such that $y\hat{y}=0$ and thus $x$ is the zero divisor associated to $\hat{x}$.

Is this correct?

Improve this question
$\endgroup$
3
  • $\begingroup$ Only textbook RSA is susceptible to chosen ciphertext attack; RSA as actually used is not. Your technique works at least in the first branch where $\gcd(N,y)=1$, though you should clarify that the adversary submits $\hat y$ for decryption, thus obtains $\hat x$, then deduces $x$; and there are other options to the attacker giving a much wider choice of $\hat y$, using knowledge of $e$. For other cases, I duno what "the zero divisor associated to $\hat x$" is, and there are attacks requiring no query. $\endgroup$
    – fgrieu ♦
    Apr 21, 2013 at 7:38
  • 1
    $\begingroup$ Cross posted? math.stackexchange.com/questions/367739/… Different user, but same question. $\endgroup$
    – mikeazo
    Apr 21, 2013 at 11:24
  • $\begingroup$ @mikeazo: It is indeed the same user, as shown by following the link pajamas, then mathematics, which leads to the other identity. The question is fine, only worded in more mathematical than cryptographic terms, and a bit obviously basic homework or exercise, but showing some effort. $\endgroup$
    – fgrieu ♦
    Apr 22, 2013 at 10:57

1 Answer 1

Reset to default
2
$\begingroup$

You can choose a random number r, and let $\hat{y}=y\cdot r^e \mod n$. Then, invoke the decryption query on the ciphertext $\hat{y}$ and suppose that the answer is $x'$. Then, you can extract $x=x/r\mod n$.

Improve this answer
$\endgroup$

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.