Public-Key Cryptography — Motivation and Key Exchange

Corresponds to Katz & Lindell, Introduction to Modern Cryptography, Chapter 9.

Motivation: where do shared keys come from?

IntuitionThe gap in everything so far

Chapters 1–6 solved secure communication given a shared secret key. But a key can’t be sent over the insecure channel it is meant to protect: the eavesdropper would get it too. This chapter explains why private-key cryptography alone cannot close that gap in open systems like the Internet, and introduces the idea that did: asymmetric (public-key) cryptography.

Limitations of private-key cryptography

The key-management problem

WarningKey distribution

Secure channels (trusted couriers carrying key material) are available to governments and militaries, not ordinary users. (The Washington–Moscow hotline is rumoured to have used a one-time pad hand-carried by diplomats.)
Physical meetings work within an organisation (a manager shares a key with each new employee on day one), but don’t scale to every pair of employees, especially across locations.
A trusted “controller” (say, the IT manager) can generate a new employee’s keys and send each existing employee their share, encrypted under the key they already share with the controller. That is cumbersome, and the controller knows every key: a dishonest controller reads all internal communication.

WarningKey storage

With $U$ users who all talk pairwise, there are $\binom U2 = \Theta(U^2)$ keys, and each user holds $U - 1$ , plus keys for servers and databases. More keys means more logistics and more to steal: malware has been deployed specifically to exfiltrate keys. Smartcards (tamper-resistant hardware that holds keys and computes with them) protect a few keys well but lack memory for thousands. Governments can afford a locked room full of keys; industry and individuals can’t.

ImportantOpen systems are out of reach

Private-key cryptography works, awkwardly, in closed systems where keys can be distributed physically. It cannot serve open or ad-hoc settings: buying something online, or emailing a colleague abroad you have never met.

Private-key solutions are insufficient for secure communication in open systems where parties can’t physically meet or interact only transiently.

Key distribution centers

DefinitionKey distribution center (KDC)

Everyone trusts one server (run by, say, the IT department). Each user shares one long-term key with the KDC, set up on their first day. When Alice wants to talk to Bob:

Alice tells the KDC she wants to talk to Bob;
the KDC picks a fresh session key $k$ and sends it to Alice encrypted under $k_A$ , and to Bob encrypted under $k_B$ ;
Alice and Bob communicate under $k$ and erase it afterwards (they can always ask again).

This is only a sketch: real protocols need much more care, and formal analysis is beyond the book.

Advantages	Disadvantages
Each user stores one key (smartcard-friendly)	One point of compromise: break the KDC and you break everyone; insiders with KDC access read everything
Joining or leaving touches only one key	One point of failure and a heavy load: if the KDC is down, no secure communication
The KDC can be heavily protected	Replication helps availability but adds attack surface and makes updates harder to keep consistent

The earlier “controller” was effectively an offline KDC (users still hold many keys). An online KDC is what lets each user hold just one.

NoteNeedham–Schroeder, tickets and Kerberos

Engineering detail (Needham–Schroeder): the KDC sends both encrypted copies to Alice, and Alice forwards Bob’s copy, the ticket, herself. The KDC never has to wait on an offline Bob. A ticket is a credential: “Alice may talk to Bob”, or “Alice may read this disk on this server”. Kerberos (MIT) implements this for authentication and secure communication, and secures Windows domains (Windows 2000 on). In practice the user–KDC secret is usually a password, which raises its own problems (guessing attacks). See security-in-distributed-systems for the systems view.

WarningWhat KDCs don’t fix

A KDC eases distribution and storage inside one trusted organisation (and, extended, among mutually trusting organisations). It still assumes an initial secure channel to the KDC, so it can’t help on the open Internet.

The public-key revolution

IntuitionAsymmetry

In New Directions in Cryptography (1976), Diffie and Hellman argued that cheap digital hardware was creating commercial demand for cryptography that removes the need for secure key-distribution channels and provides a digital equivalent of a written signature. Their key observation: some operations are easy to do and hard to undo. A padlock snaps shut without a key; a vase shatters easily but can’t be reassembled; multiplying primes is easy but factoring is hard. That suggests an encryption scheme whose encryption and decryption keys differ and which stays secure even when the encryption key is public.

DefinitionPublic-key (asymmetric) cryptography

The public key encrypts (or verifies) and can be posted on a webpage or in a newspaper. The private key decrypts (or signs) and is kept secret. Each party stores only its own private key; other parties’ public keys are fetched when needed or stored publicly. Their integrity, though, must be protected: distribution needs an authenticated (not secret) channel, which is harder than it sounds.

Primitive	What it gives	Where covered
Public-key encryption	anyone can encrypt to Alice; only Alice decrypts; non-interactive (works for email to an offline recipient)	public-key-encryption-schemes
Digital signatures	anyone can verify Alice’s signature; only Alice can sign; non-repudiation (show a judge she signed a contract); certifying public keys (PKI)	digital-signatures-and-pki
Interactive key exchange	two parties with no shared secret agree on a key over a public channel, invisible to an eavesdropper; both must be online	below

