L16 · Asymmetric Cryptography

Module 3: Cryptography Essentials · ~20 min · Lesson 16 of 71

🎯 What you'll learn

• The two jobs of a key pair: encrypt to a public key, sign with a private key
• Why asymmetric crypto is slow, and how hybrid encryption fixes that
• RSA vs elliptic curves (P-256, Curve25519), and which key sizes give equal strength
• How Diffie-Hellman lets two strangers agree on a secret in public (paint mixing, then the math)
• What quantum computers change, and what ML-KEM in your TLS handshake is for

🔥 Why this matters

In March 2023, GitHub replaced its RSA SSH host key after the private half was briefly exposed in a public repository. Anyone holding it could have pretended to be github.com to your git push. Developers everywhere then saw REMOTE HOST IDENTIFICATION HAS CHANGED!. One leaked private key, and a trust relationship used by millions had to be rebuilt. Today is about what that key does, and why the other half could be printed on a billboard.

1. Two keys, two jobs

Symmetric crypto (L15) has one problem it can't solve alone: both sides need the same secret key first. How do you give a partner bank an AES key without someone copying it on the way?

Asymmetric cryptography (also called public-key cryptography) uses a key pair: two mathematically linked keys. The public key can be shared with anyone. The private key never leaves its owner. Knowing the public key doesn't let you work out the private one.

An analogy: you hand out open padlocks (public key) to anyone who asks, and you keep the only key that opens them (private key). Anyone can lock a box for you; only you can open it. Technically, the pair supports two different operations, and mixing them up is the most common beginner mistake:

 ENCRYPT TO someone            SIGN WITH your own key
 (confidentiality)             (integrity + authenticity)

 sender                        signer
   │ uses RECIPIENT'S            │ uses OWN private key
   │ public key                  ▼
   ▼                           message + signature
 ciphertext ──sent──▶            │ ──sent──▶ anyone
   │                             ▼
   ▼ recipient's               verifier uses SIGNER'S
   private key decrypts        public key: "valid" or not

 Only the recipient can read.  Anyone can check; only the
                               private-key holder could sign.

You met the right-hand side in L01 and L11: a CA signs a certificate, and your client verifies it with the CA's public key. Signing doesn't hide anything; it proves who produced the data and that it wasn't changed. That's integrity and authenticity, not confidentiality, the distinction L01 drilled. L17 covers signatures in depth.

2. Slow and small, so we go hybrid

Asymmetric math is expensive, and RSA can only encrypt a message shorter than its key. On this Mac (Apple M5 Pro, openssl speed), RSA-3072 managed about 1,100 private-key operations a second, while AES-256-GCM pushed about 9.5 GB a second. With RSA-3072 and OAEP-SHA-256 padding, the largest message you can encrypt is 318 bytes.

So real systems use hybrid encryption: asymmetric crypto moves a small random key, and symmetric crypto (an AEAD such as AES-GCM, L15) encrypts the actual data.

 sender                                         recipient
 1. random 256-bit AES key K
 2. AES-GCM(K, 50 MB file) ─── ciphertext ─────▶
 3. RSA-OAEP(recipient pub, K) ─ wrapped K ────▶ 4. private key
                                                    unwraps K
                                                 5. K decrypts
                                                    the file

TLS does the same thing with a key agreement instead of key wrapping (section 4). AWS KMS does a cousin of it called envelope encryption, which L19 covers.

3. RSA vs elliptic curves

RSA (1977) rests on one fact: multiplying two huge primes is easy, but factoring the product back into them is extremely hard. Your public key contains the product n; the private key is built from the primes. A toy version with tiny numbers:

 primes p=61, q=53       n = 3233 (public modulus)
 public exponent e = 17  private exponent d = 2753
 encrypt m=65:  65^17   mod 3233 = 2790
 decrypt:       2790^2753 mod 3233 = 65
 Attack: factor 3233 → 61 × 53, rebuild d. Trivial here;
 infeasible for a 3072-bit n with known classical methods.

