How public-key cryptography works

For most of history, encryption had one fundamental limitation: both sides needed the same secret key, and they had to share it before they could communicate securely. Generals exchanged codebooks by courier; banks shipped keys in locked cases. On the internet, where you connect to servers you have never contacted before, that is impossible.

Public-key cryptography removes the limitation. Each party has a pair of keys: a public key that can be shown to anyone, and a private key that never leaves its owner. With them, two strangers can agree on a secret while others listen, and anyone can check that a message really comes from the holder of a private key. Every TLS connection, software update and secure messaging app depends on this.

This article explains the ideas behind it with small numbers you can check by hand, then shows how the real algorithms scale them up.

Two keys, two jobs

A key pair is created together: the private key is chosen at random, and the public key is computed from it. Going the other way, from the public key back to the private key, must be practically impossible. The pair can then do two different jobs:

• Confidentiality. Anyone can use Bob’s public key to protect a message for Bob, and only Bob’s private key can open it.
• Authenticity. Alice uses her private key to sign a message, and anyone can use her public key to verify that the signature is genuine and the message unchanged.

The private key is the part that must stay secret. If it leaks, an attacker can read what was meant for its owner and sign in their name.

One-way functions

Public-key cryptography rests on trapdoor one-way functions: calculations that are easy to perform but practically impossible to undo, unless you know a secret. Three are used today:

“Hard” here is not a matter of cleverness. For the sizes used in practice, no known method can undo these calculations with any realistic amount of computing power.

All three rely on modular arithmetic, which works like a clock: numbers wrap around when they reach the modulus. On a 12-hour clock, 10 + 5 is 3. In general, a mod n is the remainder when a is divided by n: 17 mod 5 is 2, and 5⁶ mod 23 is 15,625 mod 23, which is 8.

Diffie-Hellman: agreeing on a secret in public

In 1976, Whitfield Diffie and Martin Hellman published a method for two people to create a shared secret over a channel that everyone can read. It is still the core of every TLS handshake.

Alice and Bob first agree, in public, on a prime p and a base g. Here, with tiny numbers, p = 23 and g = 5.

1. Alice picks a secret number, a = 6, and sends Bob A = _g_ᵃ mod p = 5⁶ mod 23 = 8.
2. Bob picks a secret number, b = 15, and sends Alice B = _g_ᵇ mod p = 5¹⁵ mod 23 = 19.
3. Alice computes _B_ᵃ mod p = 19⁶ mod 23 = 2.
4. Bob computes _A_ᵇ mod p = 8¹⁵ mod 23 = 2.

Both arrive at the same number because (_g_ᵇ)ᵃ and (_g_ᵃ)ᵇ are both _g_ᵃᵇ. An eavesdropper sees 23, 5, 8 and 19. To find the secret, they would need a or b: the exponent that turns 5 into 8, or into 19. With numbers this small, trying all 22 possibilities takes seconds. With a prime of 2,048 bits, a number with more than 600 decimal digits, nobody knows a feasible way.

Diffie-Hellman has one weakness on its own: it does not tell Alice who she agreed on a secret with. An attacker in the middle could run one exchange with Alice and another with Bob, and relay everything between them. That is why real protocols combine key exchange with signatures, which prove who is on the other end.

RSA: a key pair from two primes

In 1978, Ron Rivest, Adi Shamir and Leonard Adleman published a method that can both encrypt and sign, named RSA after them. Its security rests on factoring: multiplying two large primes is easy, but recovering them from the product is not.

The steps, with the textbook example:

1. Choose two primes: p = 61 and q = 53.
2. Multiply them: n = 61 × 53 = 3233. This modulus is part of both keys.
3. Compute (p − 1)(q − 1) = 60 × 52 = 3120.
4. Choose a public exponent e that shares no factor with 3120: e = 17.
5. Find the private exponent d for which e × d leaves a remainder of 1 when divided by 3120: d = 2753, since 17 × 2753 = 46,801 = 15 × 3120 + 1.

The public key is the pair (3233, 17); the private key is 2753. To encrypt the number 65, compute 65¹⁷ mod 3233 = 2790. To decrypt, compute 2790²⁷⁵³ mod 3233, which gives back 65. Only someone who knows d can do that, and finding d requires knowing (p − 1)(q − 1), which requires factoring n.

Signing works the other way round: the owner raises a number to the private exponent, and anyone can check the result with the public exponent. Signing 123 gives 123²⁷⁵³ mod 3233 = 2746, and anyone can verify that 2746¹⁷ mod 3233 = 123.

Real RSA keys are thousands of bits long; the current OpenPGP standard, for example, no longer allows new RSA keys shorter than 3,072 bits (RFC 9580). And real RSA is never used in this “textbook” form, which leaks information and can be manipulated. Messages are first combined with random padding, called OAEP for encryption and PSS for signatures, defined in RFC 8017. Today, RSA is used mostly for signatures, for example in certificates; TLS 1.3 no longer uses it for encryption.

Elliptic curves: the same security with smaller keys

Factoring and discrete logarithms modulo a prime have something in common: clever algorithms make them easier than trying every possibility, so keys must be large. Elliptic curve cryptography (ECC) uses a different mathematical structure for which no such shortcut is known, so much smaller keys give the same security.

