This is a real piece of SageMath/Python code (Jupyter) I devised for the example. Jupyter exported HTML. Three 4096-bit RSA keys, but (public) exponent is too low - 3. If the same message was encrypted to these 3 keys, the message can be recovered. Let's see, how it works.
Chinese Remainder Theorem states, that for a system of equation...
... (unique) c can be recovered, given the fact that we know c1/c2/c3/p1/p2/p3 and p1/p2/p3 are coprimes to each other.
Now a message encrypted to three RSA public keys is:
An attacker, knowing three ciphertexts (c1/c2/c3) and three RSA public keys (e/p1/p2/p3) can calculate \( m^e \) without effort. If e is 3, getting m is simply finding cube root. p1/p2/p3 are (most often) coprimes to each other.
Next you'll see a DIY homebrew algorithm from stack overflow, that can be used instead of CRT. Simple and fast. Getting message as big as 4096-bit is no problem at all. But at least three recipients are required. Two are not enough.
If you drop the crt() function call (which is SageMath function) and use only this DIY function (solve_eq()), this will converts to pure Python code.
I tried keys with e=5, but both SageMath and Mathematica can't extract 5th root.
It's important to note that even in case of large exponent (like 65537), we can still recover \( m^e = m^{65537} \), but finding \( m \) would be much harder, if possible at all. So this information (\( m^e \)) is useless.
The moral of the story: use a large public exponent. A common exponent is 0x10001 (65537). All keys generated by OpenSSL use this exponent. Also, make all encrypted messages unique. This is achieved by adding some (random) salt or padding.
All the files. Including Wolfram Mathematica code, mostly the same. I used Mathematica for prime generation, because SageMath is too slow on this. Also, SageMath/Jupyter code.
More information about RSA is in my book.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.