# How to use CRT to compute 4 square roots while decryption in Rabin Cryptosystem

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.

• 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. – ddddavidee Oct 20 '15 at 9:15

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.

• 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. – fgrieu Oct 20 '15 at 11:37
• @ddddavidee wouldn't it be congruent sign in place of equal to ( = ). Beneath line 'consider now the system:' – Atinesh Oct 24 '15 at 18:20
• @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. – Atinesh Oct 24 '15 at 18:58