2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ What do you mean "same public key but different values of n"? n is part of the public key. $\endgroup$
    – mikeazo
    Feb 25, 2018 at 14:45
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Feb 25, 2018 at 14:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mariuslp
    Feb 25, 2018 at 14:47

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ With proper padding, e=3 isn't really an issue. $\endgroup$
    – mikeazo
    Feb 25, 2018 at 16:31
  • $\begingroup$ 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. $\endgroup$
    – Faulst
    Feb 25, 2018 at 17:30
  • $\begingroup$ 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?) $\endgroup$
    – Marian
    Mar 22, 2019 at 11:19
  • 2
    $\begingroup$ @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 ! $\endgroup$
    – Faulst
    Mar 22, 2019 at 12:51

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.