Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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. – fgrieu Apr 21 '13 at 7:38
Cross posted?… Different user, but same question. – mikeazo Apr 21 '13 at 11:24
@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. – fgrieu Apr 22 '13 at 10:57
@fgrieu, I see, thanks. – mikeazo Apr 22 '13 at 12:43

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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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