Rabin cryptosystem

Rabin cryptosystem

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be 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.

History

The process was published in January 1979 by Michael O. Rabin. The Rabin cryptosystem was the first asymmetric cryptosytem where recovering the entire plaintext from the ciphertext could be proven to be as hard as factoring.

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 "p" and "q". One may choose p equiv q equiv 3 pmod{4} to simplify the computation of square roots modulo "p" and "q" (see below). But the scheme works with any primes.
*Let "n"="p"*"q". Then "n" is the public key. The primes "p" and "q" are the private key.

To encrypt a message only the public key "n" is needed. To decrypt a ciphertextthe factors "p" and "q" of "n" are necessary.

As a (non-real-world) example, if p = 7 and q = 11, then n=77. The public key, 77, would be released, and the message encoded using this key. And, in order to decode the message, the private keys, 7 and 11, would have to be known (of course, this would be a poor choice of keys, as the factorization of 77 is trivial).

Encryption

For the encryption, only the public key "n" is used, thus producing a ciphertext out of the plaintext. The process follows:

Let P = { 0, ..., n-1 } be the plaintext space (consisting of numbers) and m in P be the plaintext. Now the ciphertext c is determined by

:c = m^2 , mod , n.

That is, "c" is the quadratic remainder of the square of the plaintext, modulo the key-number "n".

In our simple example, P = { 0, ..., 76 } is our plaintext space. We will take m = 20 as our plaintext. The ciphertext is thus c = m^2 , mod , n = 400 , mod , 77 = 15.

Here it should be noted that for exactly four different values of "m", the ciphertext 15 is produced, i.e. for m in { 13, 20, 57, 64 }. 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 m in { 0, ..., n-1 } with m^2 equiv cpmod{r}. For a composite "r" (that is, like the Rabin algorithm's n = p cdot q) there is no efficient method known for the finding of "m". If, however r in mathbb{P} (as are "p" and "q" in the Rabin algorithm), the Chinese remainder theorem can be applied to solve for "m".

Thus the square roots

:m_p = sqrt{c} , mod , p

and

:m_q = sqrt{c} , mod , q

must be calculated (see section below).

In our example we get m_p = 1 and m_q = 9.

By applying the extended Euclidean algorithm, y_p and y_q, with y_p cdot p + y_q cdot q = 1 are calculated. In our example, we have y_p = -3 and y_q = 2.

Now, by invocation of the Chinese remainder theorem, the four square roots +r, -r, +s and -s of c + n mathbb{Z} in mathbb{Z} / n mathbb{Z} are calculated (mathbb{Z} / n mathbb{Z} here stands for the ring of congruence classes modulo "n"). The four square roots are in the set { 0, ..., n-1 })::egin{matrix}r & = & ( y_p cdot p cdot m_q + y_q cdot q cdot m_p) , mod , n \-r & = & n - r \s & = & ( y_p cdot p cdot m_q - y_q cdot q cdot m_p) , mod , n \-s & = & n - s end{matrix}

One of these square roots mod , n is the original plaintext "m". In our example, m in { 64, mathbf{20}, 13, 57 }.

Computing square roots

The decryption requires to compute square roots of the ciphertext "c" modulothe primes "p" and "q". Choosing p equiv q equiv 3pmod{4} allows to compute square roots by :m_p = c^{frac{(p+1)}{4 , mod , pand:m_q = c^{frac{(q+1)}{4 , mod , q.We can show that this method works for "p" as follows.First p equiv 3!!!pmod{4} implies that ("p"+1)/4 is an integer. The assumption is trival for "c"≡0 (mod "p"). Thus we may assume that "p" does not divide "c". Then:m_p^2 equiv c^{frac{(p+1)}{2 equiv ccdot c^{frac{(p-1)}{2 equiv c cdotleft({cover p} ight) pmod{p},where left({cover p} ight) is a Legendre symbol.From cequiv m^2pmod{pq} follows that cequiv m^2pmod{p}. Thus "c" is a quadratic residue modulo "p". Hence left({cover p} ight)=1 and therefore :m_p^2 equiv c pmod{p}. The relation p equiv 3pmod{4} is not a requirement because square roots moduloother primes can be computed too. E.g. Rabin proposes to find the square roots modulo primes by using a special case of Berlekamp's algorithm.

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 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. The most common way of implementing disambiguation is known as Blum disambiguation.Fact|date=July 2008

Efficiency

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.

ecurity

The great advantage of the Rabin cryptosystem is that a random plaintext can be recovered entirely from the ciphertext only if the codebreaker is capable of efficiently factoring the public key "n". Note that this is a very weak level of security. Extensions of the Rabin cryptosystem achieve stronger notions of security.

It has been proven that decoding the Rabin cryptosystem is equivalent to the integer factorization problem, which is rather different than for RSA. Thus the Rabin system is 'more secure' in this sense than is RSA, and will remain so until a general solution for the factorization problem is discovered, or until the RSA problem is discovered to be equivalent to factorization. (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, any solution (outside classified research organizations such as NSA) would rapidly become available to the whole scientific community. However, a solution has been long in coming, and the factorization problem has been, thus, practically insoluble. Without such an advance, an attacker would have no chance today of breaking the code. This cryptosystem is provably secure (in a strong sense) against chosen plaintext attacks.

However, an active attacker can break the system using a chosen ciphertext attack, as has been mathematically proven.

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 variant is secure. The [http://www.cacr.math.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 mod p and mod q 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 n = 77, this is only 23 of the 76 possible values), other attacks on the process are possible.

ee also

* Topics in cryptography
* Blum Blum Shub

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://www.lcs.mit.edu/publications/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 resiue modulo a prime.

External links

* [http://www.cacr.math.uwaterloo.ca/hac/ Menezes, Oorschot, Vanstone, Scott: "Handbook of Applied Cryptography" (free PDF downloads), see Chapter 8]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Rabin (surname) — Yitzhak Rabin was the prime minister of Israel.Rabin is a Hebrew surname. It originates from the Hebrew word rav meaning Rabbi. (Note: Yitzhak Rabin s surname had a different origin: it had been changed from Rubitzov by his parents.)The following …   Wikipedia

  • Rabin signature algorithm — In cryptography the Rabin Signature Scheme is a method of Digital signature originally proposed by Michael O. Rabin in 1979. The Rabin Signature Scheme was one of the first digital signature schemes proposed, and it was the first to relate the… …   Wikipedia

  • Michael O. Rabin — Michael Oser Rabin Born September 1, 1931 (1931 09 01) (age 80) Breslau …   Wikipedia

  • McEliece cryptosystem — In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece.[1] It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance… …   Wikipedia

  • Cramer–Shoup cryptosystem — The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the… …   Wikipedia

  • Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… …   Wikipedia

  • Naccache–Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem. The Naccache–Stern Knapsack Cryptosystem is an atypical public key cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

  • Niederreiter cryptosystem — In cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter [1]. It applies the same idea to the parity check matrix H of a linear code. Niederreiter is equivalent to… …   Wikipedia

  • Damgård–Jurik cryptosystem — The Damgård–Jurik cryptosystem[1] is a generalization of the Paillier cryptosystem. It uses computations modulo ns + 1 where n is an RSA modulus and s a (positive) natural number. Paillier s scheme is the special case with s = 1. The order φ(ns + …   Wikipedia

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”