Textbook RSA (that raw formula) is unsafe: the same message always gives the same ciphertext, and an attacker can multiply ciphertexts to make predictable changes. Real RSA adds randomized padding. For encryption use OAEP. The older PKCS#1 v1.5 encryption padding leaks through error messages (Bleichenbacher, 1998, and it was still found in big-vendor TLS stacks in 2017, the ROBOT attack). For signatures, PSS is preferred, though PKCS#1 v1.5 signatures are still widely used and not broken the same way.

Elliptic-curve cryptography (ECC) rests on a different hard problem (the elliptic-curve discrete logarithm) and needs far smaller keys for the same strength. The curves you'll meet are P-256 (a NIST curve, used by ECDSA and ES256) and Curve25519, used as X25519 for key agreement and Ed25519 for signatures. Equal strength, per NIST SP 800-57 Part 1 Rev. 5, Table 2:

That's why an Ed25519 public key is 32 bytes while an RSA-3072 one is about 400. Pick Ed25519 or P-256 for new work unless something forces RSA; if it does, use 3072 bits or more.

4. Diffie-Hellman: a shared secret in public

Two people want the same secret, but every message between them is overheard. Diffie-Hellman (DH) solves it. The classic paint-mixing picture:

       Alice                public            Bob
  common: yellow  ◀──── agreed openly ────▶  common: yellow
  secret: red                               secret: blue
  mix → orange   ────── orange ──────▶
                 ◀────── green ───────      mix → green
  orange-from-Bob? no: green + red          orange + blue
         = brown                                = brown

 Eavesdropper has yellow, orange, green. Un-mixing paint to
 recover red or blue is the hard step, so no brown for them.

The precise version swaps paint for modular arithmetic. Public: a prime p and a base g. Alice picks secret a and sends A = g^a mod p; Bob picks b and sends B = g^b mod p. Each raises the other's value to their own secret: B^a = A^b = g^(ab) mod p. With p=23, g=5, a=6, b=15: Alice sends 8, Bob sends 19, and both compute 2. Recovering a from 8 is the discrete logarithm problem: easy at this size, infeasible at real sizes.

ECDH does the same on an elliptic curve. In L10's TLS 1.3 handshake, the key_share was an X25519 public value, and "ephemeral" (the E in ECDHE) meant fresh secrets for every connection, which is what gives forward secrecy. Plain DH doesn't prove who is on the other end, though; that's why the server also signs the handshake with its certificate key.

5. The quantum asterisk

Shor's algorithm (1994) would let a large enough quantum computer factor and solve discrete logs efficiently, breaking RSA, ECC and DH alike. No such machine exists yet, but harvest now, decrypt later is a threat today: record encrypted traffic now, decrypt it once the machine arrives. AES and SHA-2 are much less affected.

NIST published replacements in August 2024: FIPS 203 (ML-KEM) for key establishment, FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for signatures. The X25519MLKEM768 group you saw offered in L10 is a hybrid: it runs X25519 and ML-KEM-768 and combines both secrets, so an attacker must break both. The first deep dive covers what to do about it.

🧪 Worked example: who holds which key in a typical stack

The JWKS (JSON Web Key Set) that a gateway such as Kong, or a service, fetches shows the size difference directly (values shortened, IDs made up):

{"keys": [
  {"kty": "RSA", "kid": "rsa-2026-01", "alg": "RS256",
   "e": "AQAB", "n": "sXch...Qw (342 chars for RSA-2048)"},
  {"kty": "EC", "kid": "ec-2026-01", "alg": "ES256",
   "crv": "P-256", "x": "f83O...J0", "y": "x_FE...4E"}
]}

