Correctness of RSA variation using CRT to decrypt?

Question

Consider RSA variation with public key $(e,N)$ where we take $e=3$ and $N=pq$ where:

$p \equiv 1 \text{(mod 3)}$ so that we don't have $\text{gcd}(e,(p-1)(q-1)) \neq 1$

$p \equiv 7 \text{(mod 9)}$ so that we can compute a cubic root of x by doing $x^{\frac{p+2}{9}} \equiv 1 \text{(mod p)}$

For decryption take $d_p = \frac{p+2}{9}$ and $d_q = \frac{q+2}{9}$. Compute $x_p = y^{d_p} \text{(mod p)}$ and $x_q = y^{d_q} \text{(mod q)}$. Finally recover $x = CRT(x_p,x_q)$ where $CRT$ is the function that computes the isomorphism given by the Chinese Remainder theorem.

We know that we can have three different cubic roots for each number in a field. So how is it that given $x_p$ and $x_q$ I can compute $x$ with Chinese Remainder Theorem?

Answer 1

What you have won't necessarily give you the original value of $x$; it'll give you an $x$ where $x^3 \equiv x_{orig}^3$, however, it isn't necessarily the original value.

To demonstrate this, let us take as an example $p=43$ and $q=61$.

Consider $x_{orig}=5$. Then, $y=125$, and $x_p = y^5 \bmod 43 = 8$ and $x_q = y^7 \bmod 61 = 52$; this gives us a $CRT(8, 52) = 1943$, which is not the original $x$. Now, $1943^3 \bmod (43*61) = 125$, and so it also does give the ciphertext, it's just not the same plaintext that you started out with.