Edited into HTML by: AL

Description of the Rabin Public Key Cryptosystem

Note that the version of the Rabin system I/we have implemented is not exactly as described in Rabin's papers, so I may be giving him short shrift here. We/I use the Berlekamp square root algorithm (which is very much different than the exponentiation that RSA uses) in order to be sure that no one at RSA can claim this is an RSA ripoff. I think it's safe to say that this square root algorithm, coupled with the Chinese Remainder Theorem, is the "magic" that makes this whole system work.

-------- Messages follow ---------------------------------------

Date: Fri, 24 Aug 1990 11:26-EDT
From: Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU
To: Mark Riordan 
Subject: Re: Royalty-free public key algorithm wanted

It was invented by Michael Rabin, and goes like this:

• The private key is a pair of large random primes, as for RSA
• The encryption function is squaring/square root modulo pq. Squaring is easy -- modular multiplication -- but taking a square root modulo pq is as hard as factoring. Once you know the factors, though, it is possible.
• So to encrypt a short message with the public key, square the message modulo pq.
• To decrypt it, take the four square roots modulo pq, and choose the correct one somehow.

p.s. Here's a brief proof that the method is as hard as factoring:

Assume you can take arbitrary square roots modulo pq. If a number has a square root (1 out of 4 numbers do), then it has 4 square roots, two distinct ones and their negations mod pq.

To factor pq, choose a random number, square it, and take the square root. With 50% probability, you will obtain the other distinct square root. From these you can derive the factoring (damn, I can't quite remember how - was it the Chinese Remainder Theorem, or some sort of GCD?). I can fill in the details sometime if you want.

Return-Path: 
Received: from DAISY.LEARNING.CS.CMU.EDU by clvax1.cl.msu.edu with SMTP ;
          Thu, 13 Sep 90 14:09:28 EDT
Date: Thu, 13 Sep 1990 14:06-EDT
From: Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU
To: ceblair@ux1.cso.uiuc.edu, riordanmr@clvax1.cl.msu.edu
Subject: Re: Is Rabin cryptosystem covered by patents?

Bennet Yee adds:

Date: Sun, 28 Apr 91 22:06:12 EDT
From: Bennet.Yee@PLAY.MACH.CS.CMU.EDU

Aside: you can find gamma if you know p and q by using the Chinese Remainder Theorem (CRT) and solving the system of equations

        x = -1 mod p
        x = 1 mod q

Now, given P, you choose a random r between 1 and pq-1 inclusive and compute y = P(r^2). With 1/2 probability, y = +/- gamma r. Since you knew r, you can find g = y/r = +/- gamma. Now, since g-1 is either 0 mod q or 0 mod p, so GCD(g-1,pq) will give you p or q.

[ To find 1/r mod pq, use EGCD: The extended Euclidean algorithm, given m,n, will find GCD(m,n) as well as the pair a,b such that am+bn=GCD(m,n). When GCD(m,n)=1, we have a=1/m mod n. ]

Note that this can be simplfied a little, since with very high probability r does not divide pq: r(g-1) = r(y/r - 1) = y - r, so GCD(y-r,pq) will work just as well. If r divides pq, you've already (accidentally) factored the modulus.

-------- End of Messages -----------------------------------------------

H. C. Williams devised a modification of the Rabin system which allows the cryptographer to decide definitively which of the four square roots is the original message. I started to implement Williams' variation (see the code in cippkg.c that has been #if'ed out), but decided that his variation made the system look too much like RSA. The RSA system is great, but I don't want their lawyers after me.

So, the question remains: how should we distinguish which of four candidates is the original plaintext? I decided upon a brute force approach: I add 64 bits of redundant information to a message before encrypting it. The 64 bits are simply the first 64 bits of the message. If the message is less than 64 bits long, it is repeated as necessary to fill out the 64 bits. When the ciphertext is decrypted, the correct plaintext can be detected (with a probability of error of 2^-64, I assume) by looking for the redundancy.

This technique is ugly because it does not *guarantee* unique detection of the correct root (though 2^-64 is good enough for me), and also because it wastes bits. However, the waste of bits isn't as bad as it looks.

Messages in the Rabin system have to be broken up into chunks of size (just less than) pq. But since p and q need to be rather large in order to provide adequate security, each chunk of the message should be several hundred bits or more in size. Using 64 bits of that to discriminate amoungst the square roots is not much overhead. Plus, public key systems are typically used only to encipher a message key for a more conventional (and much faster) secret key system. The message key is typically much smaller than several hundred bits, so there's plenty of room left over for redundancy.

Selected References

• M. O. Rabin, "Digitized signatures and public-key functions as intractable as factorization,", MIT Lab. for Computer Science, Technical Report LCS/TR-212, 1979. [I've not located this paper myself and have instead relied upon references to it in other papers and upon Marc Ringuette's description.]
• H. C. Williams, "A Modification of the RSA Public-Key Encryption Procedure," IEEE Transactions on Information Theory, Vol IT-26, No. 6, November 1980. [I decided not to use this because it looked too RSA-like.]
• Trygve Nagell, Introduction to Number Theory. New York: Chelsea Publishing Company, 1964. [Basic number theory text, better for cryptographic purposes than most. See esp. the chapter "Theory of Quadratic Residues".]
• Henk C. A. van Tilborg, An Introduction to Cryptology. Boston: Kluwer Academic Publishers, 1988. [Especially strong on public key systems. Comes with handy appendices on number theory and the theory of finite fields.]
• Jennifer Seberry and Josef Pieprzyk, Cryptography: An Introduction to Computer Security. Sydney, Australia: Prentice Hall, 1989. [More easily readable than most similar books, with more of an eye toward applications. Contains complete C source to a DES implementation. So much for DES being a secret.]