RS256 is an RSA (PKCS#1 v1.5) signature with SHA-256; ES256 is ECDSA on P-256. Both are signatures: the token is readable by anyone, and the key pair only proves the IdP issued it. (L25 covers JWT pitfalls.) The same rule holds for a KMS key such as aws kms create-key --key-spec ECC_NIST_P256 --key-usage SIGN_VERIFY: callers with kms:Sign can produce signatures, but nobody can download the private key.

🛠 Try it (optional, ~5 min)

Make a throwaway key pair in a temp directory. This never touches ~/.ssh. -N '' means "no passphrase", fine for a demo key you'll delete, never for a real one. ssh-keygen ships with macOS; the output below is from this Mac (OpenSSH 10.5p1).

$ cd "$(mktemp -d)"
$ ssh-keygen -t ed25519 -C "you@example.com" -f ./demo -N ''
Generating public/private ed25519 key pair.
...
The key fingerprint is:
SHA256:upmzuUPwPPgVfkIZ8nFDVlpQLbJwILGn8oy6povBzaI you@example.com

$ cat demo.pub
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAICxnfJPPSR7e0kTDDqBLiCL7gr4
aTEKNwAjNa6PkltYF you@example.com          (one line, wrapped)
$ ls -l demo demo.pub
-rw-------  1 you  wheel  411 Nov  6 18:44 demo
-rw-r--r--  1 you  wheel   97 Nov  6 18:44 demo.pub
$ ssh-keygen -y -f demo      # rebuild public from private
$ ssh-keygen -lf demo.pub    # fingerprint again
256 SHA256:upmz...BzaI you@example.com (ED25519)

What to look for:

• The private file is -rw------- (owner only); the public one is world-readable, on purpose.
• ssh-keygen -y recreates the public key from the private key. The reverse is impossible.
• The fingerprint is a SHA-256 hash (L14) of the public key: a short ID to compare by eye.
• Run it again with -t rsa -b 3072 and compare: the RSA .pub file was 569 bytes here, versus 97.
• When you're done, delete the temp directory (cd .. && rm -rf the path mktemp printed).

🧠 Key takeaways

• Encrypt to someone's public key; sign with your own private key. Different jobs, different keys.
• Asymmetric crypto is slow and size-limited, so it only moves keys; AES-GCM moves the data.
• RSA needs 3072 bits for 128-bit strength; Ed25519 and P-256 get there with 256-bit keys.
• Diffie-Hellman agrees on a secret in public; ECDHE in TLS adds forward secrecy.
• Quantum computers would break RSA, ECC and DH alike; hybrid ML-KEM is already in your handshakes.

📖 Words to know

⏭ Next time

L17 · Digital signatures and MACs: what a signature actually proves, how HMAC does a similar job with a shared key, and how to verify a webhook so nobody can fake one.

What a quantum computer would actually break

Two quantum algorithms matter, and they hit very different targets:

 Shor (1994)  factoring + discrete logs ──▶ BROKEN
              RSA, DH, ECDH, ECDSA, Ed25519, X25519

 Grover (1996) brute-force search speed-up ──▶ WEAKENED
              AES-256 behaves like ~128-bit: still fine
              SHA-256, HMAC-SHA-256: still fine

So the problem is almost entirely public-key crypto: key exchange and signatures. Your AES-256-GCM data at rest (and KMS's SYMMETRIC_DEFAULT keys, which are AES-256-GCM) aren't the worry.

The two halves have different deadlines:

• Key exchange is urgent. A recording of today's TLS session can be decrypted whenever a quantum computer appears. That's harvest now, decrypt later.
• Signatures are less urgent. A forged signature only helps an attacker after the machine exists, and you can switch signature algorithms before then. Long-lived trust anchors (root CAs, firmware signing keys) are the exception, because they take years to replace.

Is your data's shelf life longer than the clock?

Michele Mosca's rule of thumb puts it as three numbers:

 X = years the data must stay secret
 Y = years it takes you to migrate
 Z = years until a quantum computer can break it

 if X + Y > Z  ──▶ you are already late

 now ──────────[ Y: migrate ]───────▶
 now ─────────────────[ X: data must stay secret ]──────▶
 now ─────────────────────────[ Z: ? ]──▶  overlap = loss

Account numbers, policy records and tax IDs have an X of decades, and Z is honestly unknown. That's why financial firms treat PQ key exchange as a now problem.

The new standards (August 2024)

A KEM (key encapsulation mechanism) is a slightly different shape from DH: the client sends a public key, the server "encapsulates" a fresh secret to it and returns a ciphertext, and both end up with the same secret. Size is the main cost you'll notice: kilobytes where you had bytes.

Hybrid: belt and braces

ML-KEM is new, and new schemes sometimes fall to classical attacks. So TLS combines it with the old one:

 X25519MLKEM768 key_share (client → server, ~1,216 bytes)
   ├── ML-KEM-768 public key  (1,184 B) ──▶ secret S1
   └── X25519 public key      (   32 B) ──▶ secret S2
 session keys derived from S1 ‖ S2
 attacker must break BOTH ML-KEM and X25519

Where you'll see it today:

• Browsers. Chrome has sent X25519MLKEM768 by default since version 131 (November 2024). Cloudflare has reported that a majority of human web traffic to it now uses PQ key exchange.
• OpenSSL 3.5+ offers it by default. Check with openssl list -kem-algorithms (Homebrew OpenSSL; macOS's /usr/bin/openssl is LibreSSL and doesn't have the list command).
• OpenSSH 10.0+ uses mlkem768x25519-sha256 by default; 10.1+ warns when a connection falls back to a non-PQ exchange. Run ssh -Q kex | grep mlkem.
• AWS. Since November 2025, ALB and NLB offer opt-in PQ TLS policies, such as ELBSecurityPolicy-TLS13-1-2-Res-PQ-2025-09. KMS now has ML_DSA_* and ML_KEM_* key specs.

The official clock

NIST IR 8547, finalized in October 2026, sets the schedule: RSA, ECDSA, EdDSA, DH and ECDH are deprecated after 2030 (still allowed, but you must justify the risk) and disallowed after 2035, at every key size. US federal high-value systems face earlier deadlines (PQ key establishment by the end of 2030). Even if your organization isn't federal, regulators and auditors tend to borrow these dates.

🧪 Worked example: a PQ to-do list for a typical API stack

1. Inventory. List where public-key crypto runs: ALB/NLB listeners, the gateway's TLS and mTLS (Kong in the examples, L11), service-to-database TLS, SSH to bastions and GitHub, JWT signing keys, KMS asymmetric keys, partner SFTP/PGP feeds. You can't migrate what you can't find.
2. Key exchange first, on long-lived data. Move internet-facing listeners carrying sensitive customer data, such as financial records, to a PQ policy, and check your clients (JDK, Python ssl, Go) can negotiate it.
3. Crypto agility. Make algorithms configuration, not code. A JWT verifier that reads alg and the key from a JWKS (with an allow-list) can switch later; one with RS256 hard-coded can't.
4. Signatures later, but plan. Track your IdP's, CA's and code-signing vendors' ML-DSA roadmaps. Certificates will grow, so watch header and handshake size limits.
5. Don't touch AES-256 just for quantum. It's not the weak link.

🛠 Try it (~3 min)

$ openssl version
OpenSSL 4.1.0 23 Oct 2026 (Library: OpenSSL 4.1.0 23 Oct 2026)
$ openssl list -kem-algorithms | grep -i mlkem
  X25519MLKEM768 @ default
  X448MLKEM1024 @ default
  SecP256r1MLKEM768 @ default
$ ssh -Q kex | grep mlkem
mlkem768nistp256-sha256
mlkem768x25519-sha256

If your OpenSSL is older than 3.5, the first list will have no ML-KEM entries; that's the inventory problem in miniature.

🧠 Extra takeaways

• Quantum breaks public-key crypto (Shor), not AES-256 or SHA-256 (Grover only dents them).
• Key exchange is urgent because of harvest now, decrypt later; signatures can follow.
• Hybrids like X25519MLKEM768 keep you safe if either half holds.
• NIST IR 8547: classical public-key crypto deprecated after 2030, disallowed after 2035.

Pick the right key type

 ed25519        ✔ default choice: small, fast, no tricky params
 ed25519-sk     ✔✔ private key lives on a FIDO2 security key;
                   a laptop compromise can't copy it
 ecdsa (P-256)  ✔ fine; use if policy requires NIST curves
 rsa ≥ 3072     ~ only for old servers that lack ed25519
 rsa 1024/dsa   ✘ weak; DSA was removed from OpenSSH 10.0

ssh-keygen -t ed25519-sk needs a hardware key that supports FIDO2. You'll touch it for each use, which also defeats malware quietly using your key. This Mac's OpenSSH 10.5 even lists an experimental hybrid ssh-mldsa44-ed25519@openssh.com key type, a sign of where SSH is heading.

Passphrase + agent: protected and convenient

A private key file with no passphrase is a password written on a sticky note: anyone who copies ~/.ssh/id_ed25519 from a backup or a stolen laptop is you on GitHub. Give real keys a passphrase, and let an SSH agent hold the unlocked key in memory so you type it once:

 ┌──────── your laptop ────────┐
 │ ~/.ssh/id_ed25519            │       ┌───────────┐
 │  (encrypted with passphrase) │       │  GitHub   │
 │        │ unlock once         │       │           │
 │        ▼                     │ 1 challenge       │
 │ ssh-agent (key in memory) ◀──┼───────┤           │
 │        │ 2 signs challenge   │       │           │
 │        └─────────────────────┼──────▶│ 3 verifies│
 └──────────────────────────────┘ sig   │ with your │
   private key never leaves             │ public key│
                                        └───────────┘

On macOS, ssh-add --apple-use-keychain ~/.ssh/id_ed25519 stores the passphrase in Keychain, and UseKeychain yes in ~/.ssh/config reuses it. The server sends a challenge, and your agent signs it: SSH login is a signature, not encryption to a public key.

Agent forwarding (ssh -A) is the trap. It lets the remote host ask your agent to sign things. Anyone with root on that bastion can use your key to reach GitHub as you while you're connected. To hop through a bastion, use ssh -J bastion target (ProxyJump) instead: the connection is tunnelled, and your agent stays on your laptop.

Check the other side's key too

The first time you connect, SSH shows the server's host-key fingerprint and asks if you trust it (TOFU, trust on first use). Compare it with the fingerprints GitHub publishes in its docs before typing yes. After GitHub's 2023 RSA host key rotation, the right response to REMOTE HOST IDENTIFICATION HAS CHANGED! was to check GitHub's announcement and remove the old line with ssh-keygen -R github.com, not to blindly delete known_hosts.

Signing Git commits with the same tools

Git's user.email is just a string. Anyone can make a commit that claims to be you. Since Git 2.34 you can sign commits with an SSH key, and GitHub shows Verified when the signature matches a signing key on your account:

git config --global gpg.format ssh
git config --global user.signingkey ~/.ssh/id_ed25519.pub
git config --global commit.gpgsign true
git config --global gpg.ssh.allowedSignersFile \
  ~/.config/git/allowed_signers

Then add the same public key in GitHub under Settings → SSH and GPG keys as a Signing Key (authentication and signing are separate entries). Branch protection rules can then require signed commits on main, and GitHub's vigilant mode flags unsigned commits that claim to be yours.

🧪 Worked example: sign, verify, tamper (run on this Mac)

ssh-keygen -Y is the signing engine Git uses. With the demo key from today's Try it:

$ echo "deploy main @ 3f2a9c1" > msg.txt
$ ssh-keygen -Y sign -f demo -n file msg.txt
Signing file msg.txt
Write signature to msg.txt.sig

$ echo "you@example.com $(cat demo.pub)" > allowed_signers
$ ssh-keygen -Y verify -f allowed_signers \
    -I you@example.com -n file -s msg.txt.sig < msg.txt
Good "file" signature for you@example.com with ED25519
key SHA256:upmzuUPwPPgVfkIZ8nFDVlpQLbJwILGn8oy6povBzaI

$ echo "deploy main @ 3f2a9c2" | ssh-keygen -Y verify \
    -f allowed_signers -I you@example.com -n file \
    -s msg.txt.sig
Signature verification failed: incorrect signature
Could not verify signature.

One changed character, and verification fails (exit code 255). Notice what didn't happen: the message was never hidden. Anyone can read msg.txt. The signature protects integrity (was it changed?) and authenticity (who wrote it?), not confidentiality. Git commit signing works the same way, with -n git as the namespace so a file signature can't be replayed as a commit signature.

🧠 Extra takeaways

• Use ed25519 (or ed25519-sk on a hardware key) with a passphrase, unlocked through an agent.
• Prefer ssh -J to ssh -A; forwarding lends your key to whoever controls the remote host.
• Verify host-key fingerprints against the provider's published list; don't just type yes.
• SSH commit signing proves who made a commit and that it wasn't altered, not that it's secret.