§ Trackr.Live

Public-Key Cryptography

Public-key cryptography is the branch of cryptography that lets two parties establish a confidential and authenticated channel without having previously shared a secret. That sentence is the entire reason the discipline exists. Symmetric cryptography is faster, simpler, and older — but it cannot solve the bootstrap problem of how two parties who have never communicated agree on a shared key. Public-key cryptography solves that problem, and once it is solved, the rest of the protocol typically falls back to symmetric primitives for the bulk work.

This page is the deep-dive companion to the Cryptography umbrella overview. The scope here is the asymmetric primitives themselves — RSA, Diffie-Hellman, elliptic curves — and the failure patterns that have repeatedly broken them in deployment. PKI, certificates, and trust frameworks are large enough subjects to get their own page.

The shape of the problem

A public-key system uses a key pair: a public key that can be freely distributed, and a private key that is held secret by its owner. The two keys are mathematically linked such that operations performed with one can only be undone with the other. The asymmetry is the entire trick.

Two distinct operations exist in this model:

Encryption / decryption. A sender encrypts a message with the recipient’s public key; only the holder of the matching private key can decrypt it.
Signing / verification. A signer produces a signature using their private key; anyone with the matching public key can verify that the signature was produced by the holder of that private key over that specific message.

These are different operations with different security properties, and the same key pair should generally not be used for both. The mathematical structures supporting them are related but distinct, and a key compromise in one role has different downstream consequences than in the other.

The third major operation worth knowing is key agreement (or key exchange), in which two parties each holding their own key pair derive a shared symmetric secret that neither party could have computed alone. Diffie-Hellman is the canonical example. Key agreement is the workhorse use case in modern protocols — TLS, SSH, Signal, IPsec all use public-key key agreement to bootstrap a symmetric session key.

The performance reality is sharp: public-key operations are typically two to three orders of magnitude slower than symmetric operations on the same hardware. RSA-2048 signing on a modern CPU runs at a few thousand operations per second, against AES-GCM throughput measured in gigabytes per second. This is why almost every real protocol uses public-key cryptography only for the initial handshake — to authenticate the parties and to agree on a symmetric key — and then switches to symmetric cryptography for the bulk data. The pattern is called hybrid cryptography, and it is universal in deployed systems.

The mathematical foundations

Public-key cryptography rests on trapdoor functions: mathematical operations that are easy to compute in one direction but hard to invert without secret knowledge. Three problems have provided the dominant trapdoors for the last fifty years.

Integer factoring underlies RSA. Multiplying two large primes is easy; factoring the product back into its primes is computationally infeasible at sufficient size. The classical algorithms for factoring (general number field sieve being the best known) are subexponential in the input size, which is why RSA key sizes have grown over time as factoring techniques and computational power have advanced.

Discrete logarithm in finite fields underlies classical Diffie-Hellman and DSA. Given a generator g and a value h in a finite cyclic group, finding the exponent x such that g^x = h is computationally infeasible at appropriate group sizes. The structure is similar to factoring in difficulty profile — subexponential classical algorithms exist, which is why finite-field DH parameters have also grown over time.

Discrete logarithm on elliptic curves underlies modern elliptic curve cryptography. The problem has the same structural shape as discrete log in finite fields, but no subexponential classical algorithm is known. This is the reason elliptic curve cryptography achieves equivalent security to RSA and finite-field DH at dramatically smaller key sizes: a 256-bit elliptic curve key provides roughly the same classical security as a 3072-bit RSA key.

All three trapdoor problems share a common weakness: Shor’s algorithm, published in 1994, solves all of them efficiently on a sufficiently large quantum computer. This is the core of the post-quantum cryptography problem, addressed at the end of this page.

RSA

The Rivest-Shamir-Adleman algorithm, published in 1977, was the first public-key cryptosystem to see widespread deployment and remains the most-deployed asymmetric primitive in 2026, though its share is declining as elliptic curve systems take over new deployments.

