Diffie-Hellman key exchange

Diffie-Hellman is a simple public-key algorithm that enables two users to establish a secret key using a public-key scheme based on discrete logarithms.

1. Principals share a prime number $q$ and an integer $\alpha$ that is a primitive root of $q$. Both $q$ and $\alpha$ may be public, or $A$ could send them in the first message.
2. $A$ and $B$ generate random numbers $X_A$ and $X_B$ both less than $q$. (these are private keys)
3. $A$ computes $Y_A={\alpha }^{X_A}\text{ mod }q$, $B$ computes $Y_B={\alpha }^{X_B}\text{ mod }q$. (these are public keys, also known as “Diffie-Hellman half keys”)
4. $A$ and $B$ exchange $Y_A$ and $Y_B$.
5. $A$ computes $K_A=Y_B^{X_A}\text{ mod }q$, $B$ computes $K_B=Y_A^{X_B}\text{ mod }q$. (the keys are equal, i.e. $K_A=K_B$)