1
$\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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – roninpro Jul 13 '12 at 6:29
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Glad to see that my comment above wasn't far off. Your answer has been upvoted! $\endgroup$ – roninpro Jul 13 '12 at 6:34
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 13 '12 at 7:13
  • $\begingroup$ 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? $\endgroup$ – xdavidliu Dec 29 '17 at 5:25
  • $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Dec 29 '17 at 5:34
  • $\begingroup$ 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? $\endgroup$ – xdavidliu Dec 29 '17 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.