Better to know some... than all 


Rabin publickey encryptionA 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 publickey encryption scheme was the first example of a provably secure publickey encryption scheme  the problem faced by a passive adversary of recovering plaintext from some given ciphertext is computationally equivalent to factoring. Algorithm Key generation for Rabin publickey encryptionSUMMARY: each entity creates a public key and a corresponding private key. Each entity A should do the following: 1. Generate two large random (and distinct) primes 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). Algorithm Rabin publickey encryptionSUMMARY: B encrypts a message m for A, which A decrypts. 1. Encryption. B should do the following: (a) Obtain A's authentic public key n. (b) Represent the message as an integer m in the range {0,1,…, n  1}. (c) Compute c = m^{2} mod n. (d) Send the ciphertext c to A. 2. Decryption. To recover plaintext m from c, A should do the following: (a) Use Algorithm to find the four square rootsm1, m2, m3, and m4 of c modulo n. (b) The message sent was either m1, m2, m3, or m4. A somehow decides which of these is m. 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 for computing the four square roots of c modulo n simplifies as follows: 1. Use the extended Euclidean algorithm 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. 2. Compute r = c^{(p+1)/4} mod p. 3. Compute s = c^{(q+1)4} mod q. 4. Compute x = (aps + bqr) mod n. 5. Compute y = (aps  bqr) mod n. 6. The four square roots of c modulo n are x,  x mod n, y, and  y mod n. Rabin publickey 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 A'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. In order to encrypt the 10bit message m = 1001111001,B replicates the last six bits of m to obtain the 16bit message m = 1001111001111001,which in decimal notation is m = 40569. B then computes c = m^{2} mod n = 40569^{2} mod 91687 = 62111 and sends this to A. Decryption. To decrypt c, A uses Algorithm and her knowledge of the factors of n to compute the four square roots of c mod n: m1 = 69654, m2 = 22033, m3 = 40569, m4 = 51118, which in binary are m1 = 10001000000010110, m2 = 101011000010001, m3 = 1001111001111001, m4 = 1100011110101110. Since only m3 has the required redundancy, A decrypts c to m3 and recovers the original message m = 1001111001. 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. 