Key exchange is like shouting across a crowded room and ending up with a secret no listener learns. It cannot be achieved with private-key techniques alone.

NoteWho built what

Diffie–Hellman (1976) defined all three primitives but constructed only key exchange. Rivest–Shamir–Adleman (1977) gave the first public-key encryption and signatures, from the RSA problem; variants are still the most widely used. ElGamal (1985) turned Diffie–Hellman into encryption, so DH “came very close”.

RemarkHistory

Merkle worked independently at the same time and is often credited as a co-inventor, though he published later.
GCHQ had the mathematics of public-key encryption in the early 1970s (Ellis, Cocks, Williamson, revealed in 1997) but did not appreciate its significance.
Under ITAR, cryptography papers counted as munitions. On Stanford’s legal advice, Hellman himself presented joint work with his students Merkle and Pohlig so that they would not risk prosecution. Export restrictions persisted, but have been much relaxed since 2000.

Public-key cryptography is what moved cryptography from intelligence agencies to the general public: no mass use was possible until key distribution was solved.

Diffie–Hellman key exchange

Definitions (eavesdropping adversaries)

DefinitionKey-exchange protocol

Alice and Bob run protocol $\Pi$ on input $1^n$ with random coins $r_A, r_B$ . They output $\mathrm{output}_A$ and $\mathrm{output}_B$ (an $n$ -bit key, or a group element), producing the message transcript $\mathrm{transcript}_\Pi(1^n,r_A,r_B)$ .

Correctness (Def. 9.1): $\Pr_{r_A,r_B}[\mathrm{output}_A\ne\mathrm{output}_B]\le\mathrm{negl}(n)$ .

DefinitionEavesdropping key-exchange experiment $\mathrm{KE}^{\mathrm{eav}}_{\mathrm{Eve},\Pi}(n)$ (Def. 9.2)

Choose $r_A, r_B$ and run $\Pi$ .
Pick $b\leftarrow\{0,1\}$ : $k$ is the real output if $b = 0$ , or uniform $\{0,1\}^n$ if $b = 1$ .
Eve receives $(1^n,\ \mathrm{transcript},\ k)$ and outputs $b'$ ; she succeeds iff $b' = b$ .

Secure against eavesdroppers: $\Pr[\mathrm{KE}^{\mathrm{eav}} = 1]\le\frac12 + \mathrm{negl}(n)$ . The key looks random even given the whole transcript, so it can be used for encryption, MACs and so on. (That composition is a theorem, but its proof is beyond the book.)

Component	Detail
Adversary power	passive: sees every message, changes none
Break	distinguishing the real key from random, given the transcript
Analogy	the transcript plays the role of a ciphertext, and the key the role of a plaintext bit

The protocol

AlgorithmDiffie–Hellman key exchange (Construction 9.3)

Alice runs $\mathcal G(1^n)$ to get a cyclic group $\mathbb G$ with a generator $g$ of order $m$ , and sends $(\mathbb G,g)$ to Bob. (These can also be fixed public parameters, in which case the two messages below are independent.)
Alice picks $x\leftarrow\{1,\ldots,m-1\}$ and sends $h_1 = g^x$ .
Bob picks $y\leftarrow\{1,\ldots,m-1\}$ and sends $h_2 = g^y$ .
Alice outputs $k = h_2^x$ ; Bob outputs $k = h_1^y$ .

Correctness: $h_2^x = g^{yx} = g^{xy} = h_1^y$ .

sequenceDiagram
  participant A as Alice (secret x)
  participant B as Bob (secret y)
  A->>B: group G, generator g
  A->>B: h1 = g^x
  B->>A: h2 = g^y
  Note over A: k = h2^x = g^xy
  Note over B: k = h1^y = g^xy

WarningWhich assumption is actually needed?

Discrete log hard? Eve can’t recover $x$ or $y$ . But she might compute $g^{xy}$ without them.
CDH hard? Eve can’t compute all of $g^{xy}$ . But she might learn half its bits, which could be enough to break whatever the key protects.
DDH hard: $g^{xy}$ is indistinguishable from a random group element given $g^x, g^y$ . That is exactly what security requires.

(Hierarchy: DDH ⇒ CDH ⇒ DL.)

NoteA group element is not a bit string

