2
$\begingroup$

I'm reading Rabin Cryptosystem which requires to compute 4 square roots $r, -r, s,- s$ while decryption of cipher text $c$ such that

$$r = (y_p \times p \times m_q + y_q \times q \times m_p) \mod n $$ $$-r = n - r $$ $$s = (y_p \times p \times m_q - y_q \times q \times m_p) \mod n $$ $$-s = n - s $$

$m_p = c^{\frac{1}{4}(p+1)} \mod p; \, \,m_q = c^{\frac{1}{4}(q+1)} \mod q; \, \, y_p \times p + y_q \times q = 1$

I'm not getting, how we can compute $r, -r, s,- s$ using Chinese Remainder Theorem.

$\endgroup$
  • $\begingroup$ I detailed the procedure to compute the 4 square roots, it should be clear enough. if you have still some doubts, please add a comment, I'll try to clarify. $\endgroup$ – ddddavidee Oct 20 '15 at 9:15
3
$\begingroup$

As first step to compute the four square roots of $c \pmod N$ one can compute the two square roots $\mod p$ and the two square roots $\mod q$ and then using the Chinese Reminder Theorem combine them to the four square roots $\mod N$ where $N = p \cdot q$.

Let's start computing the square root of ciphertext $c \mod p$. Usually $p \equiv q \equiv 3 \pmod 4$. So $m_p = c^{\frac{1}{4}(p+1)} \pmod p$.

Proof: $m_p^2 = c^{2\cdot\frac{1}{4}(p+1)}= c{\frac{1}{2}(p+1)} = c \cdot c^{\frac{p-1}{2}} = c \left( \frac{c}{p}\right) = c \pmod p$, because $c^{\frac{p-1}{2}} = \left( \frac{c}{p}\right) = 1 \pmod p$, where $\left( \frac{c}{p}\right)$ is the Legendre Symbol of $c \mod p$ and $c$ is a square (so the symbol is equal to 1).

Similarly: $m_q = c^{\frac{1}{4}(q+1)} \pmod q$.

Now you have the two square roots modulo the two primes numbers $(m_p, m_q, -m_p = p-m_p, -m_q=q-m_q)$.

Consider now the system: $$\left\{ \begin{eqnarray} m = m_p \pmod p \\ m = m_q \pmod q \end{eqnarray} \right. $$ Using the extended Euclide algorithm you know that: $p\cdot y_p + q\cdot y_q = 1$ because $\gcd(p,q)=1$. So multiplying by $m$: $m\cdot p\cdot y_p + m\cdot q\cdot y_q = m$.

look at the equality $\mod p$: $$m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m \pmod p$$ but you know that $m = m_p \pmod p$ and $m = m_q \pmod q$so: $$m_q\cdot p\cdot y_p + m_p \cdot q\cdot y_q = m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m\pmod p$$.

Combining the two possibilities for the square root $\mod p$ with the two possbilities $\mod q$ you'll find the four results you listed.

$\endgroup$
  • $\begingroup$ Addition: the formula $m=\left(\left(q^{-1}\bmod p\right)\cdot(m_p - m_q)\bmod p\right)\cdot q+m_q$, usual in the context of RSA with CRT, could help. $\endgroup$ – fgrieu Oct 20 '15 at 11:37
  • $\begingroup$ @ddddavidee wouldn't it be congruent sign in place of equal to ( = ). Beneath line 'consider now the system:' $\endgroup$ – Atinesh Oct 24 '15 at 18:20
  • $\begingroup$ @ddddavidee I have some doubts 1) why are we not using Gauss's Algorithm for the system $m_p$ = m (mod p) and $m_q$ = m (mod q). Which will give us unique solution mod n. 2)Is the method which are giving us 4 square roots (r,-r, s, -s) for the system $m_p$ = m (mod p) and $m_q$ = m (mod q) is applicable here in case of Rabin Cryptosystem or we can use it for any system which satisfies CRT. $\endgroup$ – Atinesh Oct 24 '15 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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