The Rabin and Paillier cryptosystems

Section 4 The Rabin and Paillier cryptosystems

Subsection 4.1 The Rabin cryptosystem

There is an other cryptosystem based on the difficulty of factoring large integers due to Rabin. If \(N=p\cdot q\) is a product of two large primes, then extracting square roots modulo \(N\) is a challenging computational task. The encryption and decryption is similar to the one used in RSA, however in case of the RSA exponent \(e\) we have that \(\gcd(e,\varphi(N))=1.\) Here the exponent is fixed, it is 2. The steps involved in the encryption are as follows.

Alice obtains Bob’s public key: \(N,\)
Alice represents the message as a number \(m\) from the set \(\{0,1,\ldots,N-1\},\)
Alice sends to Bob the value \(c\equiv m^2\pmod{N}.\)

The decryption works as described below.

Bob computes the square root of \(c\) modulo \(N.\)
There are 4 roots, hence it is important to have some redundancy in the message, for example the least significant \(k\) bits of the binary representation of \(m\) are all ones.

The decryption is especially easy if we choose primes \(p\) and \(q\) such that \(p\equiv q\equiv 3\pmod{4}.\) In this case Euler’s criterion provides that

\begin{equation*} (\pm c^{(p+1)/4})^2\equiv c^{(p+1)/2}\equiv c^{(p-1)/2}\cdot c\equiv c\pmod{p} \end{equation*}

and similarly for \(q\) we get that

\begin{equation*} (\pm c^{(q+1)/4})^2\equiv c^{(q+1)/2}\equiv c^{(q-1)/2}\cdot c\equiv c\pmod{q}. \end{equation*}

Having two square roots modulo \(p\) and other two modulo \(q\) yields four square roots modulo \(N\) by applying the Chinese Reminder Theorem.

Suppose that Bob’s public key is \(N=11\cdot 19=209\) and Alice wants to send the message \(m=79.\) Alice computes

\begin{equation*} c\equiv 79^2\equiv 180\pmod{N}. \end{equation*}

Bob receives \(c=180\) and determines the possible square roots, these are given by

\begin{equation*} \begin{aligned} c^{(11+1)/4}&\equiv & 9\pmod{11},\\ -c^{(11+1)/4}&\equiv & 2\pmod{11},\\ c^{(19+1)/4}&\equiv & 16\pmod{19},\\ -c^{(19+1)/4}&\equiv & 3\pmod{19}.\end{aligned} \end{equation*}

Finally, we determine the solutions of the system of congruences by means of the Chinese Reminder Theorem:

\begin{equation*} \begin{aligned} x\equiv 9\pmod{11}&&x\equiv 16\pmod{19},\\ x\equiv 9\pmod{11}&&x\equiv 3\pmod{19},\\ x\equiv 2\pmod{11}&&x\equiv 16\pmod{19},\\ x\equiv 2\pmod{11}&&x\equiv 3\pmod{19}.\\\end{aligned} \end{equation*}

We obtain that

\begin{equation*} 35^2\equiv 79^2\equiv 130^2\equiv 174^2\equiv 180\pmod{N}. \end{equation*}

Subsection 4.2 Paillier’s cryptosystem

In 1999 Paillier published an article in which he introduced a cryptosystem based on composite residuosity classes. As in case of the RSA cryptosystem we fix two large primes \(p\) and \(q.\) The public key is given by \((N,g),\) where \(N=p\cdot q\) and \(g\) is an element of \(\mathbb{Z}_{N^2}^*.\) Let us denote by \(\lambda\) the Carmichael function (\(\lambda(p\cdot q)=\lcm(p-1,q-1)\)) and

\begin{equation*} \begin{aligned} L : \mathbb{Z}_{N^2}^*&\rightarrow &\mathbb{Z}_{N}\\ u&\longmapsto &\frac{u-1}{N}.\end{aligned} \end{equation*}

The element \(g\) has to satisfy that \(\gcd(N,L(g^\lambda\bmod N^2))=1.\) To encrypt a message Alice follows the steps given below.

