[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
How do you do Rabin decryption?
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:
M1 = C^((p+1)/4) mod n
M2 = p - C^((p+1)/4) mod n
M3 = C^((q+1)/4) mod n
M4 = q - C^((q+1)/4) mod n
These formulas don't work. Also, note the "p -" and "q -". This is
suspicious. If M^2 is C, then (n-M)^2 is also C. I suspect M2 and M4
should have "n -" instead.
Try p=7, q=11, n=77. (p+1)/4 is 2, (q+1)/4 is 3. Try M=50, so C=36.
M1 = 64; M2 = 20; M3 = 71; M4 = 17. None of these are the original
M, and none of them is a square root of 36.
Anybody know the right way to do square roots mod a Blum integer?