Public Key Cryptography

For N parties to communicate pairwise with symmetric keys, each pair needs a unique shared secret:

N(N−1) / 2 keys required

10 users → 45 keys   1,000 users → 499,500 keys   1M users → ~5 × 10¹¹ keys

Key distribution requires a pre-existing secure channel — a chicken-and-egg problem.

Physical couriers, diplomatic bags, or pre-shared keys simply do not scale to the internet.

1974 Merkle's Puzzles

Ralph Merkle proposed sending N puzzles, each requiring O(N) work to solve. The intended recipient solves one; an eavesdropper must solve all N → O(N²) quadratic gap.

First published concept of public-key agreement, though only quadratic security.

1976 Diffie & Hellman

"New Directions in Cryptography" — introduced the concept of public-key cryptography and the DH key exchange protocol.

1977 RSA

Rivest, Shamir, Adleman — first practical public-key encryption and signature scheme.

a ≡ b (mod n) means n divides (a − b)

Modular arithmetic forms a ring Z/nZ with addition and multiplication.

The set of integers coprime to n forms the multiplicative group (Z/nZ)* of order φ(n).

Euler's Totient Function φ(n)

Counts integers in [1, n] coprime to n.

φ(p) = p − 1   (p prime)

φ(pq) = (p−1)(q−1)   (p,q distinct primes)

φ(p^k) = p^k − p^k−1

Fermat's Little Theorem

If p is prime and gcd(a, p) = 1:

a^p−1 ≡ 1 (mod p)

Euler's Theorem (generalization)

If gcd(a, n) = 1:

a^φ(n) ≡ 1 (mod n)

This is the mathematical foundation of RSA.

Chinese Remainder Theorem (CRT)

If gcd(m, n) = 1, then for any a, b there exists a unique x (mod mn) such that:

x ≡ a (mod m)   x ≡ b (mod n)

CRT enables a 4× speedup in RSA private key operations.

Prime Number Theorem: density of primes near N is ~1/ln(N)

For a 1024-bit prime: ~1 in 710 random odd numbers is prime.

Generation: pick random odd n, test primality, increment by 2, repeat.

Miller-Rabin Primality Test

Probabilistic test based on Fermat's Little Theorem:

Write n−1 = 2^s · d (d odd). For random witness a:

a^d ≡ 1 (mod n)   OR

a^2rd ≡ −1 (mod n) for some 0 ≤ r < s

Error probability: ≤ 4^−t for t rounds.

64 rounds → error < 2⁻¹²⁸

SAFE PRIME

p is a safe prime if p = 2q + 1 where q is also prime (a Sophie Germain prime).

Ensures (Z/pZ)* has a large prime-order subgroup → resists Pohlig-Hellman attack on DH.

STRONG PRIME

p is strong if: p − 1 has a large prime factor r, p + 1 has a large prime factor, and r − 1 has a large prime factor.

Historically required for RSA to resist Pollard's p−1 method, but modern key sizes make this less critical.

Industrial-Strength Generation

FIPS 186-5 specifies provable (Shawe-Taylor) and probable (Miller-Rabin) prime generation methods with required error bounds for each RSA key size.

SETUP Agree on public parameters: prime p and generator g of (Z/pZ)*

ALICE Choose secret a ∈ [2, p−2]

Compute and send A = g^a mod p

BOB Choose secret b ∈ [2, p−2]

Compute and send B = g^b mod p

SHARED SECRET

Alice computes: K = B^a mod p = g^ab mod p

Bob computes:  K = A^b mod p = g^ab mod p

Alice           Bob

secret a          secret b

————————————————————

A = g^a mod p ———→

      ←——— B = g^b mod p

————————————————————

K = g^ab mod p

Warning: Vanilla DH is vulnerable to man-in-the-middle attacks — no authentication of A or B. Must be combined with signatures or certificates.

Given g, p, h = g^x mod p, find x.

No polynomial-time algorithm is known for general groups. Security of DH, ElGamal, and DSA rests on DLP hardness.

CDH (Computational DH): Given g^a, g^b, compute g^ab

DDH (Decisional DH): Distinguish (g^a, g^b, g^ab) from (g^a, g^b, g^c)

DLP ≥ CDH ≥ DDH (in terms of hardness)

L_p[α, c] = exp(c · (ln p)^α · (ln ln p)^1−α)

Sub-exponential but super-polynomial for α ∈ (0,1).

