1
$\begingroup$

My task is to implement Rabin signature. I have trouble with choosing padding a such that $$x^2 \equiv a \pmod n$$ has a solution.

In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are prime numbers with $p\equiv3\pmod 4$ and $q\equiv3\pmod 4$.

  1. How do I check if a solution exists?
  2. Is there any formal way to find $a$?
$\endgroup$
2
$\begingroup$

The equation $a = x^2 \bmod N$ has at most $4$ solutions $x$.

There are solutions if $a$ is a square modulo both $p$ and $q$. This can be checked by computing the Legendre of symbol of $x$ modulo $p$ and modulo $q$.

Assuming that the two Legendre symbols are +1, when $p \equiv 3 \pmod 4$, a square-root of $a$ modulo $p$ is given by $x_p = a^{(p+1)/4} \bmod p$; the other square-root modulo $p$ is given by $-x_p$; and simililarly modulo $q$. The square-roots modulo $N$ are then obtained through Chinese remaindering (CRT): $x_1 = \mathrm{CRT}(x_p,x_q)$, $x_2 = \mathrm{CRT}(-x_p,x_q)$, $x_3 = \mathrm{CRT}(x_p,-x_q)$, $x_4 = \mathrm{CRT}(-x_p,-x_q)$.

For example, suppose $p = 852151$ and $q = 376963$ (note that $p,q \equiv 3 \pmod 4$). And so $N = pq = 321229397413$. Let also $a = 187078154864$. It is verified that the Legendre symbol of $a$ modulo $p$ is $+1$, and similarly modulo $q$.

From the previous formula, we obtain $x_p = 295070$ and $x_q = 21456$. The four square roots of $a$ are then obtained through Chinese remaindering: $184209776740$, $156318284370$, $164911113043$, and $137019620673$.

Remark 1: The Legendre symbol of $a$ modulo $p$ is given by $a^{(p-1)/2} \bmod p$.

Remark 2: Given $x_p$ and $x_q$, $\mathrm{CRT}(x_p,x_q) = x_p + p[i_p(x_q - x_p)\bmod q]$ with $i_p = p^{q-2} \bmod q$.

$\endgroup$
  • $\begingroup$ Thank you. Especially for example - they are really difficult to find. Remark 1 - I suspected you are supposed to calculate Legendre symbol for both p and q but couldn't get a straight answer form google $\endgroup$ – t4u May 13 '16 at 7:55
  • $\begingroup$ for: p=852149 and q=376949 ; p= 1( mod 4); q= 1 (mod 4); ; and not 3; $\endgroup$ – t4u May 17 '16 at 20:45
1
$\begingroup$

There is also a nice formula giving solutions for quadratic residues modulo $n$: $$x=a^{\frac{(p-1)(q-1)+4}{8}}\mod n.$$ As usual, it is sufficient to verify it modulo $p$ and modulo $q$ separately.

$\endgroup$

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.