Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

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.