-----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-----