Diffie and Hellman managed to show that it was possible for two people to decide on a key without having to send information which , when intercepted, would give away the key.
The Diffie-Hellman scheme relies on the modular function XA(mod Y). The idea being that although it is easy to work this out, it is very hard to reverse the operation. This is shown in the table below - three people are working - me (sending the message), Paul (receiving the message) and Paul's Mum (trying to intercept and decode the message).
| Paul and I both agree over the phone two numbers, X and Y (so that X<Y). Paul's Mum intercepts these, so all three of us know the two numbers. In this case, Paul and I have settled upon X=7 and Y=11. |
| Me | Paul | Paul's Mum |
| I choose a number S (eg 5) and keep it secret | Paul chooses a number P (eg 4) and keeps it secret | |
| I use the formula A = XS(mod Y) to work out A: = 75 (mod 11) = 16807 (mod 11) = 10 |
Paul uses the formula B = XP(mod Y) to work out B: = 74 (mod 11) = 2401 (mod 11) = 3 |
|
| I send A to Paul | Paul sends B to me | Paul's Mum intercepts both A and B |
| I take B from Paul, and use my value of S to calculate BS (mod Y): = 35 (mod 11) = 243 (mod 11) = 1 |
Paul takes A from me, and uses his value of P to calculate AP (mod Y): = 104 (mod 11) = 10000 (mod 11) = 1 |
Paul's Mum cannot do my calculation, since although she knows B and Y, she does not know S. She cannot do Paul's calculation, since although she knows A and Y, she does not know P. |
| I now have the number 1 - this is the key to be used from now on | Paul now has the number 1 - this is the key to be used from now on | Paul's Mum does not have the number 1 - she does not know the key |
The only way Paul's Mum can work out the key is to work out either S or P first. These have been kept secret the whole time, and the only clues to their value are A and B. To work out S from A or P from B is a very difficult task, and Paul and I can be sure that she and her powerful computer will take such a long time to work it out that our messages are secure.
The Diffie-Hellman scheme was a huge step forward in cryptography, but it was not perfect - to send something to Paul, I must first communicate with him to decide on the key. This means ringing him to decide X and Y, and waiting for him to send B before I know the key. This takes quite a while, especially if Paul is working on the night-shift and anything I send won't be seen by him for 12 hours. To decide on the key takes an annoyingly long time, and it is this that RSA was to solve.
Diffie-Hellman is a secure scheme as long as large keys are used, and so it is used for key exchange. The problem of time means that RSA is by far the most common public-key algorithm, but Diffie-Hellman is still used, and is generally thought to be the second-best option after RSA.