RFC 3526 MODP groups (2003)

Standardized groups: 1536, 2048, 3072, 4096, 6144, 8192-bit primes. All are safe primes (p = 2q+1).

RFC 7919 Negotiated FFDHE (2016)

TLS extension for negotiating named DH groups. Prevents downgrade to weak custom groups.

Groups: ffdhe2048, ffdhe3072, ffdhe4096, ffdhe6144, ffdhe8192.

Generator Selection

Use generator g of a prime-order subgroup of order q where p = 2q+1. Typically g = 2 for safe primes.

Prevents small subgroup attacks.

Static DH

Long-term DH key pair. Same shared secret for repeated exchanges with same party.

No forward secrecy: compromise of long-term key reveals all past sessions.

Ephemeral DH (DHE)

Fresh random exponent per session. Shared secret is unique each time.

Provides forward secrecy: compromise of long-term signing key does NOT reveal past session keys.

FFDHE in TLS 1.3

TLS 1.3 supports FFDHE key exchange alongside ECDHE. Only named groups allowed (no custom parameters). All key exchanges are ephemeral — forward secrecy is mandatory.

STEP 1 Choose two large distinct primes p and q

Each ~n/2 bits for an n-bit RSA modulus. |p − q| should not be too small.

STEP 2 Compute n = p · q

n is the RSA modulus (public). Its bit length defines the key size (2048, 3072, 4096, ...).

STEP 3 Compute φ(n) = (p−1)(q−1)

Alternatively use Carmichael's function: λ(n) = lcm(p−1, q−1). Smaller exponents, same correctness.

STEP 4 Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1

Standard choice: e = 65537 = 2¹⁶ + 1 (Fermat prime F₄)

Only two 1-bits → fast modular exponentiation (17 squarings + 1 multiply).

STEP 5 Compute d = e⁻¹ mod φ(n)

Via the Extended Euclidean Algorithm. d is the private exponent.

Public Key: (n, e)

Published openly. Anyone can encrypt messages or verify signatures.

Private Key: d

Kept secret. Used to decrypt or sign.

In practice, store (p, q, d, d_p, d_q, q_inv) for CRT optimization.

Example (tiny)

p = 61, q = 53 → n = 3233

φ(n) = 60 × 52 = 3120

e = 17 → d = 2753

17 × 2753 = 46801 = 15 × 3120 + 1 ✓

Encrypt (with public key):

c = m^e mod n

Message m must satisfy 0 ≤ m < n.

Decrypt (with private key):

m = c^d mod n

Why It Works

By Euler's theorem: m^ed ≡ m^{1 + kφ(n)} ≡ m · (m^φ(n))^k ≡ m · 1^k ≡ m (mod n)

This holds whenever gcd(m, n) = 1. For m = 0 or m divisible by p or q, correctness follows from CRT.

Deterministic: Same plaintext always produces same ciphertext. Attacker can build a dictionary.

Malleable: Given Enc(m₁) and Enc(m₂), attacker can compute Enc(m₁ · m₂) without decrypting:

m₁^e · m₂^e = (m₁m₂)^e mod n

No semantic security: Attacker can test whether a ciphertext corresponds to a guessed plaintext by re-encrypting the guess.

Sign (with private key):

s = m^d mod n

Only the holder of d can produce s.

Verify (with public key):

m' = s^e mod n

Accept if m' equals the original message (or its hash).

Hash-then-Sign Paradigm

Never sign the raw message directly.

1. Compute h = Hash(message)

2. Sign the hash: s = h^d mod n

Reasons: hash has fixed size (fits in one RSA block), prevents existential forgery on raw RSA.

Unforgeability: Without d, an attacker cannot produce a valid signature on a new message (under the RSA assumption).

Non-repudiation: Only the private key holder could have signed. Unlike MACs, a third party can verify without the signing key.

Textbook RSA Signature Attacks

Existential forgery: Choose arbitrary s, compute m = s^e mod n. This (m, s) is a valid pair!

Blinding attack: Get victim to sign m' = m · r^e, then s/r is signature on m.

Both attacks are prevented by hash-then-sign + proper padding (PSS).

RSA-PSS (Probabilistic Signature Scheme): randomized padding that achieves EUF-CMA security in the random oracle model.

PKCS#1 v1.5 (1993)

Format: 0x00 || 0x02 || [random padding] || 0x00 || [message]

