# CHAPTER 22

# Key-Exchange Algorithms

## 22.1 DIFFIE-HELLMAN

Diffie-Hellman was the first public-key algorithm ever invented, way back in 1976 [496]. It gets its security from the difficulty of calculating discrete logarithms in a finite field, as compared with the ease of calculating exponentiation in the same field. Diffie-Hellman can be used for key distribution—Alice and Bob can use this algorithm to generate a secret key—but it cannot be used to encrypt and decrypt messages.

The math is simple. First, Alice and Bob agree on a large prime, *n* and *g*, such that *g* is primitive mod *n*. These two integers don't have to be secret; Alice and Bob can agree to them over some insecure channel. They can even be common among a group of users. It doesn't matter.

Then, the protocol goes as follows:

- (1) Alice chooses a random large integer
*x* and sends Bob
- (2) Bob chooses a random large integer
*y* and sends Alice
- (3) Alice computes
- (4) Bob computes

Both *k* and *k*′ are equal to *g*^{xy} mod *n*. No one listening on the channel can compute that value; they only know *n*, *g*, *X*, and *Y*. Unless they can compute the discrete logarithm and recover *x* or *y*, they do not solve the problem. So, *k* is the secret key that both Alice and Bob computed independently.

The choice of *g* and *n* can have a substantial impact on the security of this system. The number (*n* − 1)/2 should also be a prime [1253]. And most important, *n* should be large: The security of the system ...