CRT Key Exchange

C18: RSA/Certicom. CC0.

Diffie-Hellman key exchange runs in parallel across 6 CRT channels. Each channel uses its own primitive root as generator. 6 small discrete-log problems instead of 1 big one. CRT reconstructs the shared secret from 6 channel agreements.

How It Works

CRT Diffie-Hellman

Classic DH: g^a mod p (one big modulus). CRT DH: g_i^a mod m_i for each channel (6 small moduli). Alice sends 6 public residues. Bob sends 6. Each computes 6 shared residues independently. CRT reconstruction gives the unique shared secret in Z/12612600.

6 generators

Primitive roots

Each channel has its own generator: {3,2,2,3,2,2}.

Parallel exchange

CRT independence

6 small key exchanges run independently.

Shared secret

CRT reconstruction

6 channel agreements → unique shared value.

Channel security

Discrete log per mod

Breaking one channel reveals only 3-6 bits.

Try It

Alice's secret (1-419):

Secrets mod 420 (= lambda of ring). Try: Alice=137 Bob=42, Alice=1 Bob=419.

CRT Key Exchange vs Traditional

ModulusRSA: single 2048-bit prime productCRT: 6 small moduli (3-49)ParallelismSequential modular exponentiation6 independent exponentiationsKey size256+ bytes6 residues (< 20 bytes)Quantum resistanceShor's algorithm breaks RSA6 small DLPs -- different attack surfacePatent statusRSA/Certicom/NIST patentsCC0. Public domain. Forever.

This work is and will always be free.
No paywall. No copyright. No exceptions.

If it ever earns anything, every cent goes to the communities that need it most.

This sacred vow is permanent and irrevocable.
— Anton Alexandrovich Lebed

Source code · Public domain (CC0)

Contributions in equal measure: Anthropic's Claude, Anton A. Lebed, and the giants whose shoulders we stand on.

Rendered by .ax via WASM DOM imports. Zero HTML authored.