The math, in one sentence: pick two large primes p and q, compute n = p × q, find an encryption exponent e and a decryption exponent d such that (m^e)^d ≡ m (mod n), publish (n, e) as the public key, keep d as the private key. The trapdoor is that recovering d requires knowing the factorization of n, which is hard if n is large enough.

Key sizes

RSA key sizes have grown steadily as factoring techniques have improved and computational resources have grown cheaper.

RSA-512 was broken in practice in 1999.
RSA-768 was broken in 2010 by a coordinated factoring effort.
RSA-1024 is no longer considered secure for any sensitive use as of the mid-2010s, though it persists in legacy systems.
RSA-2048 is the current minimum for new deployments and remains the most common deployed size.
RSA-3072 is the NIST-recommended size for long-term security and is required by Commercial National Security Algorithm Suite 2.0 for classified systems pending the post-quantum transition.
RSA-4096 is sometimes used for high-value keys (root CAs, code signing) where the performance cost is acceptable in exchange for additional security margin.

The performance cost of RSA grows worse than linearly with key size — RSA-4096 operations are roughly 5-8 times slower than RSA-2048 operations on the same hardware. This is one of the reasons elliptic curve cryptography has displaced RSA in many new applications.

Padding — the part that has caused all the trouble

Raw RSA — encrypting a message m directly as m^e mod n — is not secure. It is deterministic (the same message always encrypts to the same ciphertext), it leaks structural information about the plaintext, and it is vulnerable to a handful of mathematical attacks that exploit the algebraic structure. Real RSA encryption always uses a padding scheme that adds randomness and structure before the modular exponentiation.

Two padding schemes are widely deployed.

PKCS#1 v1.5 padding is the older scheme, published in 1993. It is also the scheme that has produced an unbroken twenty-five-year history of attacks. The Bleichenbacher attack, published in 1998, was the first practical demonstration: by submitting carefully constructed ciphertexts to an RSA decryption oracle that revealed whether the padding was valid, an attacker could recover the plaintext byte by byte. Variants of the attack — ROBOT in 2017, Marvin in 2023, and others — have repeatedly broken TLS servers and HSMs that still negotiate RSA key exchange with PKCS#1 v1.5 padding. The structural problem is that the padding format is constrained enough that an oracle can distinguish valid from invalid padding, and that information is enough to recover the message. PKCS#1 v1.5 for encryption should not appear in new systems.

OAEP (Optimal Asymmetric Encryption Padding), standardized in PKCS#1 v2.0 in 1998, replaces the v1.5 padding with a structure derived from random oracles. OAEP is provably secure under reasonable assumptions and resists the Bleichenbacher class of attacks. It is the correct choice for RSA encryption in new systems.

For RSA signing, the parallel scheme is PSS (Probabilistic Signature Scheme), also from PKCS#1 v2.0. PSS replaces the older PKCS#1 v1.5 signature padding with a probabilistic scheme that has stronger security proofs. New RSA signing should use PSS.

The structural lesson from twenty-five years of padding-attack incidents: the RSA primitive itself is sound, the padding is where the practical security lives, and the temptation to use the older simpler padding because “the new one is more complicated” is the temptation to ship a system that will be broken by an attacker reading the original Bleichenbacher paper.

Diffie-Hellman key exchange

The Diffie-Hellman algorithm, published in 1976, predates RSA by one year and was the first published public-key construction. The algorithm solves the key agreement problem: two parties exchange public values over an insecure channel and each independently compute the same shared secret.

The classical (finite-field) version, often written DH or FFDH:

Both parties agree publicly on a large prime p and a generator g of a subgroup of Z_p*.
Alice picks a random secret a, computes A = g^a mod p, sends A to Bob.
Bob picks a random secret b, computes B = g^b mod p, sends B to Alice.
Alice computes B^a = g^(ab) mod p. Bob computes A^b = g^(ab) mod p. The shared secret is g^(ab) mod p.

An eavesdropper sees A and B but cannot derive g^(ab) without solving the discrete logarithm problem in the group. This is the foundational construction of public-key cryptography and remains a building block of modern protocols, though almost always in its elliptic curve variant.

