Diffie-Hellman

We’ll look first at DH security against eavesdroppers.

We want to go from a quadratic gap to an exponential gap between the participants in the key exchange and the attacker.

Diffie-Hellman

We fix a large prime \(p\) (eg 600 digits, 2k bits).

We fix an integer \(g\) in range 1..p.

These are fixed forever.

Alice chooses a random \(a\) in \(\{1,\dots , p-1\}\).

Bob chooses a random \(b\) in \(\{1,\dots , p-1\}\).

Alice sends Bob \(A \leftarrow g^a \mod p\)

Bob sends Alice \(B \leftarrow g^b \mod p\)

The shared key \(k_{AB} = g^{ab} \;\pmod p\)

Alice can compute this as \(B^a \;\pmod p = (g^b)^a = k_{AB}\)

Bob can compute this as \(A^b \;\pmod p = (g^a)^b = k_{AB}\)

This works through properties of exponentiation, changed the world of cryptography.

So why is this secure, it’s secure to the extent of the difficulty of working out the original a and b given \(g^a,g^b\).

This turns out to be this hard, currently:

So in practice people use c. 2k mod size, but they should really be using 3k.

It becomes very difficult when we have a 256 bit key.

Can we run DH in other settings without doing the mod p arithmetic? Yes, we can translate it to another algebraic object - an elliptic curve.

The problem is harder on elliptic curves, so we can use much smaller objects.

We’re seeing a slow transition from mod p arithmetic to elliptic curves.

Note that this protocol as it stands is insecure against active attacks.

The man in the middle just intercepts the key exchange and swaps his own choices for \(a,b\).

Note that for two people, we can just put our public contribution to DH online (ie our \(g^a\)) and then we don’t need to communicate before establishing the secret key. We read the equivalent profile, and we can compute our secret key for bilateral conversation.