## Cryptography

Diffie-Hellman key exchange works by agreeing on two publicly shared values: a large prime number $q$ and a primitive root $g$. Alice and Bob each generate a secret key—a large random number—$x_a$ and $x_b$ respectively, and each raise the primitive root to the power of the secret key, modulo the large prime number.

\begin{align*} y_a &= g^{x_a} \bmod q \\ y_b &= g^{x_b} \bmod q \end{align*}

The results are sent to each other and the shared key is computed by raising the received value to the secret key modulo the primitive root.

\begin{align*} k_{ab} &= y_b^{x_a} \bmod q \\ k_{ab} &= y_a^{x_b} \bmod q \end{align*}

Given a prime number $q$, a primitive root $g$ is a number such that every number from 1 up to $q - 1$ can be computed by raising the primitive root to some number $k$.

$$\forall x \in \{1, 2, ..., q - 1\}\ \mathbb{Z}_q \\ \exists k \text { such that } g^k = x$$

A common analogy is that of mixing paint.

May 4, 2016
787aeda — October 11, 2018