5
$\begingroup$

Recently I was working on the Rabin cryptosystem. But in the decryption part of the algorithm, there are two ways to decrypt the cipher.

The first solution which has $p$ and $q$ equal to $3\pmod4$ is very clear for me. But the second solution which $p$ and $q$ can be any prime number isn't. In the second solution: (HAC's Algorithm 3.39, finding square roots modulo a prime $p$ ):

INPUT: an odd prime $p$ and a square $a\in Q_p$ .
OUTPUT: the two square roots of $a$ modulo $p$ .

  1. Choose random $b\in\mathbb Z_p$ until $b^2-4a$ is a quadratic non-residue modulo $p$, i.e., $\left({b^2-4a\over p}\right)=-1$ .
  2. Let $f$ be the polynomial $x^2−bx+a$ in $\mathbb Z_p[x]$ .
  3. Compute $r=x^{(p+1)/2}\bmod f$ using Algorithm 2.227 (Note: $r$ will be an integer).
  4. Return $(r,−r)$ .

Questions:

  1. Is it correct that in the first step, I just pick a random $b$ in range of $0$ to $(p-1)$ and replace it in this $\left({b^2-4a\over p}\right)=-1$ to calculate value of $a$ ? If it is correct so does $a$ have any other condition to follow.

  2. Second in $f$ polynomial, is it correct that I just also choose random $x$ in range of $0$ to $(p-1)$ and calculate the value of $f$ with the $x$ I choose. If it is correct so does value of $x$ which I choose and the result $f$ need any other condition ?

$\endgroup$
  • $\begingroup$ First, have a look at section 8.3 of the Handbook of Applied Cryptography; then edit the question to make it more precise, including the definition of the Rabin cryptosystem considered., if only to to establish the notation. [reposted with the first link fixed]. $\endgroup$ – fgrieu Oct 13 '17 at 13:47
  • 1
    $\begingroup$ @fgrieu I have read the section in the document you gave me and also edited the question. If anything wrong with my question please inform me $\endgroup$ – dqhuy78 Oct 15 '17 at 10:14
5
$\begingroup$

Note: It is assumed familiarity with finite ring $\mathbb Z_w$, polynomial ring, and standard notation; see final section.

Decrypting in the Rabin cryptosystem of the question involves solving for $m$ the equation $m^2\equiv a\pmod{p\,q}$ . This is performed by solving $m^2\equiv a\pmod p$ and $m^2\equiv a\pmod q$ (each yielding two solutions in most cases), combining these using the Chinese Remainder Theorem (yielding four solutions in most cases), and picking the right one in some way.

The algorithm quoted in the question is one way to solve $m^2\equiv a\pmod p$ working for any (large) prime $p$, rather than limited to the case $p\equiv3\pmod4$ . See this for a proof of its correctness.

Answering the questions:

  1. No, step 1. of the algorithm is not as stated in the question's 1. $a$ is a given of the algorithm, thus is not calculated. $b$ is picked randomly in range $[0,p)$ and the Legendre symbol $\left({b^2-4a\over p}\right)$ is computed (possibly: as $(b^2-4a)^{(p-1)/2}\bmod p$ with result $p-1$ replaced by $-1$ ), until that's $-1$ . That requires an average of about two random $b$ .
  2. No, step 3. of the algorithm is not as stated in the question's 2. $r$ is computed using polynomial arithmetic modulo the polynomial $f$, without specializing $x$ (wich is no directly related to the desired $m$ ). It happens that the result is always a constant polynomial $r$, and $m=r$ is a solution; $m=-r$ or equivalently $m=p-r$ is also a solution.

Worked out example: $p=41$, $q=53$, $a=1945$, find $m$ such that $m^2\equiv a\pmod{p\,q}$ . $a$ is the ciphertext that we are trying to decipher, thus is a given. I obtained $a=1945$ by arbitrarily choosing $m=92$, and computing $m^2\bmod(p\;q)$ .

