THE GARDEN

Composite-Modulus Key Exchange Break (CRT Projection Attack)

Updated 13 Sep 2026

• •

  What it is

  • •

    A technique for breaking a home-rolled Diffie-Hellman-style key exchange built on multiplication modulo a composite $n = pq$ (instead of a proper prime-order group), whenever the factors $p, q$ are known to the attacker. Since arithmetic mod $n$ is exactly tracked by the pair of residues mod $p$ and mod $q$ (CRT), every operation the legitimate parties perform (multiplying by a secret blinding factor, inverting it, chaining more factors) can be replayed independently in the smaller ring $\mathbb{Z}_q$​ alone. This becomes decisive when the secret value has an exploitable structural relationship with one factor (e.g. it's constructed as a multiple of $p$), fixing its residue mod $p$ for free and leaving only $v \bmod q$ to actually recover.

• •

  When to apply

  • •

    A key-exchange or blinding protocol operates on a composite modulus $n=pq$ using only multiplication/inversion (no genuine hard-DLP group), and the factorization of nn n is available. Look for a secret value with a known special relationship to one of the factors — e.g. explicitly constructed as factor * random.

• •

  Math

  • •

    For any protocol value $w \equiv v \cdot k \pmod n$, the projection $w \bmod q \equiv (v \bmod q)(k \bmod q) \pmod q$ holds independently of $p$. Chained blinding/unblinding steps can therefore be replayed mod $q$ alone, using modular inverses computed mod $q$ (easy, since $q$'s primality guarantees the inverse exists without needing $\phi(n)$).

• •

  Worked example

  • •

    Toy 32-bit primes $p,q$, simulating the full protocol ($v = p \cdot \text{rand} \bmod n$, then chained blinding by $k_A$​ and $k_B$​ in both directions): given only $p$, $q$, and the three exchanged values (never the actual secrets $k_A$​, $k_B$​, or $v$), projecting every step down mod $q$ and using $v \equiv 0 \pmod p$ to fix the other half via CRT recovered the exact true shared secret $v$ every trial.

• •

  Python

  • •

    kB_mod_q = (vkakb * pow(vka % q, -1, q)) % q
    v_mod_q  = (vkb * pow(kB_mod_q, -1, q)) % q
    k        = (v_mod_q * pow(p % q, -1, q)) % q   # since v = p*k, v mod q = (p mod q)*k mod q
    v        = (p * k) % (p * q)                    # unique in [0, n) once k mod q is known
    

• •

  Related

  • •

    Chinese Remainder Theorem

• •

  Cards

  • •

    What structural weakness does this attack exploit, beyond just "the modulus is composite"?

    • •

      The secret value v was deliberately constructed as a multiple of one known factor (p), fixing v mod p trivially and leaving only v mod q to actually recover.

  • •

    Why can chained blinding/unblinding operations be replayed independently mod q, ignoring p entirely?

    • •

      Arithmetic mod a composite n=pq is exactly tracked by its residues mod p and mod q separately (CRT), so every protocol step has an independent, valid "shadow" computation happening mod q alone.

◌ Explore connections in Graph view