Franklin's Notes


Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange is a cryptosystem that allows agents to exchange keys in public. The procedure is as follows:

1. The agents (Alice and Bob) publicly choose a prime $p$ and an element $g\in\mathbb Z_p^\times$, preferably a primitive root modulo $p$.
2. Alice privately chooses an $\alpha\in\mathbb Z$ and Bob will privately choose a $\beta\in\mathbb Z$.
3. Alice computes $g^\alpha$ and sends it (publicly) to Bob, and Bob computes $g^\beta$ and sends it (publicly) to Alice.
4. Alice privately computes $g^{\alpha\beta}$ by raising $g^\beta$ to the power $\alpha$. Bob privately computes $g^{\alpha\beta}$ by raising $g^\alpha$ to the power $\beta$.
5. Alice and Bob now have the "shared secret" $g^{\alpha\beta}$ which can be used as their key.

In theory, an eavesdropper (Clyde) could determine the values of $\alpha$ and $\beta$ and therefore $g^{\alpha\beta}$ as well, because the values of $p,g,g^\alpha,g^\beta$ are all public. However, it is claimed that this problem (i.e. the discrete logarithm problem ) is very computationally difficult, compared to the computations that Alice and Bob must perform (just exponentiation modulo $p$).

To be explicit, there are two slighly different problems under question here:

For practical purposes, $p$ should be large enough to have at least $\approx 2000$ binary digits.

cryptography

number-theory

primes

primitive-roots

back to home page