The Chinese Remainder Theorem dictates the overall resolution strategy in the three outer/left bullets below:

  • We first solve $m^2\equiv a\pmod p$. In the whole of this first bullet (including 1./2./3./4. below), we operate in the finite ring $(\mathbb Z_p,+,\times)$ and thus can replace any quantity $u$ not an exponent by $u\bmod p$. In particular $m^2\equiv a\pmod p$ becomes $m^2\equiv 18\pmod{41}$ .

    1. We try $b=2$, compute $(b^2-4a)^{(p-1)/2}\bmod p$ , that is $(4-72)^{20}\bmod41$ , that is $14^{20}\bmod41$ , that is $40$ , that is $p-1$; hence that choice $b=2$ verifies $\left({b^2-4a\over p}\right)=-1$ and we stick with it.
    2. We set the polynomial $f=x^2−b\,x+a$ with coefficients in $\mathbb Z_p$, that is $f=x^2+39x+18$ with coefficients in $\mathbb Z_{41}$ ; $x$ is the variable of the polynomial and has no particular value.
    3. We compute the polynomial $x^{(p+1)/2}\bmod f$ that is $x^{21}\bmod f$ , using polynomial arithmetic modulo the polynomial $f$. The binary representation of the exponent $21$ is 10101, and by left-to-right binary exponentiation we'll compute $x^2$, $x^4$, $x^5$, $x^{10}$, $x^{20}$, and finally $x^{21}\bmod f$.

      More precisely, we start from $x^1\bmod f$ and scan 10101 from left to right skipping the leftmost 1; for each digit in that (thus for 0 1 0 1), we square the previous result $x^k\bmod f$ (thus doubling the previous exponent $k$ ), then if the digit scanned is 1 we multiply by $x$ (thus increase the exponent $k$ by one). This goes as follows:

      • We compute $x^2\bmod f$, that is $x^2-(x^2+39x+18)$, that is $2x+23$ (note: we reduce all coefficients modulo $p$ ).
      • We compute $x^4\bmod f$, that is ${(x^2)}^2\bmod f$, that is $(2x+23)^2\bmod f$, that is $4x^2+10x+37\bmod f$, that is $4x^2+10x+37-4(x^2+39x+18)$, that is $18x+6$ .
      • We compute $x^5\bmod f$, that is $(x^4)x\bmod f$, that is $(18x+6)x\bmod f$, that is $x+4$ .
      • We compute $x^{10}\bmod f$, that is ${(x^5)}^2\bmod f$, that is $(x+4)^2\bmod f$, that is $10x+39$ .
      • We compute $x^{20}\bmod f$, that is ${(x^{10})}^2\bmod f$, that is $(10x+39)^2\bmod f$, that is $37x+8$ .
      • We compute $x^{21}\bmod f$, that is $(x^{20})x\bmod f$, that is $(37x+8)x\bmod f$, that is $31$ (as expected, the $x$ term has vanished).
    4. Thus $m^2\equiv a\pmod p$ has solution $m\in\{10,31\}\pmod p$ .
  • We similarly solve $m^2\equiv a\pmod q$, with solution $m\in\{14,39\}\pmod q$ .
  • We combine these to solve $m^2\equiv a\pmod{p\,q}$, with solution $m\in\{92,728,1445,2081\}\pmod{p\,q}$ .

Some definitions and facts.

For integer $w>0$, by definition, $u\equiv v\pmod w\iff w\ \text{ divides }\ u-v$ .

The relation $\equiv\pmod w$ is an equivalence relation over the ring of integers $(\mathbb Z,+,\times)$ and is compatible with its operators. Its equivalence classes form the finite ring $(\mathbb Z_w,+,\times)$, by definition.

The notation $v\bmod w$ stands for the remainder of the Euclidean division of $v$ by $w$. It holds that $u=v\bmod w\iff 0\le u<w\ \text{ and }\ u\equiv v\pmod w$.

The notation $u=v\bmod w$ must be understood as $u=(v\bmod w)$, much like $u=v+w$ means $u=(v+w)$ ; when $u\equiv v\pmod w$ or equivalently $u=v\pmod w$ states that $u$ and $v$ are equivalent modulo $w$. One can spot the equivalent modulo notation by the opening parenthesis immediately before $\bmod$, which never occurs when $\bmod$ is an operator.

For $k>0$, it holds that $$\begin{align} u&\equiv v\pmod w&&\iff u\bmod w\ =\ v\bmod w\\ u&\equiv v\pmod w&&\iff (u\bmod w)\equiv v&&\pmod w\\ u^k&\equiv v\pmod w&&\iff (u\bmod w)^k\equiv v&&\pmod w \end{align}$$

By the Chineese Remainder Theorem, if $w$ and $w'$ are coprime (which holds if $w$ and $w$ are distinct primes), then $$u\equiv v\pmod{w\;w'}\iff u\equiv v\pmod w\ \text{ and }\ u\equiv v\pmod{w'}$$

When $p$ is prime, $(\mathbb Z_p,+,\times)$ is a finite field.

The definition of divisibility and modulo can be extended to polynomials in $(\mathbb Z_p,+,\times)$, forming the polynomial ring in which step 3 is performed.

$\endgroup$
  • $\begingroup$ First, thanks your very much for your example. I have read it carefully but I still have some issue. 1. First, does the given $a$ have any condition or it just any random number and I have also re-read the document you gave me but I didn't found the part that said $a$ is given only $p$ and $q$ at init step. 2. In step 1, we choose $b$ $=$ $2$ so how come $(b^2-4a)$ $=$ $14$ ? 3. In step 3, how can from 10101 we'll compute $x^2$, $x^4$, $x^5$, $x^{10}$, $x^{20}$, $x^{21} ? Sorry if my question is "silly", I kind of new in this field. $\endgroup$ – dqhuy78 Oct 18 '17 at 2:25
  • $\begingroup$ @HuyDQ: I added a lot of details, explanations and links in the answer, including how $1945$ became a given, and how it changes to $18$ in the first bullet. Also I changed $x$ to $m$ when it is the message that we are trying to recover from its Rabin-encrypted form $a$. There's now a short refresher on notation and algebra in the end. $\endgroup$ – fgrieu Oct 18 '17 at 8:17
  • $\begingroup$ I have studied your example for a while and all the related document links you gave during the example and I finally understand the decryption flow of Rabin cryptosystem. Thanks you very much for spending time for such a well explained example, it really help me a lot. Again, thanks you ! $\endgroup$ – dqhuy78 Oct 25 '17 at 11: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.