The Diffie-Hellmann algorithm was ground-breaking. Its appearance provided the first answer to the problem of key exchange. It also led more or less directly to the development of asymmetric ciphers, the best known of which is RSA.
On these pages you will see frequent references to Alice, Bob and other players in the encryption process. There is a fairly well-established cast of characters in the cryptography world. The main ones we will need to think about are:
Before the Diffie-Hellmann algorithm, the area of strong encryption had been well established. The one-time pad, still the most unbreakable encryption mechanism known is a good example both of the kind of systems in use and of the major flaw. The one-time pad relies on both parties having a common list of encryption keys that are used to turn plain text into ciphertext (and back again, naturally). So how do you ensure that Alice and Bob - and only those two - have access to the encryption keys? It may be that they never meet in person, so some mechanism has to be found to get the encryption keys safely from one to the other without Eve getting hold of them.
Of course, if there is a reliable way for Alice to send a key only to Bob and vice-versa, there is no need to encrypt your messages, right? Just use that route to send the message itself. The fact is that before the work described on this page, people had to go to extraordinary lengths to ensure relatively safe transfer of encryption keys, and it was impractical to send messages themselves by the same route. All of which makes what Messrs Diffie and Hellmann did such a brilliant achievement.
Simon Singh gives an excellent account in his book The Code Book of the work of Whitfield Diffie and Martin Hellmann in developing the algorithm: I'm going to use this page to explain how the algorithm works and why it is so elegant.
Alice and Bob want to exchange some information. They would rather not let Eve see the information. They can encrypt the document using symmetric encryption provided that they can find a common encryption key and prevent Eve from knowing it.
Alice and Bob start by agreeing two numbers (j and k). These two numbers are publicly-known, so it doesn't matter if Eve knows what they are.
Alice and Bob then each think of a secret number (we'll call them Sa and Sb). They will never reveal these numbers to anyone else. However, they each run a calculation (more on this below) using S, j and k. Alice comes up with Pa and sends it to Bob. Similarly Bob comes up with Pb and sends it to Alice. Once again it doesn't matter if these numbers are intercepted by Eve.
Now comes the magic bit. Alice does another calculation using her secret value Sa and Bob's public value Pb and comes up with Xa. Bob does a similar calculation using his secret value Sb and Alice's public value Pa and comes up with Xb.
The magic of the Diffie-Hellmann algorithm is that Alice's final number Xa is the same as Bob's final number Xb. In other words, Alice and Bob have created their common key, and they have done it without passing the actual key directly between them or risking it being intercepted by anyone else.
When I first learned about Diffie-Hellmann, two aspects of this struck me as difficult to believe. First, how is it that the two numbers end up being identical? Second, how sure can Alice and Bob be that Eve (who, after all has been able to see the numbers j, k, Pa and Pb) can't work out the key Xa (or Xb - they are the same, remember)? In each case, the answer lies deep in the ingenious mathematics that underlies the process.
I use the term "dive" advisedly. There are some seriously complex concepts to take on from the word go. Let's just run through the algorithm first, running Alice and Bob's key exchange again but doing the mathematics this time.
First, Alice and Bob agree on two numbers, j and k. Alice also chooses a number, Sa, that she will keep completely secret, and uses this formula to calculate Pa.
Pa = (j ^ Sa) mod k
This says raise j to the power Sa (multiply j by itself Sa times), then divide the result by k and save only the remainder as Pa.
Bob does a similar calculation using j, k and his secret number Sb and ends up with Pb.
At this stage you may be thinking "that calculation doesn't look too difficult. Why can't Eve simply unwind it, given Pa or Pb, and work out Sa or Sb?" The answer lies in the type of calculation - modular arithmetic. Let's look at the numbers. Suppose j is 2 and k is 7 and Alice chooses 3 as her secret number.
Alice's calculation is now Pa = (the remainder of (2^3) divided by 7).
2^3 =8
8 mod 7 = 1
Pa = 1
The key step is the division mod 7. It is this that makes this a one-way function, because there are potentially a huge number of values of Alice's number Sa that would give a Pa value of 1. She has chosen 3 on this occasion, but she might have equally well chosen another number that would give a result of 1 when the answer is divided mod 7. The effort involved to find another value of Sa that gives this Pa even with small numbers like this is too much to think about, and then you don't know which of the many possible Sa values is the one Alice actually chose - they all give the same Pa.
Incidentally, this one-way (or trap-door) feature of modular arithmetic is one of the reasons that it crops up so often in cryptography. Functions that are easy to do one way but very difficult (infeasible is the term often applied) to do the other way are where cryptographers look for their tools.
So far, Alice has used her secret number Sa to create a public number Pa that she now sends to Bob. Bob does the same with the public number Pb that he has created.
Alice carries out the following calculation:
Xa = (Pb ^ Sa) mod k
And Bob carries out the following calculation:
Xb = (Pa ^ Sb) mod k
It turns out that the values the Alice and Bob have calculated, Xa and Xb are identical. They have therefore created a common key that they can use as an encryption key for exchanging encrypted data.
There is no room here for a proof of this, but I'm sure there is such a proof somewhere on the internet. However, here is a worked example to demonstrate the calculations.
Let's assume j = 5, k = 563, Sa = 9 and Sb = 14.
Pa = 5 ^ 9 mod 563
Pa = 1953125 mod 563
1953125 / 563 = 3469.138544, or 3469 with a remainder of 78. This makes Pa = 78
Now for Bob. His calculation is:
Pb = 5 ^ 14 mod 563
Pb = 6103515624 mod 563
6103515624 / 563 = 10841057.95, or 10841057 with a remainder of 534. So Pb = 534
Once keys have been exchanged, Alice can do her shared key generation:
Xa = (Pb ^ Sa) mod k
Xa = (534 ^ 9) mod 563
Xa = 3530785328217308860798464 mod 563
3530785328217308860798464 / 563 = 6271377137153301706569 with a remainder of 117
Therefore Xa = 117
And here is Bob's version:
Xb = (Pa ^ Sb) mod k
Xb = (78 ^ 14) mod 563
Xb = 308549209196654470906527744 mod 563
308549209196654470906527744 / 563 = 548044776548231742285129 with a remainder of 117
Therefore Xb = 117
The real underlying cause of the identity of these calculations is that
j ^ (Sa * Sb) mod k = 117
The other calculations provide each of the participants with a mechanism of getting an equivalent calculation to that one.