Editing Rabin cryptosystem (section)

==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 (cryptography)|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 function|trapdoor]] [[permutation]], eliminating the ambiguity.<ref name="bellare-goldwasser-bw-trapdoor">{{cite book
|title=Lecture Notes on Cryptography
|first1=Mihir
|last1=Bellare
|author-link1=Mihir Bellare
|first2=Shafi
|last2=Goldwasser
|author-link2=Shafi Goldwasser
|date=July 2008
|url=https://cseweb.ucsd.edu/~mihir/papers/gb.pdf#page=32
|section=§2.3.5 A Squaring Permutation as Hard to Invert as Factoring
|pages=32–33
}}</ref>

===Efficiency===
For encryption, a square modulo ''n'' must be calculated. This is more efficient than [[RSA (algorithm)|RSA]], which requires the calculation of at least a cube.

For decryption, the [[Chinese remainder theorem]] is applied, along with two [[modular exponentiation]]s. 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 <math>n</math>. 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 <math>(p,q)</math>.

The Rabin cryptosystem does not provide [[ciphertext indistinguishability|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).{{r|stinson|p=214}} 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 [http://cacr.uwaterloo.ca/hac/ 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 <math>\bmod{p}</math> and <math>\bmod{q}</math> and 2. application of the Chinese remainder theorem).