NOTE: This is the archived 2022-23 version of these notes, and may be out of date. Current CSC110/111 students should visit the current notes page, https://www.teach.cs.toronto.edu/~csc110y/fall/notes/.
A historical limitation of symmetric-key cryptosystems was how toestablish a shared, but secret, key. If the two communicating partieswere able to meet in person, they could agree upon a shared secret keywhile physically together (assuming no one else was spying on them). Butwhat if I want to communicate with someone securely in a different cityor different country? Or—to use a more modern example—to communicatewith a server across the Internet, which I cannot hope to meet inperson?
One solution to this problem is the Diffie-Hellman keyexchange, which is an algorithm that is executed by two people (orcomputers) to compute a shared secret, while communicating in public(open to eavesdroppers). We will introduce the intuitions of theDiffie-Hellman key exchange with an analogy that uses our familiar Aliceand Bob communicating with colours. After, we will replace colours withnumbers to understand how the process works in today’s digitalworld.
Alice and Bob are mixingpaint
Suppose that Alice and Bob would like to establish a secret paintcolour that only the two of them know. They use the followingprocedure.
First, they both agree on a random, not-secret colour ofpaint to start with: yellow. They decide on this shared colour publicly,so eavesdroppers also know this colour! Second, they each choose their own secret colour, which theywill never share with each other or anyone else. In our example, Alicedecides on red and Bob chooses teal (a green-blue colour). Third, they each mix their secret colours with their sharedcolour yellow, producing a light orange for Alice and a blue for Bob.This is also done in secret. Fourth, they exchange these colours with each other, whichis done publicly. At this point, there are three not-secret colours:yellow and the two mixtures. And there are two secret colours: Alice’sred and Bob’s teal. Fifth, Alice mixes Bob’s blue colour with her originalsecret red to produce a brown. Bob mixes Alice’s light orange with hisoriginal secret teal to produce the same brown. Why are these the samebrown? Because they both consist of the same mixture of three colours:yellow (shared), red (Alice’s secret), and teal (Bob’s secret)! Finally, why is this brown a secret? Any eavesdropper has access tothree colours: the original shared yellow (from the first step), and thetwo mixtures orange and blue (from the fourth step). If we assume thatthe colour mixtures are not easily separated (i.e., it is very difficultto extract the yellow from each mixture), then the eavesdropper cannotdetermine what Alice and Bob’s secret colours were, and therefore can’tmix them together with the yellow to produce the right shade ofbrown! |  |
The Diffie-Hellman keyexchange
Unfortunately, transmitting paint across digital channels isintractable, but transmitting numbers isn’t. The Diffie-Hellman keyexchange uses some neat (yet simple) operations from modular arithmeticto play out the same scenario as our paint analogy.
Diffie-Hellman Key Exhange Algorithm
Setting: Two parties, Alice and Bob.
Result: Alice and Bob share a secret key \(k\).
Alice chooses a prime number \(p\) greater than two and an integer \(g\) such that \(2\leq g \leq p - 1\), and sends both numbers \((p, g)\) to Bob.
Alice chooses a secret number \(a \in \{1, 2, \dots, p-1\}\) and sends Bob\(A = g^a ~\%~ p\) to Bob.
Bob chooses a secret number \(b \in \{1, 2, \dots, p-1\}\) and sends\(B = g^b ~\%~ p\) to Alice.
Alice computes \(k_A = B^a ~\%~p\). Bob computes \(k_B = A^b ~\%~p\).
Then \(k_A = k_B\), and so thisvalue is the secret key \(k\) thatAlice and Bob share.
An example
Here is an example of the Diffie-Hellman key exchange in action.
- Alice starts by choosing \(p = 23\)and \(g = 2\). She sends both \(p\) and \(g\) to Bob.
- Alice chooses a secret number \(a =5\). She sends \(A = g^a ~\%~ p = 2^5~\%~ 23 = 9\) to Bob.
- Bob chooses a secret number \(b =14\). He sends \(B = g^b ~\%~ p =2^{14} ~\%~ 23 = 8\) to Alice.
- Alice computes \(k_A = B^a ~\%~ p = 8^5~\%~ 23 = 16\). Bob computes \(k_B =A^b ~\%~ p = 9^{14} ~\%~ 23 = 16\). As expected, \(k_A = k_B\), and these form the secret key\(k\)!
Correctness: Are \(k_A\) and \(k_B\) always equal?
That last sentence in the Diffie-Hellman key exchange algorithmdescription is doing a lot of work. How do we “know” that \(k_A = k_B\)? With a proof, of course!
(Correctness of Diffie-Hellman key exchange)
For all \(p, g, a, b \in \Z^+\),\((g^b ~\%~ p)^a ~\%~ p = (g^a ~\%~ p)^b ~\%~p\).
Even though the Diffie-Hellman algorithm frames the communication interms of remainders, we can analyze the numbers using modular arithmeticmodulo \(p\). In this case thecalculation involves just switching around exponents in \(g^{ab}\).
Let \(p, g, a, b \in \Z^+\). Let\(A = g^a ~\%~ p\) and \(B = g^b ~\%~ p\). We’ll prove that \(B^a ~\%~ p = A^b ~\%~ p\).
First, we have that \(A \equiv g^a \pmodp\) and \(B \equiv g^b \pmodp\). So then \(A^b \equiv (g^a)^b\equiv g^{ab} \pmod p\), and \(B^a\equiv (g^b)^a \equiv g^{ba} \pmod p\).
Since \(g^{ab} = g^{ba}\), we canconclude that \(A^b \equiv B^a \pmodp\).
So then \(A^b\) and \(B^a\) must have the same remainder whendivided by \(p\), and so \(B^a ~\%~ p = A^b ~\%~ p\).
Security: How secret is thekey?
We’ve just proved that the Diffie-Hellman key exchange iscorrect, meaning the result at the end of the algorithm is thatAlice and Bob have a shared key. But that’s not the only purpose of thisalgorithm: it must also ensure that this shared key is alsosecret, unknown to anyone other than Alice and Bob.
So let’s look at the Diffie-Hellman key exchange from the perspectiveof an eavesdropper that has access to everything Alice and Bobcommunicate to eachother. We say that Alice and Bob’s communications arepublic, while their own computing devices areprivate. So over the course of the algorithm, theeavesdropper has access to \(p\), \(g\), \(g^a ~\%~p\), and \(g^b ~\%~ p\). Thequestion is: from this information, can the eavesdropper determine thesecret key \(k\)?
One approach an eavesdropper could take is to try to compute \(a\) and \(b\) directly. This is an instance of thediscrete logarithm problem: given \(p, g, y \in \Z^+\), find an \(x \in \N\) such that \(g^x \equiv y \pmod p\). While we couldimplement a brute-force algorithm for solving this problem thatsimply tries all possible exponents \(x \in\{0, 1, \dots, p-1\}\), this is computationally inefficient inpractice when \(p\) is chosen to beextremelylarge. We’ll explore exactly what we mean by terms like“efficient” and “inefficient” more precisely in the nextchapter.
Perhaps surprisingly, there is no known efficient algorithmfor solving the discrete logarithm problem! So we say that theDiffie-Hellman key exchange is computationally secure:while there are known algorithms that eavesdroppers could use fordetermining the shared secret key, all known algorithms arecomputationally infeasible for standard primes chosen. In practice,Diffie-Hellman key exchanges tend to use primes on the order of \(2^{2048} \approx 10^{617}\), or in otherwords prime numbers with over 600 digits!
