Key pairs: public and private keys

The key-distribution problem comes from one fact: with a single shared key, the key that locks is also the key that unlocks, so it must be kept secret and it must travel. What if the locking key and the unlocking key were different?

That is a key pair. You create two keys at the same time, and they belong together:

• The public key. You give it to anyone. You can put it on a website, print it on a business card or pin it to a noticeboard.
• The private key. Only you hold it. It never leaves your device.

The two keys are linked by mathematics, but knowing the public key does not let anyone work out the private key. That is the whole trick.

Here is what a key pair lets you do. Rosa publishes her public key. Ken wants to send her a secret order, so he encrypts it with Rosa’s public key. Now only Rosa’s private key can decrypt it. Eve the spy also has Rosa’s public key, because it is public, and she copies the encrypted order on the way. It does not help her. The public key can lock, but it cannot unlock.

This changes the key-distribution maths completely:

• Nobody has to send a secret before the first message. The only thing that travels is the public key, and it is safe to copy.
• Each person needs one key pair, not one key for every partner. A thousand people need a thousand key pairs, not 499,500 shared keys.

Two rules keep you out of trouble from the start:

1. Encrypt to the other person’s public key. Not to your own. If Ken used his own public key, only Ken could read the order.
2. Never share the private key. If someone copies it, they can read everything sent to you, and they can pretend to be you.

Encryption is one job a key pair can do. The other big job is signing, which proves who wrote something. Signing is not “encryption with the private key”, and the chapter on digital signatures explains why.

Swipe sideways to see the whole diagram.

What makes a key pair possible?

Public-key cryptography (also called asymmetric cryptography) uses maths problems that are easy in one direction and infeasible in the other.