Static vs ephemeral DH

A subtle but important distinction:

Static Diffie-Hellman reuses the same key pair across many sessions. This is faster (the key pair is computed once) but has a critical weakness: if the static private key is later compromised, every historical session that used it can be retrospectively decrypted by an attacker who captured the traffic. This is the absence of forward secrecy.

Ephemeral Diffie-Hellman (DHE / ECDHE) generates a fresh key pair for every session. The session keys are derived from the ephemeral exchange, the ephemeral private keys are discarded after the session, and a compromise of any long-term key does not retroactively decrypt past sessions. Forward secrecy is the security property this provides, and modern protocols (TLS 1.3 mandates it) use ephemeral DH exclusively.

Parameter sizes and Logjam

Finite-field DH has the same scaling problem as RSA: key sizes have grown over time. The Logjam attack in 2015 demonstrated that 512-bit DH (still common in TLS export ciphersuites at the time) could be broken with modest computational resources, and that many TLS servers reused the same 1024-bit DH parameters with hundreds of others, making precomputation attacks economical against the shared parameters.

The fallout pushed deployments toward 2048-bit minimum for finite-field DH and accelerated the transition to elliptic curve Diffie-Hellman, where the same security level requires far smaller parameters and the precomputation attack vector does not apply.

Elliptic Curve Cryptography

Elliptic curve cryptography (ECC) provides the same operations as RSA and finite-field DH — encryption, signing, key agreement — but uses a different mathematical structure: points on an elliptic curve over a finite field. The discrete logarithm problem on a well-chosen elliptic curve is believed to be substantially harder than its finite-field counterpart, which means smaller keys provide equivalent security.

The practical impact:

Classical primitive	ECC equivalent	Security level
RSA-2048	256-bit curve	112-128 bits
RSA-3072	256-bit curve (P-256, Curve25519)	128 bits
RSA-7680	384-bit curve (P-384)	192 bits
RSA-15360	521-bit curve (P-521)	256 bits

Smaller keys mean smaller signatures, smaller certificates, faster operations, and lower power consumption. For mobile, embedded, and high-volume server applications, ECC is the default choice in 2026.

The curves that matter

Several specific elliptic curves dominate deployment.

NIST P-256 (also called secp256r1 or prime256v1) is the NIST-standardized 256-bit curve, used in TLS, code signing, smart cards, and most US federal cryptographic systems. It is the most widely deployed elliptic curve.

NIST P-384 (secp384r1) is the 384-bit variant used where higher security is required. Mandated by Commercial National Security Algorithm Suite for classified systems.

NIST P-521 (secp521r1) is the 521-bit variant for the highest-security applications. Less common than P-256 or P-384 because the marginal security gain rarely justifies the performance cost.

Curve25519 (and its associated function, X25519) is an alternative 256-bit curve designed by Daniel J. Bernstein in 2005. Designed specifically for ECDH key agreement, with strong resistance to implementation errors and side channels. Used in TLS 1.3 (preferred over NIST curves by many implementations), SSH, Signal, WireGuard, and most modern protocols.

Ed25519 is the signature counterpart to Curve25519, providing Edwards-curve Digital Signature Algorithm (EdDSA) signatures. Deployed in SSH, signed commits in Git, modern code-signing pipelines, and the Signal Protocol.

Curve448 (and Ed448) are higher-security alternatives to Curve25519/Ed25519, providing roughly 224 bits of security against classical adversaries. Less widely deployed but supported in TLS 1.3.

The choice between NIST curves and Curve25519-family curves has both technical and political dimensions. Technically, the Curve25519 family was designed after the NIST curves with the benefit of two decades of additional cryptanalytic understanding, and the resulting designs avoid several implementation pitfalls. Politically, the NIST curves have been the subject of long-standing concerns about whether the curve parameters were generated transparently. For new deployments outside of US federal contexts, Curve25519-family curves are increasingly preferred. Inside FIPS-validated environments, the NIST curves remain mandatory.

