Rabin cryptosystem

Algorithm

Like all asymmetric cryptosystems, the Rabin system uses a key pair: a public key for encryption and a private key for decryption. The public key is published for anyone to use, while the private key remains known only to the recipient of the message.

Key generation

The keys for the Rabin cryptosystem are generated as follows:

1. Choose two large distinct prime numbers ${\displaystyle p}$ and ${\displaystyle q}$ such that ${\displaystyle p\equiv 3mod4}$ and ${\displaystyle q\equiv 3mod4}$.
2. Compute ${\displaystyle n=pq}$.

Then ${\displaystyle n}$ is the public key and the pair ${\displaystyle (p,q)}$ is the private key.

Encryption

A message ${\displaystyle M}$ can be encrypted by first converting it to a number ${\displaystyle m<n}$ using a reversible mapping, then computing ${\displaystyle c=m^{2}modn}$. The ciphertext is ${\displaystyle c}$.

Decryption

The message ${\displaystyle m}$ can be recovered from the ciphertext ${\displaystyle c}$ by taking its square root modulo ${\displaystyle n}$ as follows.

1. Compute the square root of ${\displaystyle c}$ modulo ${\displaystyle p}$ and ${\displaystyle q}$ using these formulas:

   ${\displaystyle \begin{array}{cc}{m}_p& =c^{\frac{1}{4}(p+1)}modp\\ m_q& =c^{\frac{1}{4}(q+1)}modq\end{array}}$

2. Use the extended Euclidean algorithm to find ${\displaystyle y_p}$ and ${\displaystyle y_q}$ such that ${\displaystyle y_p\cdot p+y_q\cdot q=1}$.
3. Use the Chinese remainder theorem to find the four square roots of ${\displaystyle c}$ modulo ${\displaystyle n}$:

   ${\displaystyle \begin{array}{cc}{r}_1& =\left(y_p\cdot p\cdot m_q+y_q\cdot q\cdot m_p\right)modn\\ r_2& =n-r_1\\ r_3& =\left(y_p\cdot p\cdot m_q-y_q\cdot q\cdot m_p\right)modn\\ r_4& =n-r_3\end{array}}$

One of these four values is the original plaintext ${\displaystyle m}$, although which of the four is the correct one cannot be determined without additional information.

Computing square roots

We can show that the formulas in step 1 above actually produce the square roots of ${\displaystyle c}$ as follows. For the first formula, we want to prove that ${\displaystyle m_p^2\equiv cmodp}$. Since ${\displaystyle p\equiv 3mod4,}$ the exponent $\frac{1}{4}(p+1)$ is an integer. The proof is trivial if ${\displaystyle c\equiv 0modp}$, so we may assume that ${\displaystyle p}$ does not divide ${\displaystyle c}$. Note that ${\displaystyle c\equiv m^{2}modpq}$ implies that ${\displaystyle c\equiv m^{2}modp}$, so c is a quadratic residue modulo ${\displaystyle p}$. Then

${\displaystyle m_p^2\equiv c^{\frac{1}{2}(p+1)}\equiv c\cdot c^{\frac{1}{2}(p-1)}\equiv c\cdot 1\mathrm{mod}p}$

The last step is justified by Euler's criterion.

Example

As an example, take ${\displaystyle p=7}$ and ${\displaystyle q=11}$, then ${\displaystyle n=77}$. Take ${\displaystyle m=20}$ as our plaintext. The ciphertext is thus ${\displaystyle c=m^{2}modn=400mod77=15}$.

Decryption proceeds as follows:

1. Compute ${\displaystyle m_p=c^{\frac{1}{4}(p+1)}modp={15}^{2}mod7=1}$ and ${\displaystyle m_q=c^{\frac{1}{4}(q+1)}modq={15}^{3}mod11=9}$.
2. Use the extended Euclidean algorithm to compute ${\displaystyle y_p=-3}$ and ${\displaystyle y_q=2}$. We can confirm that ${\displaystyle y_p\cdot p+y_q\cdot q=(-3\cdot 7)+(2\cdot 11)=1}$.
3. Compute the four plaintext candidates:

   ${\displaystyle \begin{array}{cc}{r}_1& =(-3\cdot 7\cdot 9+2\cdot 11\cdot 1)mod77=64\\ r_2& =77-64=13\\ r_3& =(-3\cdot 7\cdot 9-2\cdot 11\cdot 1)mod77=\mathbf{20}\\ r_4& =77-20=57\end{array}}$

and we see that ${\displaystyle r_3}$ is the desired plaintext. Note that all four candidates are square roots of 15 mod 77. That is, for each candidate, ${\displaystyle r_i^{2}mod77=15}$, so each ${\displaystyle r_i}$ encrypts to the same value, 15.

Evaluation of the algorithm

Effectiveness

Decrypting produces three false results in addition to the correct one, so that the correct result must be guessed. This is the major disadvantage of the Rabin cryptosystem and one of the factors which have prevented it from finding widespread practical use.

If the plaintext is intended to represent a text message, guessing is not difficult; however, if the plaintext is intended to represent a numerical value, this issue becomes a problem that must be resolved by some kind of disambiguation scheme. It is possible to choose plaintexts with special structures, or to add padding, to eliminate this problem. A way of removing the ambiguity of inversion was suggested by Blum and Williams: the two primes used are restricted to primes congruent to 3 modulo 4 and the domain of the squaring is restricted to the set of quadratic residues. These restrictions make the squaring function into a trapdoor permutation, eliminating the ambiguity.

Efficiency

For encryption, a square modulo n must be calculated. This is more efficient than RSA, which requires the calculation of at least a cube.

For decryption, the Chinese remainder theorem is applied, along with two modular exponentiations. Here the efficiency is comparable to RSA.

Security

It has been proven that any algorithm which finds one of the possible plaintexts for every Rabin-encrypted ciphertext can be used to factor the modulus ${\displaystyle n}$. Thus, Rabin decryption for random plaintext is at least as hard as the integer factorization problem, something that has not been proven for RSA. It is generally believed that there is no polynomial-time algorithm for factoring, which implies that there is no efficient algorithm for decrypting a random Rabin-encrypted value without the private key ${\displaystyle (p,q)}$.

The Rabin cryptosystem does not provide indistinguishability against chosen plaintext attacks since the process of encryption is deterministic. An adversary, given a ciphertext and a candidate message, can easily determine whether or not the ciphertext encodes the candidate message (by simply checking whether encrypting the candidate message yields the given ciphertext).

The Rabin cryptosystem is insecure against a chosen ciphertext attack (even when challenge messages are chosen uniformly at random from the message space). By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root. This thwarts this specific chosen-ciphertext attack, since the decryption algorithm then only produces the root that the attacker already knows. If this technique is applied, the proof of the equivalence with the factorization problem fails, so it is uncertain as of 2004 if this variant is secure. The Handbook of Applied Cryptography by Menezes, Oorschot and Vanstone considers this equivalence probable, however, as long as the finding of the roots remains a two-part process (1. roots ${\displaystyle modp}$ and ${\displaystyle modq}$ and 2. application of the Chinese remainder theorem).