• RSA. Multiplying two large prime numbers is easy. Finding the two primes from their product is infeasible when the numbers are big enough. The public key is the product n (the “modulus”) and a small exponent, almost always 65537. The private key contains the matching private exponent and the two primes. RSA is specified in RFC 8017 (PKCS #1).
• Elliptic curves. The private key is a random number d. The public key is a point Q on a curve, found by “multiplying” a fixed starting point by d. Going from d to Q is fast. Going back from Q to d is the elliptic-curve discrete logarithm problem, which has no feasible solution for well-chosen curves. NIST’s approved curves, such as P-256, are in SP 800-186.
• Curve25519 and Ed25519. A family of curves designed to be fast and hard to implement wrongly. X25519 (RFC 7748) is used for key agreement and Ed25519 (RFC 8032) for signatures. Both target about 128 bits of security.

Which algorithm does which job?

Not every algorithm does every job. This matters when you choose keys and read configuration files.

The security strengths for RSA and P-256 come from Table 2 of NIST SP 800-57 Part 1. Notice that a 256-bit elliptic-curve key is stronger than a 2,048-bit RSA key. Bit counts only compare within one algorithm.

How does public-key encryption work in practice?

With RSA, you encrypt with the recipient’s public key using the OAEP padding scheme, and they decrypt with their private key. RFC 8017 section 7 says RSAES-OAEP is required for new applications, and the older PKCS #1 v1.5 encryption is “included only for compatibility with existing applications”.

RSA can only encrypt something smaller than its modulus. With a 3,072-bit key and OAEP using SHA-256, the limit is 318 bytes (384 − 2 × 32 − 2, from section 7.1.1). It is also slow compared with AES. So nobody encrypts a whole document with RSA. You encrypt a fresh random AES key with RSA, and the document with AES. This is hybrid encryption, and it is how almost all real public-key encryption works. The modern standard for it is HPKE (RFC 9180), which combines elliptic-curve key agreement, a key derivation function and an AEAD. The next chapter, key exchange, explains the key agreement part.

What do keys look like on disk?

Keys are usually stored as PEM text: Base64 between -----BEGIN …----- and -----END …----- lines.

• BEGIN PUBLIC KEY holds a SubjectPublicKeyInfo structure: the algorithm and the public key. This is the same structure that sits inside every certificate (RFC 5280, section 4.1.2.7).
• BEGIN PRIVATE KEY holds a PKCS #8 private key (RFC 5958). BEGIN ENCRYPTED PRIVATE KEY is the same thing protected by a passphrase.

The appendix on file formats covers PEM, DER, PKCS #12 and the rest.

The safest private key is one that never exists as a file at all. Hardware security modules (HSMs), TPM chips and phone secure elements generate the key inside the chip and only ever expose the public key. You ask the chip to use the key; you can never read it out. See guarding the keys.

What about quantum computers?

A large enough quantum computer running Shor’s algorithm could work out RSA and elliptic-curve private keys from public keys. No such machine exists today, but planning has started: NIST proposes deprecating quantum-vulnerable public-key algorithms at the 112-bit security level after 2030 and disallowing all of them after 2035. Symmetric ciphers such as AES are not broken in the same way. The chapter on post-quantum cryptography covers the new algorithms.

Make an elliptic-curve key pair

OpenSSL’s genpkey command creates a private key. The public key is computed from it, and pkey -pubout writes it out:

openssl genpkey -algorithm EC -pkeyopt ec_paramgen_curve:P-256 -out ec-key.pem
openssl pkey -in ec-key.pem -pubout -out ec-pub.pem
cat ec-pub.pem

-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEkM/tgwTFpn8lP7EvbDGclSqj5Ibg
IB5cQRz3uLPZ3aoYG1Z1RrQF9nGMOT2vcB0Oy4nWS47Nkh5Y4TEeKGTm5g==
-----END PUBLIC KEY-----

That public key is safe to share. To look inside both halves, ask OpenSSL to print the key as text (we shortened the private value; never post a real one):

openssl pkey -in ec-key.pem -text -noout

Private-Key: (256 bit)
priv:
    d1:e4:35:ce:… (32 bytes in total, shortened here)
pub:
    04:90:cf:ed:83:04:c5:a6:7f:25:3f:b1:2f:6c:31:
    9c:95:2a:a3:e4:86:e0:20:1e:5c:41:1c:f7:b8:b3:
    d9:dd:aa:18:1b:56:75:46:b4:05:f6:71:8c:39:3d:
    af:70:1d:0e:cb:89:d6:4b:8e:cd:92:1e:58:e1:31:
    1e:28:64:e6:e6
ASN1 OID: prime256v1
NIST CURVE: P-256

The private key is a 32-byte random number. The public key is 65 bytes: the byte 04 (meaning “uncompressed point”) followed by the 32-byte x and y coordinates of a point on the curve.

Make an RSA key pair

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out rsa-key.pem
openssl pkey -in rsa-key.pem -pubout -out rsa-pub.pem
openssl pkey -pubin -in rsa-pub.pem -text -noout | head -2

Public-Key: (3072 bit)
Modulus:

The public exponent printed at the end is 65537 (0x10001). RSA keys are much larger than elliptic-curve keys of similar strength: here the private key file was about 2.5 KB and the public key file about 0.6 KB, against roughly 240 and 180 bytes for the P-256 pair. (Exact sizes vary by a few bytes between systems, for example with Windows line endings.)

Encrypt a small secret to a public key

This is the core move of hybrid encryption: make a random AES key, then encrypt that key to the recipient’s RSA public key with OAEP.

openssl rand 32 > aes.key
openssl pkeyutl -encrypt -pubin -inkey rsa-pub.pem \
  -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
  -in aes.key -out aes.key.enc
openssl pkeyutl -decrypt -inkey rsa-key.pem \
  -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
  -in aes.key.enc | cmp - aes.key && echo "same key"

same key

The 32-byte key became 384 bytes of ciphertext, the size of the RSA modulus. With a different private key, decryption fails instead of returning garbage:

Public Key operation error
…:error:02000079:rsa routines:RSA_padding_check_PKCS1_OAEP_mgf1:oaep decoding error:…

In real systems a library or protocol does this for you, for example CMS, HPKE or TLS. The commands only show what happens underneath.

SSH keys are key pairs too

ssh-keygen -t ed25519 -C "demo key" -f id_demo -N ""
cat id_demo.pub

Generating public/private ed25519 key pair.
Your identification has been saved in id_demo
Your public key has been saved in id_demo.pub
The key fingerprint is:
SHA256:wcidri7t/dcJCQN+uPbylt94bdOO9A3FVoueP7Zq1xc demo key
…
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIKEAmRo5/bI0zyKZV94Ip4roHSg3uylIYaEtnRLCTPaq demo key

The .pub file goes into ~/.ssh/authorized_keys on every server you log in to. The private key file id_demo stays on your machine. (We used -N "" to make a demo key without a passphrase; for a real key, set one.) The “fingerprint” line is a hash of the public key, explained in hashes and fingerprints.

Look after private keys

• File permissions. A private key file should be readable only by the account that uses it (on Linux, chmod 600). OpenSSH refuses to use a private key that others can read.
• Passphrases. Encrypt key files that people use, such as SSH keys. Servers usually load unencrypted keys at start-up, so protect them with permissions, or better, keep the key in an HSM or a cloud key vault.
• Never in Git, never in tickets. A private key that has been pasted anywhere is compromised. Replace it, and if a certificate belongs to it, get the certificate revoked (see revocation).

Common mistakes

• “The public key decrypts.” What you encrypt with someone’s public key can only be decrypted with their private key. The public key cannot undo its own encryption.
• “I encrypt with my own public key.” Then only you can read it. To send a secret, use the recipient’s public key. In the classic 1999 usability study “Why Johnny Can’t Encrypt”, seven of the eleven participants who managed to encrypt at all used only their own public key.
• “Public keys must be kept secret.” No. They are meant to be copied. What you must protect is the private key, and you must check whose public key you have (see binding identity).
• “RSA encrypts the whole message.” RSA can only encrypt a few hundred bytes and is slow. Real systems use hybrid encryption: a public-key step for a symmetric key, then AES for the data.
• “Signing is encrypting with the private key.” This only half-fits textbook RSA and does not fit ECDSA or Ed25519 at all. Signing is a separate operation; see digital signatures.
• “A 256-bit key is weaker than a 2,048-bit key.” Not across algorithms. A P-256 elliptic-curve key gives about 128 bits of security, RSA-2048 about 112.

Check yourself

Check yourself

Ken wants to send Rosa an order that only Rosa can read. Which key does he encrypt it with?

1. Ken's own private key
2. Rosa's public key
3. Rosa's private key

Show answer

Answer B Rosa's public key

What happened

Ken encrypts with Rosa's public key, which anyone may have.

Why

Only the matching private key, which only Rosa holds, can decrypt what her public key encrypted. Ken never has Rosa's private key, and his own keys would not help Rosa.

The rule

To send a secret, encrypt to the recipient's public key. Only the recipient's private key can open it.

Check yourself

Eve has Rosa's public key and a copy of the encrypted order. What can she do with them?

1. Decrypt the order, because she has the key that encrypted it
2. Nothing useful: the public key cannot decrypt, and the private key cannot be worked out from it
3. Work out Rosa's private key from the ciphertext

Show answer

Answer B Nothing useful: the public key cannot decrypt, and the private key cannot be worked out from it

What happened

Eve holds only public information: the public key and the ciphertext.

Why

Public-key encryption is designed so that the public key can encrypt but not decrypt, and deriving the private key from the public key is infeasible.

The rule

A public key is safe to share. Only the private key must stay secret.

Check yourself

A team wants to replace its P-256 keys with RSA-2048 because '2,048 bits is more than 256 bits'. What is the right answer?

1. Yes, a bigger key is always stronger
2. No: P-256 gives about 128 bits of security, which is more than RSA-2048's 112 bits
3. It makes no difference what algorithm or size you use

Show answer

Answer B No: P-256 gives about 128 bits of security, which is more than RSA-2048's 112 bits

What happened

The team compared raw key sizes across two different algorithms.

Why

Different algorithms need very different key sizes for the same strength. NIST SP 800-57 rates P-256 at 128 bits and RSA-2048 at 112 bits.

The rule

Compare security strength, not bit counts. Key sizes only compare within one algorithm.

Go deeper

• RFC 8017 (PKCS #1): RSA, including OAEP encryption and PSS signatures.
• NIST SP 800-186: the elliptic curves NIST approves, including P-256 and Curve25519.
• RFC 7748 and RFC 8032: X25519 for key agreement and Ed25519 for signatures.
• RFC 9180: HPKE, the modern standard for hybrid public-key encryption.
• NIST SP 800-57 Part 1 Rev. 5: Table 2 compares the strength of RSA, elliptic-curve and symmetric keys.
• OpenSSL genpkey documentation: every key type and option the command supports.
• OpenSSH ssh-keygen manual: making and managing SSH key pairs.

In the gameLevel 3: Two keys: the open padlockThe Locksmith, Keystone. In development

Short on time? The crash course covers this chapter and the next in Lesson 2: Two keys.