I understand that if the same message is sent to 3 people with $e=3$ that even with different public keys, the message can be decoded using the Chinese Remainder Theorem.

I have tried to figure out the steps to do so, but I am unable to actually lay it out even using small numbers. How would one decrypt a message $m$ = 10, for example with $n_1=6$, $n_2=35$, and $n_3=143$, with $e=3$?

  • 2
    $\begingroup$ Did you search this site. There are examples of this. $\endgroup$ – kelalaka Mar 8 at 10:24
  • $\begingroup$ @kelalaka I have searched, it was more general and I could not replicate it myself. I think that the answer below is helpful in seeing the process though. $\endgroup$ – newm Mar 8 at 10:58
  • 1
    $\begingroup$ Duplicate of this, except with small values. There's a simple answer, and mine, with a step-by-step method (restrict to item 5). $\endgroup$ – fgrieu Mar 8 at 11:31
  • $\begingroup$ Since you don't know the name: Håstad's broadcast attack. $\endgroup$ – kelalaka Mar 8 at 11:36

We have the three cipher texts $m^3\equiv c_1\equiv 4\pmod{6}$, $m^3\equiv c_2\equiv 20\pmod{35}$ and $m^3\equiv c_3\equiv 142\pmod{143}$. An application of the Chinese remainder theorem tells us that $m^3\equiv 1000\pmod{30030}$, but because $m$ is less than $\root 3\of{30030}$ we know $m^3=1000$. A regular cube root now recovers $m=10$.


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