Show that if the encryption exponent $3$ is used for the RSA cryptosystem by three different people with different moduli, a plaintext message $P$ encrypted using each of their keys can be recovered from these resulting three ciphertext messages.
Proof. We have
$$x_1\equiv P^3\pmod{n_1},$$
$$x_2\equiv P^3\pmod{n_2},$$
$$x_3\equiv P^3\pmod{n_3},$$
and using the Chinese Remainder Theorem, we can get
$$P^3\equiv x_1(n_2n_3)(n_2n_3)^{-1}+x_2(n_1n_3)(n_1n_3)^{-1}+x_3(n_1n_2)(n_1n_2)^{-1}\pmod{n_1n_2n_3}.$$
Therefore, $P$ can be found by testing all cubes that satisfy this congruence. $\square$
Does this proof seem rigorous enough, or should I step it up one more notch and compute for $P$? Or is perhaps the exercise asking for something else? What do you guys think? Thanks in advance!
Best Answer
The basic idea is that by the configuration of RSA you know that $0 < P^3 < N_1 N_2 N_3$. But also by the Chinese remainder theorem you are guaranteed a unique solution $p$ to the congruences, with $p$ lying between $1$ and $N_1 N_2 N_3 - 1$.
Thus these numbers coincide (i.e. $P^3 = p$) and we get equality, not just congruence. This enables you to then take the cube root and regain the plaintext $P$.
The point of this question is to show you that sometimes in RSA we can avoid guesswork/brute force and if you fall into certain traps then the system is totally insecure.