ECDH and ECDSA

ECDH is elliptic curve Diffie-Hellman: the same key agreement algorithm as classical DH, just performed on an elliptic curve instead of in a finite field. Almost always deployed as ephemeral ECDHE for forward secrecy.

ECDSA is the elliptic curve variant of the Digital Signature Algorithm. ECDSA signatures are widely deployed in TLS certificates, code signing, and blockchain systems (Bitcoin uses ECDSA over secp256k1).

ECDSA has one infamous failure mode: nonce reuse. The ECDSA signature algorithm requires a per-signature random value (k); reusing the same k for two different messages allows the private key to be recovered algebraically. The most famous instance was the Sony PlayStation 3 incident in 2010, where Sony’s signing implementation used a constant value for k across all signatures, allowing the firmware signing key to be recovered. The same failure has appeared in Bitcoin wallets, Java’s cryptographic libraries (CVE-2022-21449), and various other systems. The modern mitigation is deterministic ECDSA (RFC 6979), which derives k from a hash of the message and private key, eliminating the dependency on a working random number generator.

EdDSA (specifically Ed25519 and Ed448) eliminates the nonce-reuse failure mode by design. EdDSA derives the per-signature randomness from the message itself, making it deterministic. EdDSA signatures are smaller, faster, and harder to misimplement than ECDSA signatures. For new deployments, EdDSA is preferred wherever the deployment context allows.

How public-key cryptography fails

Like symmetric cryptography, the primitive choice is rarely the failure mode in real incidents. The recurring patterns:

Weak random number generators. Almost every public-key operation depends on high-quality randomness — for key generation, for nonces in ECDSA, for OAEP padding in RSA. A weak RNG produces predictable keys or predictable nonces, both of which can be exploited. The Debian OpenSSL incident in 2008, in which a packaging change reduced the entropy pool to a 15-bit seed, produced predictable keys across millions of systems and required a fleet-wide key rotation. The ROCA vulnerability in 2017 found that Infineon’s RSA key generation produced keys with a specific structural weakness, allowing the private key to be recovered from the public key for affected systems. Smart cards, TPMs, and Estonian national ID cards were all affected.

Side channels. Public-key operations are particularly vulnerable to timing attacks, cache-timing attacks, and power-analysis attacks because the operations involve secret-dependent branching or memory access patterns. Constant-time implementations are mandatory; libraries that get this right (libsodium, BoringSSL, modern OpenSSL versions) are the only ones that should be trusted.

Padding oracle attacks. Bleichenbacher’s 1998 attack against PKCS#1 v1.5 padding has reappeared in dozens of variants over the subsequent decades, repeatedly breaking deployments that should have moved to OAEP. The most recent significant instance was the Marvin attack in 2023, which generalized previous attacks and showed that many supposedly-mitigated implementations were still vulnerable through subtle timing differences.

Small subgroup attacks against Diffie-Hellman exploit DH implementations that fail to validate the received public value. If a server accepts arbitrary values without confirming they lie in the intended subgroup, an attacker can force the shared secret into a small subgroup where it can be recovered. The mitigation is rigorous parameter validation.

Insufficient parameter sizes persist in long-lived systems. RSA-1024 keys in legacy TLS certificates, 1024-bit DH parameters in old SSH server configurations, weak elliptic curves in IoT devices that have not been updated. The work is migration, not detection.

Key reuse across protocols. A single key pair used for both signing and encryption, or used in two different protocols with different security assumptions, can produce failures where neither protocol alone would have. The general principle is one key, one purpose, one protocol.

The post-quantum transition

Public-key cryptography is the part of the discipline that quantum computers will break. Shor’s algorithm, published by Peter Shor in 1994, solves both the integer factoring problem (breaking RSA) and the discrete logarithm problem (breaking finite-field DH, ECDH, ECDSA, EdDSA) efficiently on a sufficiently large quantum computer.

