Public Key Cryptography: Keys, Signatures and Exchange
A key pair has a public and a private half. Learn the encryption, the signature, the key exchange, and the trust problem.
By Velloreth
The key pair
A public key and a private key.
| Operation | Key used |
|---|---|
| Encrypt | the public key |
| Decrypt | the private key |
| Sign | the private key |
| Verify | the public key |
The public key can be published, which solves the key distribution problem.
The encryption
ciphertext = encrypt(message, publicKey)
message = decrypt(ciphertext, privateKey)
Only the holder of the private key can read it.
It is slow, so it is used to encrypt a small value, such as a session key.
The signature
signature = sign(message, privateKey)
valid = verify(message, signature, publicKey)
It proves the origin and the integrity.
It does not hide the content.
A signature is used for a release, a certificate and a token.
The key exchange
Two parties derive a shared secret without sending it.
Alice: a (private), A = g^a (public)
Bob: b (private), B = g^b (public)
Alice computes: B^a = g^(ab)
Bob computes: A^b = g^(ab)
An observer sees A and B but cannot compute g^(ab).
It is how TLS establishes a session key.
Forward secrecy
A compromise of the long-term key does not reveal a past session.
Each session uses an ephemeral key that is discarded.
ECDHE is the ephemeral form.
It is the default in TLS 1.3.
The trust problem
A public key proves nothing about who holds it.
An attacker could publish a key and claim to be someone else.
The solution is a certificate.
The root CA (in the trust store)
-> an intermediate CA
-> the leaf certificate for example.com
The certificate binds a public key to a name, and it is signed by a CA the client trusts.
The algorithms
| Algorithm | Basis | Key size |
|---|---|---|
| RSA | factoring | 2048–4096 bits |
| ECDSA | a discrete log on a curve | 256 bits |
| Ed25519 | a curve, a modern form | 256 bits |
| Diffie-Hellman | a discrete log | 2048+ bits |
| ECDHE | a curve, ephemeral | 256 bits |
A shorter key is faster and smaller for the same security.
Ed25519 is the modern choice for a signature.
The hybrid
A public key operation is slow, so it is used to exchange a symmetric key.
1. A key exchange derives a shared secret
2. The secret is used as a symmetric key
3. The data is encrypted with the symmetric key
That is what TLS does, and it is why the handshake is a small part of the cost.
The use cases
| Use | Mechanism |
|---|---|
| TLS | a key exchange and a certificate |
| A signed release | a signature |
| An SSH login | a key pair |
| A JWT | a signature |
| A signed email | a signature |
| A password | not this, use a hash |
A password is not encrypted with a public key, because the server must not be able to recover it.
The key management
The private key must be protected.
- A hardware module or a key store
- A passphrase
- A rotation
- A revocation
A leaked private key compromises everything it protects.
A certificate has an expiry, so a renewal is required.
Common mistakes
A private key in the repository. A leak.
A private key in a log. A leak.
A short RSA key. A weak security.
A self-signed certificate in production. A warning.
No revocation. A compromised key stays valid.
A password encrypted with a public key. The server can recover it.
A signature assumed to hide the content. It does not.
No forward secrecy. A past session is exposed.
A key with no rotation. A long exposure.
A certificate with no renewal. An expiry.
A quotable summary
Public key cryptography uses a key pair, where the public key encrypts and the private key decrypts, or the private key signs and the public key verifies. A key exchange derives a shared secret without sending it, and an ephemeral form provides forward secrecy, so a compromise of the long-term key does not reveal a past session. The trust problem is solved by a certificate that binds a public key to a name and is signed by a certificate authority the client trusts.
Related reading
For the related topics, see encryption-basics and digital-signatures-explained. For the broader context, ssl-tls-certificates and ssh-and-keys-guide.