Section 6: Asymmetric (Public-Key) Cryptography

Everything we have covered so far — block ciphers, stream ciphers, MACs — assumes that the two communicating parties already share a secret key. That assumption hides an enormous practical problem, and solving it required one of the most important ideas in the history of computer science: the split of a single key into a public half and a private half. This section covers RSA, Diffie–Hellman, elliptic curves, digital signatures, and the public-key infrastructure that glues them into the systems you use every day.

1. The key distribution problem

Symmetric cryptography is fast and strong, but it needs a shared secret. How do two people who have never met agree on one? Before the 1970s the answers were couriers, diplomatic pouches, and codebooks — expensive, slow, and vulnerable at every hop. Worse, the problem scales terribly: in a network of n users where every pair wants a private channel, you need a distinct key for each pair, which is

      n(n - 1)
      --------   keys.
         2

  10 users     ->        45 keys
  1,000 users  ->   499,500 keys
  1,000,000    -> ~500 billion keys
    

Every one of those keys must be generated, distributed securely, stored, and eventually rotated. This is the key distribution problem, and for most of the 20th century it was considered a fundamental, unavoidable cost of secrecy.

Then, in 1976, Whitfield Diffie and Martin Hellman published New Directions in Cryptography and shattered the assumption. Their revolutionary idea: what if the key used to encrypt did not have to be the same as the key used to decrypt? Split the key into two mathematically linked halves. Publish one half to the entire world — the public key. Keep the other half secret — the private key. Anyone can encrypt a message to you using your public key, but only you, holding the private key, can decrypt it. Suddenly, no prior shared secret is needed at all.

Symmetric vs asymmetric at a glance

Because asymmetric operations are so slow, real systems are hybrid: public-key cryptography is used once, at the start of a session, to establish a symmetric key; the actual data is then encrypted with AES or ChaCha20. TLS, SSH, Signal, and PGP all work this way.

2. RSA — the full math walkthrough

RSA (Rivest, Shamir, Adleman, 1977) was the first practical public-key encryption and signature system, and it is still everywhere. Its security rests on a simple asymmetry: multiplying two large primes is trivial, but recovering the primes from their product — factoring — appears to be extremely hard.

Key generation

1. Choose two large random primes p and q (in practice each about 1024–2048 bits).
2. Compute the modulus n = p × q.
3. Compute Euler’s totient φ(n) = (p − 1)(q − 1) — the count of integers below n that are coprime to n.
4. Choose a public exponent e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. Almost everyone uses e = 65537 (a prime with only two 1-bits, making encryption fast).
5. Compute the private exponent d = e−1 mod φ(n) — the modular inverse of e, found with the extended Euclidean algorithm. So e × d ≡ 1 (mod φ(n)).

The public key is (n, e). The private key is d (and p, q, which must stay secret — anyone who learns them can recompute d).

Encryption and decryption

  Encrypt (with public key):   c = m^e  mod n
  Decrypt (with private key):  m = c^d  mod n
    

The message m is treated as a number smaller than n. Note the beautiful symmetry: the same operation, modular exponentiation, is used in both directions — only the exponent differs.

Why it works: Euler’s theorem

Euler’s theorem states that for any m coprime to n:

  m^φ(n)  ≡  1  (mod n)
    

Now trace what decryption does to a ciphertext. Since e × d ≡ 1 (mod φ(n)), we can write e × d = 1 + kφ(n) for some integer k. Then:

  c^d = (m^e)^d = m^(ed) = m^(1 + kφ(n))
      = m × (m^φ(n))^k
      ≡ m × 1^k          (Euler)
      ≡ m  (mod n)
    

Decryption exactly undoes encryption. (A slightly more careful argument using the Chinese Remainder Theorem shows this also holds for the rare m not coprime to n.) The private exponent d works because it is the arithmetic mirror of e in the hidden group of order φ(n) — and computing φ(n) requires knowing p and q, i.e. factoring n.

A complete worked toy example

1. Choose primes: p = 61, q = 53.
2. Modulus: n = 61 × 53 = 3233.
3. Totient: φ(n) = (61 − 1)(53 − 1) = 60 × 52 = 3120.
4. Public exponent: pick e = 17. Check: gcd(17, 3120) = 1. Valid.
5. Private exponent: solve 17d ≡ 1 (mod 3120). The extended Euclidean algorithm gives d = 2753. Check: 17 × 2753 = 46801 = 15 × 3120 + 1. Correct.
6. Encrypt m = 65: c = 6517 mod 3233 = 2790. (Computed by square-and-multiply: 65² = 4225 ≡ 992; 992² ≡ 1232 (m⁴); 1232² ≡ 1547 (m⁸); 1547² ≡ 789 (m¹⁶); finally m¹⁶ × m = 789 × 65 = 51285 ≡ 2790 mod 3233.)
7. Decrypt c = 2790: m = 27902753 mod 3233 = 65. The original message is recovered.

