# 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?

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.