Signatures, Public Keys and PKI

Topics Covered

Public Key Cryptography in Practice

Key pairs

The algorithm families

Key exchange

Hybrid encryption

Performance profiles

Private keys are the whole game

Randomness at key generation

What public keys do not tell you

Quantum computers

Choosing an algorithm

Libraries to reach for

Public key cryptography solves a problem symmetric encryption cannot: how two parties who have never shared a secret can communicate securely, and how anyone can check that a message came from a particular party without being able to forge one. It underpins TLS, software updates, package registries, single sign on tokens, code signing and secure messaging. This lesson explains what public key algorithms do, how signatures work and fail, how certificates connect keys to names, and how teams operate certificates and signing keys without outages or compromise.

Key pairs

A public key algorithm uses a pair of keys generated together. The private key is kept secret by its owner, and the public key can be published to anyone. Operations performed with one key can be checked or reversed only with the other. For signatures, the owner signs with the private key and anyone verifies with the public key. For key exchange, two parties combine their own private key with the other party public key to derive the same shared secret, which no eavesdropper can compute. The security rests on mathematical problems that are easy in one direction and infeasible to reverse at the chosen key sizes.

The algorithm families

Two families dominate. RSA, based on the difficulty of factoring large numbers, has been in use since the 1970s and supports both signatures and encryption. Elliptic curve cryptography, based on the discrete logarithm problem on elliptic curves, offers the same security with much smaller keys and faster operations. The common elliptic curve algorithms are ECDSA over the NIST P-256 curve, Ed25519 for signatures and X25519 for key exchange. New designs should prefer elliptic curve algorithms, with Ed25519 and X25519 as the simplest to use safely, and RSA remains acceptable at 3072 bits or more where compatibility requires it.

For about 128 bit security, AES needs 128 bit keys, elliptic curves 256 bits and RSA 3072 bits. An Ed25519 public key is 32 bytes and a signature 64 bytes, against 384 bytes each for RSA-3072.

Key exchange

Key exchange lets two parties agree a symmetric key over a public network. In elliptic curve Diffie Hellman, each side generates a key pair, sends the public half and combines the received public key with its own private key to compute the same secret. TLS 1.3 uses ephemeral key exchange for every connection, generating fresh key pairs that are discarded afterwards, which gives forward secrecy: an attacker who later steals the server long term private key still cannot decrypt recorded traffic, because the keys that protected it no longer exist. Forward secrecy is one reason TLS 1.3 removed the older RSA key transport mode.

Hybrid encryption

Public key algorithms are slow and can only process small inputs directly, so they are almost never used to encrypt data itself. Instead, systems use hybrid encryption: generate a random symmetric key, encrypt the data with an AEAD cipher under that key, and encrypt or derive the symmetric key with public key cryptography. Standards such as HPKE, hybrid public key encryption, package this pattern with well defined key derivation, and tools such as age use it for files. Teams that need to encrypt data to a public key should use these constructions rather than calling RSA encryption directly, which has a long history of padding attacks.

Performance profiles

The algorithms differ sharply in speed, and the differences matter for capacity planning. RSA signing is slow because it uses the large private exponent, while RSA verification is fast because the public exponent is small. Elliptic curve signing is fast, and verification is somewhat slower than signing. A server that signs many tokens per second, such as an identity provider, may need far less hardware with Ed25519 than with RSA, while a client that only verifies may see little difference. TLS handshakes, which involve signature and key exchange operations, are a common place where this shows up in CPU profiles.

On one core, RSA-3072 signs about 800 times a second but verifies about 25,000 times. Ed25519 signs about 50,000 times and verifies about 20,000.

Private keys are the whole game

Everything in public key cryptography depends on the private key staying private. A stolen signing key lets an attacker sign anything as its owner, such as malware that passes code signing checks or tokens that pass authentication. A stolen TLS key lets an attacker impersonate a server to anyone who can be routed to them. Private keys should be generated where they will be used, ideally inside a hardware security module or a cloud key management service that never exports them, should be readable only by the processes that need them and should never appear in source control, container images, logs or chat.

Randomness at key generation

Key pairs must be generated with a strong source of randomness. Weak randomness at key generation has produced some of the largest public key failures: studies of internet facing devices have found thousands of RSA keys sharing prime factors, because embedded devices generated keys at first boot before their random generators had gathered enough entropy, letting anyone factor the keys by computing common divisors. A well known Linux distribution bug once reduced key generation randomness to a few thousand possibilities, so every affected key could be enumerated. Generating keys in a mature library on a properly seeded system, or in a key service, avoids these failures.

What public keys do not tell you

A public key is just a number. On its own it says nothing about who owns it. If an attacker can substitute their own public key for the real one, for example by intercepting the first connection, by editing a configuration file or by publishing a lookalike key in a directory, they can sign or decrypt as the intended party and everyone will be fooled. The central practical problem of public key cryptography is therefore not the mathematics but the binding between keys and identities, which certificates and public key infrastructure, covered later in this lesson, exist to provide.

Quantum computers

A sufficiently large quantum computer would break RSA, elliptic curve signatures and elliptic curve key exchange, because efficient quantum algorithms exist for factoring and discrete logarithms. No such machine exists today, but data recorded now and decrypted later is a real concern for long lived secrets. Standards bodies have published post quantum algorithms, such as ML-KEM for key exchange and ML-DSA and SLH-DSA for signatures, and major browsers and TLS libraries already use hybrid key exchange combining X25519 with ML-KEM. For most teams, the practical step is to keep libraries current and maintain the cryptographic inventory that will make migration manageable.

Choosing an algorithm

For new systems the choices are short. Use Ed25519 for signatures unless a standard or partner requires something else, in which case use ECDSA P-256 or RSA-PSS at 3072 bits. Use X25519, or a hybrid with ML-KEM where supported, for key exchange. Use HPKE or a vetted library construction to encrypt to a public key. Do not use RSA PKCS#1 version 1.5 encryption in new designs, do not implement any of these algorithms yourself, and do not accept algorithm choices from untrusted input, a mistake that has broken many token and signature systems.

Libraries to reach for

The safest path is a high level library that offers sealed boxes, signatures and key exchange without exposing the primitives underneath. Libsodium and its bindings, the cryptography package in Python, the standard crypto packages in Go and the Tink library from Google all provide this, with defaults chosen by specialists. Low level interfaces that ask the caller to pick padding modes, curve parameters or nonce handling should be treated as expert territory and kept behind a small internal wrapper that the rest of the codebase calls, so that algorithm choices live in one reviewed place.

Prefer small, modern and boring

Use public key algorithms for signatures and key exchange, and hybrid encryption for data. Prefer Ed25519 and X25519, keep RSA at 3072 bits or more for compatibility, generate keys with strong randomness inside key services where possible, protect private keys absolutely and remember that a public key proves nothing about who owns it.