### What is
Diffie-Hellman?

The Diffie-Hellman key agreement
protocol (also called exponential key agreement) was
developed by Diffie and Hellman [DH76] in 1976 and published in the ground-breaking
paper "New Directions in Cryptography." The
protocol allows two users to exchange a secret key over an
insecure medium without any prior secrets.

The protocol has two system parameters
p and g. They are both public and may be used by all the
users in a system. Parameter p is a prime number and
parameter g (usually called a generator) is an integer less
than p, which is capable of generating every element from 1
to p-1 when multiplied by itself a certain number of times,
modulo the prime p.

Suppose that Alice and Bob want to
agree on a shared secret key using the Diffie-Hellman key
agreement protocol. They proceed as follows: First, Alice
generates a random private value a and Bob generates a random
private value b. Then they derive their public values using
parameters p and g and their private values. Alice's public
value is g^{a} mod p and Bob's public value is g^{b}
mod p. They then exchange their public values. Finally, Alice
computes k_{ab} = (g^{b})^{a} mod p,
and Bob computes k_{ba} = (g^{a})^{b}
mod p. Since k_{ab} = k_{ba} = k, Alice and
Bob now have a shared secret key k.

The protocol depends on the discrete
logarithm problem for its security. It assumes that it is
computationally infeasible to calculate the shared secret key
k=g^{ab} mod p given the two public values g^{a}
mod p and g^{b} mod p when the prime p is
sufficiently large. Maurer [Mau94] has shown
that breaking the Diffie-Hellman protocol was equivalent to
computing discrete logarithms under certain assumptions.

The Diffie-Hellman key exchange is
vulnerable to a middleperson attack. In this attack, an
opponent, Carol, intercepts Alice's public value and sends
her own public value to Bob. When Bob transmits his public
value, Carol substitutes it with her own and sends it to
Alice. Carol and Alice thus agree on one shared key and Carol
and Bob agree on another shared key. After this exchange,
Carol simply decrypts any messages sent out by Alice or Bob,
and then reads and possibly modifies them before
re-encrypting with the appropriate key and transmitting them
to the correct party. This vulnerability is due to the fact
that Diffie-Hellman key exchange does not authenticate the
participants. Possible solutions include the use of digital
signatures and other protocol variants (see Question 25).