# Correctness of RSA variation using CRT to decrypt?

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?

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.
• @Rodrigo: yes, unless you address the plaintext ambiguity problem somehow. If both $p, q \equiv 7 \pmod{9}$, then for (almost) every valid ciphertext, there will be 9 possible plaintexts; as written, the cryptosystem gives no indication which was is the correct one. – poncho Dec 6 '16 at 1:19