The Rabin Cryptosystem

The Rabin Cryptosystem

Introduction

RSA raises a number to a power. The Rabin cryptosystem does something simpler: it squares the message. The ciphertext is c = m^2 mod n, where n is the product of two secret primes. Anyone can square a number, so the public key is just n. Taking a square root modulo n is easy only for someone who knows the two primes, and that is the trapdoor.

The scheme has one famous property and one famous flaw. The property is that finding the square roots is provably as hard as factoring n, which nobody has proved for RSA. The flaw is that every ciphertext has four square roots, so the receiver needs a way to tell which one is the real message. This guide shows how decryption works, how redundancy fixes the ambiguity, and how a chosen-ciphertext attack factors the key.

Table of Contents

• History and Standards
• Key Generation
• Encryption
• Decryption
• The Four Roots and Redundancy
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

Michael Rabin published the squaring trapdoor function as part of a signature scheme, in the chapter “Digitalized Signatures” of the book “Foundations of Secure Computation” in 1978. The MIT technical report TR-212 of January 1979 is titled “Digitalized Signatures and Public-Key Functions as Intractable as Factorization”. According to Wikipedia, this was the first digital signature scheme in which forging a signature could be proven to be as hard as factoring.

The encryption scheme that bears Rabin’s name came later. Wikipedia notes that textbooks turned the trapdoor function into an encryption scheme, even though Rabin never published it as one. The textbook form is the one in this guide. Blum and Williams suggested a fix for the ambiguity: use primes that are 3 modulo 4, and restrict the squaring to the quadratic residues, which turns the squaring into a permutation. A product of two such primes is called a Blum integer.

Rabin encryption is used mainly as an example in textbooks. RSA with OAEP padding is the basis of the standard encryption schemes that are widely used. The Rabin function does appear in the literature on exact security of signatures, for example in the paper of Bellare and Rogaway at EUROCRYPT 1996 on how to sign with RSA and Rabin.

Key Generation

Choose two large, different primes p and q such that both are 3 modulo 4, and compute n = p * q. The public key is n. The private key is the pair (p, q).

The condition p = 3 mod 4 is what makes decryption easy. For these primes, a square root modulo p can be computed with a single exponentiation, as the next sections show. For other primes, a longer algorithm is needed.

Encryption

A message is first turned into a number m that is smaller than n. The ciphertext is then:

c = m^2 mod n

This takes one modular multiplication. It is cheaper than RSA, where the public exponent needs at least a cube. There is no randomness in it, so the same message always gives the same ciphertext.

Decryption

The receiver has to find a square root of c modulo n. Knowing p and q, this splits into two easy problems.

Step 1: roots modulo p and q. Because p = 3 mod 4, the number (p + 1) / 4 is a whole number. The two roots are:

mp = c^((p+1)/4) mod p
mq = c^((q+1)/4) mod q

Why does this work? The ciphertext c is a square modulo p, because c = m^2 modulo n, and so also modulo p. For such a number, Euler’s criterion says that c^((p-1)/2) = 1 mod p. From this, mp^2 = c^((p+1)/2) = c * c^((p-1)/2) = c mod p, which means that mp is a square root of c modulo p. The same holds for q.

Step 2: the extended Euclidean algorithm. Find yp and yq such that yp * p + yq * q = 1. They exist because p and q are different primes.

Step 3: the Chinese remainder theorem. Combine the roots modulo p and q into roots modulo n:

r1 = (yp * p * mq + yq * q * mp) mod n
r2 = n - r1
r3 = (yp * p * mq - yq * q * mp) mod n
r4 = n - r3

All four numbers are square roots of c modulo n. The first is the root that is mp modulo p and mq modulo q. The second is its negative. The third is -mp modulo p and mq modulo q, and the fourth is its negative. A number has two square roots modulo each prime, so it has four modulo n.

The Four Roots and Redundancy

The original message is one of the four roots. The decryption cannot tell which one, because all four give the same ciphertext. If the message is a sentence of English, a person can pick the root that reads as text. A program needs a rule.

The usual rule is redundancy. Before encrypting, the sender adds a pattern that a random root is unlikely to have. In this guide, the last 8 bits of the message are written again after it:

m' = m * 2^8 + (m mod 2^8)

After decryption, the receiver keeps the root whose lowest 8 bits are equal to the 8 bits before them. This is the idea of repeating the last bits of the message. Real systems repeat many more bits. The message must be small enough that m' stays below n.