“Sufficiently large” is not yet achievable. Estimates of the resources required range from roughly 4,000 logical qubits to break RSA-2048, with current state-of-the-art quantum computers operating with on the order of 1,000 noisy physical qubits and substantially fewer logical qubits after error correction. The gap is real and the timeline is genuinely uncertain — estimates of when a cryptographically-relevant quantum computer will exist range from a decade to several decades, with no scientific consensus. But “harvest now, decrypt later” is a real threat model for traffic that needs to remain confidential into the era of practical quantum computing, which is why the post-quantum migration is being treated as urgent even though the quantum threat is not yet immediate.

NIST has finalized the first generation of post-quantum standards as of August 2024:

FIPS 203 (ML-KEM) — Module-Lattice-Based Key Encapsulation Mechanism, based on the CRYSTALS-Kyber design. Replaces RSA and ECDH for key encapsulation. Lattice-based.
FIPS 204 (ML-DSA) — Module-Lattice-Based Digital Signature Algorithm, based on CRYSTALS-Dilithium. Replaces RSA, ECDSA, and EdDSA for most signature applications. Lattice-based.
FIPS 205 (SLH-DSA) — Stateless Hash-Based Digital Signature Algorithm, based on SPHINCS+. A conservative hash-only signature scheme used where ML-DSA’s assumptions are too aggressive (long-term root signing, firmware signing for devices that may need to remain secure for decades).

In 2026, the deployment pattern for new systems concerned about post-quantum security is hybrid: run a classical public-key primitive (ECDHE or RSA) alongside a post-quantum primitive (ML-KEM), and combine their outputs. This protects against both today’s adversaries (in case the post-quantum algorithm turns out to have a classical weakness) and tomorrow’s quantum-capable adversaries (the classical algorithm provides no protection). Major deployers — Cloudflare, Google, Apple, Signal — have rolled out hybrid post-quantum key exchange in their respective protocols.

The Quantum Computing page on this site goes deeper into the algorithms themselves and the engineering challenges of building the quantum computers that would break them.

Standards and references

The relevant specifications:

PKCS#1 v2.2 (RFC 8017) — RSA Cryptography Specifications, including OAEP and PSS.
NIST SP 800-56A — Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (DH and ECDH).
NIST SP 800-56B — Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography (RSA-based key establishment).
FIPS 186-5 — Digital Signature Standard (RSA, ECDSA, EdDSA).
RFC 6979 — Deterministic ECDSA.
RFC 8032 — Edwards-Curve Digital Signature Algorithm (EdDSA), including Ed25519 and Ed448.
RFC 7748 — Elliptic Curves for Security, including Curve25519 and Curve448.
FIPS 203, 204, 205 — Post-quantum standards (ML-KEM, ML-DSA, SLH-DSA).

What to actually use in 2026

For new systems, the short answer is elliptic curve cryptography by default, with the specific choices:

Key agreement: X25519 (Curve25519 ECDH) for non-FIPS environments, P-256 ECDH for FIPS-validated systems. Always ephemeral for forward secrecy.
Signatures: Ed25519 (EdDSA) for non-FIPS environments, P-256 ECDSA with RFC 6979 deterministic nonces for FIPS-validated systems.
Encryption (rare): RSA-OAEP if asymmetric encryption is genuinely required, but the common pattern is to use ECDH or ML-KEM to agree on a symmetric key and encrypt the data with AEAD instead.

For systems that need to be post-quantum-safe: hybrid mode combining a classical primitive (X25519 or P-256) with ML-KEM for key agreement, and either ML-DSA or SLH-DSA for signatures depending on the deployment context.

Avoid: RSA at less than 2048 bits, finite-field DH at less than 2048 bits, PKCS#1 v1.5 padding for new RSA encryption, ECDSA without deterministic nonces, custom curves, hand-rolled implementations, and any system that uses the same key pair for both signing and encryption.

The cryptographic math has been good enough for decades. The deployments fail at the boundaries: padding choices, random number generators, parameter validation, key management. The work is in those boundaries, not in choosing the primitive.