Security and key sizes

Breaking RSA (as far as anyone publicly knows) requires factoring n. The best classical algorithm, the General Number Field Sieve, runs in sub-exponential but super-polynomial time; the current public factoring record is RSA-250, an 829-bit modulus (2020). Consequently, 1024-bit RSA is broken-adjacent and forbidden, 2048 bits is the accepted minimum, and 3072 bits or more is preferred for anything that must stay secure past 2030. Note also that a large fault-tolerant quantum computer running Shor’s algorithm would factor n in polynomial time — a major driver of post-quantum cryptography.

3. Diffie–Hellman key exchange

Diffie–Hellman (DH) solves a different problem than RSA: it lets two parties who have never met agree on a shared secret over a public channel, even while an eavesdropper records every message.

The classic intuition is paint mixing. Alice and Bob publicly agree on a common starting color (yellow). Each secretly mixes in a private color: Alice adds red, Bob adds blue. They swap the resulting mixtures in the open — orange and green fly across the wire. Finally each adds their own private color to the other person’s mixture. Both end up with yellow + red + blue: the identical muddy brown. The eavesdropper sees yellow, orange, and green, but unmixing paint to recover the secret colors is infeasible.

The math replaces paint with modular exponentiation. Publicly fixed: a large prime p and a generator g.

        ALICE                    public channel                    BOB
  --------------            --------------------           --------------
  pick secret a                                            pick secret b

  A = g^a mod p   ---------------- A ---------------->
                  <--------------- B -----------------     B = g^b mod p

  s = B^a mod p                                            s = A^b mod p

        \______________  identical shared secret  ______________/
                     s = g^(ab) mod p  on both sides

  Eve sees:  p, g, A, B   — but recovering a from A = g^a mod p
             is the DISCRETE LOGARITHM problem: believed hard.
    

Why do both sides get the same value? Exponents commute: Ba = (gb)a = gab = (ga)b = Ab (mod p). The eavesdropper holds ga and gb but needs gab; the only known route is computing a discrete logarithm, which — like factoring — is believed intractable for well-chosen 2048-bit-plus primes.

Ephemeral DH and forward secrecy. If Alice and Bob generate fresh secrets a and b for every session and delete them afterwards (DHE / ECDHE, the E for ephemeral), then even an adversary who records all traffic for years and later steals the server’s long-term private key still cannot decrypt old sessions — the session secrets no longer exist anywhere. This property, forward secrecy, is mandatory in TLS 1.3 and is the reason ephemeral key exchange has displaced RSA key transport entirely.

4. Elliptic Curve Cryptography

RSA and classic DH keys keep growing because sub-exponential attacks (number field sieve) chip away at them. Elliptic curves offer a different group in which the discrete logarithm problem has no known sub-exponential attack — so keys can be dramatically smaller for the same security:

Smaller keys mean faster computation, smaller certificates, and less bandwidth — which is why virtually all new deployments are elliptic-curve based.

The curve and point addition

An elliptic curve over a field is the set of points satisfying

  y² = x³ + ax + b
    

plus a special “point at infinity” that acts as zero. The magic is that the points form a group under a geometric addition rule — the chord-and-tangent construction: to add distinct points P and Q, draw the line through them; it hits the curve at exactly one more point; reflect that point across the x-axis to get P + Q. To double a point (P + P), use the tangent line at P instead.

Scalar multiplication is repeated addition: kP = P + P + … + P (k times), computed efficiently by double-and-add, just like square-and-multiply for exponentiation. The one-way function of ECC is: given a base point G and a result Q = kG, find k. This is the Elliptic Curve Discrete Logarithm Problem (ECDLP); the best known attacks take about √n steps, i.e. 2¹²⁸ work for a 256-bit curve.

Named curves

In practice everyone uses standardized curves. P-256 (NIST, 1999) dominates in certificates and TLS. Curve25519 (Daniel J. Bernstein, 2005) is increasingly favored: its parameters were derived by transparent, rigid criteria (dispelling the fear of hidden backdoors that haunts the unexplained NIST seed constants), and its Montgomery-ladder arithmetic is naturally constant-time and free of the exceptional-case bugs that plague naive P-256 implementations. Curve25519 powers key exchange (X25519) in TLS 1.3, SSH, Signal, and WireGuard; its twin Ed25519 handles signatures.

