Deciphering the RSA encrypted message from three different public keys

Question

I have three different 1024-bit public keys with common exponent $e$ but different moduli. A message $m$ is encrypted (without padding) using the three keys, which results in three different encrypted messages.

Given the three pairs of public keys $(N_i,e)$ and the encrypted messages $c_i=m^e\bmod N_i$ , how do I decipher the original message $m$ ?

Answer 1

In the question, the same message is directly encrypted to three different public keys using textbook RSA. This has dire consequences, including the following (with 1./2./3. not using the multiple public keys, and the answer likely thought at 5. or its extension 6.):

1. It severely limits the size of the message (to less than 128 octets).

2. A guess of the message can be checked by anyone with a public key $(N_i,e)$ and the ciphertext $c_i$, which by a standard assumption in cryptography includes adversaries. They simply encipher a guess of $m$ with $(N_i,e)$ and check it against $c_i$. Poof goes confidentiality if the message is a name on the class roll, a guessable password..

3. If $m$ is less than say $2^{70}$ , there is a good chance that there exits $r<2^{30}$ and $s<2^{40}$ with $m=r\cdot s$. In that case, regardless of $e$, there's a meet-in-the-middle attack recovering $m$: the attacker computes $c_0/r^e\bmod N_0$ for all candidates $r$ and store that for quick search (10 GiB of RAM for hash tables and 128 GiB of seldom used disk will do); then for each candidate $s$ computes $s^e\bmod N_0$ and searches that; it there's a match, $m$ is found as $r\cdot s$ .

4. If $e$ is small, and/or the message $m$ is small enough (less than about $2^{1023/e}$ ), then $m=\sqrt[e]{c_i}$ (where $i$ is the index of the largest $N_i$ and it is used straight, not modular arithmetic). Even though the $c_i$ are distinct, this attack could still work in the case at hand, when $m$ is close enough to the limit $\sqrt[e]{\max(N_i)}$ . Further, that e^th root attack can be easily extended to like $m<2^{1060/e}$, and much more when we consider the multiple encryptions, see 6.

5. If $e=3$, the system is plain vulnerable to the archetypal RSA broadcast attack (also the simplest form of Håstad's broadcast attack). $e=3$ is a common choice in textbook RSA, because that allows the fastest encryption, using modular squaring and one modular multiplication; and is as safe as can be when $m$ is essentially random in an interval like $[0,N_i)$ and chosen independently for each encryption (contrary to the situation at hand where the same $m$ was used thrice).

   We should first check that the three $\gcd(N_i,N_j)=1$ for $0\le i<j<3$. Otherwise, the GCD is a non-trivial factor of $N_i$ and $N_j$, and we have factored $N_i$ and $N_j$ (at least in two-factors RSA), and can compute a working private exponent and decipher, per the normal way in textbook RSA. Succeeding in that way is not supposed to happens, but does here and there, due to Random Number Generators that are not true, and gave the same results on different platforms, when they should not; and in academic exercises.

   Having thus checked (or blindly assumed) that we can invoke the Chinese Remainder Theorem, we use it to solve for $x$ the system of 3 equations $x\equiv c_i\pmod{N_i}$ for $0\le i<3$ with $x\in[0,\prod N_i)$. That goes:

   • $x\gets c_0$
   • $N\gets N_0$
   • For each $i$ with $1\le i<3$
     • $x\gets(((N^{-1}\bmod N_i)\cdot(c_i-x))\bmod N_i)\cdot N+x$
     • $N\gets N\cdot N_i$
   • At that point $N=\prod N_i$, and $x$ is the desired solution.
     
     

   Then we computes $m=\sqrt[3]x$ (which will be an exact integer); this is a non-modular cube root, and thus easy. This will always work because $m<\min(N_i)$, thus $m^3<N$, thus $m^3=x$ since by the CRT, there's no other $m$ with $m^3\equiv c_i\pmod{N_i}$.

6. Attacks 4. and 5. combine and can work for some $e>3$. If $m<\sqrt[e]{\prod N_i}$ , then after computing $x$ just as above it comes $m=\sqrt[e]x$ (which will be an exact integer).

   This can be extended to $m$ up to about $(3072+k)/e$-bit with with $O(2^k)$ work; with $e=5$ perhaps $m$ up to $\approx78$ bytes (out of the maximum capacity of $<128$ bytes). An idea is to scan integers $r$ with $0\le r<2^k$, until $\sqrt[e]{r\cdot N+x}$ is an exact integer.

   Further, we can save significant computational work in this search by reusing an approximation of $\sqrt[e]{r\cdot N+x}$ in order to test if $\sqrt[e]{(r+1)\cdot N+x}$ is an integer, and computing an approximation of $\sqrt[e]{(r+1)\cdot N+x}$.

   And perhaps that attack can get even better; see this answer wondering about extending the e^th root attack by combining Coppersmith's theorem with lattice methods.

---

Conclusions:

• Do not use textbook RSA without random encryption padding, unless enciphering a mostly random $m$ nearly as wide as the public modulus, and enciphering that $m$ only once.
• Rather, use a sound random padding for each RSA encryption, and hybrid encryption for the whole thing.
• Do not conclude that a large $e$ like $e=65537$ will always save the day; it does not. Apply the above!

Answer 2

If $e = 3$ we can use Hastad's Broadcast Attack to recover $m$. We can write the three encrypted messages as follows:

$$c_1 \equiv m^3 \text{ mod } N_1$$ $$c_2 \equiv m^3 \text{ mod } N_2$$ $$c_3 \equiv m^3 \text{ mod } N_3$$

Using the Chinese remainder theorem it is possible to find a value $c_4$ that has the following properties:

$$c_4 \equiv c_1 \text{ mod } N_1$$ $$c_4 \equiv c_2 \text{ mod } N_2$$ $$c_4 \equiv c_3 \text{ mod } N_3$$ $$c_4 \equiv m^3 \text{ mod }N_1N_2N_3$$

Note that in RSA any message we encrypt must be smaller than the modulus, so $m$ is smaller than $N_1, N_2, N_3$. This implies that $m^3 < N_1N_2N_3$, which in turn implies that $c_4 = m^3$. So to recover $m$ all we have to do is compute $m = \sqrt[3]{c_4}$ (for which there are known efficient algorithms).

In general, if we have $e = x$ then we need to have $x$ encryptions of $m$ under the same $e$ and different $N$ for this attack to work. This follows from the fact that we need to be able to find a value congruent to $m^e$ mod some value greater than $m^e$ so that we can take the $e$th root of that value to recover $m$. If we have $e$ moduli for which we know $c_i \equiv m^e \text{ mod } N_i$ then we can always construct such a value via the CRT since for $m < N_i$ it holds that $m^e < N_1N_2 ... N_e$.

Answer 3

If $e$ is low, you can do next:
Solve system of three equations $x_1=c_1 \bmod n_1$, $x_2=c_2 \bmod n_2$, $x_3=c_3 \bmod n_3$ using Chinese Reminder Theorem. You should obtain result like $x=a \bmod n$.

Then calculate e-th degree root of $a$.

This works with low exponents, because it's hard to compute n-th degree root.