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

X = g^x mod n

(2)  Bob chooses a random large integer y and sends Alice

Y = g^y mod n

(3)  Alice computes

k = Y^x mod n

(4)  Bob computes

k´ = X^y mod n

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 is based on the difficulty of factoring numbers the same size as n. You can choose any g, such that g is primitive mod n; there’s no reason not to choose the smallest g you can—generally a one-digit number. (And actually, g does not have to be primitive; it just has to generate a large subgroup of the multiplicitive group mod n.)

Diffie-Hellman with Three or More Parties

The Diffie-Hellman key-exchange protocol can easily be extended to work with three or more people. In this example, Alice, Bob, and Carol together generate a secret key.

(1)  Alice chooses a random large integer x and sends Bob

X = g^x mod n

(2)  Bob chooses a random large integer y and sends Carol

Y = g^y mod n

(3)  Carol chooses a random large integer z and sends Alice

Z = g^z mod n

(4)  Alice sends Bob

Z´ = Z^x mod n

(5)  Bob sends Carol

X´ = X^y mod n

(6)  Carol sends Alice

Y´ = Y^z mod n

(7)  Alice computes

k = Y´^x mod n

(8)  Bob computes

k = Z´^y mod n

(9)  Carol computes

k = X´^z mod n

The secret key, k, is equal to g^xyz mod n, and no one else listening in on the communications can compute that value. The protocol can be easily extended to four or more people; just add more people and more rounds of computation.

Extended Diffie-Hellman

Diffie-Hellman also works in commutitive rings [1253]. Z. Shmuley and Kevin McCurley studied a variant of the algorithm where the modulus is a composite number [1442,1038]. V. S. Miller and Neal Koblitz extended this algorithm to elliptic curves [1095,867]. Taher ElGamal used the basic idea to develop an encryption and digital signature algorithm (see Section 19.6).

This algorithm also works in the Galois field GF(2^k) [1442,1038]. Some implementations take this approach [884,1631,1632], because the computation is much quicker. Similarly, cryptanalytic computation is equally fast, so it is important to carefully choose a field large enough to ensure security.

Hughes

This variant of Diffie-Hellman allows Alice to generate a key and send it to Bob [745].

(1)  Alice chooses a random large integer x and generates

k = g^x mod n

(2)  Bob chooses a random large integer y and sends Alice

Y = g^y mod n

(3)  Alice sends Bob

X = Y^x mod n

(4)  Bob computes

z = y^-1

k´ = X^z mod n

If everything goes correctly, k = k´.

The advantage of this protocol over Diffie-Hellman is that k can be computed before any interaction, and Alice can encrypt a message using k prior to contacting Bob. She can send it to a variety of people and interact with them to exchange the key individually later.

Key Exchange without Exchanging Keys

If you have a community of users, each could publish a public key, X = g^x mod n, in a common database. If Alice wants to communicate with Bob, she just has to retrieve Bob’s public key and generate their shared secret key. She could then encrypt a message with that key and send it to Bob. Bob would retrieve Alice’s public key to generate the shared secret key.

Each pair of users would have a unique secret key, and no prior communication between users is required. The public keys have to be certified to prevent spoofing attacks and should be changed regularly, but otherwise this is a pretty clever idea.

Patents

The Diffie-Hellman key-exchange algorithm is patented in the United States [718] and Canada [719]. A group called Public Key Partners (PKP) licenses the patent, along with other public-key cryptography patents (see Section 25.5). The U.S. patent will expire on April 29, 1997.