Bleichenbacher's attack (1998): adaptive chosen-ciphertext attack. ~1 million queries to decrypt by exploiting padding validity oracle.

ROBOT attack (2017) showed this was still exploitable in practice across major TLS implementations.

RSA-OAEP (1994/2001)

Optimal Asymmetric Encryption Padding (Bellare & Rogaway)

Two-round Feistel structure using hash functions G and H:

s = m ⊕ G(r),   t = r ⊕ H(s)

Encrypt: c = (s || t)^e mod n

Provably IND-CCA2 secure in the random oracle model.

PKCS#1 v1.5 Signatures

Format: 0x00 || 0x01 || [0xFF padding] || 0x00 || [DigestInfo]

Bleichenbacher (2006) / BERserk: parsing vulnerabilities in implementations that don't check padding strictly. Allowed signature forgery.

Still widely used (TLS 1.2 and earlier) but being phased out.

RSA-PSS (1996/2003)

Probabilistic Signature Scheme

Randomized via a salt value. Uses MGF (mask generation function) based on hash.

Provably EUF-CMA secure in the random oracle model.

Mandatory in TLS 1.3 for RSA signatures.

GNFS (General Number Field Sieve) is the fastest known algorithm for factoring general integers > ~100 digits.

RSA-768 (768-bit, 232 digits) — factored 2009

~2,000 CPU-years equivalent. Lenstra et al.

RSA-250 (829-bit, 250 digits) — factored 2020

~2,700 CPU-years. Boudot, Gaudry, Guillevic, Heninger, Thomé, Zimmermann.

RSA-1024 is within reach of nation-state adversaries (estimated ~10⁸ CPU-years with current methods).

Square-and-Multiply

Compute m^e mod n by scanning bits of e:

result = 1

for bit in e (MSB to LSB):

  result = result² mod n

  if bit == 1: result = result · m mod n

For a k-bit exponent: k squarings + ~k/2 multiplies on average.

Montgomery Multiplication

Replaces expensive division (mod n) with shifts and additions by working in Montgomery form: ˜a = a · R mod n, where R = 2^k.

MontMul(˜a, ˜b) = ˜a · ˜b · R⁻¹ mod n

Reduction uses only additions and right-shifts — no trial division.

The standard method in all serious RSA implementations.

Instead of computing m = c^d mod n directly:

m_p = c^{d mod (p−1)} mod p

m_q = c^{d mod (q−1)} mod q

m = CRT(m_p, m_q)

~4× speedup: two half-size exponentiations are 4× faster than one full-size.

This is why PKCS#8 RSA private keys store p, q, d_p, d_q, q_inv.

Multi-Prime RSA

Use n = p₁ · p₂ · ... · p_r (r ≥ 3 primes).

CRT gives r²× speedup for r primes.

3 primes: ~9× faster than single modular exponentiation.

Caution: each prime is smaller → easier to factor individually. Need larger n to compensate.

Choose prime p, generator g of (Z/pZ)*.

Choose secret x ∈ [1, p−2].

Compute h = g^x mod p.

Public key: (p, g, h)   Private key: x

To encrypt message m ∈ (Z/pZ)*:

Choose random k ∈ [1, p−2].

c₁ = g^k mod p

c₂ = m · h^k mod p

Ciphertext: (c₁, c₂)

Note: ciphertext is 2× the size of plaintext (message expansion).

Compute shared secret: s = c₁^x mod p

Recover message: m = c₂ · s⁻¹ mod p

Works because s = g^kx = h^k, so c₂ · s⁻¹ = m · h^k · h^−k = m.

ElGamal is essentially DH key exchange followed by one-time-pad encryption.

The ephemeral key k creates a DH shared secret h^k = g^xk which masks the message.

Security reduces to the DDH assumption (stronger than CDH).

Properties

Semantically secure (IND-CPA) due to randomization via k.

Homomorphic: Enc(m₁) · Enc(m₂) = Enc(m₁ · m₂)

Used in voting protocols, mix-nets, threshold cryptography.

Speed: RSA-2048 encrypt is ~1,000× slower than AES-128-GCM per byte.

Message size: RSA can only encrypt messages < n (256 bytes for RSA-2048 minus padding overhead).

Expansion: ElGamal doubles ciphertext size.

KEM/DEM Paradigm

KEM (Key Encapsulation Mechanism): Use public-key crypto to establish a shared symmetric key.

