# Breaking RSA using Chinese Remainder Theorem

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?

• What do you mean "same public key but different values of n"? n is part of the public key. – mikeazo Feb 25 '18 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 '18 at 14:47
• 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 '18 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.

• With proper padding, e=3 isn't really an issue. – mikeazo Feb 25 '18 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 '18 at 17:30
• Why would a bigger $e$ make it much more difficult? I see that we then always have the $m^e > n$ situation, but is this enough? (In other words, is roots with modulus way harder than without?) – Marian Mar 22 '19 at 11:19
• @Marian Yes it is way harder to compute a root with modulus. In fact, to compute it we need to know the modular inverse of the exponent in order to compute the root. If we don't have the modular constraint, the inverse of e is just -e, but with the modular constraint, the modular inverse of e is d. In other word, if you can compute the modular e-th root of c without knowing the private key, you broke RSA ! – Faulst Mar 22 '19 at 12:51