Diffie-Hellman key exchange

From CRYPTUTOR

Diffie-Hellman key exchange (or Diffie-Hellman key agreement) is a protocol for two parties who have never interacted before to publicly compute a common secret (say, for use as a key in a private-key encryption scheme). That is, without sharing any common secret information, by exchanging messages over an insecure channel, they can both compute a shared secret, but anyone observing the messages they exchange gets no information about their shared secret.

[edit]

The protocol

Let $G$ be a cyclic group of prime order $p$ with generator $g$ . The Diffie-Hellman key exchange protocol between Alice and Bob works like this:

Diffie-Hellman key exchange:

Alice chooses a random $a \gets \mathbb{Z}_p$ , and sends $A = g a$ to Bob.
Bob chooses a random $b \gets \mathbb{Z}_p$ , and sends $B = g b$ to Alice.
Alice can compute the shared secret $B a = g a b$ .
Bob can compute the shared secret $A b = g a b$ .

Clearly the protocol is correct in that Alice and Bob both compute the same secret $g a b$ .

The protocol achieves the security described above, if the decisional Diffie-Hellman assumption holds for the group $G$ . To see this, observe that any eavesdropping PPT adversary sees only the messages $A = g a$ and $B = g b$ , for randomly chosen $a$ and $b$ . The DDH assumption is that the shared secret $g a b$ is pseudorandom given $A$ and $B$ . Thus, from the adversary's point of view, Alice and Bob share a truly random secret.