RSA encryption with multiple publickeys

Question

Suppose Bob wishes to send an encrypted message $M$ to 4 people $P_1,P_2,P_3,P_4.$ Each one has their own RSA key $(N_1;e_1),(N_2;e_2),(N_3;e_3),(N_4;e_4)$.

The encrypted messages are $C_i=M^{e_i}\bmod{N_i}.$

The $e_i$ are pairwise distinct (per comment).

How to decipher the original message $M$ ?

Answer 1

Eureka: this looks like a variant of Håstad's broadcast attack after all. We workaround the different $e_i$ by using the Least Common Multiple of an adequate subset of the $e_i$, and can still succeed if the bit size of $M$ is low enough.

Among the 11 subsets of $\{1,2,3,4\}$ with more than 1 element, find which minimizes the quantity $\operatorname{lcm}(e_i)/\displaystyle\sum\log_2(N_i)$ where the Least Common Multiple and the sum are computed for $i$ in the subset. In the rest of this section, $i$ varies in this subset.

Compute $e=\operatorname{lcm}(e_i)$. Compute $D_i\gets C_i^{(e/e_i)}\bmod N_i$. It holds that $D_i=M^e\bmod N_i$. That allows to compute $y=M^e\bmod\left(\displaystyle\prod N_i\right)$ using the Chinese Remainder Theorem.

If we are lucky enough that $m<\left\lfloor\sqrt[e]{\displaystyle\prod N_i}\right\rfloor$ (roughly, $m$ of bit size less than $1/e$ of the sum of the sizes of the moduli in the set), then $y$ will be exactly the $e^\text{th}$ power of some integer $x$, we can get that $x$, and it will be $M$.

If not, we can try, for incremental $j$, if any if the $y_j=y+j\displaystyle\prod N_i$ is exactly an $e^\text{th}$ power; that slightly extends the attack.

---

If that does not work, we are left with generic attacks that do not take advantage of the operational goof of using the same $M$ for multiple recipients:

1. Common prime: We can compute $\gcd(N_i,N_j)$ for the 6 $(i,j)$ with $i<j$, and if any of these is not $1$, we have factored $N_i$ and $N_j$ (for two-primes RSA). With a full factorization, we can decipher the normal way. This attack has occasionally succeeded on deployed cryptosystems, an example is related there.
2. The $e^\text{th}$ root attack: perhaps $M$ is small enough that $M^{e_i}<N_i$ for some $i$. We can chose the $i$ with the smallest $e_i\log_2(N_i)$ and try if $\sqrt[e_i]{C_i}$ is an integer, in which case that integer is $M$. We can similarly try $\sqrt[e_i]{k\,N_i+C_i}$ for small $k$.
3. Search of $M$: If there's context about $M$ (like, it's a credit card number in ASCII, or a password), it might be possible to find it by enumeration. We can check a guess of $M$ with the $(C_i,N_i,e_i)$ allowing the fasted test of $C_i=M^{e_i}\bmod{N_i}$.
4. Meet-in-the-middle search of $M$: it is reasonably likely that $M=X\,Y$ for sizable integers $X$ and $Y$, $X<Y$, in which case there is an attack of cost $O(Y)$ with $O(X)$ memory. For the appropriate $i$ as in 3, it tabulates candidates $X^{-e_i}\,C_i\bmod{N_i}$, then searches among these candidates $Y^{e_i}\bmod{N_i}$. A match reveals $X$ and $Y$, thus $M$.
5. Factoring an $N_i$: if any recipient uses a key generator with a flaw, including too small an $N_i$, it might be possible to factor that $N_i$, then decipher normally.

Only attack 1 is specific to multiple keys. The others simply select the most vulnerable key.

---

All attacks in this answer fails for RSA as correctly practiced. 1 and 5 fail for proper key generator. Other attacks fail when what's raised to the power $e$ modulo $N$ is a randomly padded message (per e.g. RSAES-OAEP) computed separately for each ciphertext sent, and almost as wide as the public modulus.