The test is not perfect. A wrong root passes it by chance with a small probability. In a test with a 64-bit n, 20,000 random messages were encrypted, and 151 of them, which is 0.76 percent, had a second root with the right redundancy. A naive estimate, with 3 wrong roots that each pass with a probability of 1/256, gives 1.17 percent. In such a case the receiver cannot decide, and the sender must choose another message or add more redundancy. With 64 bits of redundancy, the naive estimate is about 3 in 2^64.

Interactive Visualizer

The visualizer above runs this exact algorithm with small numbers, so that every value fits on the screen. Choose the textbook variant, or the variant with 8 bits of redundancy. Enter the primes p and q, which must be prime and 3 modulo 4, and a message. Then click Encrypt and decrypt. The log shows the public key, the encryption, the roots modulo p and q, the extended Euclidean algorithm, and the four roots. For each root, it shows its square modulo n. In the second variant it also shows the redundancy check, and the message that is recovered.

A Worked Example

The first example is the one that the Wikipedia article uses. The primes are p = 7 and q = 11, so n = 77. The message is m = 20.

Encryption. The square of 20 is 400, and 400 modulo 77 is 15, so the ciphertext is c = 15.

Roots modulo p and q. The exponent for p is (7 + 1) / 4 = 2. We have c mod 7 = 1, so mp = 1^2 mod 7 = 1. The exponent for q is (11 + 1) / 4 = 3. We have c mod 11 = 4, so mq = 15^3 mod 11 = 9.

The extended Euclidean algorithm. The numbers yp = -3 and yq = 2 satisfy (-3) * 7 + 2 * 11 = 1.

The four roots. The formulas give r1 = 64, r2 = 13, r3 = 20, and r4 = 57. Squaring them modulo 77 gives 15 for 64, 15 for 13, 15 for 20, and 15 for 57. All four give the ciphertext. The message is r3, and nothing in the ciphertext says so.

A larger example with redundancy. Now take p = 1000003 and q = 1000039, so n = 1000042000117. The message is m = 123456. Its lowest 8 bits are 64. The padded message is m' = 123456 * 256 + 64 = 31604800, and the largest message that fits is 3906414062. The ciphertext is c = 821466923234. Then mp = 395296, mq = 603591, yp = 194452, and yq = -194445. The four roots, with their lowest 8 bits and the 8 bits before them, are:

Root	Value	Lowest 8 bits	Next 8 bits	Redundancy right?
r1	799803794699	11	101	no
r2	200238205418	234	137	no
r3	31604800	64	64	yes
r4	1000010395317	181	174	no

Only the root r3 passes the check. Dropping its last 8 bits gives 123456, the original message. Without the redundancy, the same message 123456 encrypts to 15241383936, and its four roots are 123456, 1000041876661, 659835856046, 340206144071. Nothing in these four numbers says which one is the message.

Python Implementation

This is a complete Rabin cryptosystem, with a primality test and the key generation. The function square_roots follows the three steps above. The function factor_from_root_oracle is the attack of the next section.

# rabin.py
#
# The Rabin cryptosystem (the textbook form of Michael Rabin's squaring
# trapdoor function). The public key is n = p * q, where p and q are primes
# with p = q = 3 (mod 4). Encryption is a squaring: c = m^2 mod n. Decryption
# takes a square root of c modulo p and modulo q and joins them with the
# Chinese remainder theorem. This gives four roots, so the plaintext must carry
# some redundancy that tells the right root from the three wrong ones.

import random

SMALL_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def is_probable_prime(n, rounds=40, rng=None):
    """Miller-Rabin. The first twelve primes as bases are exact for n below 3.3 * 10^24."""
    if n < 2:
        return False
    for p in SMALL_PRIMES:
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    bases = list(SMALL_PRIMES)
    if n.bit_length() > 80:
        rng = rng or random.Random()
        bases += [rng.randrange(2, n - 1) for _ in range(rounds)]
    for a in bases:
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True


def random_blum_prime(bits, rng):
    """A random prime of the given size with p = 3 (mod 4)."""
    while True:
        p = rng.getrandbits(bits) | (1 << (bits - 1)) | 3
        if is_probable_prime(p, rng=rng):
            return p


