Asymmetric crypto: RSA and the discrete-log family

Public-key cryptography is the answer to a problem symmetric cryptography cannot solve: two parties who have never met, sharing no prior secret, exchanging messages over a network where everything they say can be read by everyone else, need to end up with a shared secret no eavesdropper can derive. The solution looked impossible until 1976, when Diffie and Hellman published the paper that essentially launched modern cryptography. Their construction, with refinements, is the foundation of every TLS handshake, every SSH login, every WireGuard tunnel, every Signal conversation in 2026. RSA arrived in 1977 with a different but related construction. Both belong to a family of "asymmetric" primitives where one operation (with a public key) is computationally tractable while its inverse (without the private key) is not. This module is the foundational pass: enough to read protocol specs, recognize when a public-key choice is consequential, and understand why X25519 became the boring default in everything modern.

Prerequisites

• Module 2.1 — Symmetric encryption, block ciphers, AES. Public-key crypto's value comes partly from contrast with symmetric.
• Module 2.3 — Hash functions and message authentication. Hashes show up inside RSA padding and signature schemes.

Learning objectives

By the end of this module you should be able to:

1. Explain why public-key cryptography solves a different problem from symmetric encryption, and why the answer is fundamentally slower.
2. Describe RSA from first principles — the modular exponentiation, the public/private exponent split, why padding is necessary — and articulate why modern protocol designers are using less of it.
3. Compare finite-field Diffie-Hellman, elliptic-curve Diffie-Hellman, and Curve25519/X25519 at the engineering level.
4. Distinguish the three roles public-key crypto plays in real protocols: encryption, key agreement, and signing.
5. Reason about why TLS 1.3 dropped RSA key exchange but retained RSA signatures, and what that means for protocol designers in 2026.

What public-key crypto is buying

Symmetric cryptography requires both parties to share a secret key in advance. If you've never met the person you want to communicate securely with, you can't use AES with them — there's no shared key.

Public-key cryptography splits the key into two halves:

• The public key can be published openly. Anyone can know it.
• The private key stays secret with the owner.

The two halves are mathematically related, but knowing the public key doesn't let you derive the private key (assuming the math holds — that's what cryptanalysis tries to break). With this split, the operations possible without prior shared state include:

• Encrypt to a public key. Anyone can encrypt a message that only the holder of the private key can decrypt.
• Sign with a private key. Only the holder can produce a signature that anyone can verify with the public key.
• Agree on a shared secret. Two parties, each holding their own private key, can compute a shared value that no eavesdropper can derive without one of the private keys.

These three operations — encryption, signature, key agreement — are what public-key crypto buys. They solve key distribution, authentication, and shared-key bootstrapping in open networks. Without them, the modern internet's security model would not exist; the only alternative is pre-shared symmetric keys distributed out-of-band, which doesn't scale to billions of users.

The cost is computational. Public-key operations are typically 1,000-10,000 times slower than symmetric encryption per byte. An RSA-2048 signature takes milliseconds; AES-128-GCM encrypts a megabyte in microseconds. The performance gap is fundamental: public-key math depends on hard arithmetic problems (factoring, discrete logarithms) and even efficient implementations require thousands of large-number operations per primitive call.

The pragmatic protocol design pattern: use public-key cryptography sparingly, to set up symmetric keys. TLS 1.3 uses public-key crypto for the handshake (key agreement + signatures), then derives symmetric session keys, then encrypts all application data symmetrically. The slow operations happen once per connection; the fast operations happen for every byte. WireGuard, SSH, Signal, and basically every modern protocol use the same pattern.

RSA from first principles

RSA (Rivest, Shamir, Adleman, 1977) was the first practical public-key system. The math:

1. Pick two large primes, p and q. Compute n = p × q. (For RSA-2048, n is 2048 bits ≈ 617 decimal digits.)
2. Compute phi(n) = (p-1)(q-1).
3. Choose a public exponent e (typically 65537).
4. Compute the private exponent d such that d × e ≡ 1 (mod phi(n)).

The public key is (n, e). The private key is (n, d), plus optionally p and q for faster computation.

To encrypt a message m (treated as a number less than n):

c = m^e mod n

To decrypt:

m = c^d mod n

The math works because of Euler's theorem and the relationship between e and d. The security rests on the assumption that factoring n into p × q is hard. If you can factor n, you can compute phi(n), derive d from e, and decrypt anything. Best classical factoring algorithms (the General Number Field Sieve) take roughly subexponential time; for 2048-bit n, factoring is far beyond practical adversaries.

To sign a message, RSA signing is conceptually signature = hash(m)^d mod n (with proper padding — see below). The signer uses their private key. Verifying a signature: anyone with the public key checks signature^e mod n == hash(m). Verification is fast (small public exponent), signing is slow (large private exponent).

