1

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?

Mike Warren
  • 223
  • I feel as if I misled my poor classmates... – Mike Warren Sep 28 '16 at 21:45
  • 1
    Hint: What if you wrote $c \equiv m^2 +B m \pmod{n}$. From this, we add something we know to both sides as $c +\left(\dfrac{B}{2}\right)^2 \equiv m^2 +B m +\left(\dfrac{B}{2}\right)^2 \pmod{n}$. This is now $c +\left(\dfrac{B}{2}\right)^2 \equiv \left(m +\dfrac{B}{2}\right)^2 \pmod{n}$. Of course, the $2$ is a modular inverse here. Can you now make that look like Rabin and continue? – Moo Sep 28 '16 at 22:31
  • Yes, I can. The math major in me should have prevailed and tried that, instead of blindly trying to extend a formula to this ring. – Mike Warren Sep 28 '16 at 23:57
  • That answered my question. Thanks! – Mike Warren Sep 29 '16 at 00:49

1 Answers1

1

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.

Mike Warren
  • 223
kodlu
  • 9,338