### Question 24. 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).