That's RSA in three paragraphs. The catch is in the surrounding details.

Why raw RSA is a footgun

The RSA primitive — m^e mod n — is mathematically correct but operationally dangerous. Direct use leads to several catastrophic failures:

Deterministic encryption. If you encrypt the same plaintext twice, you get the same ciphertext. An attacker who knows the structure of likely plaintexts can encrypt them all and look up which one matches. For small message spaces (yes/no responses, four-digit PINs), this is a complete break.

Multiplicative property. Raw RSA has a malleability issue: (m1 × m2)^e mod n = (m1^e × m2^e) mod n. An attacker with two ciphertexts can produce the encryption of the product without decrypting. In some protocols this lets attackers manipulate plaintexts they can't read.

Padding oracle attacks. When raw RSA is wrapped in PKCS#1 v1.5 padding (a 1980s construction still in some legacy protocols), implementations that leak whether the padding parsed correctly leak information about the plaintext. The Bleichenbacher 1998 attack against TLS using PKCS#1 v1.5 was the canonical example; variants have shown up periodically ever since (DROWN, ROBOT).

The fixes:

• OAEP (RFC 8017) — Optimal Asymmetric Encryption Padding. Adds randomness and mask-generation around the plaintext before applying RSA. Eliminates determinism, malleability, and padding-oracle leaks.
• PSS — Probabilistic Signature Scheme. The right padding for RSA signatures. Provably secure under standard assumptions, unlike PKCS#1 v1.5 signatures which have weaker proofs.
• Don't use raw RSA. All modern crypto libraries' RSA APIs default to OAEP or PSS. If you find yourself using RSA_NO_PADDING or equivalent, you're almost certainly making a mistake.

The deeper lesson: RSA-the-primitive is fine, but RSA-as-deployed has a long history of subtle protocol breaks. This is one of the engineering reasons newer protocols (TLS 1.3, WireGuard) avoid RSA wherever they can.

Discrete logarithms and Diffie-Hellman

Diffie-Hellman (1976) was published a year before RSA and addresses a different problem: key agreement.

Two parties want to end up with a shared secret. They've never met. Eavesdroppers see everything they exchange. Diffie-Hellman:

1. Public parameters: a large prime p and a generator g (small integer with specific properties relative to p).
2. Alice picks a random private value a and sends Bob A = g^a mod p.
3. Bob picks random b and sends Alice B = g^b mod p.
4. Alice computes B^a = g^(ba) mod p. Bob computes A^b = g^(ab) mod p. These are the same value — the shared secret.

An eavesdropper sees A = g^a and B = g^b but cannot compute g^(ab) without knowing either a or b. Recovering a from A = g^a mod p is the discrete logarithm problem — believed to be hard for properly-chosen p.

The shared secret g^(ab) mod p is then run through a key-derivation function (Module 2.6) to produce session keys for symmetric encryption.

Diffie-Hellman is key agreement, not encryption. It produces a shared key that both parties hold; it doesn't transport a chosen plaintext. Most modern protocols use it instead of RSA encryption because:

• Forward secrecy is automatic. Each session uses fresh a and b. After the session ends, both are discarded, and the shared secret can't be reconstructed even if the long-term keys are later compromised.
• No padding-oracle history. DH doesn't have RSA's accumulated padding pitfalls.
• Simpler implementation. No need for OAEP or PSS; the primitive itself is the protocol.

The size of p matters. Classic finite-field DH needs 2048-3072 bit primes for security comparable to RSA-2048; the operations are correspondingly slow. This is what motivated the move to elliptic curves.

Elliptic curves without mysticism

Elliptic-curve Diffie-Hellman (ECDH) does the same thing as classical DH, but the math is over a different group: points on an elliptic curve y² = x³ + ax + b mod p rather than integers mod p.

The crucial engineering property: the discrete-log problem on a well-chosen curve is harder per bit than on integers. A curve over a 256-bit prime has security comparable to a finite-field group with a 3072-bit prime. Smaller keys, smaller signatures, faster operations — for the same security level.

Two curve families dominate practical use:

NIST curves (P-256, P-384, P-521). Standardized by NIST in 1999. Used widely in TLS, X.509 certificates, and U.S. government applications. Some unease about whether the curve parameters were chosen with NSA influence (the Dual_EC_DRBG fiasco didn't involve these curves but cast a shadow). Still in widespread use; almost certainly safe; but not the modern engineering default.

Curve25519 / X25519. Designed by Daniel J. Bernstein, published 2006. Designed for performance and constant-time implementation; the parameters are derived from natural mathematical constants ("nothing-up-my-sleeve" numbers) rather than chosen to optimize anything mysterious. Standardized in RFC 7748. Used in TLS 1.3, WireGuard, Signal, SSH (Ed25519 for signatures), and basically every modern protocol that adopted an elliptic curve.

X25519's design choices are conservative engineering rather than aggressive cryptography:

• The Montgomery ladder. A simple algorithm for scalar multiplication on the curve that's naturally constant-time, regardless of the input. No data-dependent branches; no cache-timing leaks.
• Compact representation. A 32-byte private key, 32-byte public key, 32-byte shared secret. Fits trivially in any protocol.
• Cofactor handling baked in. The X25519 function definition includes the cofactor multiplication, so library users can't accidentally produce the small-subgroup attack class of bug.
• Speed. A modern CPU does X25519 in ~70,000 cycles — under a microsecond. Multiple-thousand operations per second per core, easily.

The pragmatic 2026 choice: for new protocols, use X25519 for ECDH and Ed25519 for signatures unless interop with a NIST-mandated standard requires P-256/ECDSA.

The three roles of public-key crypto

Public-key primitives can play three distinct roles in protocols. Confusing them is the source of many "what does TLS 1.3 actually use?" questions.

Encryption. The sender encrypts a message under the receiver's public key; only the receiver can decrypt. RSA-OAEP is the classic instance. In TLS 1.2 and earlier, this was used for key exchange: the client encrypted a "premaster secret" under the server's public key, and the server decrypted it. The legacy protocols call this "RSA key exchange."

Key agreement. Both parties contribute private random values; they exchange public values; they derive the same shared secret without explicitly transporting a plaintext. Diffie-Hellman in any of its variants. Provides forward secrecy automatically.

Signing. The signer uses their private key to produce a signature that anyone can verify with the public key. Used for authentication: a server proves it's who its certificate says it is by signing the handshake transcript with the certificate's private key. Algorithms: RSA-PSS, ECDSA (typically P-256), Ed25519.

A given algorithm family can play multiple roles:

• RSA can encrypt or sign.
• Diffie-Hellman / X25519 can only do key agreement (it's a key-exchange primitive, not an encryption primitive).
• ECDSA / Ed25519 can only sign.

So when a protocol description says "uses ECDH for key exchange and ECDSA for signatures," it's using elliptic-curve math twice with different operations, both producing different security properties from the same underlying curve.

The slow death of RSA key exchange

TLS 1.2 supported many cipher suites, including:

• Static-RSA key exchange. Client encrypts premaster secret under server's RSA certificate public key. Server decrypts with the certificate's private key.
• Ephemeral DH (DHE). Both parties generate fresh DH keys per connection.
• Ephemeral ECDH (ECDHE). Same, with elliptic curves.

Static-RSA had a fatal property: no forward secrecy. If an attacker recorded a connection and later compromised the server's private key, they could decrypt the recorded traffic. With DHE/ECDHE, the ephemeral keys are gone after the connection — recording today and breaking later doesn't recover anything.

By the mid-2010s, "use ephemeral key agreement for forward secrecy" was security best practice. Most TLS 1.2 deployments configured ECDHE-RSA or ECDHE-ECDSA cipher suites by default.

TLS 1.3 made it mandatory: all key exchange must be ephemeral. RSA key exchange was removed entirely. The only public-key roles RSA still plays in TLS 1.3 are:

• Server certificate signatures. RSA-PSS signs the handshake transcript to prove possession of the certificate's key.
• CA signatures on certificates. RSA signatures on the certificate chain.

Even those uses have been retreating. Modern best practice is to issue certificates with ECDSA (P-256) or Ed25519 keys; RSA certificates persist mostly because:

• Some legacy clients don't support ECDSA.
• Compliance regimes mandate specific algorithms.
• HSMs (hardware security modules) often have better RSA support than ECC support.

Within a few years, the typical TLS 1.3 connection will be RSA-free: ECDH key exchange, ECDSA or Ed25519 signatures. RSA's role will be largely historical.

Hands-on exercise

Exercise 1 — Generate and inspect an RSA keypair

# Generate a 2048-bit RSA keypair
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out /tmp/rsa.pem

# Extract just the public key
openssl pkey -in /tmp/rsa.pem -pubout -out /tmp/rsa.pub

# Inspect the public key
openssl pkey -in /tmp/rsa.pub -pubin -text -noout

# Inspect the private key (warning: contains the actual private exponent)
openssl pkey -in /tmp/rsa.pem -text -noout | head -30

Look at the output. The public key has:

• Modulus (n). A 2048-bit value — about 617 decimal digits or 256 bytes. This is the n = p × q of the RSA setup.
• Public exponent (e). Almost always 65537. This is the exponent used during encryption and signature verification.

The private key has all of those plus:

• Private exponent (d). Same size as n, used for decryption and signing.
• Prime factors (p, q). Each about 1024 bits.
• CRT exponents and coefficient. Helper values used for faster decryption via the Chinese Remainder Theorem.

You can see why RSA operations are slow: every encryption is a 2048-bit modular exponentiation, which is thousands of 64-bit multiplications.

Stretch: generate an Ed25519 keypair and compare sizes:

openssl genpkey -algorithm Ed25519 -out /tmp/ed25519.pem
openssl pkey -in /tmp/ed25519.pem -text -noout

The Ed25519 private key is 32 bytes; the public key is 32 bytes. Compare to RSA-2048's 256-byte public key. The size difference at the same security level is one of the practical reasons elliptic-curve crypto won.

Exercise 2 — X25519 key agreement

"""Two parties derive the same shared secret with X25519."""

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey

# Alice generates her keypair
alice_private = X25519PrivateKey.generate()
alice_public = alice_private.public_key()

# Bob generates his keypair
bob_private = X25519PrivateKey.generate()
bob_public = bob_private.public_key()

# They exchange public keys (over an insecure channel — that's fine).
# Each computes the shared secret using their own private and the other's public.
alice_shared = alice_private.exchange(bob_public)
bob_shared = bob_private.exchange(alice_public)

assert alice_shared == bob_shared
print(f"shared secret: {alice_shared.hex()}")
print(f"both parties computed the same value")

Run it. Both parties end up with the same 32-byte shared secret without ever exchanging anything secret. An eavesdropper saw both public keys but cannot derive the shared value.

Notice the symmetry: Alice's exchange() takes Bob's public and combines with her private; Bob does the symmetric operation. The result is the same. This is the entire Diffie-Hellman bargain in 5 lines of Python.

In a real protocol, the shared secret isn't used directly — it's run through HKDF (Module 2.6) to derive multiple symmetric keys. But the heart of the operation is what you just did.

Common misconceptions

"Public-key crypto is just stronger encryption." It's a different category of operation. Symmetric encryption assumes a pre-shared key and is fast. Public-key cryptography solves key distribution and identity (no pre-shared key needed) but is dramatically slower. Real protocols use public-key once per connection to bootstrap symmetric keys, then symmetric for the bulk traffic.

"RSA and Diffie-Hellman are interchangeable." Both are public-key primitives, but they do different jobs. RSA-encryption transports a plaintext under a public key. Diffie-Hellman lets two parties agree on a shared secret without transporting one. Most modern protocols use DH-style key agreement for forward secrecy; RSA is mostly used for signatures.

"Elliptic curves are suspicious because they're 'too mathematical.'" All public-key crypto is mathematical — RSA depends on integer factoring being hard, DH on discrete logarithms being hard. Elliptic curves are a different math but no more mystical. The standard curves (X25519, Ed25519) have nothing-up-my-sleeve parameters; the suspicion that's sometimes attached to NIST curves doesn't apply to the modern engineering defaults.

"If a protocol uses ECC, it doesn't need symmetric crypto." Public-key operations bootstrap symmetric session keys. The bulk of any data transfer is symmetric. Public-key is the one-time setup; symmetric is the everyday operation.

"RSA is broken because TLS 1.3 dropped RSA key exchange." TLS 1.3 dropped static-RSA key exchange because it didn't provide forward secrecy and had a long history of padding-related attacks. RSA signatures (RSA-PSS) are still supported in TLS 1.3 and still used widely. RSA-the-algorithm isn't broken; specific RSA-based deployments lost favor for forward-secrecy and protocol-cleanup reasons.

Further reading

1. Whitfield Diffie and Martin Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, 1976. The paper that started it all.
2. Rivest, Shamir, Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, CACM 1978. The original RSA paper. Short, readable.
3. RFC 8017 — PKCS #1 (RSA, OAEP, PSS). The current RSA standards. The OAEP and PSS sections are the right uses; PKCS#1 v1.5 sections are mostly there for compatibility with legacy code.
4. RFC 7748 — X25519 and X448. The standard for modern elliptic-curve key agreement.
5. Daniel J. Bernstein, Curve25519: new Diffie-Hellman speed records, PKC 2006. The original X25519 paper. Worth reading once for the design rationale.
6. Daniel Bleichenbacher, Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, CRYPTO 1998. The attack that retired PKCS#1 v1.5 from new use; classic example of why "the primitive is fine, the deployment is broken" matters.
7. Boneh, Joux, Nguyen, Why Textbook ElGamal and RSA Encryption Are Insecure, Asiacrypt 2000. A cleaner discussion of why raw public-key encryption needs padding.

The next module — Digital signatures — picks up from "RSA can sign" and goes deep on the signature schemes that TLS, code-signing, package managers, and certificate authorities all depend on.