def keygen(bits, rng=None):
    """Two distinct primes of `bits` bits each, both 3 mod 4. Returns (n, p, q)."""
    rng = rng or random.Random()
    p = random_blum_prime(bits, rng)
    q = p
    while q == p:
        q = random_blum_prime(bits, rng)
    return p * q, p, q


def egcd(a, b):
    """Extended Euclid: returns (g, x, y) with a*x + b*y = g."""
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b:
        qt = a // b
        a, b = b, a - qt * b
        x0, x1 = x1, x0 - qt * x1
        y0, y1 = y1, y0 - qt * y1
    return a, x0, y0


def check_key(p, q):
    if p == q or p % 4 != 3 or q % 4 != 3:
        raise ValueError("p and q must be different primes with p = q = 3 (mod 4)")
    if not (is_probable_prime(p) and is_probable_prime(q)):
        raise ValueError("p and q must be prime")


def encrypt(m, n):
    """c = m^2 mod n, for a plaintext number m with 0 <= m < n."""
    if not 0 <= m < n:
        raise ValueError("the plaintext must be a number below n")
    return m * m % n


def square_roots(c, p, q, trace=None):
    """The four square roots of c modulo n = p * q, in the order r1, r2, r3, r4 (r2 = n - r1, r4 = n - r3)."""
    n = p * q
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    g, yp, yq = egcd(p, q)
    assert g == 1 and yp * p + yq * q == 1
    r1 = (yp * p * mq + yq * q * mp) % n
    r3 = (yp * p * mq - yq * q * mp) % n
    roots = [r1, (n - r1) % n, r3, (n - r3) % n]
    if trace is not None:
        trace.update({"mp": mp, "mq": mq, "yp": yp, "yq": yq})
    return roots


# redundancy: the last k bits of the message are written again after it
def add_redundancy(m, k):
    return (m << k) | (m & ((1 << k) - 1))


def has_redundancy(r, k):
    return (r & ((1 << k) - 1)) == ((r >> k) & ((1 << k) - 1))


def remove_redundancy(r, k):
    return r >> k


def max_message(n, k):
    """The largest message number that fits: the padded number must stay below n."""
    return (n - 1) >> k


def decrypt(c, p, q, k):
    """The plaintext whose redundancy is right. Raises an error when no root or more than one root has it."""
    good = [r for r in square_roots(c, p, q) if has_redundancy(r, k)]
    if len(good) != 1:
        raise ValueError("%d roots have the redundancy" % len(good))
    return remove_redundancy(good[0], k)


def factor_from_root_oracle(n, oracle, rng, tries=64):
    """Factor n with a decryption oracle that returns ANY square root of c. This is the chosen-ciphertext attack,
    and also the proof that finding square roots is as hard as factoring."""
    from math import gcd
    for attempt in range(1, tries + 1):
        x = rng.randrange(2, n - 1)
        if gcd(x, n) != 1:
            return gcd(x, n), n // gcd(x, n), attempt
        y = oracle(x * x % n)
        if y not in (x, n - x):
            p = gcd(x - y, n)
            return p, n // p, attempt
    raise RuntimeError("no luck")


if __name__ == "__main__":
    # the example of the Wikipedia article: p = 7, q = 11, m = 20
    p, q, m = 7, 11, 20
    n = p * q
    c = encrypt(m, n)
    print("n = %d, c = %d" % (n, c))
    print("roots: " + ", ".join(str(r) for r in square_roots(c, p, q)))
    # with 8 bits of redundancy the right root can be told apart
    p, q, k = 1000003, 1000039, 8
    n = p * q
    m = 123456
    c = encrypt(add_redundancy(m, k), n)
    print("n = %d, c = %d, recovered m = %d" % (n, c, decrypt(c, p, q, k)))

Running it produces this output:

n = 77, c = 15
roots: 64, 13, 20, 57
n = 1000042000117, c = 821466923234, recovered m = 123456

I checked this code in several ways before writing it up. It reproduces the example of the Wikipedia article, including mp, mq, yp, yq, and the four roots. For all 66 pairs of primes below 80 that are 3 modulo 4, every square root found by brute force is one of the roots that the formulas give. For keys of 128, 512, and 1024 bits, 150 random messages gave four different roots in each case, each root squares to the ciphertext, and one of them is the message. The OpenSSL in Node.js confirms that all the generated primes are prime. The redundancy figures and the attack below were also run on those keys. Rabin encryption has no official test vectors, so the checks are mathematical ones, not comparisons with a standard.

Security Status

Equivalence with factoring. If an algorithm can find a square root modulo n for every ciphertext, it can factor n. The proof is short. Pick a random x and compute c = x^2 mod n. Give c to the algorithm. It returns a root y, and it cannot know which root x was. With probability one half, y is not x and not n - x. Then x^2 = y^2 mod n, so n divides (x - y)(x + y) but divides neither factor. The greatest common divisor of x - y and n is therefore one of the primes.

The code runs this attack. With n = 1000042000117, the random number x = 425475920318 gives c = 725136990418. The oracle returns the root y = 610339474907. The difference x - y is 815178445528 modulo n, and its greatest common divisor with n is 1000003. The other factor is 1000039. It took 1 attempt. For keys of 128, 512, and 1024 bits, the code factors n in a few tries.

The chosen-ciphertext attack. The same idea breaks the plain scheme. An attacker who can ask for decryptions chooses a random x, sends x^2 mod n as a ciphertext, and gets back a root. With probability one half it is a different root, and the attacker factors n. The Rabin cryptosystem is insecure against a chosen-ciphertext attack even for random messages. Adding redundancy defends against this specific attack, because the decryption then returns only the root that the attacker already knows. But the proof of equivalence with factoring no longer applies to that version. Wikipedia says that it was uncertain as of 2004 whether the variant is secure, and that the Handbook of Applied Cryptography considers the equivalence probable as long as finding the roots remains a two-part process.

No semantic security. The encryption is deterministic, so an attacker who guesses the message can encrypt the guess and compare it with the ciphertext. For small sets of messages, this reveals the message. A real system needs randomized padding.

For new systems, use a standard scheme such as RSA-OAEP or an elliptic-curve scheme. Rabin encryption is a good way to learn how trapdoor functions and the factoring problem relate.

FAQ

Why must the primes be 3 modulo 4?

Because then a square root modulo p is a single exponentiation, c^((p+1)/4). For other primes, the root needs a longer algorithm such as Tonelli-Shanks. The condition is not needed for the security.

Why are there four square roots?

A number that is a square modulo a prime has exactly two roots modulo that prime, one the negative of the other. With two primes, there are two choices for each, which makes four combinations modulo n. The Chinese remainder theorem joins each combination into one root.

Can the receiver always tell the right root?

The receiver cannot always tell without help. Redundancy in the message, such as a repeated pattern, lets the receiver pick the right root almost always. A very small chance remains that two roots look valid, and then the message must be sent again.

Is Rabin encryption better than RSA?

It has a stronger proof of security for the one-way property, and encryption is cheaper. It has the four-root problem, and the plain version falls to a chosen-ciphertext attack. In practice, RSA with OAEP is the standard choice.

What happens if the message is a multiple of p or q?

Then the ciphertext shares a factor with n, and there are fewer than four different roots. For example, with n = 77, the message 14 gives c = 42 and only two roots, 14 and 63. This is also a danger, because the greatest common divisor of the ciphertext and n is then a prime factor of n. In the example, the greatest common divisor of 42 and 77 is 7, which is p. Anyone who sees such a ciphertext can compute it.

References

1. Rabin, Michael O. “Digitalized Signatures and Public-Key Functions as Intractable as Factorization.” MIT Laboratory for Computer Science, Technical Report TR-212, January 1979.

2. Rabin, Michael O. “Digitalized Signatures.” In “Foundations of Secure Computation,” Academic Press, 1978, pages 155 to 168.

3. Menezes, Alfred J., van Oorschot, Paul C., and Vanstone, Scott A. “Handbook of Applied Cryptography.” CRC Press, 1996, Section 8.3, “Rabin public-key encryption”. Available at: https://cacr.uwaterloo.ca/hac/about/chap8.pdf

4. Bellare, M. and Rogaway, P. “The Exact Security of Digital Signatures: How to Sign with RSA and Rabin.” EUROCRYPT 1996, Lecture Notes in Computer Science 1070, Springer.

5. Galbraith, Steven D. “Mathematics of Public Key Cryptography.” Cambridge University Press, 2012, Section 24.2, “The textbook Rabin cryptosystem”.

6. Wikipedia. “Rabin cryptosystem.” Available at: https://en.wikipedia.org/wiki/Rabin_cryptosystem