4.7 The Rabin Cryptosystem

In this section, we describe the Rabin Cryptosystem, which is computationally secure against a chosen-plaintext attack provided that the modulus n = pq cannot be factored. The system is described in Figure 4.13.

Figure 4.12  Binary search for RSA decryption

We will show that the encryption function e_K is not an injection, so decryption cannot be done in an unambiguous fashion. In fact, there are four possible plaintexts that could be the encryption of any given ciphertext. More precisely, let w be one of the four square roots of 1 modulo n. Let . Then, we can verify the following equations:

(Note that all arithmetic is being done in , and division by 2 and 4 is the same as multiplication by 2^-1 and 4^-1 modulo n, respectively.)

The four plaintexts that encrypt to e_K(x) are x, -x - B, ω(x + B/2) - B/2 and -ω(x + B/2) - B/2, where ω is a non-trivial square root of 1 modulo n. In general, there will be no way for Bob to distinguish which of these four possible plaintexts is the “right” plaintext, unless the plaintext contains sufficient redundancy to eliminate three of these four possible values.

Figure 4.13  Rabin Cryptosystem

Let us look at the decryption problem from Bob’s point of view. He is given a ciphertext y and wants to determine x such that

This is a quadratic equation in the unknown x. We can eliminate the linear term by making the substitution x₁ = x + B/2, or equivalently, x = x₁ - B/2. Then the equation becomes

or

If we define C == B² /4 + y, then we can rewrite the congruence as

So, decryption reduces to extracting square roots modulo n. This is equivalent to solving the two congruences

and

(There are two square roots of C modulo p and two square roots modulo q. Using the Chinese remainder theorem, these can be combined to yield four solutions modulo n.) We can use Euler’s criterion to determine if C is a quadratic residue modulo p (and modulo q). In fact, C will be a quadratic residue modulo p and modulo q if encryption was performed correctly. But Euler’s criterion does not help us find the square roots of C; it yields only an answer “yes” or “no.”

When p ≡ 3 (mod 4), there is a simple formula to compute square roots of quadratic residues modulo p. Suppose C is a quadratic residue and p ≡ 3 (mod 4). Then we have that

Here we again make use of Euler’s criterion, which says that if C is a quadratic residue modulo p, then C^(p-1)/2 ≡ 1 (mod p). Hence, the two square roots of 7 modulo P are ±C^(p+1)/4 mod p. In a similar fashion, the two square roots of 7 modulo q are ±C^(q+1)/4 mod q. It is then straightforward to obtain the four square roots x₁, of C modulo n using the Chinese remainder theorem.

REMARK  It is interesting that for p ≡ 1 (mod 4) there is no known polynomial-time deterministic algorithm to compute square roots of quadratic residues modulo p. There is a polynomial-time Las Vegas algorithm, however.

Once we have determined the four possible values for x₁, we compute x from the equation x = x₁ - B/2 to get the four possible plaintexts. This yields the decryption formula