Solving a quadratic equation for a variant of Rabin

My understanding of Rabin

We have $p$ and $q$ which are distinct primes congruent to $3 \pmod 4$. Then we have $n = pq$.

Encryption is done as $e(m) = m^2 \pmod n$, where $m$ is our message.

Decryption is done by evaluating $d(c) = \sqrt{m} \pmod n$, where $c$ is our ciphertext. This can be accomplished by determining $m_p = c^{(p+1)/4} \pmod p$ and $m_q = c^{(q+1)/4} \pmod q$ and their negative counterparts. Then, $m$ is congruent to both $m_p \pmod p$ and $m_q \pmod q$. Chinese remainder theorem can be used to calculate the four possible values of $m$.

The variant of Rabin which I'm having trouble with

I'm having trouble with a variant of Rabin which uses the encryption function $e(m) = m^2 + Bm$ where B is an arbitrary value. We then have $c = m^2 + Bm$ which leads us to $0 = m^2 + Bm - c$. I'm confused as to how to proceed from this point.

My guess is that I must solve the quadratic formula, yet solve the $\sqrt{b^2 - 4ac}$ portion as you solve the square root in regular Rabin. However, my attempts at this have failed. Is this the correct approach?

migrated from security.stackexchange.comNov 17 '14 at 14:57

This question came from our site for information security professionals.

The tricky point is that modulo a Blum integer (the product $n = pq$ of two primes $p$ and $q$ that are equal to 3 modulo 4), in general, a quadratic residue (a value that is a square of something) has four square roots, not two.

Consider the "normal" Rabin algorithm. Message $m$ is encrypted into $c=m^2\bmod n$. To decrypt, you work modulo $p$ and modulo $q$. Modulo $p$, you first compute $c_p = c \bmod p$, then $d_p=c_p^{(p+1)/4} \bmod p$ . The value $d_p$ is a square root of $c_p$ modulo $p$; however that is not the only square root. The other one is $d'_p=p-d_p$ .

Similarly, working modulo $q$, you get two square roots of $c$ called $d_q$ and $d'_q$. By combining these square roots with the CRT, you end up with four candidates for $m$. This is the usual problem with Rabin encryption: you have to include some redundancy of format in the message (e.g. deterministic padding computed through a hash function) to determine which of the four candidates is the right one.

With the variant, things are similar: you must still work modulo $p$ and modulo $q$, and get two candidates modulo each prime, hence four combinations. With encryption $c=m^2+Bm \bmod n$ , you solve modulo $p$ the equation:

$$c_p \equiv d_p^2+Bd_p \pmod p$$

which is equivalent to: $$d_p^2+Bd_p-c_p \equiv 0 \pmod p$$

you solve it by computing $D_p=B^2-4c_p$, then extracting one square root $S_p=D_p^{(p+1)/4} \bmod p$. The two candidates are then:

$d_p=(-B+S_p)/2 \bmod p$

$d'_p=(-B-S_p)/2 \bmod p$

You also get two candidates $d_q$ and $d'_q$ modulo $q$, and the CRT gives you the four candidates for the decryption result.

Note that whenever you extract a square root with the $(p+1)/4$ exponent, you should verify that you indeed get a square root (by squaring it and checking that you indeed get the source value). Modulo $n$, only about one value in four is a quadratic residue. If the encrypted message is correct, then all square root extractions shall succeed, and you get four candidates; if it is not, then you get wrong values, and you should report an error.