2
$\begingroup$

Considering plain RSA encryption, assume we have B who wants to send 10 messages to either A1 or A2. The recipients' public key, namely the exponent e1, e2 and prime product n1, n2 for A1/A2 respectively, is publicly known.

When B sends out, he will either encrypt his messages via $c_i = (m_i)^{e_1} mod (n_1)$ or $c_i = (m_i)^{e_2} mod (n_2)$

Let's assume eavesdropper E gets hold of the 10 encrypted messages $c_i$. Given that she knows e1, e2, n1, n2 - while she can't figure out the messages m themselves, can she figure out whether B sent the messages to A1 or A2, and if so, how?

$\endgroup$
  • 2
    $\begingroup$ What research have you done? What have you tried, and what are your thoughts? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. Are all the messages the same? Have you searched on Crypto.SE? There are standard attacks if the exponent is small and you send the same message every time. There are standard attacks if you have no padding: search for "textbook RSA". There are easy attacks if $n_1,n_2$ are very different in size. $\endgroup$ – D.W. Oct 9 '15 at 16:34
  • $\begingroup$ I have already went through the attacks mentioned in the famous "Twenty Years of Attacks on the RSA Cryptosystem" by Dan Boneh, but most attacks aim to figure out the private key or the plaintext and make assumptions about d and/or e. What about a situation like the one i described? You don't have to provide me the answer, but perhaps refer to a treatise on RSA anonymity? $\endgroup$ – Marcel Oct 10 '15 at 14:12
  • $\begingroup$ It's still not clear whether all the messages are the same, or whether the messages use padding or not. I suggest that you edit the question to (a) include all information from the comments, so the question stands on its own, (b) include all relevant information that you know, such as whether the messages are padded, whether they are the same, whether $n_1,n_2$ are very different or how they are chosen, and so on. That affects the answer. I expect this will help you get better answers. $\endgroup$ – D.W. Oct 10 '15 at 23:43
  • $\begingroup$ It is not specified, but we should assume that (1) the messages are not the same (2) only textbook plain RSA, so no padding, (3) no further assumptions about n1, n2 $\endgroup$ – Marcel Oct 11 '15 at 11:58
  • $\begingroup$ OK, please edit the question to incorporate that information in the question. We want questions to stand on their own -- readers shouldn't have to read the comments to understand the question (and comments are intended to be transitory and can disappear). Thank you! $\endgroup$ – D.W. Oct 12 '15 at 2:32
3
$\begingroup$

I'll just expand one of the attacks mentioned in D.W.'s comment; this attack seems the most relevant to your question, but other attacks may exist according to the parameters you actually use.

Ideally, an encryption can be viewed as a permutation $\pi_i$ (determined by $e_i$), that maps $\{0,\ldots,n-1\}$ to itself. If you don't know the two permutations and you don't know the messages $m_i$, there is no way to tell if you used the permutation $\pi_1$ or $\pi_2$ by only seeing a small number of (image only) samples.

Under certain assumptions, RSA is a good encryption. This means you cannot decrypt a codeword $c$ and find $m$ such that $m^e=c \mod n$, even if you know $e$. Of course, information-theoretically, knowing $e$ gives you all the information you need to find $m$ from $c$–it fully specifies the permutation. But for a computationally-bounded Eve, we assume this is impossible.

However, if $n_1 \ne n_2$, Eve gets a certain advantage in distinguishing ecryptions in the two settings. By definition, $c_1 \in \{0,\ldots, n_1-1\}$ while $c_2 \in \{0, \ldots, n_2-1\}$. So if $n_1$ is very different from $n_2$ (say, $n_2>n_1$), and Eve is lucky to see $c_i \in \{n_1, \ldots, n_2-1\}$, she knows that this message was encrypted using $(e_2,n_2)$. Assuming RSA is close to a random permutation, then this has probability of about $1/(n_2-n_1)$ per sample.

$\endgroup$
  • $\begingroup$ Very well reasoned Ran. The only thing you should explain is how you arrived at the probability value for the permutation and what that implies. $\endgroup$ – Marcel Oct 11 '15 at 11:55

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.