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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.