24
$\begingroup$

I'm having trouble understanding the algorithm for finding the original message $m$, when there is a small public exponent. Here is the example I'm trying to follow (you can also read it in the 'Low exponent RSA paragraph' of this article- http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/rsa.pdf):

Someone sends a message, $m$ to 3 people (without any padding) with public keys $n_b$, $n_c$ and $n_d$ and public exponent of 3. The article says:

By using the Chinese Remainder Theorem, the eavesdropper computes a number $c$ such that $c = m^3 \mod n_b \cdot n_c \cdot n_d$.

Maybe I don't completely understand the Chinese Remainder Theorem, but I don't understand how you could choose a system of congruences to solve that would end up being equivalent to $c = m^3 \mod n_b \cdot n_c \cdot n_d$ when you don't know what $m$ is. Can you please help me understand what to use as the system of congruences to get to that point because I think I understand the rest.

$\endgroup$
2
  • 5
    $\begingroup$ The lesson from this attack is that RSA encryption MUST pad the message to be enciphered with randomness, distinct for each destination, as in PKCS#1 RSAES; a secondary lesson is that bad uses of RSA tend to get worse with low exponent; it should not be that RSA with low exponent is always weak. $\endgroup$
    – fgrieu
    Mar 17, 2013 at 9:33
  • 1
    $\begingroup$ Glad you found the right site :) $\endgroup$
    – Maarten Bodewes
    Mar 17, 2013 at 15:30

1 Answer 1

36
$\begingroup$

You don't need to know $m$. You know $m^3$ modulo each modulus, which is sufficient. You want to find:

$$c \equiv m^3 \pmod{n_b}$$

$$c \equiv m^3 \pmod{n_c}$$

$$c \equiv m^3 \pmod{n_d}$$

Because $n_b$, $n_c$, $n_d$ are pairwise coprime (assume they have no common factors) a solution must exist.

The Wikipedia page has a nice explanation of the algorithm to find $c$. The actual expression is:

$$c = c_b (n_c \cdot n_d) [ (n_c \cdot n_d)^{-1} ]_{n_b} + c_c (n_b \cdot n_d) [ (n_b \cdot n_d)^{-1} ]_{n_c} + c_d (n_b \cdot n_c) [ (n_b \cdot n_c)^{-1} ]_{n_d}$$

Where $[a^{-1}]_b$ is the multiplicative inverse of $a$ modulo $b$. Note $\gcd{(a, b)} = 1$ is always satisfied. Also, I used the notation $c_b = m^3 ~ \text{mod} ~ n_b$, $c_c = m^3 ~ \text{mod} ~ n_c$, $c_d = m^3 ~ \text{mod} ~ n_d$.

Let's try with some numbers. Suppose someone sends the message $m = 102$ to three different people with textbook RSA, with moduli $n_b = 377$, $n_c = 391$ and $n_d = 589$. So:

$$c_b = 102^3 ~ \text{mod} ~ 377 = 330$$ $$c_c = 102^3 ~ \text{mod} ~ 391 = 34$$ $$c_d = 102^3 ~ \text{mod} ~ 589 = 419$$

So the attacker wants to solve the following system of congruences:

$$c \equiv 330 \pmod{377}$$

$$c \equiv 34 \pmod{391}$$

$$c \equiv 419 \pmod{589}$$

Using the equation above, we obtain (compute each term separately for clarity):

$$t_b = c_b (n_c \cdot n_d) [ (n_c \cdot n_d)^{-1} ]_{n_b} = 330 (391 \times 589) [ (391 \times 589)^{-1}]_{377} = 24471571740$$

$$t_c = c_c (n_b \cdot n_d) [ (n_b \cdot n_d)^{-1} ]_{n_c} = 34 (377 \times 589) [ (377 \times 589)^{-1}]_{391} = 505836734$$

$$t_d = c_d (n_b \cdot n_c) [ (n_b \cdot n_c)^{-1} ]_{n_d} = 419 (377 \times 391) [ (377 \times 391)^{-1}]_{589} = 35452267942$$

$$\therefore c = t_b + t_c + t_d ~ \text{mod} ~ (n_b \cdot n_c \cdot n_d) = 1061208$$

And we get $m = \sqrt[3]{c} = \sqrt[3]{1061208} = 102 = m$.

Note this attack on textbook RSA would work on any exponent given a sufficiently large number of people, of course $e = 3$ is the most realistic setting (and easiest to demonstrate, for obvious reasons).

The idea, of course, being to use these relations with the CRT to manufacture a relation of the form $m^3 \equiv x \pmod{n'}$ where $n'$ is on the order of $n^3$ (and, more crucially, where $1 < m < n$) such that $m^3$ is not reduced (and so you can just take cube roots).

$\endgroup$
3
  • 3
    $\begingroup$ It seems like I need $e=3$ congruences in order to use this attack. How and why does e influence the number of congruences? If I am correct, CRT doesn't say anything about the number of congruences needed to find a solution - so why would it not just work with two congruences? $\endgroup$ Jul 24, 2014 at 7:24
  • 4
    $\begingroup$ @CGFoX If you had only two congruences then your $n'$ would be on the order of $n^2$ (product of two moduli) and so your $m^3$ would be larger than $n^2$ (by an order of $n$) and you couldn't easily take the cube root without knowing the factorization of the moduli, so it doesn't work. $\endgroup$
    – Thomas
    Jul 24, 2014 at 7:40
  • $\begingroup$ brilliant, thanks a lot, this really helped me $\endgroup$ May 7, 2021 at 14:38

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.