An elliptic curve is the set of points that satisfy an equation of the form _y_² = _x_³ + ax + b. Its points can be “added” with a geometric rule: draw a line through two points; it meets the curve in one more point; reflect that point across the horizontal axis.

With the curve _y_² = x_³ − x + 1 and the points P = (0, −1) and Q = (3, 5), the line through them, y = 2_x − 1, meets the curve again at (1, 1), so P + Q = (1, −1). Adding a point to itself uses the tangent line instead.

Cryptography uses this rule on curves over a finite field, where coordinates are whole numbers modulo a large prime, and the “curve” is a scattered set of points. A private key is a large number k; the public key is the point k × G, the result of adding a fixed base point G to itself k times. Computing it is fast, because the point can be doubled repeatedly: a 256-bit number needs only a few hundred doublings and additions. Recovering k from the result is the hard problem.

Elliptic curves power most key exchanges and many signatures today:

• X25519 (RFC 7748), Diffie-Hellman on the curve Curve25519, is widely deployed as a key exchange in TLS 1.3, on its own or combined with a post-quantum algorithm (RFC 10024).
• P-256, a curve standardized by NIST, is used with ECDSA signatures and in key exchange.
• Ed25519 (RFC 8032) is a signature scheme on a related curve, used for example in TLS 1.3 and SSH (RFC 8709).

Digital signatures in practice

Signing a whole document with a public-key operation would be slow, so signature schemes first compute a hash of the message, a short fingerprint such as a SHA-256 value, and sign that. To verify, the receiver hashes the message too and checks the signature against the hash with the signer’s public key. If even one bit of the message changed, the hash changes and the check fails.

A valid signature shows two things: the message was signed by the holder of the private key, and it has not been changed since. It does not show who that holder is; that is the job of certificates, in which a trusted authority signs the binding between a public key and a name.

Signature schemes can fail in subtle ways. ECDSA needs a fresh secret random number, a nonce, for every signature, and even slight flaws in how it is chosen can be turned into attacks (RFC 6979). In the worst case, if the same nonce is used twice with the same key, anyone can compute the private key from the two signatures. Modern schemes avoid the trap by deriving the nonce from the message and the key: Ed25519 does this by design, and RFC 6979 describes how to do it for ECDSA.

Key sizes

Key sizes are not comparable across algorithms. NIST expresses security as a security strength in bits, a measure of the work needed to break an algorithm. A strength of 128 bits, for example, is the strength NIST assigns to AES-128, a symmetric cipher whose 128-bit key has 2¹²⁸ possible values.

For elliptic curves, NIST gives a range of sizes for each strength; the chart shows the smallest. A 256-bit elliptic curve key offers about the same security as a 3,072-bit RSA key. Smaller keys mean smaller certificates, faster handshakes and less work for small devices, which is one reason elliptic curves are the usual choice for key exchange today: TLS 1.3, for example, requires every implementation to support key exchange with the curve P-256 (RFC 9846).

Hybrid encryption

Public-key operations are far slower than symmetric encryption such as AES, and they can only process small amounts of data at a time. So real systems combine both: public-key cryptography establishes or protects a short random key, and that key encrypts the actual data with a fast symmetric algorithm. TLS, encrypted email and messaging apps all work this way.

The quantum threat

In the mid-1990s, Peter Shor described an algorithm that would let a large enough quantum computer factor numbers and compute discrete logarithms efficiently, including on elliptic curves. Such a computer would break RSA, Diffie-Hellman and elliptic curve cryptography alike. Large-scale quantum computers do not exist yet, but an attacker could record encrypted traffic today and decrypt it once one exists, an attack known as “harvest now, decrypt later” (RFC 9958).

For this reason, NIST published three standards for post-quantum cryptography in August 2024, based on mathematical problems that quantum computers are not known to solve efficiently:

• ML-KEM (FIPS 203), for establishing shared keys;
• ML-DSA (FIPS 204), for signatures;
• SLH-DSA (FIPS 205), a second signature scheme, whose security rests only on properties of hash functions.

ML-KEM and ML-DSA are based on problems in mathematical structures called lattices. Because the new algorithms are young, they are usually deployed in hybrid mode, combined with a classic algorithm so that the connection stays secure as long as either one holds. For TLS, RFC 10024 (2026) defines such combinations, for example X25519MLKEM768, which pairs X25519 with ML-KEM.

A little history

Public-key cryptography entered the open literature with Whitfield Diffie and Martin Hellman’s paper “New Directions in Cryptography” in November 1976, followed by RSA in February 1978. Before then, every practical cipher required the two sides to share a secret key in advance.

Key points

• A key pair has a public key for everyone and a private key for its owner alone. It serves two jobs: confidentiality (encrypt with the receiver’s public key) and authenticity (sign with your own private key).
• Security rests on one-way functions: factoring for RSA, discrete logarithms for Diffie-Hellman, and the elliptic curve version of discrete logarithms for X25519, ECDSA and Ed25519.
• Diffie-Hellman creates a shared secret in public, but needs signatures to know who is on the other end.
• Elliptic curves give the same security as RSA with much smaller keys.
• Real systems use hybrid encryption, and are moving to post-quantum algorithms such as ML-KEM, usually combined with classic ones.