Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
3  
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. –  fgrieu Mar 17 '13 at 9:33
1  
Glad you found the right site :) –  owlstead Mar 17 '13 at 15:30
add comment

1 Answer 1

up vote 9 down vote accepted

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).

share|improve this answer
    
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? –  CGFoX yesterday
1  
@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. –  Thomas yesterday
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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