# Example of breaking RSA with CRT [duplicate]

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

• Did you search this site. There are examples of this. Commented Mar 8, 2021 at 10:24
• @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.
– newm
Commented Mar 8, 2021 at 10:58
• Duplicate of this, except with small values. There's a simple answer, and mine, with a step-by-step method (restrict to item 5).
– fgrieu
Commented Mar 8, 2021 at 11:31
• Since you don't know the name: Håstad's broadcast attack. Commented Mar 8, 2021 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$$.