2
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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<e$ 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.

$\endgroup$
4
  • $\begingroup$ in this question's answer Deciphering the RSA encrypted message from three different public keys says that you need $e$ ciphertext. $\endgroup$
    – kelalaka
    Oct 30, 2018 at 18:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Oct 30, 2018 at 19:25
  • $\begingroup$ I'm fine with your solution. if $e=5$ then 5 $c$'s? $\endgroup$
    – kelalaka
    Oct 30, 2018 at 19:28
  • 1
    $\begingroup$ @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) $\endgroup$
    – fgrieu
    Oct 30, 2018 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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