# The Diffie-Hellman system

The Diffie-Hellman algorithm is a public key algorithm. It was invented in 1976 by Whitfield Diffie and Martin Hellman (US patent 4,200,770). It allows two parties, commonly called Alice and Bob, to agree on a key that they can use to encrypt messages they want to send to each other. They can to this even when an eavesdropper (Eve) listens in on their entire conversation.

The security of this algorithm depends on the assumption that it is easy to raise a number to a certain power, but difficult to compute which power was used given the number and the outcome.

## Generating the Diffie-Hellman public key

The Diffie-Hellman system allows Alice and Bob to agree on a key even when Eve is listening to everything they say to each other. Alice and Bob need to agree on a prime number p, which they can do by simply sending it to each other. Eve is allowed to learn this number p. In practice the number p is often simply advertised somewhere public.

### Generators

Given a prime number p, it is possible to come up with a number g (the so-called generator) with a very interesting property. Every number between 1 and p-1 can be written as a power of g when calculating modulo p. For example, using p = 5 the generator is 2, because

- 2
^{0}= 1 - 2
^{1}= 2 - 2
^{2}= 4 - 2
^{3}= 3 (because 8 = 3 mod 5)

Alice and Bob agree in the same way on a generator g for the numbers between 1 and p-1.

### The public key

The numbers p and g serve as the public key.

## Establishing a key

Alice and Bob both choose
random numbers (a and b respectively). Alice then computes
g^{a} and Bob computes
g^{b}. They exchange their results.

The key that Alice and Bob now agree on is simply
g^{a*b}. This is all very
easy to compute. Alice knows a and g^{b},
and Bob knows b and g^{a}, and

^{a})

^{b}= (g

^{b})

^{a}= g

^{a*b}

Alice and Bob can use the key g^{a*b} to
encrypt messages with any secret key algorithm.

## The security of Diffie-Hellman

The security of the Diffie-Hellman system depends on the assumption that
it is easy to raise a number to a certain power, but difficult to compute
which power was used given the number and the outcome. For example, it's
easy to compute 2^{10} = 1024, but more difficult to
determine that 1024 is the 10th power of 2.

Eve knows g^{a} and g^{b},
but since she does not know a or b itself, she cannot compute the
key in a reasonable amount of time. To do that, she has to calculate
the g-logarithm of g^{a} (which mathematicians
write as log_{g}(g^{a})).
And calculating this logarithm takes a long time.