DEM (Data Encapsulation Mechanism): Use the symmetric key with a fast cipher (AES-GCM) for bulk data.

Clean separation with provable security composition.

1. Choose random r ∈ [0, n). Compute c = r^e mod n.

2. Derive symmetric key: K = KDF(r)

3. Encrypt data with AES-GCM using K.

4. Send (c, AES-GCM ciphertext).

Simpler and more efficient than RSA-OAEP for key transport. Standardized in ISO 18033-2.

HPKE (RFC 9180)

Hybrid Public Key Encryption — modern framework combining:

KEM (DHKEM with X25519/P-256) + KDF (HKDF) + AEAD (AES-GCM/ChaCha20-Poly1305)

Used in: TLS Encrypted ClientHello (ECH), MLS messaging protocol, OHTTP.

WIENER (1990)

If d < n^0.25/3, continued fraction expansion of e/n recovers d efficiently.

Exploits small private exponent.

Boneh-Durfee (1999) extended to d < n^0.292 using lattice methods.

COPPERSMITH (1996)

Uses LLL lattice reduction to find small roots of polynomials mod n.

Applications: small e with small message padding, partial key exposure (knowing ~half of d suffices to recover the rest), stereotyped messages.

HÅSTAD BROADCAST

If same message m is encrypted with e = 3 to 3 different recipients (different n_i), CRT + cube root recovers m.

Prevented by proper padding (OAEP).

TIMING (Kocher, 1996)

Square-and-multiply branches on key bits. Measuring execution time reveals the private exponent d.

Countermeasure: constant-time implementation, RSA blinding.

FAULT ON CRT-RSA

Boneh-DeMillo-Lipton (1997): A single fault during CRT computation leaks p or q.

If fault in m_p but not m_q: gcd(s_faulty^e − m, n) = q.

Devastating: one faulty signature breaks the key.

Countermeasure: verify signature before output.

COMMON MODULUS

If two users share the same n with different e₁, e₂ where gcd(e₁, e₂) = 1, an attacker with both ciphertexts can decrypt using the extended Euclidean algorithm.

MAN-IN-THE-MIDDLE

Mallory intercepts Alice's A and Bob's B, substitutes her own values. Establishes separate shared secrets with each party.

Vanilla DH provides NO authentication.

Fix: authenticate key exchange with digital signatures (STS protocol, TLS handshake).

SMALL SUBGROUP

If the group order has small prime factors, attacker sends elements of small subgroups. Victim's shared secret leaks information about the private exponent modulo small primes.

Fix: use safe primes (p = 2q+1) or validate received elements (check g^q = 1 in prime-order subgroup).

LOGJAM (2015)

Precomputation attack on 512-bit DH (export-grade):

NFS precomputation for a fixed prime takes ~1 week. After that, individual DLPs take ~90 seconds.

A single 1024-bit prime used by most of the internet could be targeted by a nation-state with ~$100M in custom hardware (est.).

Fix: use ≥ 2048-bit groups, prefer ECDH.

PRECOMPUTATION DANGER

