From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Mon, 16 May 94 19:39:44 PDT
To: cypherpunks@toad.com
Subject: Re: Rabin
Message-ID: <9405170239.AA23367@flammulated.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Earlier, anonymous asked:

> In the Rabin PK system, your modulus is a Blum integer, a number n
> of the form p*q, where p and q are primes equal to 3, mod 4.
> According to Schneier, p. 289, encryption is done by C = M^2 mod n.
> On the next page, he gives four possible square roots of C:

> Anybody know the right way to do square roots mod a Blum integer?

Well, I'll look at what Schneier says; maybe there is a typo in the
formula... but the way you can solve this is with the Chinese
Remainder Theorem.

If c = m^2 mod n, then a solution is a common solution of

m^2 mod n = c mod p
m^2 mod n = c mod q

Since p+1 and q+1 are divisible by 4, then (a^((p+1)/4))^2 = a since a
is a quadratic residue modulo p, and then a^((p-1)/2) mod p = 1

anyway, you calculate x1 = a^((p+1)/4) mod p
                      x2 = a^((q+1)/4) mod q

and then use the CRT four times to get the solution.

For this example, p = 7, q = 11, n = p q = 77, m = 50

c = 50^2 mod 77 = 36

x1 = c^((p+1)/4) mod p = 36^2 mod 7  = 1
x2 = c^((q+1)/4) mod q = 36^3 mod 11 = 5

So now you use the Chinese Remainder Theorem for the following four
cases

CRT(n, p, q, x1, x2)
CRT(n, p, q, x1, q - x2)
CRT(n, p, q, p - x1, q)
CRT(n, p, q, p - x1, q - x1)

yeilding:

CRT(77, 7, 11, 1, 5) --> 71
CRT(77, 7, 11, 1, 6) --> 50
CRT(77, 7, 11, 6, 5) --> 27
CRT(77, 7, 11, 6, 6) --> 6

Sorry, but I don't have time to write out the steps for the CRT ;)
It's pretty straightforward, given the algorithm.

so (71, 50, 27, 6) satisfy the equation x^2 mod n = c
                                        x^2 mod 77 = 36

as you can see, the original message (m = 50) is one of the choices.

This is similar to an oblivious transfer protocol.  Actually, I think
it is an oblivious transfer as described by Blum.

Karl Barrus
klbarrus@owlnet.rice.edu

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdguSYOA7OpLWtYzAQG35wP+MpdhCUBtSodd53Ppn41UHcKSpkkamx13
YqMmlmP0dKsRV2Vas1IVdcIGcjcowBxDT7IkRJO9UNtj33BB2tTsRDNOi2GqERZl
AARVL/y941EIAXwwj2w+WQ/jCAaFhy4ohvZVbI5snWw6D+dsxQ7jMx193ehLjnu1
ieEL4BvHUzA=
=MJ0E
-----END PGP SIGNATURE-----