This document is taken from the now-defunct RPEM distribution.

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