-----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-----
Karl posted a good answer about square roots modulo a Blum integer. I'd like to explain some of the context for this math. Recall that a multiplicative group modulo n=pq is the product of two multiplicative groups modulo p and modulo q. That is, Z^*/nZ =~= Z^*/pZ x Z^*/qZ (The superscript asterisks denote multiplication.) So an element of Z/nZ can be represented by an ordered pair of residues mod p and mod q. This same situation explains why there is another decryption exponent in RSA, a previous thread. Anyway, if p is prime, then every square mod p has two square roots. When p = 3 (mod 4), these square roots are easy to find. See the article in the current MAA Monthly for a discussion of the other case. If <m,n> is a square in Z/nZ, then each component m and n must also be a square. Thus if <m,n>=<a^2,b^2>, there are four possible square roots <a,b>, <a,-b>, <-a,b>, and <-a,-b>. These are additive inverses in one pairing and conjugates in the other. For completeness, it should be noted that the set of all squares of a group is a subgroup. The commutative case is easy; the non-commutative case is much harder. It is a good exercise to calculate some square groups, to see how they generally behave, for example, properties about their sizes. Karl's explanations of using the Chinese remainder theorem to get the canonical representations is fine, as is his observation about the error in Schneier's text, although n-x = x (mod n), so the "n -" part is unnecessary. Eric
participants (2)
-
hughes＠ah.com -
Karl Lui Barrus