Diffie-Hellman Key Exchange

17 Dec 2021

Notes Cryptography Diffie-Hellman Key Exchange

§ Motivation

In a public channel it is sometimes useful to generate a shared secret key between two parties to use in encrypting subsequent messages to one another. Diffie-Hellman is not a cryptosystem, i.e. it is not used to send messages, but rather it is used to exchange keys.

§ Diffie-Hellman Key-Exchange

Suppose that Alice and Bob want to create a shared secret, $k$ , over a public channel. In this case Diffie-Hellman key exchange can be used instead of encrypting and decrypting messages.

Diffie-Hellman Key Exchange

First, Alice and Bob agree to a common (large) prime $p$ , and some positive non-zero integer $g \pmod{p}$ . As such, anyone on the public channel will have access to these values $g, p$ .

Next, Alice and Bob both choose a random secret key $a$ and $b$ , respectively. Alice computes $A \equiv_p g^a$ , and Bob computes $B \equiv_p g^b$ . Alice and Bob then exchange $A$ and $B$ with one another.

Finally, Alice computes $k \equiv_p B^a$ and Bob computes $k \equiv_p A^b$ . The values of $k$ computed by both Alice and Bob are equivalent, thus it is a shared secret key.

§ Sketch of Proofs

Correctness

We can show that the computed secret key $k$ for both Alice and Bob are equal as follows

A^b \equiv_p (g^a)^b \equiv_p g^{ab} \equiv_p (g^b)^a \equiv_p B^a.

Hardness

Suppose Eve, an eavesdropper, listens to a public channel and intercepts the values of $g, p, A, B$ , would she be able to compute $k$ ?

Looking at $A$ , we know that $A \equiv_p g^a$ , meaning Eve would have to solve for $a$ , likewise she would also need to solve for $b$ .

If a "good" value of $g$ was chosen, then solving for $a, b$ immediately becomes a very difficult task, as this is the discrete log problem.

§ Man-in-the-Middle Attack

If Eve was able to intercept the messages between Alice and Bob as well, then she can pose as the other party to both. In this case when Eve will do the Diffie-Hellman key exchange protocol individually with Alice and Bob.

Alice would send her value $A$ to Bob normally, then Eve can intercept the message and respond with her own value of $E \equiv_p g^e$ , where $e$ is Eve's secret key. Then Eve can do the same with Bob. In the end, there would be a secret key between Alice/Eve and Eve/Bob. Eve knowing both secret keys can decode a message from Alice, read it, then re-encode the message using the secret between Eve/Bob and sending that message to Bob.