The key is in $\mathbb G$ , and its encoding needn’t look like uniform bits (in $\mathbb Z_p^*$ the top bit is biased towards 0). So the analysis uses $\mathrm{KE}^{\mathrm{eav}'}$ , in which the “random” key is a uniform group element. Turning a pseudorandom group element into a uniform bit string takes a randomness extractor (in practice, a key-derivation function such as HKDF).

TheoremTheorem 9.4 — DDH ⇒ DH key exchange is secure against eavesdroppers

If DDH is hard relative to $\mathcal G$ , Construction 9.3 is correct and secure in $\mathrm{KE}^{\mathrm{eav}'}$ .

ProofEve’s view is exactly a DDH instance

Eve sees $(\mathbb G,g,g^x,g^y,k)$ , with $k = g^{xy}$ if $b = 0$ and uniform $h$ if $b = 1$ . If she succeeds with probability $\frac12 + \varepsilon$ , then

$\tfrac12\Pr[\mathrm{Eve}(\ldots,g^{xy}) = 0] + \tfrac12\Pr[\mathrm{Eve}(\ldots,h) = 1] = \tfrac12 + \varepsilon$

and rearranging with $\Pr[\cdot = 0] = 1 - \Pr[\cdot = 1]$ gives

$\Pr[\mathrm{Eve}(\mathbb G,g,g^x,g^y,h) = 1] - \Pr[\mathrm{Eve}(\mathbb G,g,g^x,g^y,g^{xy}) = 1] = 2\varepsilon$

So Eve is a DDH distinguisher with advantage $2\varepsilon$ , which must be negligible. (Exponents drawn from $\{1,\ldots,m-1\}$ rather than $\mathbb Z_m$ change the distribution only negligibly.)

∎

Active attacks: man-in-the-middle

WarningBasic DH is completely insecure against an active adversary (Exercise 9.1)

Mallory sits on the wire with her own exponents $x', y'$ :

She intercepts $h_1 = g^x$ and sends Bob $g^{x'}$ instead.
She intercepts $h_2 = g^y$ and sends Alice $g^{y'}$ instead.
Alice computes $k_1 = g^{xy'}$ and Bob computes $k_2 = g^{x'y}$ . Mallory knows both ( $k_1 = h_1^{y'}$ , $k_2 = h_2^{x'}$ ).
Relay: decrypt each of Alice’s ciphertexts with $k_1$ , read (or alter) it, re-encrypt under $k_2$ for Bob, and vice versa.

Both parties see a working encrypted channel and no sign of attack. The root cause: nothing authenticates $g^x$ and $g^y$ .

ImportantImportance despite the flaw

DH was the first demonstration that number-theoretic asymmetry solves key distribution, a conceptual breakthrough.
With only private-key techniques, secure key exchange is impossible even against eavesdroppers (no shared secret to start from). Black-box separations (Impagliazzo–Rudich) suggest one-way functions alone don’t suffice.
In practice the DH core is authenticated, for example with signatures on the exchanged values or pre-shared credentials: IPsec’s IKE, and TLS’s (elliptic-curve) ephemeral DH with signed parameters. Solutions to man-in-the-middle via PKI come in Chapter 12. The basic protocol is everywhere, inside authenticated wrappers.

ExampleA one-time-pad “key exchange” is broken (Exercise 9.2)

Alice sends $s = k\oplus r$ ; Bob replies $u = s\oplus t$ ; Alice sends $w = u\oplus r = k\oplus t$ ; Bob outputs $w\oplus t = k$ .

Correct: $w\oplus t = k\oplus t\oplus t = k$ .
Insecure: Eve XORs all three messages: $s\oplus u\oplus w = (k\oplus r)\oplus(k\oplus r\oplus t)\oplus(k\oplus t) = k$ .

Each message alone is perfectly hidden (a fresh pad), but jointly they reveal $k$ . This is the “pad reuse” lesson of the one-time pad, and a concrete instance of why private-key tricks can’t do key exchange. (Worked here.)

Quick reference

Object	Statement	Note
Pairwise keys	$\binom U2 = \Theta(U^2)$ total; $U - 1$ per user	doesn’t scale; storage risk
Controller	offline key distribution	knows every key
KDC	one key per user; fresh session keys online	single point of compromise and failure
Ticket	session key under Bob’s key, carried by Alice	Needham–Schroeder, Kerberos
Public key / private key	publish one, keep one	integrity of public keys still matters
Three primitives	encryption, signatures, key exchange	DH built only key exchange
Non-repudiation	anyone can verify, only the owner can sign	contracts, PKI
KE correctness	outputs agree except with negligible probability
KE security	key looks random given the transcript	eavesdroppers only
DH	$g^x, g^y\to g^{xy}$	secure iff DDH (eavesdroppers)
Proof	KE advantage $\varepsilon$ ⇒ DDH advantage $2\varepsilon$
Group element vs string	extract/derive the key	KDFs in practice
MitM	Mallory runs DH with each side	needs authentication
Private-key-only key exchange	impossible	Exercise 9.2 shows why

Facts to keep to hand

Private-key cryptography has a key-management problem it can’t solve. Pairwise keys scale quadratically and are hard to store, and every scheme needs an initial secure channel. That rules out open systems.
KDCs make private-key cryptography workable inside one organisation. One key per user, fresh session keys and tickets (Kerberos), at the price of a trusted, attractive, single point of compromise and failure.
Public-key cryptography exploits computational asymmetry. Publishable keys enable encryption to strangers, signatures with non-repudiation, and key exchange from no shared secret.
Diffie–Hellman key exchange is secure against eavesdroppers exactly under DDH, not merely DL or CDH. It is wide open to man-in-the-middle attacks unless the exchanged values are authenticated, which is how it is used everywhere today.

References

Katz & Lindell, Introduction to Modern Cryptography — Chapter 9
Diffie & Hellman, “New Directions in Cryptography” (1976)
Kaufman, Perlman & Speciner, Network Security — KDCs, Needham–Schroeder, Kerberos
Levy, Crypto (2001) — the history of the public-key revolution

Related