The message \(m\) is represented as an element of \(\mathbb{Z}_{N},\)
Alice picks a random number \(r\in \mathbb{Z}_{N}^*,\)
the ciphertext is in the set \(\mathbb{Z}_{N^2},\) it is computed via the formula

\begin{equation*} c\equiv g^m\cdot r^N\pmod{N^2}. \end{equation*}

Bob can decrypt the ciphertext using his private key \((p,q)\) as follows:

\begin{equation*} m\equiv \frac{L(c^\lambda\bmod N^2)}{L(g^\lambda\bmod N^2)}\pmod{N}. \end{equation*}

To show that the decryption in fact works we need a theorem of Carmichael.

Carmichael If \(a\) and \(N\) are relatively prime numbers, then

\begin{equation*} a^{\lambda(N)}\equiv 1\pmod{N}. \end{equation*}

The element \(g\) comes from \(\mathbb{Z}_{N^2}^*,\) so \(g^{\lambda(N)}\equiv 1\pmod{N}.\) Therefore there exists a \(k\in\mathbb{Z}_N\) such that

\begin{equation*} g^{\lambda(N)}\equiv 1+kN\pmod{N^2}. \end{equation*}

We also need to compute \(c^{\lambda(N)}\pmod{N^2}.\) Here we obtain

\begin{equation*} c^{\lambda(N)}\equiv g^{m\lambda(N)}\cdot r^{N\lambda(N)}\pmod{N^2}. \end{equation*}

Clearly we have \(\varphi(N^2)=N\varphi(N)=N(p-1)(q-1),\) therefore \(r^{N\lambda(N)}\equiv 1\pmod{N^2}.\) That is we get that

\begin{equation*} c^{\lambda(N)}\equiv g^{m\lambda(N)}\pmod{N^2}. \end{equation*}

Putting together the above results we have

\begin{equation*} c^{\lambda(N)}\equiv (1+kN)^m\equiv 1+kmN\pmod{N^2}. \end{equation*}

The remaining part is as follows

\begin{equation*} \frac{L(c^\lambda\bmod N^2)}{L(g^\lambda\bmod N^2)}\equiv \frac{km}{k}\equiv m\pmod{N}. \end{equation*}

Consider an example with \(N=p\cdot q=17\cdot 29=493\) and \(g=35.\) Alice wants to send the message \(m=28\) to Bob and she chooses the random integer \(r=9.\) Alice computes

\begin{equation*} c\equiv 35^{28}\cdot 9^{493}\equiv 43562\pmod{N^2}. \end{equation*}

Bob may decrypt it by evaluating \(L(c^\lambda\bmod N^2)\) and \(L(g^\lambda\bmod N^2).\) He obtains

\begin{equation*} \begin{aligned} L(c^\lambda\bmod N^2)&=&313,\\ L(g^\lambda\bmod N^2)&=&64.\end{aligned} \end{equation*}

So it remains to determine

\begin{equation*} \frac{L(c^\lambda\bmod N^2)}{L(g^\lambda\bmod N^2)}\equiv\frac{313}{64}\equiv 28\pmod{N}, \end{equation*}

we see that the message is decrypted.

SageMath summary.

crt(): Applies the Chinese Reminder Theorem.
lcm(): Returns the least common multiple.
randint(): Returns a random integer from a range.
random_prime(): Returns a random prime number from a range.

Exercises 4.3 Exercises

1.

Bob uses a Rabin public-key cryptosystem with \(N= 1817 = 23\cdot 79.\) Alice tells Bob that the two-digit message will be padded with starting digits "11" and she sends 882 as encrypted message. Decode the message.

2.

The Paillier’s cryptosystem has an additive homomorphic property that we check in case of a concrete example. Let \((N,g)=(2501,92)\) and \((m_1,r_1)=(34,5),(m_2,r_2)=(16,7).\) Compute the two encoded messages \(c_1, c_2\) and show that \(c_1\cdot c_2\) is the same as the ciphertext of \(m_1+m_2\) with random integer \(r=35.\)