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. Cryptography (from Greek kryptós, hidden, and gráphein, to write) is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — the art of encryption. ... In cryptography, RSA is an algorithm for public-key encryption. ... In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In cryptography, RSA is an algorithm for public-key encryption. ...

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). The same year Michal Jackson had his first crush on a 9 year old. This page refers to the year 1979. ... For the violinist, see Michael Rabin (violinist) Michael O. Rabin (born 1931 in Breslau, Germany, today in Poland) is a noted computer scientist and a recipient of the Turing Award, the most prestigious award in the field. ...

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. PKC, see PKC (disambiguation) Public-key cryptography is a form of modern cryptography which allows users to communicate securely without previously agreeing on a shared secret key. ... ...

The precise key-generation process follows:

• Choose two large distinct primes p and q. One may choose p≡q≡3 (mod 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 ciphertext the factors p and q of n are necessary.

As a (non-real-world) example, if p = 7 and q = 11, then n = 77. 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 be the plaintext. Now the ciphertext c is determined by The plain text term has a different meaning. ... This article is about algorithms for encryption and decryption. ...

.

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 cryptography, a block cipher is a type of symmetric key cipher which operates on groups of bits of a fixed length, termed blocks. ...

In our simple example, P = {0,...,76} is our plaintext space. We will take m = 20 as our plaintext. The ciphertext is thus .

Here it should be noted that for exactly four different values of m, the ciphertext 15 is produced, i.e. for . 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 with . For a composite r (that is, like the Rabin algorithm's ) there is no efficient method known for the finding of m. If, however (as are p and q in the Rabin algorithm), the Chinese remainder theorem can be applied to solve for m. A composite number is a positive integer which has a positive divisor other than one or itself. ... The Chinese remainder theorem is the name for several related results in abstract algebra and number theory. ...

Thus the square roots In mathematics, the principal square root of a non-negative real number is denoted and represents the non-negative real number whose square (the result of multiplying the number by itself) is For example, since This example suggests how square roots can arise when solving quadratic equations such as or...

and

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 are calculated. In our example, we have y_p = − 3 and y_q = 2. The extended Euclidean algorithm is an algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers a and b, as well as integers x and y such that (This equation is known as Bezouts identity. ...

Now, by invocation of the Chinese remainder theorem, the four square roots + r, − r, + s and − s of are calculated. ( here stands for the set of the class of remainders modulo n; the four square roots are in the set {0,...,n − 1}): In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ...

One of these square roots is the original plaintext m. In our example, .

Computing square roots

The decryption requires to compute square roots of the ciphertext c modulo the primes p and q. Choosing p≡q≡3 (mod 4) allows to compute square roots by

and

.

We can show that this method works for p as follows. First p≡3 (mod 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

where is a Legendre symbol. From follows that c is a quadratic residue. Hence and therefore The Legendre symbol is used by mathematicians in the area of number theory, particularly in the fields of factorization and quadratic residues. ...

The relation p≡ 3 (mod 4) is not a requirement because square roots modulo other primes can be computed too.

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 what has 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. In cryptography, padding is the practice of adding material of varying length to the plaintext of messages. ...

Efficiency

For encryption, a square must be calculated. This is more efficient than RSA, which requires the calculation of at least a cube. In cryptography, RSA is an algorithm for public-key encryption. ...

For decryption, the Chinese remainder theorem is applied, along with two modular exponentiations. Here the efficiency is comparable to RSA. The Chinese remainder theorem is the name for several related results in abstract algebra and number theory. ... Modular exponentiation is a type of exponentiation performed over a modulus. ...

Disambiguation introduces additional computational costs, and is what has prevented the Rabin cryptosystem from finding widespread practical use.

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. A chosen ciphertext attack is an attack on a cryptosystem in which the cryptanalyst chooses ciphertext and causes it to be decrypted with an unknown key. ...

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 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 and 2. application of the Chinese remainder theorem). 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ...

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.

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 (in PDF). MIT Laboratory for Computer Science, January 1979.

See also: Topics in cryptography, Blum Blum Shub. ... Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ...