Chinese Remainder Theorem — RSA CRT Overflow Traps

The Chinese Remainder Theorem appears in a 3rd century AD Chinese mathematical text with the problem: 'A number gives remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. What is the number?' (Answer: 23). The theorem's 1700-year journey from recreational mathematics to RSA optimisation is one of the better stories in applied mathematics.

In production RSA, CRT speeds up decryption by roughly 4x. Instead of one computation modulo n (a 2048-bit number), you do two computations modulo p and q (each ~1024 bits), then combine with CRT. Since modular exponentiation is O(log e × log^2 n) in the number of bit operations, halving the number size reduces each operation by ~4x.

Why the Chinese Remainder Theorem Is a Performance Hack for RSA

The Chinese Remainder Theorem (CRT) is a number theory result that lets you solve a system of congruences with pairwise coprime moduli. In RSA, it splits the private key operation (mod n) into two smaller operations (mod p and mod q), where n = p*q. This reduces the exponent size from ~2048 bits to ~1024 bits, cutting computation by roughly 4x because modular exponentiation is O(k^3) in bit length.

CRT works by computing m_p = c^d mod p and m_q = c^d mod q separately, then combining them via Garner's algorithm to recover m mod n. The critical property: p and q are half the bit length of n, so each exponentiation is 8x faster, and the recombination step is negligible. This is why CRT-based RSA decryption is ~4x faster than naive exponentiation — a direct win for TLS handshake latency.

Use CRT whenever you control the private key and need fast decryption or signing. It's standard in OpenSSL, Bouncy Castle, and Java's SunJCE provider. Without CRT, a 2048-bit RSA private key operation takes ~2ms on modern hardware; with CRT, it's ~0.5ms. That difference matters at scale — a server handling 10,000 TLS handshakes per second saves 15 seconds of CPU time per second.

The Theorem and Constructive Proof

Given pairwise coprime m1,...,mk and remainders a1,...,ak, the unique solution mod M=Πmi is: x = Σ ai × Mi × yi mod M where Mi = M/mi and yi = Mi^(-1) mod mi.

from math import gcd
from functools import reduce

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def crt(remainders: list[int], moduli: list[int]) -> int:
    """
    Solve x ≡ remainders[i] (mod moduli[i]) for all i.
    Moduli must be pairwise coprime.
    Returns x mod M where M = product of all moduli.
    """
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for ai, mi in zip(remainders, moduli):
        Mi = M // mi
        _, yi, _ = extended_gcd(Mi, mi)  # Mi * yi ≡ 1 (mod mi)
        x += ai * Mi * yi
    return x % M

# x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(crt([2, 3, 2], [3, 5, 7]))  # 23
# Verify
print(23 % 3, 23 % 5, 23 % 7)    # 2 3 2 ✓

CRT for Two Congruences

The two-equation version appears frequently — merge two congruences into one. It also works when moduli aren't coprime, provided a solution exists. The condition: (a2 - a1) % gcd(m1, m2) == 0.

