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 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 at 16:58
  • You still haven't specified what Bob actually does. – Maeher Oct 25 at 17:12
  • 3
    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 at 18:06
  • @fgrieu a) works as long as $\prod M^{e_i} < \prod N_i$ with fixed $e_i$? – kelalaka Oct 25 at 22:27
up vote 4 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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