[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Rabin decryption*From*: [email protected]*Date*: Sun, 15 May 1994 22:09:53 -0500*Remailed-By*: Mr. Nobody <[email protected]>*Sender*: [email protected]

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?

- Prev by Date:
**Quantum Computers and stuff** - Next by Date:
**Cryptosystems Journal** - Prev by thread:
**Re: Quantum Computers and stuff** - Next by thread:
**Re: Rabin decryption** - Index(es):