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.