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

• Glad to see that my comment above wasn't far off. Your answer has been upvoted! – roninpro Jul 13 '12 at 6:34
• Thanks, @roninpro. The content is more or less identical to that of your comment. This type of a probabilistic approach is simple, but my friends in crypto have described many a similar attack, so I guess it is bread-and-butter for them. – Jyrki Lahtonen Jul 13 '12 at 7:13
• wait, what if N = 1000, the set S is {11, 12, 13...20}, which is exactly 1 percent of N, and P(M1) = 500? Then all P(M1) * P(M2) are either 0 or 500, neither of which are in S, so this method would fail in that case? – xdavidliu Dec 29 '17 at 5:25
• @xdavidliu In RSA $n$ is a product of two primes. Also, if we run into a case where $P_A(M_2)$ is not invertible modulo $n$, then we can factor $n$ and we have cracked the key. – Jyrki Lahtonen Dec 29 '17 at 5:34
• ah yes, I forgot about n=pq. However, suppose we have n = 202, which is a product of two primes, and M1 = 101, and the set S is {1, 2} (it wouldn't be exactly a 1 percent success rate, but close). Would that break this method? – xdavidliu Dec 29 '17 at 5:43