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

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.

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

A common analogy is that of mixing paint.

May 4, 2016