1
$\begingroup$

I have this question I am trying to figure out the answer about RSA. I'd be grateful if someone could actually help me understand how the procedure would work. I am new to cryptography and with all the maths in it, I am barely understanding it.

Assuming that we have a sender A and 2 recipients B and C. This sender wants to send 12 messages.

If A wants to send to B he'd use B's public key $(n_B,e_B)$. Meaning: $$\text{ciphertext}_i = (\text{plaintext}_i)^{e_B} \bmod n_B$$

If A wants to send to C he'd use C's public key $(n_C,e_C)$. Meaning: $$\text{ciphertext}_i = (\text{plaintext}_i)^{e_C} \bmod n_C$$

An attacker gets the 12 ciphertexts A encrypted. He also knows the public key of B and C.

How can he determine whether A sent her messages to B or C?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Does the attacker knows the 12 messages? if so, this is textbook RSA, he can also encrypt for B and C and compare. $\endgroup$
    – kelalaka
    Oct 31, 2019 at 17:36
  • 1
    $\begingroup$ Hint1: the attacker could send the ciphertexts to B and C, and check which appears to have deciphered it (if one sends an answer to Alice on the tune of what is this giberish, the message likely was the other; you already said that gives another info). Hint2: if the attacker does not know the plaintexts (including, if proper RSA encryption padding is used), s/he can use a property following from the definition of $x\bmod n$: that's the uniquely defined $y$ with $x-y$ multiple of $n$ and $0\le y<n$. Depending on the key generation process, that could have a fair chance to work. $\endgroup$
    – fgrieu ♦
    Oct 31, 2019 at 18:17
  • $\begingroup$ @kelalaka the attacker doesn't know the messages, he only gets the ciphertext and needs to figure out their destination $\endgroup$
    – Nesr
    Oct 31, 2019 at 19:30
  • $\begingroup$ By the way, is this homework? $\endgroup$
    – kelalaka
    Oct 31, 2019 at 19:31
  • 1
    $\begingroup$ BTW, beside the textbook math - real world protocols and formats might also have additional info like keyid, keyhash or key copy. For example in pgp you can request pgp to not add key information so the recipient key is not obvious. But attackers can still replicate the encryption if they have a instance of the session key. $\endgroup$
    – eckes
    Oct 31, 2019 at 20:21

1 Answer 1

Reset to default
4
$\begingroup$

First, we'll assume that $n_B > n_C$, and we'll assume that he has no knowledge of the plaintext messages (which, if $A$ uses randomized padding, which he ought, is an appropriate assumption, even if the adversary knows the text of the message).

Then, if any of the 12 messages $\mathit{ciphertext}_i \ge n_C$, then he knows that message cannot be to $n_C$ (because the result of the RSA encryption process is always an integer less then the modulus. Hence, if all messages were to the same endpoint, then they all must be to $B$.

In contrast, if all 12 messages $\mathit{ciphertext}_i < C$, then it is possible that the messages were to either, however it is somewhat more plausible that there were to $C$, because of the possibility that, if there were to $B$, that fact would be leaked above.

Now, we can actually estimate the probability that the messages were actually towards $B$, but that fact wasn't leaked; RSA encrypted messages can be modeled as random values between $0$ and the modulus size. Hence, the probability that all 12 encrypted messages happen to be $< n_C$ is approximately $(1 - n_C/n_B)^{12}$; how large that is depends on the relative magnitude of the two modulii.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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