This document describes the basic Diffie-Hellman key agreement scheme. The main reason it is here is to define the terms I use in the the accompanying paper describing advanced techniques. If you are familiar with Diffie-Hellman then just skip ahead.

Diffie-Hellman Key Agreement

Diffie-Hellman was the first Public key cryptography algorithm to become known to the public. Unlike the better known RSA algorithm, Diffie Hellman is not a public key encryption algorithm, it is a public key agreement algorithm. What this means is that rather than Alice encrypting a message under her public key and sending it to Bob to decrypt under his public key, Diffie Hellman is a mechanism that allows Alice and Bob to both agree on a common key to encrypt and decrypt a message using traditional symmetric key encryption.

One of the main reasons that Diffie-Hellman is attracting a lot more attention is that the Diffie-Hellman algorithm can be applied to mathematical fields formed from Elliptic Curves and the RSA algorithm cannot. There is also some reason to expect that any Quantum Cryptanalysis Resistant public key algorithms that are developed will be key agreement mechanisms rather than encryption since an encryption operation is reversible by definition while a key agreement mechanism need not be.

When I first started getting interested in cryptography, Diffie-Hellman was presented as an essay in the craft that had been superseded by the more capable RSA system. But over the years I have increasingly come to realize that the simplicity and flexibility of Diffie-Hellman may actually make it the superior scheme. In particular, we can actually perform mathematical operations on Diffie-Hellman keys and results.

Diffie Hellman Key Agreement

The mathematical fact at the heart of Diffie Hellman is very simple and very powerful. It is:

(e^x)^y = (e^y)^x = e^xy

e^x is simply e multiplied by itself x times:

So (e^x)^y is e multiplied by itself x.y times:

Since x.y = y.x, it doesn't matter if we multiply e by itself x times first and then multiply the result by itself y times or vice versa. The result is exactly the same in either case.

At this point, we are only missing one thing to turn this mathematical fact into a public key agreement scheme. We need to use a mathematical system in which calculating e^x is easy but working out x from the result is hard.

A simple exponent won't do because it is a nice smooth function that has an inverse function, the logarithm that we calculate very easily using the Newton-Raphson algorithm discovered in 1685.

To complete the system, we need to use a little bit of set theory. In mathematics, a commutative group is a set G with an operation * that combines any two the elements of the set a and b to produce another element that we write as a * b such that:

Closure: For all a, b in G, a * b is in G.
Associativity: For all a, b, c in G, (a * b) * c = a * (b * c)
Identity element: There exists an element i in G such that a * i = i * a = a for all a in G.
Inverse element: For every element a in G, there exists an element b in G such that a * b = b * a = i where i is the identity element.
Commutative: For all a, b in G, a * b = b * a

If these requirements appear to be a little abstract, it is because that is exactly what they are. But all they are really saying is that we are going to define a new mathematical operator on a set of 'things' that behaves in the same sort of way that we expect numbers to behave under addition.

There are many mathematical groups and more are discovered every day. But the one we use for the basic Diffie-Hellman algorithm is the one most of us learn in school as modular or 'clock' arithmetic.

If p is a prime then the operation a . b mod p on the set 1..(p-1) is a commutative group.

The number 0 is excluded because it doesn't have an inverse (a* 0 = 0). This in turn means that the order of the group, that is, the number of elements in the set is p-1.

If you are so inclined, it is not too difficult to prove for yourself that modular arithmetic is a commutative group using the fact that integer multiplication is associative and commutative and the following relationship:

a . b mod p = a . b - n.p (where n is an integer)

Diffie Hellman Parameters

To use the Diffie-Hellman problem as a key agreement scheme, Alice and Bob first agree on a set of shared parameters:

The group prime p
The generator e

Alice and Bob both generate a private key and a public key as follows:

Private key: A random number x from the set 1..(p-1)
Public key: The value P_x = e^x mod p

If the private keys of Alice and Bob are a and b respectively, their corresponding public keys are P_a = e^a mod p and P_b =e^b mod p.

The key agreement value for Alice and Bob is e^ab mod p.

Alice calculates the key agreement using her private key a and Bob's public key P_b :

P_b^a mod p = (e^b mod p)^a mod p.

= (e^b )^a mod p.

= e^ab mod p.

Diffie-Hellman vs RSA

One big advantage of Diffie-Hellman over the RSA algorithm is that generating private keys does not require searching for pairs of prime numbers. Any number that is greater than 0 and less than p can be used as a private key.

The two principal percieved limitations of Diffie-Hellman versus the RSA system are:

Diffie-Hellman cannot be used to encrypt data directly. It is always necessary to use it in combination with a symmetric cipher like AES.
In RSA, only the recipient requires a public keypair. In Diffie-Hellman, both the sender and the receiver require a keypair.

Neither is really a problem in practice. While it is true that Diffie-Hellman requires the use of a symmetric cipher like AES, this is equally true of RSA if you want to build a robust, scalable protocol. All forms of public key cryptography are considerably slower than symmetric cryptography. All forms of public key cryptography have particular requirements for formatting or extraction of the symmetric key data.

The second issue is really just a matter of terminology. In the RSA system, generation of public keypairs is a slow, CPU intensive process. In the Diffie-Hellman system, generating a keypair takes us only the same time as a public key operation. So it is quite reasonable to have a Diffie-Hellman protocol in which the sender generates a new keypair for every message they send. So what we call the sender's public keypair could equally well be called a nonce, which is a value that is introduced into a protocol that is random and used exactly once.

So in an email security application such as S/MIME, the steps Alice follows to send a message to Bob using Diffie-Hellman and AES are:

Use Bob's public key P_b to calculate d = e^ab mod p
Apply a key expansion function i>H(d) to derive the AES encryption key k
Encrypt the message m as E(m, k)
Send P_a, E(m, k) to Bob

Beyond basic Diffie-Hellman.

So far we have just seen the basic Diffie-Hellman exchange that you can find in any textbook on modern cryptography. But as I show in the next part, there is a lot more to Diffie-Hellman than most textbooks describe. In particular we can do:

Three (or more) key exchanges
Adding two keypairs to create a third keypair
Der riving a set of keys from a single master key so that we use a different public key for every party we communicate with.
Split a private key into two or more parts so that all are required to decrypt a message.