Offensive Security Researcher & Quantum Cryptography Analyst

Rabin Cryptosystem Algorithm: Working, Explanation, and Security Analysis

Abdul Wahab Junaid
Rabin algorithm and working of this algorithm

Rabin algorithm and working of this algorithm

I find the Rabin cryptosystem fascinating because it is one of the very few public-key encryption schemes with a security proof that is provably as hard as factoring the modulus — not just “believed to be” as hard, the way RSA’s security is generally assumed but not formally proven equivalent to factoring. I use it as a teaching example whenever I want to show that a cryptosystem’s security can be tied directly, and provably, to a well-studied hard mathematical problem, at the cost of a small quirk: decryption naturally produces four possible plaintexts instead of one, which the scheme needs extra logic to resolve.

History and Background

I trace the Rabin cryptosystem to Michael O. Rabin’s 1979 paper, published as an MIT technical report, just a couple of years after RSA was introduced in 1977. Rabin designed the scheme specifically to achieve a security reduction to integer factorization — meaning that if someone could reliably break the encryption, they could equally reliably factor the modulus $n$, something RSA has never been formally proven to require. Despite this strong theoretical guarantee, Rabin’s scheme saw less real-world adoption than RSA, partly because of the ciphertext ambiguity problem (needing to select the correct plaintext out of four candidates) and partly because RSA became the entrenched industry standard first. Variants like Rabin-Williams later refined the scheme to resolve some of its practical usability issues.

Problem Statement

I want an encryption scheme whose difficulty to break is provably tied to a hard mathematical problem, rather than just conjectured. I choose modular square roots as the core operation: encryption squares the plaintext modulo $n = pq$, and decryption requires computing a modular square root, which is easy if the factorization of $n$ is known but computationally equivalent to factoring $n$ if it is not.

Core Concepts

How It Works

I lay out key generation, encryption, and decryption:

  1. Key generation: Choose two large primes $p$ and $q$, both congruent to $3 \bmod 4$, and compute $n = pq$. The public key is $n$; the private key is the pair $(p, q)$.
  2. Encryption: To encrypt a plaintext $m$ (with $0 \leq m < n$), compute the ciphertext as $c = m^2 \bmod n$.
  3. Decryption: Compute the square roots of $c$ modulo $p$ and modulo $q$ separately, using the fact that when $p \equiv 3 \pmod 4$, a square root mod $p$ can be computed directly as $c^{(p+1)/4} \bmod p$.
  4. Use the Chinese Remainder Theorem to combine the two square roots mod $p$ and mod $q$ into four distinct square roots modulo $n$.
  5. Select the correct plaintext among the four candidates using redundancy built into the original message (such as a repeated pattern of bits) to unambiguously identify which root is the true one.

Working Principle

I see the internal logic resting on the fact that squaring modulo a prime $p \equiv 3 \pmod 4$ has a simple closed-form inverse: $c^{(p+1)/4} \bmod p$ directly yields a square root of $c$, without needing the more general (and more complex) Tonelli-Shanks algorithm required for primes not of this special form. This is why Rabin’s key generation insists $p \equiv q \equiv 3 \pmod 4$. Because squaring mod $n$ is a 4-to-1 map (each quadratic residue mod $n$ has four square roots, formed by combining $\pm$ roots mod $p$ and mod $q$ via CRT), an attacker who could reliably invert the squaring operation without knowing $p$ and $q$ would, as a side effect, be able to find two different square roots of the same value — from which the factorization of $n$ can be recovered efficiently using the Euclidean algorithm. This is the crux of Rabin’s provable security-equals-factoring reduction.

Mathematical Foundation

I define the encryption function as:

$$ c = m^2 \bmod n $$

Decryption computes square roots modulo each prime factor:

$$ m_p = c^{(p+1)/4} \bmod p, \qquad m_q = c^{(q+1)/4} \bmod q $$

which are valid because for $p \equiv 3 \pmod 4$:

$$ \left(c^{(p+1)/4}\right)^2 = c^{(p+1)/2} = c \cdot c^{(p-1)/2} \equiv c \cdot 1 \equiv c \pmod p $$

using Euler’s criterion, since $c$ is a quadratic residue mod $p$ and $c^{(p-1)/2} \equiv 1 \pmod p$. I then apply the Chinese Remainder Theorem to combine $\pm m_p \pmod p$ and $\pm m_q \pmod q$ into four square roots modulo $n$:

$$ r_1 = (y_p \cdot q \cdot (q^{-1} \bmod p) + y_q \cdot p \cdot (p^{-1} \bmod q)) \bmod n $$

for each combination of $y_p \in {m_p, -m_p}$ and $y_q \in {m_q, -m_q}$, giving four roots ${r_1, n-r_1, r_2, n-r_2}$. The security reduction is captured by:

$$ \text{Breaking Rabin} \iff \text{Factoring } n $$

because finding any square root $x’$ of $c$ different from the one used originally lets an attacker compute:

$$ \gcd(x’ – m, n) $$

which yields a non-trivial factor of $n$ with probability $\frac{1}{2}$ for a randomly chosen root.

Diagrams

flowchart TD
    A["Choose two prime numbers"] --> B["Compute the public key"]
    B --> C["Encrypt the plaintext"]
    C --> D["Compute the first square root"]
    C --> E["Compute the second square root"]
    D --> F["Combine the results using CRT"]
    E --> F
    F --> G["Select the correct plaintext"]

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    R->>S: Public key n
    S->>S: Compute c = m^2 mod n
    S->>R: Send ciphertext c
    R->>R: Compute mp and mq using p, q
    R->>R: Combine via CRT into 4 candidates
    R->>R: Pick correct plaintext using redundancy check

