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?