Cracking a Simple RSA Encryption

Question

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!

Answer 1

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.

Answer 2

Let $n_1$ be the smallest modulus and $n_3$ the largest. Then $P < n_1$ and thus $$P^3 < n_1 n_2 n_3$$. This enables you to solve the system

$$P^3=z_i n_i+x_i,\quad i=1,2,3$$

uniquely for $z_i$ over integers [just take the three pairwise differences and use knowledge that $z_i$ lie in $[1,\ldots,n_j n_k]$ and this should work I think. Then obtain $P^3$ and take integer cube root.

Edit: Use binary search with complexity at most $$c \log(n_2 n_3) \leq 2c \log(n_3) =O(\log n_3).$$ The cube root complexity should also be comparable.