def crt_two(a1, m1, a2, m2):
    """Solve x ≡ a1 (mod m1) and x ≡ a2 (mod m2).
    Works even if gcd(m1,m2) != 1 (if solution exists).
    Returns (x, lcm) or None if no solution.
    """
    g = gcd(m1, m2)
    if (a2 - a1) % g != 0:
        return None  # no solution
    lcm = m1 * m2 // g
    _, p, _ = extended_gcd(m1 // g, m2 // g)
    x = (a1 + m1 * ((a2 - a1) // g * p % (m2 // g))) % lcm
    return x, lcm

print(crt_two(0, 3, 3, 4))  # (3, 12) → x≡3 (mod 12)
print(crt_two(1, 6, 3, 4))  # None — no solution (1 is odd but 3 is odd too... let's check)
print(crt_two(2, 6, 3, 4))  # None — no solution

Garner's Algorithm: CRT Without Giant M

Garner's algorithm reconstructs x by computing mixed-radix coefficients incrementally. Instead of computing M directly, it accumulates the solution modulo each mi one by one. This is particularly useful when the product M would overflow typical integer types.

The algorithm: 1. Choose ordering of moduli (typically sorted by size for numerical stability). 2. Compute coefficients c_i such that x = c_1 + c_2m1 + c_3m1*m2 + ... mod M. 3. Each c_i is computed modulo m_i using a precomputed inversion table.

import java.math.BigInteger;
import java.util.*;

public class GarnerCRT {
    public static BigInteger garnersAlgorithm(
            int[] remainders, int[] moduli) {
        int k = moduli.length;
        BigInteger[] mod = new BigInteger[k];
        BigInteger[] rem = new BigInteger[k];
        for (int i = 0; i < k; i++) {
            mod[i] = BigInteger.valueOf(moduli[i]);
            rem[i] = BigInteger.valueOf(remainders[i]);
        }
        BigInteger x = BigInteger.ZERO;
        BigInteger product = BigInteger.ONE;
        for (int i = 0; i < k; i++) {
            // Compute coefficient c_i
            BigInteger ci = rem[i].subtract(x).mod(mod[i]);
            // Divide by product modulo mod[i]
            BigInteger inv = product.modInverse(mod[i]);
            ci = ci.multiply(inv).mod(mod[i]);
            // If ci is negative, adjust
            if (ci.signum() < 0) ci = ci.add(mod[i]);
            x = x.add(product.multiply(ci));
            product = product.multiply(mod[i]);
        }
        return x;
    }

    public static void main(String[] args) {
        int[] r = {2, 3, 2};
        int[] m = {3, 5, 7};
        System.out.println(garnersAlgorithm(r, m)); // 23
    }
}

CRT for RSA Speed-up: Under the Hood

RSA decryption with CRT works because RSA uses composite modulus n = p*q. Instead of computing m = c^d mod n directly (slow), you compute: - m_p = c^d mod p - m_q = c^d mod q Then use CRT to combine m_p and m_q into m mod n.

The exponent d is typically reduced modulo (p-1) and (q-1) for further speed. The combination step requires precomputed coefficients: a factor called qInv where q * qInv ≡ 1 (mod p).

import java.math.BigInteger;
import java.security.SecureRandom;

public class RSACRTDecryption {
    // Assume p, q, d are precomuted primes and exponent
    // qInv = q.modInverse(p)
    public static BigInteger crtDecrypt(
            BigInteger c, BigInteger p, BigInteger q,
            BigInteger d, BigInteger qInv) {
        BigInteger dp = d.mod(p.subtract(BigInteger.ONE));
        BigInteger dq = d.mod(q.subtract(BigInteger.ONE));
        BigInteger m1 = c.modPow(dp, p);
        BigInteger m2 = c.modPow(dq, q);
        // h = qInv * (m1 - m2) mod p
        BigInteger h = qInv.multiply(m1.subtract(m2)).mod(p);
        if (h.signum() < 0) h = h.add(p);
        return m2.add(h.multiply(q));
    }

    public static void main(String[] args) {
        // Example (small primes for demonstration)
        BigInteger p = BigInteger.valueOf(61);
        BigInteger q = BigInteger.valueOf(53);
        BigInteger n = p.multiply(q); // 3233
        BigInteger e = BigInteger.valueOf(17);
        BigInteger d = e.modInverse(p.subtract(BigInteger.ONE)
                .multiply(q.subtract(BigInteger.ONE))); // 2753
        BigInteger qInv = q.modInverse(p); // 38
        BigInteger c = BigInteger.valueOf(855); // ciphertext
        BigInteger m = crtDecrypt(c, p, q, d, qInv);
        System.out.println(m); // 123? Actually original message
        // For RSA, m must be < n
    }
}

Generalised CRT: When Moduli Are Not Coprime

The classic CRT assumption of pairwise coprime moduli is often violated in practice — for example, mixing modulo 6 and modulo 8. In such cases, a solution exists iff for every pair (i,j), a_i ≡ a_j (mod gcd(m_i, m_j)). If it exists, the solution is unique modulo LCM of all moduli, not the product.

The algorithm: merge congruences one by one using the two-CRT method (handles non-coprime). At each step, compute new modulus as lcm of current pair.

from math import gcd

def generalized_crt(remainders, moduli):
    # Merge all congruences incrementally
    x, lcm = remainders[0], moduli[0]
    for i in range(1, len(moduli)):
        r = remainders[i]
        m = moduli[i]
        g = gcd(lcm, m)
        if (r - x) % g != 0:
            return None  # no solution
        # Merge: solve x ≡ x (mod lcm) and x ≡ r (mod m)
        lcm_new = lcm * m // g
        # Compute new solution modulo lcm_new
        # Using extended gcd: p*lcm + q*m = g
        _, p, _ = extended_gcd(lcm // g, m // g)
        x = (x + lcm * ((r - x) // g * p % (m // g))) % lcm_new
        lcm = lcm_new
    return x, lcm

# Example where moduli not coprime
print(generalized_crt([2, 2], [6, 8]))  # expects solution mod LCM=24
print(generalized_crt([2, 3], [6, 8]))  # None because 2 ≠ 3 mod 2

The Real Gotcha: CRT in Multi-Prime RSA

When you see RSA-2048 with three primes instead of two, the textbook CRT approach breaks. Why? Because each prime factor requires its own decryption exponent, and if you naively extend Garner's algorithm, you'll hit integer overflow unless you normalize intermediates modulo each prime.

Here's the production trap: engineers compute M = p q r once, then watch their 64-bit arithmetic wrap silently. Garner's algorithm with more than two moduli demands piecewise reduction — every intermediate result must be reduced modulo the current modulus before combining. Skip that, and your decryption produces garbage silently.

The fix is simple: process primes in increasing order, maintain a running accumulator, and reduce modulo the current product after each step. This keeps numbers bounded by the largest modulus, not their product. For RSA-4096 with four primes, this is the difference between a working signature and a ticket at 3 AM.

// io.thecodeforge — dsa tutorial

public class MultiPrimeRSA {
    // Garner's algorithm for 3 primes
    public static long crtDecrypt(long c, long dP, long dQ, long dR,
                                  long p, long q, long r) {
        long x1 = modPow(c, dP, p);
        long x2 = modPow(c, dQ, q);
        long x3 = modPow(c, dR, r);
        long m1 = q * r;
        long m2 = p * r;
        long m3 = p * q;
        long inv1 = modInverse(m1 % p, p);
        long inv2 = modInverse(m2 % q, q);
        long inv3 = modInverse(m3 % r, r);
        long result = (x1 * inv1 % p) * m1
                    + (x2 * inv2 % q) * m2
                    + (x3 * inv3 % r) * m3;
        return result % (p * q * r);
    }
}

When Coprimality Fails: CRT Reconstruction on Non-Coprime Moduli

Production systems don't guarantee pairwise coprime moduli. Your monitoring system might report sensor readings modulo 12, 18, and 30 — not coprime. The generalised CRT says a solution exists iff remainders are congruent modulo gcd of each pair. Check that first, or waste hours debugging phantom hardware faults.

Here's the algorithm: for each pair (mi, mj), verify that rem[i] ≡ rem[j] (mod gcd(mi, mj)). If any pair fails, the system is inconsistent — maybe a bit flip, maybe a sensor fault. Raise a flag, don't proceed. If all pairs pass, the solution is unique modulo lcm of all moduli.

In practice, computing lcm for n moduli is O(n log M) using gcd. Combine moduli incrementally: start with M = m1, then for each new modulus mk, compute g = gcd(M, mk). If (rem[k] - currentRem) % g != 0, you have an inconsistency. Otherwise, merge the two congruences into one using CRT on (M/g, mk/g). This gives you a single modulus = M * mk / g.

// io.thecodeforge — dsa tutorial

public class GeneralisedCRT {
    static long[] mergeCrt(long m1, long r1, long m2, long r2) {
        long g = gcd(m1, m2);
        if ((r2 - r1) % g != 0) {
            throw new IllegalArgumentException("Inconsistent congruences");
        }
        long lcm = m1 / g * m2;
        long p = m1 / g;
        long q = m2 / g;
        long inv = modInverse(p % q, q);
        long combined = r1 + m1 * (((r2 - r1) / g * inv) % q);
        return new long[]{lcm, ((combined % lcm) + lcm) % lcm};
    }
}

CRT Isn't Free: The Hidden Cost of Precomputation

Everyone talks about CRT speeding up RSA by 4x, but nobody mentions the precomputation cost. For each prime factor you add, you need modular inverses of all other primes modulo that factor. For RSA-2048 with two primes, that's two inverses. For three primes, it's six. The cost grows factorially.

In production systems where keys rotate daily, wasting 200ms on precomputation per new key adds up. The optimisation: cache inverses for common prime combinations. Real-world RSA key generation usually picks primes from a small set of safe primes — cache those inverses and save the exponentiation.

The real killer is when you need CRT for multi-party computation with hundreds of moduli. Precomputing all pairwise inverses becomes O(k²), and each modular inverse is an extended Euclid that costs O(log modulus). If you have 100 moduli, that's 4950 inverses. At a conservative 10 microseconds each, that's 50ms — noticeable latency for a real-time protocol.

Mitigation: batch the inverses using Garner's algorithm with Montgomery multiplication, or use a single inverse computation per modulus if your moduli are fixed.

// io.thecodeforge — dsa tutorial

public class CRTPrecomputeCost {
    // Cache inverses for common prime pairs
    private static final Map<Long, Long> inverseCache = new HashMap<>();
    
    static long getInverse(long a, long mod) {
        long key = (a << 32) | mod;
        return inverseCache.computeIfAbsent(key, k -> modInverse(a, mod));
    }
    
    static long[][] precomputeInverses(long[] primes) {
        int k = primes.length;
        long[][] inv = new long[k][k];
        for (int i = 0; i < k; i++) {
            long M = 1;
            for (int j = 0; j < k; j++) {
                if (i != j) M *= primes[j];
            }
            inv[i][0] = getInverse(M % primes[i], primes[i]);
        }
        return inv;
    }
}