Cryptography/Diffie-Hellman

Diffie-Hellman, named for creators Whitfield Diffie and Martin Hellman, was the first (publicly known, at least) public key algorithm and was published in 1976. Its security relies on the discrete logarithm problem, which is still thought to be difficult.

Diffie-Hellman is generally used to generate a unique key by two (or more) parties with which they may then encrypt and exchange another key. This is similar to the use of the RSA algorithm within PGP.

Alice and Bob select a large prime number n, which will be the modulus. They then select another number c that is primitive mod n, which will be the base. These two numbers may be broadcast far and wide. At this point Bob and Alice both select large, random integers (a and b, respectively) in secret, and exchange the result of the exponentiation:

Alice performs $A=c^{a}mod\ n$ and sends A to Bob in the clear.

Bob then performs $B=c^{b}mod\ n$ and sends B to Alice in the clear.

At which point Alice knows a and B, so she computes:

$K_{2}=B^{a}\ mod\ n$

while Bob, knowing A and b, computes:

$K_{1}=A^{b}\ mod\ n$

and,

$K_{1}\ =\ K_{2}$

This is simply based on the commutative property of multiple exponents

$(x^{y})^{z}\ =\ (x^{z})^{y}$.

An eavesdropper can get A and B, but cannot easily calculate the key.