Rabin public-key encryption
A desirable property of any encryption scheme is a proof that breaking it is as difficult as solving a computational problem that is widely believed to be difficult, such as integer factorization or the discrete logarithm problem. While it is widely believed that breaking the RSA encryption scheme is as difficult as factoring the modulus n, no such equivalence has been proven. The Rabin public-key encryption scheme was the first example of a provably secure public-key encryption scheme - the problem faced by a passive adversary of recovering plaintext from some given ciphertext is computationally equivalent to factoring.
8.10 Algorithm Key generation for Rabin public-key encryption
SUMMARY: each entity creates a public key and a corresponding private key.
Each entity A should do the folio whig:
- 1. Generate two large random (and distinct) prunes p and q, each roughly the same size.
- 2. Compute n = pq.
- 3. A’s public key is n A’s private key is (p, q).
- 8.11 Algorithm Rabin public-key encryption
SUMMARY: В encrypts a message m for A, which A decrypts.
- 1. Encryption. В should do the following:
- 2. Decryption. To recover plaintext m from c, A should do the following:
- (a) Use Algorithm 3.44 to find the four square roots mi, m2, m3, and m4 of c modulo n? (See also Note 8.12.)
- (b) The message sent was either mi, m2, m3, or m4. A somehow (cf. Note 8.14) decides which of these is m.
- 8.12 Note (finding square roots of c modulo n = pq when p = q = 3 (mod 4)) If p and q are both chosen to be = 3 (mod 4), then Algorithm 3.44 for computing the four square roots of c modulo n simplifies as follows:
- 1. Use the extended Euclidean algorithm (Algorithm 2.107) to find integers a and b satisfying ap + bq = 1. Note that a and b can be computed once and for all during the key generation stage (Algorithm 8.10).
- 2. Compute r = <4p+1)/4 mod p.
- 3. Compute s = c^q+1^4 mod q.
- 4. Compute x = (aps + bqr) mod n.
- 5. Compute у = (aps — bqr) mod n.
- 6. The four square roots of c modulo n axe x, -x mod n, y, and — у mod n.
- 8.13 Note (security’ of Rabin public-key encryption)
- (i) The task faced by a passive adversary is to recover plaintext m from the corresponding ciphertext c. This is precisely the SQROOT problem of §3.5.2. Recall (Fact 3.46) that the problems of factoring n and computing square roots modulo n are computationally equivalent. Hence, assuming that factoring n is computationally intractable, the Rabin public-key encryption scheme is provably secure against a passive adversary.
- (ii) While provably secure against a passive adversary, the Rabin public-key encryption scheme succumbs to a chosen-ciphertext attack (but see Note 8.14(h)). Such an attack can be mounted as follows. The adversary' selects a random integer m e Z* and computes c = m2 mod n. The adversary then presents c to A’s decryption machine, which decrypts c and returns some plaintext y. Since A does not know m, and m is randomly chosen, the plaintext у is not necessarily the same as m. With probability
у ф ±m mod n, in which case gcd(m - y, n) is one of the prune factors of n. If у = ±m mod n, then the attack is repeated with a new m.3
- (iii) The Rabin public-key encryption scheme is susceptible to attacks similar to those on RSA described in §8.2.2(h), §8.2.2(iii), and §8.2.2(v). As is the case with RSA, attacks (ii) and (hi) can be circumvented by salting the plaintext message, while attack
- (v) can be avoided by adding appropriate redundancy prior to encryption.
- 8.14 Note (use of redundancy)
- (i) A drawback of Rabm’s public-key scheme is that the receiver is faced with the task of selecting the correct plaintext from among four possibilities. This ambiguity in decryption can easily be overcome in practice by adding prespecified redundancy to the original plaintext prior to encryption. (For example, the last 64 bits of the message may be replicated.) Then, with high probability, exactly one of the four square roots ть m2, m3, m„i of a legitimate ciphertext c will possess this redundancy, and the receiver will select tins as the intended plaintext. If none of the square roots of c possesses this redundancy, then the receiver should reject c as fraudulent.
- (ii) If redundancy is used as above, Rabin’s scheme is no longer susceptible to the chosen- ciphertext attack of Note 8.13(ii). If an adversary selects a message m having the required redundancy and gives c = m2 mod n to A's decryption machine, with very high probability the machine will return the plaintext m itself to the adversary (since the other three square roots of c will most likely not contain the required redundancy), providing no new information. On the other hand, if the adversary selects a message m which does not contain the required redundancy, then with high probability none of the four square roots of c = m2 mod n will possess the required redundancy. In this case, the decryption machine will fail to decrypt c and thus will not provide a response to the adversary. Note that the proof of equivalence of breaking the modified scheme by a passive adversary to factoring is no longer valid. However, if the natural assumption is made that Rabin decryption is composed of two processes, the first which finds the four square roots of c mod n, and the second which selects the distinguished square root as the plaintext, then the proof of equivalence holds. Hence, Rabin public-key encryption, suitably modified by adding redundancy, is of great practical interest.
JThis chosen-ciphertext attack is an execution of the constructive proof of the equivalence of factoring n and the SQROOT problem (Fact 3.46), where .4’s decryption maclune is used instead of the hypothetical polynonual- tnne algorithm for solving the SQROOT problem in the proof.
8.15 Example (Rabin public-key encryption with artificially small parameters)
Key generation. Entity A chooses the primes p = 277, q = 331, and computes n = pq = 91687. A’s public key is n = 91687, while /l’s private key is (p = 277, q = 331). Encryption. Suppose that the last six bits of original messages are required to be replicated prior to encryption (cf. Note 8.14(i)). In order to encrypt the 10-bit message m = 1001111001, В replicates the last six bits of m to obtain the 16-bit message m = 1001111001111001, which in decimal notation is m = 40569. В then computes
and sends this to A.
Decryption. To decrypt c, A uses Algorithm 3.44 and her knowledge of the factors of n to compute the four square roots of c mod n:
which in binary are
Since only ?пз has the required redundancy, A decrypts c to m3 and recovers the original message m = 1001111001. □
8.16 Note (efficiency) Rabin encryption is an extremely fast operation as it only involves a single modular squaring. By comparison, RSA encryption with e = 3 takes one modular multiplication and one modular squaring. Rabin decryption is slower than encryption, but comparable in speed to RSA decryption.