When the same message is encrypted for three people who happen to have same public key but different values of n, it is possible to get the value of message by using Chinese Remainder Theorem.

Wherever I have read about this technique, it says that the message value should be smaller than individual values of n. Will someone please elaborate why this restriction? And why does this technique not work if message is greater than any value of n?

  • 3
    What do you mean "same public key but different values of n"? n is part of the public key. – mikeazo Feb 25 at 14:45
  • With the public exponent usually set to a static value, the fourth prime of Fermat, you could even say it is the only variable part of the public key, so having a separate modulus and an identical public key is next to impossible. – Maarten Bodewes Feb 25 at 14:47
  • 1
    Plus, if you're doing textbook RSA, without breaking down the message in chucks, then since everything is done modulo n you can't retrieve anything that is bigger than n, which is maybe why the explanations you read specified that the message should be smaller than n: it's not that the attack doesn't work, it's just that the message is impossible to retrieve. – Mariuslp Feb 25 at 14:47

I guess you are refering to the case where three people have the following public keys : $(n_1, 3)$, $(n_2, 3)$ and $(n_3, 3)$ (yes, $e = 3$, and this attack is one of the reasons we don't use $e = 3$ anymore).

In this case, if the same message $m$ is sent to those three persons, we have the following system : $$ \left\{ \begin{array}{ll} c_1 = & m^3\mod n_1 \\ c_2 = & m^3\mod n_2 \\ c_3 = & m^3\mod n_3 \\ \end{array} \right. $$

Applying the CRT to $$ \left\{ \begin{array}{ll} c_1 = & x\mod n_1 \\ c_2 = & x\mod n_2 \\ c_3 = & x\mod n_3 \\ \end{array} \right. $$ with $x = m^3$ will give you $x = m^3\mod n_1\times n_2\times n_3$

However, we know that $m \lt n_1,\ n_2,\ n_3$ so we have $ m^3 \lt n_1\times n_2\times n_3$ so a simple cubic root will give us the original message.

If the message is greater than any $n_i$, you wouldn't be able to recover it with a simple cubic root because you would have a modular result.

Today, we usually use $e=2^{16} + 1 = 65537$ which make this attack much more difficult to apply.

  • 1
    With proper padding, e=3 isn't really an issue. – mikeazo Feb 25 at 16:31
  • Regarding the question and the attack considered, we consider a schoolbook RSA where the padding is put aside. But indeed, using a proper padding could avoid this issue. – Faulst Feb 25 at 17:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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