Many servers used the same DH primes (e.g., Apache's hardcoded 1024-bit prime). Precomputation against that prime breaks ALL connections using it.

Snowden documents suggest NSA may have performed such precomputation.

INVALID GROUP

Attacker sends a value from a different (weaker) group. If not validated, victim computes in the wrong group.

Fix: validate received public keys are in the expected group.

A certificate binds a public key to an identity (domain name, organization), signed by a trusted Certificate Authority (CA).

Key fields: subject, issuer, validity period, public key, extensions (SAN, key usage), CA signature.

Certificate Chains

Root CA (self-signed, in trust store)
 ↓ signs
Intermediate CA
 ↓ signs
End-entity certificate (your server)

Root CAs are pre-installed in browsers/OSes (~150 trusted roots).

Revocation

CRL (Certificate Revocation List): CA publishes list of revoked serial numbers. Scalability issues.

OCSP (Online Certificate Status Protocol): Real-time check. Privacy concern (CA learns which sites you visit).

OCSP Stapling: Server fetches its own OCSP response and staples it to the TLS handshake.

HIERARCHICAL PKI

Used by TLS/SSL (WebPKI). Top-down trust from root CAs.

Scalable, well-understood, legally binding.

Single point of failure: compromised CA can issue rogue certificates (DigiNotar 2011, Symantec 2015).

WEB OF TRUST

Used by PGP/GPG. Decentralized: users sign each other's keys.

Trust is transitive and user-defined. No central authority.

Difficult to bootstrap, poor UX, key management burden on users.

CERTIFICATE TRANSPARENCY

Append-only public log of all issued certificates (RFC 6962).

Domain owners monitor logs to detect misissued certs.

Required by Chrome since 2018 for all new certificates.

The ratio grows because RSA relies on sub-exponential factoring (L[1/3]) while ECC relies on exponential ECDLP (Pollard's rho: O(√n)).

RSA advantage: Verification is extremely fast (e = 65537 has only 17 squarings). Ideal when verification is done far more often than signing (certificate validation, firmware signatures).

Perfect Forward Secrecy (PFS): Compromise of long-term private keys does not compromise past session keys.

Even if an attacker records all ciphertext and later obtains the server's private key, they cannot decrypt historical traffic.

Why It Matters

Without FS (RSA key transport): Server's RSA private key decrypts the pre-master secret from any recorded session.

Mass surveillance: "record now, decrypt later" is a realistic threat.

With FS: Each session uses unique ephemeral keys. Breaking one session does not help with any other.

DHE Ephemeral Diffie-Hellman

Fresh DH exponents per session. Long-term key only used for signing the ephemeral public values.

ECDHE Ephemeral Elliptic Curve DH

Same concept on elliptic curves. Faster, smaller keys.

The dominant key exchange in modern TLS.

TLS 1.3 Mandates Forward Secrecy

RSA key transport (non-FS) was removed entirely from TLS 1.3.

Only (EC)DHE key exchange is allowed.

Cipher suites: TLS_AES_128_GCM_SHA256, TLS_AES_256_GCM_SHA384, TLS_CHACHA20_POLY1305_SHA256.

Factoring: Shor's algorithm factors n-bit integers in O(n³) quantum time using O(n) logical qubits.

RSA-2048 can be broken in hours on a sufficiently large fault-tolerant quantum computer.

Discrete Log: Shor also solves DLP in polynomial time.

Breaks DH, ECDH, ElGamal, DSA, and ECDSA.

Qubit Estimates (Logical Qubits)

RSA-2048:   ~4,100 logical qubits

RSA-3072:   ~6,200 logical qubits

ECC P-256:   ~2,330 logical qubits

With current error rates, physical qubit overhead is ~1,000×–10,000×.

Recent work by Gidney & Ekerå (2021): RSA-2048 in ~8 hours with 20M physical qubits.

NIST PQC STANDARDS

ML-KEM (FIPS 203) — lattice-based KEM (ex-CRYSTALS-Kyber)

ML-DSA (FIPS 204) — lattice-based signatures (ex-CRYSTALS-Dilithium)

SLH-DSA (FIPS 205) — hash-based signatures (ex-SPHINCS+)

Finalized August 2024.

Harvest Now, Decrypt Later

Adversaries recording encrypted traffic today can decrypt it once quantum computers arrive. Long-lived secrets (government, healthcare, financial) are already at risk.

CNSA 2.0 Timeline (NSA)

2025: begin transition to PQC

2030: PQC for all new systems

2033: exclusive PQC for web browsers/servers

2035: exclusive PQC for all NSS

Radix-2 Montgomery: Process one bit per clock cycle. Area-efficient but slow (k cycles for k-bit modulus).

High-Radix (2^w): Process w bits per cycle. k/w cycles but needs w-bit multiplier. Common: w = 16 or 32.

Systolic Array: Pipeline multiple word-level multiplications. Throughput of one Montgomery multiplication per cycle after pipeline fills.

FPGA & ASIC

RSA-2048 on Virtex-7: ~0.3ms per modular exponentiation (CRT)

RSA-2048 on 28nm ASIC: ~0.05ms per operation

Throughput limited by modular exponentiation: O(k²) multiplications for k-bit modulus.

With CRT, two independent half-size exponentiations can run in parallel on dual Montgomery cores.

Combined CRT + dual-core: ~8× speedup over single full-width exponentiation.

RSA BLINDING

Before decryption: multiply c by r^e for random r.

After: divide result by r.

Attacker's timing/power observations are decorrelated from the actual c and d.

CONSTANT-TIME

Always perform both square and multiply (discard multiply result when bit = 0). No branching on secret bits.

Montgomery ladder: another constant-time approach for modular exponentiation.

Input Primes:

Click "Compute" to see results...