Rabin cryptosystem

History

The process was published in January 1979 by Michael O. Rabin. The Rabin cryptosystem was the first asymmetric cryptosystem where recovering the entire plaintext from the ciphertext could be proven to be as hard as factoring.

Key generation

As with all asymmetric cryptosystems, the Rabin system uses both a public and a private key. The public key is necessary for later encryption and can be published, while the private key must be possessed only by the recipient of the message.

The precise key-generation process follows:

To encrypt a message only the public key n is needed. To decrypt a ciphertext the factors p and q of n are necessary.

As a (non-real-world) example, if p = 7 and q = 11 , then n = 77 . The public key, 77, would be released, and the message encoded using this key. And, in order to decode the message, the private keys, 7 and 11, would have to be known (of course, this would be a poor choice of keys, as the factorization of 77 is trivial; in reality much larger numbers would be used).

Encryption

For the encryption, only the public key n is used, thus producing a ciphertext out of the plaintext. The process follows:

Let P = { 0 , … , n − 1 } be the plaintext space (consisting of numbers) and m ∈ P be the plaintext. Now the ciphertext c is determined by

That is, c is the quadratic remainder of the square of the plaintext, modulo the key-number n.

In our simple example, P = { 0 , … , 76 } is our plaintext space. We will take m = 20 as our plaintext. The ciphertext is thus c = m 2 mod n = 400 mod 77 = 15 .

For exactly four different values of m, the ciphertext 15 is produced, i.e. for m ∈ { 13 , 20 , 57 , 64 } . This is true for most ciphertexts produced by the Rabin algorithm, i.e. it is a four-to-one function.

Decryption

To decode the ciphertext, the private keys are necessary. The process follows:

If c and n are known, the plaintext is then m ∈ { 0 , … , n − 1 } with m 2 ≡ c ( mod n ) . For a composite n (that is, like the Rabin algorithm's n = p ⋅ q ) there is no efficient method known for the finding of m. If, however n is prime (or p and q are, as in the Rabin algorithm), the Chinese remainder theorem can be applied to solve for m.

Thus the square roots

and

must be calculated (see section below).

In our example we get m p = 6 and m q = 9 .

By applying the extended Euclidean algorithm, we wish to find y p and y q such that y p ⋅ p + y q ⋅ q = 1 . In our example, we have y p = − 3 and y q = 2 .

Now, by invocation of the Chinese remainder theorem, the four square roots + r , − r , + s and − s of c + n Z ∈ Z / n Z are calculated ( Z / n Z here stands for the ring of congruence classes modulo n). The four square roots are in the set { 0 , … , n − 1 } :

One of these square roots mod n is the original plaintext m. In our example, m ∈ { 64 , 20 , 13 , 57 } .

Rabin pointed out in his paper, that if someone is able to compute both, r and s , then he is also able to find the factorization of n because:

Since the Greatest common divisor can be calculated efficiently you are able to find the factorization of n efficiently if you know r and s . In our example (picking 57 and 13 as r and s ):

Computing square roots

The decryption requires to compute square roots of the ciphertext c modulo the primes p and q. Choosing p ≡ q ≡ 3 ( mod 4 ) allows to compute square roots more easily by

and

We can show that this method works for p as follows. First p ≡ 3 ( mod 4 ) implies that (p+1)/4 is an integer. The assumption is trivial for c≡0 (mod p). Thus we may assume that p does not divide c. Then

where ( c p ) is a Legendre symbol.

From c ≡ m 2 ( mod p q ) follows that c ≡ m 2 ( mod p ) . Thus c is a quadratic residue modulo p. Hence ( c p ) = 1 and therefore

The relation p ≡ 3 ( mod 4 ) is not a requirement because square roots modulo other primes can be computed too. E.g., Rabin proposes to find the square roots modulo primes by using a special case of Berlekamp's algorithm.

Effectiveness

Decoding 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.

Disambiguation introduces additional computational costs, and is what has prevented the Rabin cryptosystem from finding widespread practical use.

Security

The great advantage of the Rabin cryptosystem is that a random plaintext can be recovered entirely from the ciphertext only if the codebreaker is capable of efficiently factoring the public key n. Note that this is a very weak level of security. Extensions of the Rabin cryptosystem achieve stronger notions of security.

It has been proven that decoding the Rabin cryptosystem is equivalent to the integer factorization problem, something that has not been proven for RSA. Thus the Rabin system is 'more secure' in this sense than is RSA, and will remain so until a general solution for the factorization problem is discovered, or until the RSA problem is discovered to be equivalent to factorization. (This assumes that the plaintext was not created with a specific structure to ease decoding.)

Since the solution to the factorization problem is being sought on many different fronts, any solution (outside classified research organizations such as NSA) would rapidly become available to the whole scientific community. However, a solution has been long in coming, and the factorization problem has been, thus far, practically insoluble. Without such an advance, an attacker would have no chance today of breaking the encryption of random messages.

However, this 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).

Furthermore, it has been proven an active attacker can break the system using 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 speific chosen-ciphertext attack, since the decoding 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 mod p and mod q and 2. application of the Chinese remainder theorem).

Since in the encoding process, only the modulo remainders of perfect squares are used (in our example with n = 77 , this is only 23 of the 76 possible values), other attacks on the process are possible.