Diffie-Hellman Key Exchange

One of the first cryptographic techniques to become available for distributed computing was this algorithm for distributing keys.

The Problem

The problem that led to the algorithm is that Alfred and Zelda wish to exchange encrypted information. To do this they choose, because of its efficiency in encryption speed, to use a Secret/Symmetric/Session key algorithm.

Now they have a new problem: how to agree upon a key, known only to the two of them and no one else.

Of course they could meet in the dark behind Katie's Diner and each scribble the same key on a piece of paper. Besides the fact that this is subject to typographical error, loss of the paper, discovery of the paper by someone else, and other obvious problems, there is also the fact that Alfred lives in Zululand and Zelda lives in Antartica: they are not likely to meet.

So it will be nice if there will be a "spontaneous" way to both suddenly agree on a key, exchanging only information that will not compromise the knowledge of the key to those who might eavesdrop electronically on their conversation.

The Key Exchange

The Mathematics

The discrete logarithm problem is hard, even for computers. That is, given a prime number p, and a particular base element g, it is difficult from knowledge of the power g^x mod p to determine x.

So the transformation x -> g^x will be our trapdoor function.

It will be nice if g is chosen to be a primitive element of the multiplicative group Z_p, that is, the integers with arithmetic done mod p. The non-zero elements do in fact form a group under multiplication, with identity element 1, and thanks to Fermat's "little theorem" saying that a^(p-1)=1 for every a between 0 and p, any element a has the inverse a^p-2.

There are primitive elements of the group; perhaps the easiest way to find one is just try 2 (1 certainly does not work unless p=2), and if that does not work try 3, and so on. Mathematics tells us that there are many primitive elements, so we will soon hit upon one.

Back to the exchange

So Alfred and Zelda agree on a prime p, preferably rather large, and agree upon a primitive element g in Z_p. It does not create a problem for them if the whole world knows of these choices, the problem is hard even when the base is known (and meaningless if the base is not known!).

• Alfred chooses x and sends g^x to Zelda,
• Zelda chooses y and sends g^y to Alfred.

• Alfred knows x, and now knows g^y, so calculates the shared secret as (g^y)^x.
• Zelda knows y, and now knows g^x, so calculates the shared secret as (g^x)^y.

Epilogue: nothing is perfect

Along comes Malicious, who lives in Malta, and is able to eavesdrop on the communications between Alfred and Zelda, and in fact to intercept and make subsitutions in their communications. Malicious is terrible at mathematics, does not have a clue as to how to solve the discrete logarithm problem, but is malicious.

Malicious hits upon a simple scheme, which as always described as a "man-in-the-middle" attack (apparently women do not involve themselves in such attacks).

Malicious chooses numbers also, one for Alfred which he will call a, and one for Zelda, which he will call z.

1. Malicious intercepts and throws away the transmission of g^x to Zelda, and sends instead g^z.
2. Malicious intercepts and throws away the transmission of g^y to Alfred, and sends instead g^a.
3. Alfred is now happily ready to communicate with Zelda (he thinks) using the secret key g^ax.
4. Zelda is ready to happily communicate with Alfred (she thinks) using the secret key g^zy.
5. Malicious is ecstatic, knowing both secret keys and able to manipulate Alfred and Zelda from the position in the middle.

Epilogue-epilogue: Thwarting Malicious

But wait: what if Alfred and Zelda communicate their original information securely in some way? From then on they could communicate using the really secret secret-key, and Malicious could not change what they said (Malicious could still disrupt communications completely, but that would be much easier to find and fix, and in the meantime nothing secret would have been learned).

But if they know how to do that why would they ever have started down this Diffie-Hellman road?

It seems that encryption with secret-keys is very fast relative to that with public-private-keys, so the latter form of communication should be reserved for only small pieces of data, like (guess what?) keys!

Of course now who needed x and y, and p and g, why doesn't Alfred just pick a secret key, and send it sealed to Zelda, using her public key? For good measure Alfred might even sign this key using his private key.

That approach is very common, and works just fine, and gives another form of key exchange. But sometimes we want both parties to be more equal, and maybe we do not want Alfred to have special knowledge that Zelda does not have, or to be able to take advantage of his more powerful role.

So we go back to our original idea, and have Alfred protect g^x when sending it to Zelda, and Zelda protect g^y when sending it to Alfred.

Maybe we need to think about the protection needed: do we want the transmission

• signed
• sealed
• signed and sealed
• sealed and signed?

Well, lets see. Malicious knows, or certainly should be able to obtain, the public keys of both Alfred and Zelda. So Malicious could send a message sealed for Alfred, and a message sealed for Zelda, and those could have the substitute key information inside. Malicious cannot however substitute for a message signed by Alfred, as long as Zelda really has the real public key for Alfred, and not a substitute sent by Malicious. And similarly Malicious cannot substitute for a message signed by Zelda, as long as Alfred has the real public key for Zelda.

Its time to stop. You already know how to assure the above! Either let Alfred and Zelda each check with (perhaps different) certificate authorities regarding the public key of the other, or have each send a public-key certificate trusted by the other. You might even make an initial exchange, and then have one call the other on the phone so that they can exchange fingerprints of the keys supplied: Malicious lets hope has not tapped their phones, or cannot imitate both voices if he has.