2
$\begingroup$

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

  • 0
    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.2012-07-13

1 Answers 1

2

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.

  • 0
    ah gotcha; I didn't understand the second part of your post, but i see now. But that brings to mind the following question: what did the problem mean when it said "decrypt every message encrypted with PA *with high probability*? If we used the method in this answer and had it loop indefinitely until a success, then it is guaranteed to return the correct answer when it terminates, right?2017-12-29