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?


1 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.

  • $\begingroup$ so i can consider this scheme as incorrect? $\endgroup$ Dec 6, 2016 at 0:11
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Dec 6, 2016 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.