Editing Rabin cryptosystem

{{Short description|Public-key encryption scheme}}
{{about|the textbook public-key encryption scheme|the digital signature scheme it was based on|Rabin signature}}
The '''Rabin cryptosystem''' is a family of [[public-key encryption]] schemes
based on a [[trapdoor function]] whose security, like that of [[RSA (algorithm)|RSA]], is related to the difficulty of [[integer factorization]].<ref name="galbraith2012mathpkc">{{cite book
|author1-last=Galbraith
|author1-first=Steven D.
|title=Mathematics of Public Key Cryptography
|publisher=Cambridge University Press
|year=2012
|isbn=978-1-10701392-6
|section=§24.2: The textbook Rabin cryptosystem
|pages=491–494
}}</ref><ref name="bellare-goldwasser-rabin-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=29
|section=§2.3.4 The Squaring Trapdoor Function Candidate by Rabin
|pages=29–32
}}</ref>

The Rabin trapdoor function has the advantage that inverting it has been [[Mathematics|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.<ref name="galbraith2012mathpkc"/>

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 [[PKCS 1|RSAES-PKCS1-v1_5]] and [[Optimal asymmetric encryption padding|RSAES-OAEP]] that are used widely in practice.

==History==
The Rabin trapdoor function was first published as part of the [[Rabin signature]] scheme in 1978 by [[Michael O. Rabin]].<ref name="rabin1978digsigs">{{cite book
|author1-last=Rabin
|author1-first=Michael O.
|author1-link=Michael O. Rabin
|editor1-last=DeMillo
|editor1-first=Richard A.
|editor1-link=Richard DeMillo
|editor2-last=Dobkin
|editor2-first=David P.
|editor2-link=David P. Dobkin
|editor3-last=Jones
|editor3-first=Anita K.
|editor3-link=Anita K. Jones
|editor4-last=Lipton
|editor4-first=Richard J.
|editor4-link=Richard Lipton
|title=Foundations of Secure Computation
|year=1978
|publisher=Academic Press
|location=New York
|isbn=0-12-210350-5
|pages=155–168
|chapter=Digitalized Signatures
}}</ref><ref name="rabin1979lcs-tr">{{cite tech report
|last=Rabin
|first=Michael O.
|author-link=Michael O. Rabin
|title=Digitalized Signatures and Public Key Functions as Intractable as Factorization
|number=TR-212
|institution=MIT Laboratory for Computer Science
|date=January 1979
|location=Cambridge, MA, United States
|url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf
}}</ref><ref name="bellare-rogaway1996exactsigs">{{cite conference
|last1=Bellare
|first1=Mihir
|author-link1=Mihir Bellare
|last2=Rogaway
|first2=Phillip
|author-link2=Phillip Rogaway
|title=The Exact Security of Digital Signatures—How to Sign with RSA and Rabin
|editor-last=Maurer
|editor-first=Ueli
|editor-link=Ueli Maurer (cryptographer)
|conference=Advances in Cryptology – EUROCRYPT ’96
|date=May 1996
|conference-url=https://link.springer.com/book/10.1007/3-540-68339-9
|volume=1070
|series=Lecture Notes in Computer Science
|publisher=Springer
|location=Saragossa, Spain
|isbn=978-3-540-61186-8
|pages=399–416
|doi=10.1007/3-540-68339-9_34
|doi-access=free
}}</ref>
The Rabin signature scheme was the first [[digital signature]] scheme where forging a signature could be proven to be as hard as factoring.

The trapdoor function was later repurposed in textbooks as an example of a [[public-key encryption]] scheme,<ref name=stinson>{{cite book
|title=Cryptography: Theory and Practice
|last=Stinson
|first=Douglas
|author-link=Doug Stinson
|edition=3rd
|isbn=978-1-58488-508-5
|publisher=Chapman & Hall/CRC
|date=2006
|section=5.8
|pages=211–214
}}</ref><ref name="hac">{{cite book
|author1-last=Menezes
|author1-first=Alfred J.
|author1-link=Alfred Menezes
|author2-last=van Oorschot
|author2-first=Paul C.
|author2-link=Paul van Oorschot
|author3-last=Vanstone
|author3-first=Scott A.
|author3-link=Scott Vanstone
|title=Handbook of Applied Cryptography
|publisher=CRC Press
|date=October 1996
|isbn=0-8493-8523-7
|section=§8.3: Rabin public-key encryption
|url=https://cacr.uwaterloo.ca/hac/about/chap8.pdf#page=11
|pages=292–294
}}</ref><ref name="galbraith2012mathpkc"/>
which came to be known as the Rabin cryptosystem even though Rabin never published it as an encryption scheme.

==Algorithm==
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 generation===

The keys for the Rabin cryptosystem are generated as follows:

# Choose two large distinct [[prime numbers]] <math>p</math> and <math>q</math> such that <math>p \equiv 3 \bmod{4}</math> and <math>q \equiv 3 \bmod{4}</math>.
# Compute <math>n = p q</math>. 
Then <math>n</math> is the public key and the pair <math>(p,q)</math> is the private key.

===Encryption===
A message <math>M</math> can be encrypted by first converting it to a number <math>m < n</math> using a reversible mapping, then computing <math>c = m^2 \bmod{n}</math>. The ciphertext is <math>c</math>.

===Decryption===
The message <math>m</math> can be recovered from the ciphertext <math>c</math> by taking its square root modulo <math>n</math> as follows.

# Compute the square root of <math>c</math> modulo <math>p</math> and <math>q</math> using these formulas:
#: <math>\begin{align}
  m_p &= c^{\frac{1}{4}(p+1)} \bmod{p} \\
  m_q &= c^{\frac{1}{4}(q+1)} \bmod{q}
\end{align}</math>
# Use the [[extended Euclidean algorithm]] to find <math>y_p</math> and <math>y_q</math> such that <math>y_p \cdot p + y_q \cdot q = 1</math>. 
# Use the [[Chinese remainder theorem]] to find the four square roots of <math>c</math> modulo <math>n</math>: 
#: <math>\begin{align}
   r_1 &= \left( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p \right) \bmod{n} \\
   r_2 &= n - r_1  \\
   r_3 &= \left( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p \right) \bmod{n} \\
   r_4 &= n - r_3 
\end{align}</math>

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

====Computing square roots====
We can show that the formulas in step 1 above actually produce the square roots of <math>c</math> as follows. For the first formula, we want to prove that <math>m_p^2 \equiv c \bmod{p}</math>. Since <math>p \equiv 3 \bmod{4},</math> the exponent <math display="inline">\frac{1}{4}(p+1)</math> is an integer. The proof is trivial if <math>c \equiv 0 \bmod{p}</math>, so we may assume that <math>p</math> does not divide <math>c</math>. Note that <math>c \equiv m^2 \bmod{pq}</math> implies that <math>c \equiv m^2 \bmod{p}</math>, so c is a [[quadratic residue]] modulo <math>p</math>. Then
: <math>m_p^2 \equiv c^{\frac{1}{2}(p+1)} \equiv c\cdot c^{\frac{1}{2}(p-1)} \equiv c \cdot 1 \mod p</math>
The last step is justified by [[Euler's criterion]].

===Example===
As an example, take <math>p = 7</math> and <math>q = 11</math>, then <math>n=77</math>. Take <math>m = 20</math> as our plaintext. The ciphertext is thus 
<math>c = m^2 \bmod{n} = 400 \bmod{77} = 15</math>.

Decryption proceeds as follows:
# Compute <math>m_p = c^{\frac{1}{4}(p+1)} \bmod{p} = 15^2 \bmod{7} = 1</math> and <math>m_q = c^{\frac{1}{4}(q+1)} \bmod{q} = 15^3 \bmod{11} = 9</math>. 
# Use the extended Euclidean algorithm to compute <math>y_p = -3</math> and <math>y_q = 2</math>. We can confirm that <math>y_p \cdot p + y_q \cdot q =  (-3 \cdot 7) + (2 \cdot 11) = 1</math>.
# Compute the four plaintext candidates:
#: <math>\begin{align}
  r_1 &= (-3 \cdot 7 \cdot 9 + 2 \cdot 11 \cdot 1) \bmod{77} = 64 \\
  r_2 &= 77 - 64 = 13 \\
  r_3 &= (-3 \cdot 7 \cdot 9 - 2 \cdot 11 \cdot 1) \bmod{77} = \mathbf{20} \\
  r_4 &= 77 - 20 = 57
\end{align}</math>

and we see that <math>r_3</math> is the desired plaintext. Note that all four candidates are square roots of 15 mod 77. That is, for each candidate, <math>r_i^2 \bmod{77} = 15</math>, so each <math>r_i</math> encrypts to the same value, 15.

==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).

==See also==
* [[Topics in cryptography]]
* [[Blum Blum Shub]]
* [[Shanks–Tonelli algorithm]]
* [[Schmidt–Samoa cryptosystem]]
* [[Blum–Goldwasser cryptosystem]]

==Notes==
{{reflist}}

==References==
* 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. ''[http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf 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 links==
* [http://cacr.uwaterloo.ca/hac/ Menezes, Oorschot, Vanstone, Scott: ''Handbook of Applied Cryptography'' (free PDF downloads), see Chapter 8]

{{Cryptography navbox | public-key}}

[[Category:Public-key encryption schemes]]