ECDH is Diffie–Hellman transplanted onto a curve: instead of ga mod p, Alice sends aG (her secret scalar times the base point) and Bob sends bG; both compute the shared point abG, whose x-coordinate is hashed into a session key. Same commutativity, same protocol flow, far smaller messages — this is the ECDHE in modern TLS cipher suites.

ECDSA is the elliptic-curve digital signature algorithm: the signer combines the message hash, their private scalar, and a fresh random nonce k into a pair (r, s) that anyone can verify with the public point. It signs everything from TLS handshakes to Bitcoin transactions. Its Achilles heel is that nonce.

5. Digital signatures

Signatures run public-key cryptography in reverse: you sign with your private key and anyone can verify with your public key. Since only you hold the private key, a valid signature proves the message came from you and was not altered — giving integrity, authentication, and non-repudiation (you cannot later deny having signed; a MAC cannot provide this, because both parties share the MAC key).

In practice you never sign the document itself — public-key operations are slow and messages can be huge. You sign a hash of it (“hash-then-sign”): the fixed-size digest stands in for the document, and the collision resistance of the hash (Section 4) guarantees the signature cannot be transplanted onto a different document.

  SIGNER                                        VERIFIER
  ------                                        --------
  document ---> SHA-256 ---> digest             receive document + signature
                               |                document ---> SHA-256 ---> digest'
                               v                signature --verify with--> digest''
                     sign with PRIVATE key                    PUBLIC key
                               |
                               v                digest' == digest''  ?
  attach signature to document ----->              YES: authentic + intact
                                                   NO:  reject
    

Three families dominate. RSA signatures (with PSS padding) are the venerable default of the X.509 certificate world — large but universally supported. ECDSA offers small, fast signatures but is fragile (the nonce problem above, plus tricky constant-time implementation). Ed25519 is the modern default: deterministic (no nonce to botch), fast, constant-time by design, with 64-byte signatures and 32-byte keys — the choice of SSH, Signal, and most new protocols.

6. PKI and certificates

Public keys solve key distribution — but create a trust problem. When your browser connects to google.com and receives a public key, how does it know that key actually belongs to Google and not to an attacker on your coffee-shop Wi-Fi? A public key is just a number; nothing about it says who owns it. The answer is Public Key Infrastructure (PKI): use digital signatures to vouch for the binding between an identity and a key.

An X.509 certificate is a signed statement: “This public key belongs to this domain name, valid from date A to date B, says the Certificate Authority (CA), signed with the CA’s private key.” Trust is arranged in chains:

  +--------------------------+
  |        ROOT CA           |   self-signed; its public key ships
  |  (offline, in your OS /  |   pre-installed in your OS and browser
  |   browser trust store)   |   trust store
  +------------+-------------+
               |  signs
               v
  +--------------------------+
  |     INTERMEDIATE CA      |   does the day-to-day issuing, so the
  |   (online issuing CA)    |   root key can stay locked in a vault
  +------------+-------------+
               |  signs
               v
  +--------------------------+
  |    LEAF CERTIFICATE      |   contains google.com and its
  |   CN = google.com        |   public key; presented to your
  |   + server public key    |   browser in the TLS handshake
  +--------------------------+
    

When a browser validates a certificate it: (1) checks that each certificate in the chain is correctly signed by the one above it, terminating at a root already in its trust store; (2) checks the validity dates; (3) checks that the domain name matches; and (4) checks revocation — whether the certificate has been cancelled before its expiry (a compromised key must be killable). Revocation uses CRLs (downloadable lists of revoked serial numbers) or OCSP (a live query to the CA, often “stapled” by the server into the handshake to protect privacy and speed).

Let’s Encrypt transformed this ecosystem in 2015 by issuing certificates for free, automatically, via the ACME protocol: a client proves control of a domain (by publishing a challenge value over HTTP or DNS), and the CA issues a short-lived 90-day certificate that renews itself. The result: HTTPS went from a paid nuisance to the default for the entire web.

Certificate Transparency (CT) addresses the remaining nightmare — a compromised or coerced CA issuing a fraudulent certificate for a domain it should not. CT requires every issued certificate to be recorded in public, append-only, cryptographically verifiable logs (Merkle trees again, from Section 4). Browsers reject certificates without CT proof, and domain owners can monitor the logs and instantly spot any certificate issued for their domain that they never requested.

Check your understanding

Further resources