DESCRIPTION OF THE RABIN PUBLIC KEY CRYPTOSYSTEM Here are some messages from Marc Ringuette and Bennet Yee concerning the Rabin system. They provide a succinct description of the system, and statements concerning its public domainness. 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 <riordanmr@clvax1.cl.msu.edu> Subject: Re: Royalty-free public key algorithm wanted Happy news - I have something for you. My friend Bennet Yee introduced me to it, and it's a simple PK technique, provably as hard as factoring, that is probably equivalent to or better than RSA. It's not patented as far as I know...but I haven't written away to the author yet. 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. In a practical system, you use this function to encrypt a one-time key for DES or some other private-key system, then encrypt the rest of the message with the private key system. 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: <Marc.Ringuette@DAISY.LEARNING.CS.CMU.EDU> 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? I just got mail from Michael Rabin, saying that his technique is in the public domain. Yay! Bennet Yee adds: Date: Sun, 28 Apr 91 22:06:12 EDT From: Bennet.Yee@PLAY.MACH.CS.CMU.EDU Rabin's protocol is equivalent to factoring: Suppose you have a procedure P which, given a quadratic residue, gives one of its square roots mod pq. The four nsquare roots of a quadratic residue y=x^2 mod pq is -x, x, -gamma x, gamma x, where gamma is the nontrivial square root of unity mod pq. 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 [ You can see where the other square roots of unity comes from: they are the other possible patterns of signs on the 1's in the system of eqns for CRT. ] 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 ----------------------------------------------- Let me add a few words about "choosing the correct root somehow". If there's one square root of X mod pq, then there are four square roots. In general, it's not obvious which of the four square roots is the original message. 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.] Mark Riordan riordanmr@clvax1.cl.msu.edu late April 1991
qfx