Rabin cryptosystem
Encyclopedia
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.
. The Rabin cryptosystem was the first asymmetric cryptosystem where recovering the entire plaintext from the ciphertext could be proven to be as hard as factoring.
The precise key-generation process follows:
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
and 
, then 
. 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; in reality much larger numbers would be used).
Let
be the plaintext space (consisting of numbers) and 
be the plaintext
. Now the ciphertext
is determined by
.
That is, c is the quadratic remainder of the square of the plaintext, modulo the key-number n.
In our simple example,
is our plaintext space. We will take 
as our plaintext. The ciphertext is thus
.
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.
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 
is prime (as are p and q in the Rabin algorithm), the Chinese remainder theorem
can be applied to solve for m.
Thus the square root
s
and
must be calculated (see section below).
In our example we get
and 
.
By applying the extended Euclidean algorithm
, we wish to find
and 
such that 
. In our example, we have 
and 
.
Now, by invocation of the Chinese remainder theorem, the four square roots
, 
, 
and of 
are calculated (
here stands for the ring of congruence classes modulo n). The four square roots are in the set 
:
One of these square roots
is the original plaintext m. In our example, 
.
Rabin pointed out in his paper, that if someone is able to compute both,
and 
, then he is also able to find the factorization of 
because:
Since the Greatest common divisor
can be calculated efficiently you are able to find the factorization of
efficiently if you know 
and 
. In our example (picking 
and 
as 
and 
):
the primes p and q. Choosing
allows to compute square roots by
and
.
We can show that this method works for p as follows.
First
implies that (p+1)/4 is an integer. The assumption is trivial for
c≡0 (mod p). Thus we may assume that p does not divide c. Then
where
is a Legendre symbol
.
From
follows that 
. Thus c is a quadratic residue modulo p.
Hence
and therefore
The relation
is not a requirement because square roots modulo
other 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
.
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. 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
permutation
, eliminating the ambiguity.
For decryption, the Chinese remainder theorem
is applied, along with two modular exponentiation
s. 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.
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 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).
Since in the encoding process, only the modulo remainders of perfect squares are used (in our example with
, this is only 23 of the 76 possible values), other attacks on the process are possible.
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
, 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. RabinMichael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
. The Rabin cryptosystem was the first asymmetric cryptosystem 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
to simplify the computation of square roots modulo p and q (see below). But the scheme works with any primes. - Let
. 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
and , then . 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; in reality much larger numbers would be used).Encryption
For the encryption, only the public key n is used, thus producing a ciphertext out of the plaintext. The process follows:Let
be the plaintext space (consisting of numbers) and be the plaintextPlaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
. Now the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
is determined by.That is, c is the quadratic remainder of the square of the plaintext, modulo the key-number n.
In our simple example,
is our plaintext space. We will take as our plaintext. The ciphertext is thus.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 compositeComposite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
r (that is, like the Rabin algorithm's
) there is no efficient method known for the finding of m. If, however is prime (as are p and q in the Rabin algorithm), the Chinese remainder theoremChinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
can be applied to solve for m.
Thus the square root
Square root
In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...
s
and
must be calculated (see section below).
In our example we get
and .By applying the extended Euclidean algorithm
Extended Euclidean algorithm
The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
, we wish to find
and such that . In our example, we have and .Now, by invocation of the Chinese remainder theorem, the four square roots
, , and of are calculated ( here stands for the ring of congruence classes modulo n). The four square roots are in the set :One of these square roots
is the original plaintext m. In our example, .Rabin pointed out in his paper, that if someone is able to compute both,
and , then he is also able to find the factorization of because:
- either
or 
, where 
means Greatest common divisorGreatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
.
Since the Greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
can be calculated efficiently you are able to find the factorization of
efficiently if you know and . In our example (picking and as and ):Computing square roots
The decryption requires to compute square roots of the ciphertext c modulothe primes p and q. Choosing
allows to compute square roots byand
.We can show that this method works for p as follows.
First
implies that (p+1)/4 is an integer. The assumption is trivial forc≡0 (mod p). Thus we may assume that p does not divide c. Then
where
is a Legendre symbolLegendre symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....
.
From
follows that . Thus c is a quadratic residue modulo p.Hence
and thereforeThe relation
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
Berlekamp's algorithm
In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields . The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967...
.
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
Padding (cryptography)
-Classical cryptography:Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the...
, 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
Trapdoor function
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction without special information, called the "trapdoor"...
permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
, eliminating the ambiguity.
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
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
is applied, along with two modular exponentiation
Modular exponentiation
Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....
s. 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.
Security
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 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).Since in the encoding process, only the modulo remainders of perfect squares are used (in our example with
, this is only 23 of the 76 possible values), other attacks on the process are possible.See also
- Topics in cryptography
- Blum Blum Shub
- Shanks–Tonelli algorithm
- Schmidt–Samoa cryptosystemSchmidt–Samoa cryptosystemThe Schmidt–Samoa cryptosystem is an asymmetric cryptographic technique, whose security, like Rabin depends on the difficulty of integer factorization...