The maths behind the Diffie-Hellman algorithm

Here is how to understand the mathematics behind the Diffie-Hellman key exchange protocol.

Suppose that Alice and Bob wish to create a shared secret key. They will have no control over what the key is (so Alice and Bob cannot send messages between each other directly using this protocol), but they can be assured that no-one else but them will know their eventual shared secret key (at least, not without the adversary doing an unfeasibly large computation).

Alice chooses a large prime number (p). (By large, note that those used in real life often have about 600 decimal digits!) There are a number of quick primality testing algorithms available, so finding such primes is computationally feasible, although we won’t discuss them in this course.

For her prime, (p), she also needs to find a generator or primitive root (g). Such a number has the following important property: every integer that is not divisible by (p) can be written as a power of (g) modulo (p). That is, given an integer (A) that is not divisible by (p), we can find an integer (a) such that (A equiv g^atext{ (mod }ptext{)}). (Remember from the first week, this notation means that (p) divides (A – g^a).)

Example

3 is a primitive root of the prime 7. To see this, we calculate the first six powers of 3 (3, 9, 27, 81, 243, 729) and reduce them mod 7: this gives the numbers 3, 2, 6, 4, 5, 1: all the numbers from 1 to 6. Any integer (A) that is not divisible by 7 must be equivalent, when working mod 7, to one of the numbers 1 to 6, and we’ve just checked that we can then find an integer (a) such that (A equiv 3^a text{ (mod 7)}).

That such a (g) should exist is quite a surprisingly deep result. Proving this result, whilst very interesting, would take us too far afield from our main purpose, but it essentially comes down to the fact that the non-zero residue classes modulo (p) form a cyclic group under multiplication: if you’re interested in learning more then this Wikipedia page is a good place to get started.

Having found a prime (p) and generator (g), Alice shares them publicly.

She also thinks up a secret exponent (a) that she tells no-one. She calculates (g^a text{ (mod }ptext{)}) and calls this number (A), which she reduces mod (p) and shares with Bob. It’s important to know that she must reduce by modulo (p) for this to be secure. That is, (A) should be an integer between (1) and (p-1). It’s also important to recognise that we assume a malicious eavesdropper may obtain the value of (A). But because Alice tells no-one her secret exponent (a), we may assume that the eavesdropper doesn’t know the value of (a).

Similarly Bob thinks up a secret exponent (b) and calculates (B equiv g^b text{ (mod }ptext{)}). He shares this with Alice.

Here’s a summary of who knows what:

Alice can now take Bob’s shared (B) and raise it to the power of her secret (a), finding (K equiv B^a text{ (mod }ptext{)})

Bob can similarly take Alice’s shared (A) and raise it to the power of his secret (b), calculating (K equiv A^b text{ (mod }ptext{)}).

The magic is that they have both obtained the same value of (K), even though they got there via different calculations! To see this, recall that (B = g^b text{ (mod }ptext{)}), and note that Alice’s calculation is

[K = B^a = (g^b)^a = g^{b times a} text{ (mod }ptext{)}]

whereas Bob finds

[K = A^b = (g^a)^b = g^{a times b} text{ (mod }ptext{)}.]

In these two calculations, we used the law of indices which says that ((g^b)^a = g^{ab}), and we used the fact that the usual rules of arithmetic are preserved when you reduce modulo (p).

This whole process relies on the fact that it is easy to calculate powers of numbers when reducing modulo (p). But if you are told (A) (and (p) and (g)), then for large (p) it is generally very difficult to find the (a) such that (A equiv g^a text{ (mod }ptext{)}). This is known as the discrete logarithm problem. It is this discrepancy – it is easy to go one way, but hard to go the other – that makes this a suitable trapdoor function.