# Prove that textbook RSA is susceptible to a chosen ciphertext attack

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?

-
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? math.stackexchange.com/questions/367739/… 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$.

-