Rabin cryptosystem

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA.[1]:145 It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.


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

Encryption AlgorithmEdit

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 generationEdit

The keys for the Rabin cryptosystem are generated as follows:

  1. Choose two large distinct prime numbers   and   such that   and  .
  2. Compute  .

Then   is the public key and the pair   is the private key.


A message   can be encrypted by first converting it to a number   using a reversible mapping, then computing  . The ciphertext is  .


The message   can be recovered from the ciphertext   by taking its square root modulo   as follows.

  1. Compute the square root of   modulo   and   using these formulas:
  2. Use the extended Euclidean algorithm to find   and   such that  .
  3. Use the Chinese remainder theorem to find the four square roots of   modulo  :

One of these four values is the original plaintext  , although which of the four is the correct one cannot be determined without additional information.

Computing square rootsEdit

We can show that the formulas in step 1 above actually produce the square roots of   as follows. For the first formula, we want to prove that  . Since   the exponent   is an integer. The proof is trivial if  , so we may assume that   does not divide  . Note that   implies that  , so c is a quadratic residue modulo  . Then


The last step is justified by Euler's criterion.


As an example, take   and  , then  . Take   as our plaintext. The ciphertext is thus  .

Decryption proceeds as follows:

  1. Compute   and  .
  2. Use the extended Euclidean algorithm to compute   and  . We can confirm that  .
  3. Compute the four plaintext candidates:

and we see that   is the desired plaintext. Note that all four candidates are square roots of 15 mod 77. That is, for each candidate,  , so each   encrypts to the same value, 15.

Digital Signature AlgorithmEdit

The Rabin cryptosystem can be used to create and verify digital signatures. Creating a signature requires the private key  . Verifying a signature requires the public key  .


A message   can be signed with a private key   as follows.

  1. Generate a random value  .
  2. Use a cryptographic hash function   to compute  , where the bar denotes concatenation.   should be an integer less than  .
  3. Treat   as a Rabin-encrypted value and attempt to decrypt it, using the private key  . This will produce the usual four results,  .
  4. One might expect that encrypting each   would produce  . However, this will be true only if   happens to be a quadratic residue modulo   and  . To determine if this is the case, encrypt the first decryption result  . If it does not encrypt to  , repeat this algorithm with a new random  . The expected number of times this algorithm needs to be repeated before finding a suitable   is 4.
  5. Having found an   which encrypts to  , the signature is  .

Verifying a signatureEdit

A signature   for a message   can be verified using the public key   as follows.

  1. Compute  .
  2. Encrypt   using the public key  .
  3. The signature is valid if and only if the encryption of   equals  .

Evaluation of the algorithmEdit


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.[3]


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.[citation needed]


It has been proven that any algorithm which decrypts a Rabin-encrypted value can be used to factor the modulus  . Thus, Rabin decryption 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 Rabin-encrypted value without the private key  .

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).[1]:150 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   and   and 2. application of the Chinese remainder theorem).

See alsoEdit


  1. ^ a b Stinson, Douglas (1995). Cryptography: Theory and Practice. CRC Press LLC.
  2. ^ Rabin, Michael (January 1979). "Digitalized Signatures and Public-Key Functions as Intractable as Factorization" (PDF). MIT Laboratory for Computer Science.
  3. ^ Shafi Goldwasser and Mihir Bellare "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001


  • Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001. ISBN 3-540-41283-2
  • Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7
  • Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization (in PDF). MIT Laboratory for Computer Science, January 1979.
  • Scott Lindhurst, An analysis of Shank's algorithm for computing square roots in finite fields. in R Gupta and K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Aug 1999.
  • R Kumanduri and C Romero, Number Theory w/ Computer Applications, Alg 9.2.9, Prentice Hall, 1997. A probabilistic for square root of a quadratic residue modulo a prime.

External linksEdit