Diffie-Hellman using numbers

The operation that acts as the mixing step is called modular exponentiation: raising a number to a power, modulo a large prime number.

The protocol

Alice and Bob publicly agree on two numbers: a large prime number p and a base g.

              (public: p, g)
Alice                                   Bob
  a (secret)                              b (secret)
  A = g^a mod p
       ------------- A ------------->
       <------------ B --------------     B = g^b mod p
  s = B^a mod p                           s = A^b mod p

Both calculations result in the same number:

B^a = (g^b)^a = g^(ab) mod p
A^b = (g^a)^b = g^(ab) mod p

The order of the exponents makes no difference — just like the order of the paintings.

A tiny example

Let’s take p = 23 and g = 5. Alice chooses a = 6, Bob chooses b = 15.

A = 5^6  mod 23 = 15625 mod 23 = 8
B = 5^15 mod 23 = 19
s = 19^6 mod 23 = 2          (Alice's rating)
s = 8^15 mod 23 = 2          (Bob's rating)

Both arrive at 2. Eve, on the other hand, has seen 23, 5, 8 and 19.

Why Eve is stumped

To find a, Eve must solve 5^a mod 23 = 8. With such small numbers, she tries every possible value and wins in a matter of moments.

But in practice, p is 2048 bits or more, which is over 600 decimal digits. The number of values to test therefore far exceeds what any machine could ever process.

Note the asymmetry: Alice calculates g^a mod p instantly using fast exponentiation, whilst working backwards from A to a remains out of reach. Easy in one sense, impossible in the other — the mixing of paints, in arithmetic.