05 — Asymmetric (Public-Key) Cryptography

Key pair (public, private). The foundation of nearly every modern protocol: TLS, SSH, S/MIME, PGP, Signal, cryptocurrencies. Slower than symmetric — which is why TLS goes hybrid: asymmetric exchanges the key, symmetric encrypts the data.

1. Underlying mathematical problems

All classical public-key cryptography is based on a hard problem:

All the classical ones (IFP, DLP, ECDLP) break under Shor (quantum computer).

2. Diffie-Hellman Key Exchange (1976)

Whitfield Diffie + Martin Hellman, New Directions in Cryptography (IEEE Trans. Info Theory, 1976). Credit also goes to Ralph Merkle (Merkle's Puzzles, 1974) and CocksWilliamsonEllis at GCHQ (1969–1974, classified).

Protocol

Public setup: group \(\mathbb{Z}_p^*\) of prime order \(q\), generator \(g\).

1. Alice: \(a \stackrel{\\)}{leftarrow} {1, ..., q-1}\(, sends \)A = g^a$.
2. Bob: \(b \stackrel{\\)}{leftarrow} {1, ..., q-1}\(, sends \)B = g^b$.
3. Alice computes \(K = B^a = g^{ab}\).
4. Bob computes \(K = A^b = g^{ab}\).

An eavesdropper sees \(g^a, g^b\); they must solve CDH.

Variants

• Static DH: long-term keys. No forward secrecy.
• Ephemeral DH (DHE): keys used once. Forward secrecy.
• Static-Ephemeral: one side static (server cert), the other ephemeral.

Standardized groups (RFC 7919, 3526)

Attacks

• Man-in-the-middle: DH does not authenticate. Always combine with a signature or prior authentication.
• Small subgroup confinement: validate \(B^q \equiv 1 \mod p\) (or use safe primes).
• Logjam (2015): precomputation against common DH-1024 primes; feasible for a state actor.
• Triple Handshake (TLS): cross-protocol attack — mitigated in TLS 1.3.

ECDH

Same structure on an elliptic curve: \(A = aG\), \(B = bG\), shared \(= aB = bA = abG\).

3. RSA (1977)

Ron Rivest + Adi Shamir + Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (CACM 1978, MIT/LCS Tech Memo 82, 1977).

Previously discovered by Clifford Cocks at GCHQ (1973, classified until 1997).

Setup

1. Choose large secret primes \(p, q\).
2. \(N = pq\) (public modulus).
3. \(\varphi(N) = (p-1)(q-1)\) (Euler totient).
4. Choose \(e\) such that \(\gcd(e, \varphi(N)) = 1\) (typically \(e = 65537 = 2^{16} + 1\)).
5. \(d = e^{-1} \mod \varphi(N)\) (private key).

Public key: \((N, e)\). Private key: \(d\) (or \(p, q\)).

Encryption (textbook RSA — ❌ NEVER use raw)

\(C = M^e \mod N\), \(M = C^d \mod N\).

Why it is insecure:

• Deterministic (same \(M\) → same \(C\)): leaks patterns.
• Malleable: \(C_1 \cdot C_2 \mod N = (M_1 M_2)^e\).
• Small \(M\) + small \(e\): \(C = M^e\) without mod (if \(M^e < N\)) — \(e\)-th root.
• Coppersmith attacks with small, partially known messages.

Secure padding

OAEP (Optimal Asymmetric Encryption Padding) — Bellare + Rogaway 1994.

PKCS#1 v1.5 padding — old, vulnerable to Bleichenbacher 1998 (padding oracle).

RSA-PSS for signatures

PSS (Probabilistic Signature Scheme) — Bellare + Rogaway 1996. A secure replacement for PKCS#1 v1.5 signing.

Status: PKCS#1 v1.5 signing is still widely used (X.509 certs!). Susceptible to Bleichenbacher-style attacks but with mitigation; PSS is more secure but adoption is slow.

Key generation

• \(p, q\) must be distinct, both prime, with \(|p - q|\) not too small (Fermat factoring), and adequate entropy.
• \(|N| \in \{2048, 3072, 4096\}\).
• ROCA (CVE-2017-15361, Infineon): faulty generation in millions of smartcardTPMEstonian eID keys. Breakable by a specific Coppersmith algorithm.
• Mining your Ps and Qs (Heninger et al. 2012): SSH/SSL keys with primes shared due to entropy starvation at boot.

Speed

RSA is slow: 2048-bit signing ~1ms; encryption ~50µs (small \(e\)). Even slower at 4096. Slower than ECC at the same security level.

Equivalent sizes

2026 recommendation: 3072 minimum; 4096 on legacy systems where ECC is unavailable. Migration to PQC in 2025–2030.

4. ElGamal (1984)

Taher ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (IEEE Trans. Info Theory 1985).

Encryption

Setup: \(\mathbb{Z}_p^*\), \(g\), private key \(x\), public \(y = g^x\).

1. The sender chooses random \(k\), sends \((c_1, c_2) = (g^k, m \cdot y^k)\).
2. The receiver: \(m = c_2 / c_1^x\).

IND-CPA secure under DDH.

Signing

Standardized as a variant: DSA (Digital Signature Algorithm, FIPS 186, 1991).

ElGamal encryption is rarely used directly; the ElGamal signature evolved into DSA → ECDSA → EdDSA.

5. DSA / ECDSA / EdDSA

DSA (FIPS 186, 1991)

Modular, based on DLP in \(\mathbb{Z}_p^*\).

Signing a message \(m\) with private key \(x\):

1. \(k \stackrel{\\)}{leftarrow} {1, ..., q-1}$ (ephemeral nonce).
2. \(r = (g^k \mod p) \mod q\).
3. \(s = k^{-1}(H(m) + xr) \mod q\).
4. Signature: \((r, s)\).

Verify: \(w = s^{-1}\), \(u_1 = H(m) w\), \(u_2 = rw\), check \((g^{u_1} y^{u_2} \mod p) \mod q = r\).

ECDSA (1992 Vanstone, FIPS 186-3 standard in 2009)

The elliptic-curve version. Standard in Bitcoin (secp256k1), TLS (P-256384521), SSH.

Nonce \(k\) is critical: if \(k\) is repeated or predictable, the private key is extractable from 2 signatures (solve a linear system). Famous incidents:

• PS3 (Sony, 2010): constant nonce → master key leaked by the fail0verflow group.
• Bitcoin wallets with broken RNG: drained.

Mitigation: RFC 6979 — deterministic nonces via HMAC. The modern standard.

EdDSA (Bernstein 2011, RFC 8032)

Schnorr-style + Curve25519 (Ed25519) or Curve448 (Ed448). Deterministic without RFC 6979 (nonce derived from a hash of key + msg). Constant-time. No special points. No encoding ambiguity.

Ed25519:

• 32-byte public key.
• 64-byte signature.
• ~128-bit security.
• ~70k signs/sec per modern core.
• ~25k verifies/sec.
• Batch verification available (10× speedup).

Ed448: 56-byte pubkey, ~224-bit security. Slower.

Status: Ed25519 is the recommended standard for any new signing. OpenSSH default since 2020. RFC 8032.

Schnorr signatures

Claus Schnorr, 1989. Simpler than ECDSA, with a cleaner security proof in the ROM. Patented until 2008. Bitcoin adopted it via Taproot (BIP340, activated Nov 2021) — Schnorr signatures + MuSig (aggregation).

BLS signatures (Boneh-Lynn-Shacham, 2001)

Pairing-based on elliptic curves with a pairing (BLS12-381, BN curves). Aggregatable signatures — 1000 signatures → 1 short signature. Used in Ethereum 2.0 consensus, dfinity, Filecoin, threshold signing.

• Signature: 48 bytes (BLS12-381 G1).
• Public key: 96 bytes (G2).
• Aggregation: \(\sigma = \prod \sigma_i\).
• Aggregated verification: 1 pairing per signer.

6. ECC (Elliptic Curve Cryptography)

Proposed independently by Neal Koblitz (1985, Elliptic Curve Cryptosystems, Math. Comp.) and Victor Miller (1985, CRYPTO).

Short Weierstrass elliptic curve

with \(4a^3 + 27b^2 \not\equiv 0 \mod p\) (non-singular).

Points form an abelian group under geometric addition (with \(O\) = point at infinity). Order \(\#E(\mathbb{F}_p) = p + 1 - t\) where \(|t| \leq 2\sqrt{p}\) (Hasse).

ECDLP

Given \(P, Q = kP\), recover \(k\). No subexponential algorithm like GNFS for IFP — hence ECC with a much smaller key than RSA.

Standardized curves

NIST (FIPS 186, SEC 2)

Controversy: the NIST curve seeds were generated by hashing a non-public string (Jerry Solinas). A backdoor is suspected — no evidence, but it reduces confidence. The P-* curves have implementation quirks (non-Edwards, branches, special points).

Bernstein curves

• Curve25519 (\(y^2 = x^3 + 486662 x^2 + x\) mod \(2^{255} - 19\), Montgomery form) — X25519 ECDH (RFC 7748). ~128-bit. Fast, simple, easy constant-time.
• Curve448 (\(2^{448} - 2^{224} - 1\)) — X448 ECDH. ~224-bit.
• Ed25519 — Edwards form of the same curve for signing.
• Ed448 — likewise for Curve448.

Advantages:

• Public constants, deterministic, transparent generation.
• Twist-secure: twist points have a secure order (no leak).
• Constant-time scalar multiplication trivially implementable.
• Small cofactor (8) — no "weak" keys.

Brainpool (Germany, RFC 5639)

brainpoolP256r1, P384r1, P512r1 — a NIST-paranoid European alternative. Seeds derived from \(\pi, e\).

Bitcoin

secp256k1 — a curve with no visible random characteristics, faster than P-256 for some operations. Non-NIST. Adopted by Bitcoin, Ethereum.

Pairing-friendly

BLS12-381, BN254, BN382, BLS12-377 — curves with an efficient pairing for BLS, zk-SNARKs (Groth16, PLONK, Halo). Adopted in Ethereum, Zcash, Filecoin.

SM2 (China GM/T 0003)

The sm2p256v1 curve (256 bit), with its own parameters. Mandatory in Chinese systems.

7. Public-key-based encryption schemes

RSA-OAEP

The modern standard for RSA encryption. Bellare-Rogaway 1994. RFC 8017.

ECIES (Elliptic Curve Integrated Encryption Scheme)

Hybrid: generates an ECDH shared secret with the recipient's public key, derives a symmetric key, encrypts with AEAD.

ephemeral_priv = random
ephemeral_pub = ephemeral_priv * G
shared = ECDH(ephemeral_priv, recipient_pub)
key = KDF(shared)
ciphertext, tag = AEAD(key, plaintext)
send (ephemeral_pub, ciphertext, tag)

ISO/IEC 18033-2, SEC 1. Variants: ECIES, ECIES-KEM, ChaCha20-Poly1305-Curve25519 (libsodium crypto_box_seal).

HPKE — Hybrid Public Key Encryption (RFC 9180, 2022)

A modern IETF standardization of the ECIES style. Supports multiple modes (base, PSK, auth, auth-PSK). Used in ECH (Encrypted Client Hello, TLS), MLS.

8. Identity-Based Encryption (IBE)

Concept proposed by Shamir 1984; first practical implementation Boneh-Franklin 2001 with pairings.

Public key = a string (email, phone). No traditional PKI required. Key escrow: a TA (Trust Authority) generates private keys — it must be trusted.

Uses: email encryption, healthcare EHR. Little mainstream adoption; DID-based alternatives (decentralized identifiers) are growing.

9. Threshold cryptography

A key \(sk\) split among \(n\) parties; \(t\) parties can sign/decrypt; \(< t\) cannot.

Shamir Secret Sharing (1979)

A polynomial \(f(x)\) of degree \(t-1\) with \(f(0) = sk\). Each party receives \((i, f(i))\). Lagrange interpolation reconstructs.

Information-theoretically secure (each party alone = zero info).

Threshold signatures

• Threshold RSA: Shoup 2000.
• Threshold Schnorr: Stinson-Strobl 2001, FROST (Komlo + Goldberg 2020).
• Threshold BLS: trivial thanks to linearity.
• Threshold ECDSA: much harder (Gennaro-Goldfeder, Lindell — used in enterprise MPC wallets).

Applications

• Distributed HSMs.
• Custodial crypto wallets (BitGo, Fireblocks, Coinbase Prime use threshold ECDSA).
• DKG (Distributed Key Generation) without a trusted dealer.

10. Practical comparison — what to use in 2026?

11. Comparative performance (cycles, modern 2026 CPU)

ECC is ~10–100× faster than RSA at equivalent security. PQC is competitive in modern performance (not trivial — Kyber is faster than ECDH on CPUs without ECC acceleration).

12. Side-channel concerns

• Constant-time scalar mult: implement as a Montgomery ladder; never branch on a key bit.
• Table lookup leaks: precomputed tables leak via cache.
• Branchless conditional swap: mask = -bit; a ^= mask & (a ^ b).
• Validate untrusted points: ECDH with an invalid point can reveal the key (invalid curve attack).
• Power analysis on smartcards: well-known, mitigated by blinding/dummy operations.

13. Bibliography

• Hankerson, Menezes, Vanstone, Guide to Elliptic Curve Cryptography, Springer 2004.
• Silverman, The Arithmetic of Elliptic Curves, Springer 1986 (math).
• Bernstein papers on Curve25519, Ed25519, qhasm.
• Bernstein + Lange, SafeCurves (safecurves.cr.yp.to) — a checklist for choosing a curve.
• RFC 8032 EdDSA, RFC 7748 X25519, RFC 8446 TLS 1.3, RFC 9180 HPKE.
• FIPS 186-5 Digital Signature Standard.

14. Cross-reference

• Attacks: 11-attacks.md (Bleichenbacher, ROCA, invalid curve, twist, Coppersmith).
• Protocols that use them: 07-protocols.md (TLS, SSH, Signal, IKE, OPAQUE).
• PQC successors: 08-post-quantum.md (ML-KEM, ML-DSA, SLH-DSA).
• People: 12-people.md (Diffie, Hellman, Rivest, Shamir, Adleman, Merkle, Koblitz, Miller, Bernstein, Boneh).