7.3 The Diffie-Hellman key-exchange protocol

Alice and Bob communicate over an insecure channel. They can establish a shared secret K using the following protocol steps [49]:

1. Alice and Bob publicly agree on a cyclic group 𝔾 and a corresponding generator g. Very often, this step is performed out of band long before the actual key agreement. For example, 𝔾 and g might be specified in a public document.
2. Alice chooses a natural number α, where 1 < α < N, where N is the order of 𝔾. α is Alice’s private key SKAlice. She must not disclose this number to any other party.
3. Bob does the same as Alice: he independently chooses a number 1 < β < N as his private key SKBob.
4. Alice computes A = gα in G and sends A to Bob. The number A (together with G and g) can be seen as Alice’s public key: PKAlice = (g,G,A).
5. Bob computes B = gβ in G and sends B to Alice. The number B (together with G and g) can be seen as Bob’s public key: PKBob = (g,G,B).
6. Alice computes KA = Bα. Bob computes KB = Aβ. However, both compute the same value K, because

These protocol steps are also visualized in Figure 7.1. Can you see the trapdoor mechanism? The public parameters A and B can be computed easily enough via the power function in G, but in order to compute K, it seems an eavesdropping attacker would have to invert the power function and solve a discrete logarithm problem, which is supposed to be hard. Their private key, however, gives Alice and Bob a way to circumvent the need to compute discrete logarithms. Instead, they can keep on computing powers of group elements to arrive at the shared secret K. By using a Key Derivation Function (KDF), as discussed in the previous chapter, actual cryptographic keys can then be derived from K.

Figure 7.1: Diffie-Hellman key exchange over a generic cyclic group 𝔾

We will shortly discuss the security of this protocol, but let’s turn to the original formulation of the protocol in the original paper [49] first. Here, the protocol is not described for a generic group 𝔾, but for the specific group 𝔽p∗. Figure 7.2 shows what it looks like in this special case. Here, specifying a prime number p is sufficient to fix the group 𝔽p∗, and the powers of g in G become gx mod p in this specific setting.

Figure 7.2: Diffie-Hellman key exchange over 𝔽p∗

For example, let’s assume Alice and Bob use the prime p = 11 and the generator g = 2 as public parameters (you might check for yourself that g = 2 is indeed a generator). Alice’s private key is α = 3, so she computes A = 23 mod 11 = 8 and sends A to Bob. Bob’s private key is β = 4, so he computes B = 24 mod 11 = 5 and sends B to Alice. Alice can now compute her version of the shared secret as KA = Bα mod p = 53 mod 11 = 4, while Bob computes KB = Aβ mod p = 84 mod 11 = 4.