Diffie-Hellman key agreement

Principles

Diffie-Hellman key agreement allows two principals (people) to agree upon a shared key without authentication.

Algorithm

Setup

We have a public, large, secure prime $p$ and a generator $g \in Z^*_p$.

Key Exchange

The following calculations all take place $\mod p$

  1. We have principals $A$ and $B$
  2. The principals choose keys
    1. $A$ selects a random integer $x$ such that $1 \leq x \lt p-1$
    2. $B$ selects $y$ similarly
  3. The principals send their keys
    • $A \overset{g^x}{\rightarrow} B$
    • $B \overset{g^y}{\rightarrow} A$
  4. The principals calculate the same key together
    • $A$ receives $m =g^y$ from $B$ and calculates $m^x = (g^y)^x = g^{xy}$
    • $B$ receives $n = g^x$ and calculates $g^{xy}$ similarly
  5. Both principals now know $g^{xy}$ in such a way that a passive attacker cannot find it, presuming DHP to be intractable.

Attacking

Diffie-Hellman is vulnerable to a man in the middle attack in which an eavesdropper $E$ intercepts each communication and sets up their own key agreement with each principal. $E$ can then decrypt all messages from each principal and re-encrypt them for the other, potentially changing the message.

Back to Computer Security