Cryptography
 Computer Science Computer Catlog Cryptography Catlog

 Caesar Cipher Digital Signature Public key cryptography Symmetric vs. public-key Key Management Stream Ciphers Self-Synchronizing Ciphers Feedback Shift Registers Modes of Operation Multiple Encryption Transposition Ciphers Substitution Ciphers Poly-alpha Substitutions Poly-alpha Cipher Machine Cryptanalysis Ciphers Data Encryption Standard DES Algorithm IDEA Algorithm RC5 Algorithm RSA Encryption Rabin Encryption ElGamal Encryption MD4 & MD5 Secure Hash Algorithm Kerberos Authentication Diffie-Hellman protocols Key Management Life Cycle

## 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.

### 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 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 public-key encryption

SUMMARY: 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 = m2 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 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 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 10-bit message m = 1001111001,B replicates the last six bits of m to obtain the 16-bit message m = 1001111001111001,which in decimal notation is m = 40569. B then computes

c = m2 mod n = 405692 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.