Crypto Home

Key Exchange using Diffie-Hellman

Overview

Let's say that Alice and Bob want to exchange a symmetric cipher key. They don't really care what key they end up using, as long as they are they only two people that know it. Since neither care what the key ends up being, they will both participate in its generation.

Alice and Bob start off by agreeing to some public information, public. It doesn't matter how they come to this agreement, we'll assume that whoever started the conversation (say that's Alice) chooses the information and sends it as part of the message greeting.

Now Alice and Bob each generate a secret piece of information that they will never transmit directly - we'll call Alice's secret information a and Bob's secret information b.

Each person then combines the public information with their secret information in a certain way to generate a key fragment.

Alice: FA = f1(public, a)

Bob: FB = f1(public, b)

They then exchange the key fragments (which Eve and anyone else can easily see).

Then then each combine the key fragment received from the other party with their secret information in a certain way to generate their secret key.

Alice:  Key = f2(FB, a)

Bob: Key = f2(FA, b)

Clearly, for this to work Alice and Bob must end up with the same Key, which means that

Key = f2(f1(public, b), a) = f2(f1(public, a), b)

If the functions f1() and f2() are the same and are commutative, then this requirement is automatically satisfied. For instance, let's use simple multiplication:

Key = ((public)(b))(a) = ((public)(a))(b)

In either case, the Key is the product of the public information and both of the secret pieces.

But it must also be the case that, given the public information and the two key fragments, that no else can generate the key - that they must have either a or b as well.

Simple multiplication fails this requirement since it is a trivial matter to extract a and/or b from the transmitted key fragments using division. What about exponentiation?

Now we have

Key = (publicb)a = (publica)b

As before, both parties end up with the same key - the public information raised to the product of the two secret pieces - but, as before, the adversary (Eve) can divine the secret pieces from the key fragments using logarithms.

However, this we can do something about. It turns out that while logarithms are easy to perform in ordinary arithmetic, there is no known easy way to perform them under modular arithmetic. This is known as the Discrete Log Problem and, at the present time, is considered to be a very hard problem - meaning that no means that is significantly more efficient that brute force trial and error is known.

So now our public information is not just a number (which we'll now call g), but also a modulus (which we'll call n).

public = {g, n}

Alice's Key Fragment (sent to Bob): FA = ga mod n

Bob's Key Fragment (sent to Alice): FB = gb mod n

After exchanging Key Fragments

Alice's Key = (FB)a mod n = (gb)a mod n = (gba) mod n

Bob's Key = (FA)a mod n = (ga)b mod n = (gab) mod n

 

Alice Transmits Bob
Secret Knows Computes (Eve Knows) Secret Computes Knows
  g, n   g, n (to Bob)     g, n
a   FA = ga mod n FA (to Bob)      
      FB (to Bob) b FB = gb mod n  
  Key = FAa mod n       Key = FAb mod n  

The actual protocol can be implemented with just two transmissions:

Alice to Bob

Bob to Alice

Each party can compute the secret key as soon as they have the other person's transmission.

A Key Exchange Protocol, Not a Cipher

Notice that the Diffie-Hellman protocol results in the two way transmission of a "message" that originated with neither party - it was created as the result of the interactions between the information each party had control of. If Alice had wanted to transmit a specific secret to Bob, this protocol would not have worked. For instance, Bob has no way to determine her secret portion, a, of the key. Similarly, Alice can't determine Bob's secret portion, b, of the key.

Thus, Diffie-Hellman is limited to serving as a key exchange protocol and not a cryptographic cipher. Of course, Alice and Bob may use the exchanged key as their shared secret key for a symmetric cipher to transmit the actual message traffic - that's the whole point.

Constraints on the Public Information (g, n)

It would be nice if Alice and Bob could use any random value for both g and n, but unfortunately a bad choice for either could be disastrous.

For instance, what if the choice for (g, n) was (3, 13)? It turns out that there are only three possible values for the secret key, namely {1, 3, 9}. It goes without saying that 1 would not be a very good value, so there are only two possible keys.

The reason is that 3x mod 13 forms a small cycle of only three values, namely {1, 3, 9} because

3x+3 3x (mod 13)

3x33 3x (mod 13)

33 1 (mod 13)

An even worse choice would be (10, 15) since 10x mod 15 is always 10 (for any x greater than 0).

The longest that the cycle can be is n-1 elements (since if gx can ever generate 0 then that is all it can generate). However, this can only be achieved if n is prime. Even if n is prime, the cycle may not be maximal length (as shown by (3, 13) above).

Those values of g that do generate maximal length cycles are called primitive roots (or generators) modulo n. More specifically, a generator modulo n is a value g such that any residue modulo n that is relatively prime to n can be generated as a power of g. There is no simple way to determine what values are primitive roots for a certain modulus, but there are ways to test if candidate primitive roots really are.

The choice of prime numbers and roots when actually performing Diffie-Hellman is further complicated by trying to avoid certain specialized attacks against the protocol. The treatment of this topic is well beyond the scope of this website.

Example

Alice decides to use (g, n) = (10, 23) as the public information. She then chooses 5 as her secret information and

Alice to Bob

Bob to Alice

Each party can compute the secret key as soon as they have the other person's transmission.

Alice: Key = 135 mod 23 = 4

Bob: Key = 1912 mod 23 = 4