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.
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.
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
- 20 = 1
- 21 = 2
- 22 = 4
- 23 = 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.
Alice and Bob both choose random numbers (a and b respectively). Alice then computes ga and Bob computes gb. They exchange their results.
The key that Alice and Bob now agree on is simply ga*b. This is all very easy to compute. Alice knows a and gb, and Bob knows b and ga, and
Alice and Bob can use the key ga*b to encrypt messages with any secret key algorithm.
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 210 = 1024, but more difficult to determine that 1024 is the 10th power of 2.
Eve knows ga and gb, 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 ga (which mathematicians write as logg(ga)). And calculating this logarithm takes a long time.