# RSA encryption with multiple publickeys

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$$ ?

• There seems to be some information missing. What exactly does Bob send? – Maeher Oct 25 '18 at 16:45
• Its Hastad's Broadcast Attack but I can only find paper that assume all public exponents are equal to 3. In my case its four different exponents – Fatworm Oct 25 '18 at 16:58
• You still haven't specified what Bob actually does. – Maeher Oct 25 '18 at 17:12
• What Maeher is asking is if A) Bob computes the four $M^{e_i}\bmod N_i$ and sends these; B) Bob computes a random padding $\tilde M$ from $M$, computes the four $\tilde M^{e_i}\bmod N_i$ and sends these. C) Bob computes four random paddings $\tilde M_i$ from $M$, computes the four $\tilde M_i^{e_i}\bmod N_i$ and sends these. D) something else, perhaps involving RSA/AES hyvrid cryptography. – fgrieu Oct 25 '18 at 18:06
• @fgrieu a) works as long as $\prod M^{e_i} < \prod N_i$ with fixed $e_i$? – kelalaka Oct 25 '18 at 22:27

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, 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} 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, 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.