I am in cryptography class, working on homework that is due tomorrow, and I came across the following problem:
Modified Rabin Cryptosystem
Consider modification to Rabin cryptosystem in which ek(x) = x*(x+B) mod n, where B (in integers modulo n) is part of public key. Suppose n = p * q, where p = 199, q = 211, and B = 1357. Perform the following computations:
a.) Compute y = ek(32767)
b.) Determine the four possible decryptions of this given ciphertext y.
I have already done part a, and have decided to try b like thus:
x*(x+B) = y (mod n)x*(x+B) - y = x^2 + B*x - y = 0 (mod n)x = (-B +/- sqrt(B^2 + 4*y))/2 (mod n)
I essentially handwaved the last part, after noting that 1/2 = (n+1)/2 in the integers modulo n . The division on the right hand side is simply integer division.
I computed this, with other classmates, and after telling them this, and got that the set formed by my attempt at b doesn't contain the answer in a . In fact, after applying the algorithm, I get the set { 28875, 11757, 39820, 812 }.
Is my attempt at extending the quadratic formula to the integers modulo n false? If so, what would be the solution, and the proof that it is the solution?
After completing the square you need to solve an equation of the form $$(X+2^{-1}B)^2 \equiv y+(2^{-1}B)^2~(mod ~n).$$
So, $\gcd(2,n)=1$ is required for the multiplicative inverse of 2 to exist in the ring of integers modulo $n.$
Moreover, the quantity in the right hand side of the equation above must be a quadratic residue, not all integers modulo $n$ are squares.