THEORY
in rpem.tar.Z,
available from dcssparc.cl.msu.edu (35.8.1.6).
Edited into HTML by: AL
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 RiordanHappy 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.Subject: Re: Royalty-free public key algorithm wanted
It was invented by Michael Rabin, and goes like this:
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:I just got mail from Michael Rabin, saying that his technique is in the public domain. Yay!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.EDURabin'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.
Mark Riordan, riordanmr@clvax1.cl.msu.edu, late April 1991