Another method for public key cryptography, developed by Michael O. Rabin, similar in intent and spirit to RSA and ElGamal. This scheme depends on the difficulty of computing square roots modulo a composite number, which has been shown to be equivalent to factoring.
To create public and private keys for this method, one would generate two large prime numbers p and q, both congruent to 3 mod 4. These primes are the private key, and the public key is their product n.
If Alice and Bob wish to communicate using this scheme, Alice would do the following to send a message to Bob:
- Obtain Bob's authentic public key n.
- Convert her message into a number M less than n
- Compute C = M2 mod n
When Bob receives C, he can compute the original message M using the factorization of n (which is his private key) p and q and the Chinese Remainder Theorem. First he computes these four values:
m1 = C(p+1)/4 mod p
m2 = (p - C(p+1)/4) mod p
m3 = C(q+1)/4 mod q
m4 = (q - C(q+1)/4) mod q
Then Bob chooses integers a = q(q-1 mod p) and b = p(p-1 mod q). Then there are four possiblilities for the message Alice sent:
M1 = (am1 + bm3) mod n
M2 = (am1 + bm4) mod n
M3 = (am2 + bm3) mod n
M4 = (am2 + bm4) mod n
If the message has a recognizable pattern, such as English text, it should be obvious to Bob which of these four possible solutions is Alice's message. If it was random text or something otherwise unrecognizable Alice had sent she should prepend a predictable message header to her message before doing her encryption.