# Attack on RSA when I know $e$, ciphertexts $c_1, c_2$ of the same message $m$ with 2 coprime modules?

I know that the same message $$m$$ was sent to two people resulting in ciphertexts $$c_1, c_2$$. The public keys are $$n_1$$ and $$n_2$$, $$gcd(n_1, n_2) = 1$$. And $$e=3$$ in both cases. How can I retrieve the original message without brute-forcing it?

I.e. the exponent $$e$$ is the same in both public keys, but the modulus $$n$$ is different: $$n_1, n_2$$.

• My question is different: e is the same, n is different – SlowerPhoton Oct 30 '18 at 17:35
• CRT based attack requires 3 ciphertexts for $e=3$ See the comment at Low Public Exponent Attack for RSA – kelalaka Oct 30 '18 at 18:08

The problem seems like a variant of Håstad's broadcast attack, except that is usually stated with $$e$$ ciphertexts, when here there is $$2 ciphertexts.

We know $$m^e$$ modulo $$n_1$$ and modulo $$n_2$$ (that's the givens $$c_1$$ and $$c_2$$), thus we can compute $$m^e\bmod(n_1\,n_2)=y$$ using the Chinese Remainder Theorem, per $$y\gets(n_2^{-1}(c_1-c_2)\bmod n_1)\,n_2+c_2$$

If we are lucky enough that $$m<\left\lfloor\sqrt[e]{n_1\,n_2}\right\rfloor$$ (roughly, $$m$$ of bit size less than $$1/e$$ of the sum of the bit sizes of the moduli), 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 $$i$$, if any of the $$y_i=i\,c_1\,c_2+y$$ is exactly an $$e^\text{th}$$ power; that slightly extends the attack.

Note: none of this is RSA as correctly practiced. What's raised to the power $$e$$ modulo $$n$$ should not be the message, but a randomly padded message (per e.g. RSAES-OAEP) computed separately for each ciphertext sent, and almost as wide as the public modulus.

• in this question's answer Deciphering the RSA encrypted message from three different public keys says that you need $e$ ciphertext. – kelalaka Oct 30 '18 at 18:47
• @kelalaka: we need $e=3$ ciphertext for the attack to succeed for any $m$, and that's how the standard Håstad's broadcast attack is usually stated. This is a variant, and it will succeed only if $m$ is small enough. – fgrieu Oct 30 '18 at 19:25
• I'm fine with your solution. if $e=5$ then 5 $c$'s? – kelalaka Oct 30 '18 at 19:28
• @kelalaka: yes the standard Håstad's broadcast attack works for 5 $c_i$ when $e=5$, whatever $m$. It could work for less $c_i$ for small enough $m$, namely for $m<\left\lfloor\sqrt[e]{\displaystyle\prod n_i}\right\rfloor$ (or slightly above that thresold with some extra guesswork) – fgrieu Oct 30 '18 at 20:03