4. Rabin Encryption Algorithm

Rabin algorithm also introduce ambiguities to the decryption. Even decrypt the ciphertext correctly, four candidate keys are supposed to be gotten.

4.1. Key Setup

Alice chooses two prime numbers \(p\) and \(q\) such that \(|p| \approx |q|\), and \(n=pq\). In practice, \(p\) and \(q\) have \(p \equiv q \equiv 3 ~mod~ 4\), then \(n\) is a Blum integer. Because computing square roots would be easier. Random integer \(b\) is randomly chosen from \(\mathbb{Z}_n^*\).

Public key: \((n, b)\)

Private key: \((p, q)\)

4.2. Encryption

Let \(m\) be the message. \(c = m(m+b)~mod~n\)

4.3. Decryption

Alice solves \(m^2 + bm - c \equiv 0~mod~n\).

\[\begin{split}&m \equiv \frac{-b \pm \sqrt{\Delta }}{2}~mod~n\\ &\Delta = b^2 + 4c\end{split}\]

4.3.1. Theorem

Let \(y \in QR_n\) where \(n = pq\) and \(p\), \(q\) are distinct odd primes, \(y\) has four square roots.

\(y~mod~p\) has 2 roots and \(y~mod~q\) has 2 roots, so \(y~mod~n\) has \(2\times2=4\) roots.

Apply the theorem, \(\Delta \in QR_n\) has 4 square roots and we will have 4 candidate for plaintext.

4.3.2. Compute Square Roots

For \(p \equiv 3, 5, 7~mod~8\) and \(a \in QR_p\),

\[\begin{split}\sqrt{a}~mod~p = \begin{cases}a^{(p+1)/4}~mod~p& if~p\equiv 3, 7~mod~8\\a^{(p+3)/8}~mod~p& if~a^{(p-1)/4}\equiv1~mod~p\\(4a)^{(p+3)/8}/2& o.w.\end{cases}\end{split}\]

The complexity is \(O(\log^3 p)\).

So in decryption, Alice computes

\[\begin{split}&r=c^{(p+1)/4}~mod~p\\&s=c^{(q+1)/4}~mod~q\\&t=aps+bqr~mod~n\\&u=aps-bqr~mod~n\end{split}\]

\(m \in \{\pm t, \pm u\}\)

How to distinguish the true message from candidates? The answer is to add structure information to the message. Say, make the lower significant bits the same as the higher significant bits.

4.3.3. Performance

Rabin Algorithm has constant expansion rate and is as efficient as RSA.