The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.
[1][2] The Rabin trapdoor function has the advantage that inverting it has been mathematically proven to be as hard as factoring integers, while there is no such proof known for the RSA trapdoor function.
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.
Naive attempts to work around this often either enable a chosen-ciphertext attack to recover the secret key or, by encoding redundancy in the plaintext space, invalidate the proof of security relative to factoring.
[1] Public-key encryption schemes based on the Rabin trapdoor function are used mainly for examples in textbooks.
In contrast, RSA is the basis of standard public-key encryption schemes such as RSAES-PKCS1-v1_5 and RSAES-OAEP that are used widely in practice.
The trapdoor function was later repurposed in textbooks as an example of a public-key encryption scheme,[6][7][1] which came to be known as the Rabin cryptosystem even though Rabin never published it as an encryption scheme.
by taking its square root modulo
We can show that the formulas in step 1 above actually produce the square roots of
Note that all four candidates are square roots of 15 mod 77.
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
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.
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.
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
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
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).
[6]: 214 By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root.
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 2. application of the Chinese remainder theorem).