# RSA probabilistic decryption problem

I encountered this problem in an algorithms book and could not see how multiplicative could be used as a probabilistic algorithm.

Using the fact that RSA is multplicative: $$P_A(M_1) P_A(M_2)\equiv P_A(M_1M_2)\pmod n$$ if someone could efficiently decrypt 1 percent of messages from $Z_n$ encrypted with $P_A$, then he could employ a probabilistic algorithm to decrypt every message encrypted with $P_A$ with high probability

-
Just an idea: suppose $C=P_A(M)$ is a ciphertext we wish to decrypt, and $M$ is the unknown message. Suppose we can efficiently decrypt some class of ciphertexts $C_i=P_A(M_i)$, where the $M_i$ are known messages. Then, look at $CC_i=P_a(MM_i) \pmod{n}$ over all $i$. If we reach an $i$ so that $CC_i$ can be decrypted efficiently, then we will know $MM_i=P_A^{-1}(CC_i)$, which means that $M=P_A^{-1}(CC_i)M_i^{-1}$, the message sought. So at this point, just maybe, your problem boils down to measuring the probability that $CC_i$ can be deciphered efficiently. – roninpro Jul 13 '12 at 6:29

Ok, so the attacker has a way of calculating $M$ from $P_A(M)$, if $P_A(M)$ is in a set $S$ that covers about 1 per cent of the residue classes modulo $n$.
The attacker, facing the task of calculating $M_1$, given $P_A(M_1)$ can then generate a few hundred random $(M_2,P_A(M_2))$ pairs. S/he can then check, whether $P_A(M_1)P_A(M_2)$ is in the set $S$ for any $M_2$. If that happens, the attacker will know $$M_1M_2=P_A^{-1}(P_A(M_1)P_A(M_2))$$ AND s/he will know $M_2$, so figuring out $M_1$ is then easy.
If the choices for $M_2$ were truly random, the probabilities of failure with each $M_2$ are independent from each other, and all about $0.99$. So with, say, $200$ trials, the probability of failure is $0.99^{200}\approx e^{-2}$ or about $13$ per cent. Make four hundred attempts, if that is not good enough.
Observe that there is no need to have a good description of the set $S$. The attacker can just attempt to decode any $P_A(M_1)P_A(M_2)$ that is generated.