Rabin cryptosystem
|
|
The Rabin cryptosystem is an asymmetric cryptographic technique, which like RSA is based on the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it is based is provably as hard as integer factorization, which is not currently known to be true of the RSA problem. 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.
| Contents |
History
The process was published in January, 1979, by Michael Rabin. The Rabin cryptosystem was the first asymmetric cryptosytem whose security could be proven mathematically (assuming that the problem of fast factorization is insoluble).
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 encoding and can be published, while the private key must be possessed only by the recipient of the message.
The precise key-generation process follows:
- Choose two large distinct primes <math>p<math> and <math>q<math> (<math>p , q \in \mathbb{P}<math>) such that they satisfy the congruence relation below.
- Let <math>n=p \cdot q<math>. <math>n<math> is the public key.
With only <math>n<math>, encoding is possible, but not decoding. To decode, <math>n<math> would have to be factored into <math>p<math> and <math>q<math>.
As a (non-real-world) example, if <math>p = 7<math> and <math>q = 11<math>, then <math>n=77<math>. This would be a poor choice of keys, as the factorization of 77 is trivial.
Congruence relation
In order for the system to work, a specific congruence relation is required:
For both <math>p<math> and <math>q<math> we must have :<math>\left(\frac{p-1}{p}\right) = (p-1)<math> and :<math>\left(\frac{q-1}{q}\right) = (q-1)<math> so that :<math>\left(\frac{n-1}{n}\right) = (n-1)^{\frac{n-1}{2}} \equiv (n-1) \bmod n = (n-1)<math> also holds. (Note that the form <math>\left(\frac{p-1}{p}\right)<math> does not represent division here. See Legendre symbol.)
Simplified, this yields:
- <math>p \equiv q \equiv 3 \, \bmod \, 4<math>
In the formulas, <math>\mod<math> refers to the modulo operator. The two forms are equivalent, since <math>\left(\frac{-1}{p}\right) = -1<math> and <math> p \equiv -1 \, \bmod \, 4<math> and <math> p \equiv 3 \, \bmod \, 4<math> are all equivalent statements.
In general, for <math>r \in \mathbb{P}<math>, with <math>r \equiv 3 \, \bmod \, 4<math> and <math>a \in \mathbb{Z}<math> with <math>a \equiv b^2 \, \bmod \, r<math>:
- <math>a^{\frac{(r+1)}{4}} \equiv \sqrt{a} \, \bmod \, r<math> (Proof in German (http://www.abbiseite.de/seminar_kryptologie/3mod4.html)).
This property serves to facilitate the decoding process in the end.
Since <math>7 \equiv 11 \equiv 3 \, \bmod \, 4 <math>, we can continue using this <math>p<math> and <math>q<math> in our examples.
Encryption
For the encryption, only the public key n is used, thus producing a ciphertext out of the plaintext. The process follows:
Let <math>P = \{ 0, ..., n-1 \}<math> be the plaintext space (consisting of numbers) and <math>m \in P<math> be the plaintext. Now the ciphertext <math>c<math> is determined by
- <math>c = m^2 \, \bmod \, n<math>.
That is, c is the quadratic remainder of the square of the plaintext, modulo the key-number n. In practice, block ciphers are generally used.
In our simple example, <math>P = \{ 0, ..., 76 \}<math> is our plaintext space. We will take <math>m = 20<math> as our plaintext. The ciphertext is thus <math>c = m^2 \, \bmod \, n = 400 \, \bmod \, 77 = 15<math>.
Here it should be noted that for exactly four different values of m, the ciphertext 15 is produced, i.e. for <math>m \in \{ 13, 20, 57, 64 \}<math>. 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 r are known, the plaintext is then <math>m \in \{ 0, ..., n-1 \}<math> with <math>m^2 \equiv c \, \bmod \, r<math>. For a composite r (that is, like the Rabin algorithm's <math>n = p \cdot q<math>) there is no efficient method known for the finding of m. If, however <math>r \in \mathbb{P}<math> (as are p and q in the Rabin algorithm), the Chinese remainder theorem can be applied to solve for m.
Thus the square roots
- <math>m_p = \sqrt{c} \, \bmod \, p<math>
and
- <math>m_q = \sqrt{c} \, \bmod \, q<math>
must be calculated.
Because of the congruence relation,
- <math>m_p = c^{\frac{(p+1)}{4}} \, \bmod \, p<math>
and
- <math>m_q = c^{\frac{(q+1)}{4}} \, \bmod \, q<math>.
In our example, then, <math>m_p = 1<math> and <math>m_q = 9<math>.
By applying the extended Euclidean algorithm, <math>y_p<math> and <math>y_q<math>, with <math>y_p \cdot p + y_q \cdot q = 1<math> are calculated. In our example, we have <math>y_p = -3<math> and <math>y_q = 2<math>.
Now, by invocation of the Chinese remainder theorem, the four square roots <math>+r<math>, <math>-r<math>, <math>+s<math> and <math>-s<math> of <math>c + n \mathbb{Z} \in \mathbb{Z} / n \mathbb{Z}<math> are calculated. (<math>\mathbb{Z} / n \mathbb{Z}<math> here stands for the set of the class of remainders modulo n; the four square roots are in the set <math>\{ 0, ..., n-1 \}<math>):
- <math>\begin{matrix}
r & = & ( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \, \bmod \, n \\ -r & = & n - r \\ s & = & ( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \, \bmod \, n \\ -s & = & n - s \end{matrix}<math>
One of these square roots <math>\mod \, n<math> is the original plaintext m. In our example, <math>m \in \{ 64, \mathbf{20}, 13, 57 \}<math>.
Evaluation of the 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. However, it is possible to choose plaintexts with special structures to eliminate this problem. Since correct padding is required for semantic security in any case, this is not a problem.
Efficiency
For encoding, a square <math>\mod n<math> must be calculated. This is more efficient than the RSA, which requires the calculation of a cube.
For decoding, the Chinese remainder theorem is applied, along with two modular exponentiations. Here the efficiency is comparable to RSA.
Security
The great advantage of the Rabin cryptosystem is that the code can only be broken if the codebreaker is capable of efficiently factoring the public key n.
It has been proven that decoding the Rabin cryptosystem is equivalent to the factorization problem, unlike in RSA. Thus the Rabin system is more secure than RSA, and will remain so until a general solution for the factorization problem is discovered. (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, the solution would rapidly become available to the whole scientific community. However, this solution has been long in coming, and the factorization problem is thus practically insoluble. An eavesdropper would have no chance today of breaking the code.
However, an active attacker can break the system using a chosen ciphertext attack, as has been mathematically proven. This weakness has prevented the Rabin cryptosystem from finding practical use.
By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root. This thwarts the 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 system is secure. The Handbook of Applied Cryptography (http://www.cacr.math.uwaterloo.ca/hac/) 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>\mod p<math> and <math>\mod q<math> 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 <math>n = 77<math>, this is only 23 of the 76 possible values), other attacks on the process are possible.
References
- Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001. ISBN 3540412832
- Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0849385237
- Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization (http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-212.pdf) (in PDF). MIT Laboratory for Computer Science, January 1979.
See also: Topics in cryptography.de:Rabin-Kryptosystem