Pseudocode

Function RabinKeyGen(bits):
    p = RandomPrimeCongruent3Mod4(bits/2)
    q = RandomPrimeCongruent3Mod4(bits/2)
    n = p * q
    publicKey = n
    privateKey = (p, q)
    return (publicKey, privateKey)

Function RabinEncrypt(m, n):
    c = (m * m) mod n
    return c

Function RabinDecrypt(c, p, q):
    mp = modpow(c, (p+1)/4, p)
    mq = modpow(c, (q+1)/4, q)
    (yp_inv) = modinverse(q, p)
    (yq_inv) = modinverse(p, q)
    r1 = (mp * q * yp_inv + mq * p * yq_inv) mod (p*q)
    r2 = (p*q) - r1
    r3 = (mp * q * yp_inv - mq * p * yq_inv) mod (p*q)
    r4 = (p*q) - r3
    candidates = [r1, r2, r3, r4]
    m = SelectValidCandidate(candidates)   // uses redundancy/padding to disambiguate
    return m

Step-by-Step Example

I use small numbers for illustration. Let $p = 7$ and $q = 11$ (both $\equiv 3 \pmod 4$), so $n = 77$. Suppose the message is $m = 20$. Encryption computes $c = 20^2 \bmod 77 = 400 \bmod 77 = 15$. To decrypt, I compute $m_p = 15^{(7+1)/4} \bmod 7 = 15^2 \bmod 7 = 225 \bmod 7 = 1$, and $m_q = 15^{(11+1)/4} \bmod 11 = 15^3 \bmod 11 = 3375 \bmod 11 = 5$. Using CRT to combine $m_p = \pm 1 \pmod 7$ and $m_q = \pm 5 \pmod{11}$, I get four candidate roots modulo 77: these work out to ${20, 57, 43, 34}$. Since I know the true message was $20$, I confirm it appears among the four candidates; in practice the receiver would use redundancy (like requiring the last 16 bits to be a repeated copy of an earlier segment) to automatically pick $20$ over the other three.

Time Complexity

I break this into encryption and decryption. Encryption is a single modular squaring:

$$ T_{\text{encrypt}} = O(\log^2 n) $$

using standard modular multiplication algorithms (or $O(\log n \log\log n)$ with fast multiplication techniques). Decryption computes two modular exponentiations (one mod $p$, one mod $q$), each costing $O(\log^3 n)$ using simple square-and-multiply, plus a constant number of CRT combination steps:

$$ T_{\text{decrypt}} = O(\log^3 n) $$

This is generally faster than RSA decryption since exponents used are small and fixed relative to $p$ and $q$’s bit length.

Space Complexity

I store the modulus $n$ (public key) and the two primes $p, q$ (private key), each roughly half the bit-length of $n$:

$$ S = O(\log n) $$

which matches the space requirements of RSA-style cryptosystems.

Correctness Analysis

I consider the scheme correct because Euler’s criterion guarantees that for $p \equiv 3 \pmod 4$ and $c$ a quadratic residue mod $p$, the value $c^{(p+1)/4} \bmod p$ is genuinely a valid square root of $c$ modulo $p$; the same logic applies for $q$. The Chinese Remainder Theorem then guarantees a unique reconstruction of any combination of residues mod $p$ and mod $q$ into a residue mod $n$, so all four combinations produce valid square roots of $c$ modulo $n$, one of which is always the original message $m$ (or its negation, or one of the other two roots arising from the CRT symmetry). As long as the redundancy scheme used to select the correct root is well-designed, decryption always successfully and unambiguously recovers the intended plaintext.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

/* Small helper: modular exponentiation */
long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

/* Extended Euclidean algorithm for modular inverse */
long long ext_gcd(long long a, long long b, long long *x, long long *y) {
    if (b == 0) { *x = 1; *y = 0; return a; }
    long long x1, y1;
    long long g = ext_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

long long mod_inverse(long long a, long long m) {
    long long x, y;
    ext_gcd(a, m, &x, &y);
    return ((x % m) + m) % m;
}

int main() {
    long long p = 7, q = 11; /* toy primes, both = 3 mod 4 */
    long long n = p * q;

    long long m = 20; /* plaintext, must be < n */
    long long c = (m * m) % n;
    printf("Plaintext m = %lld\n", m);
    printf("Ciphertext c = m^2 mod n = %lld\n", c);

    /* Decryption */
    long long mp = mod_pow(c, (p + 1) / 4, p);
    long long mq = mod_pow(c, (q + 1) / 4, q);

    long long q_inv_mod_p = mod_inverse(q, p);
    long long p_inv_mod_q = mod_inverse(p, q);

    long long r1 = ((mp * q % n) * q_inv_mod_p % n + (mq * p % n) * p_inv_mod_q % n) % n;
    long long r2 = (n - r1) % n;

    long long mp_neg = (p - mp) % p;
    long long r3 = ((mp_neg * q % n) * q_inv_mod_p % n + (mq * p % n) * p_inv_mod_q % n) % n;
    long long r4 = (n - r3) % n;

    printf("Four candidate roots: %lld, %lld, %lld, %lld\n", r1, r2, r3, r4);

    return 0;
}

Sample Input and Output

Plaintext m = 20
Ciphertext c = m^2 mod n = 15
Four candidate roots: 20, 57, 43, 34

The original plaintext, 20, appears correctly among the four candidate roots, matching my worked example above.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version