Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

Diffie Hellman: The Basic Asymmetric Cipher

The Diffie-Hellman Key exchange is one of the older (and consequently simpler) asymmetric key exchange protocols. There are few better ways to understand the basic principles of asymmetric key exchange.

The Values

Diffie Hellman is a technique which produces a shared symmetric key based on asymmetric values. That is, without access to both ends of the equation, you basically cannot determine what the final key will be.

Suppose Alice and Bob (“A” and “B” – classic names for describing the process of an algorithm) want to create a shared secret without informing everyone in the area about their secret. They will first agree to two values p and g.

p is a relatively large prime number.

g is a prime number which is a prime root modulo of p. That means that, for every value x which is between 1 and p-1, g*x mod p will produce a unique result between 1 and p-1.

Because there’s no encryption so far, anyone can find out what p and g are. The magic is coming.

Alice will choose some value “a” which is between 1 and p, and Alice will never tell anyone what a is. At the same time, Bob will choose some value “b” between 1 and p, and Bob won’t tell anyone what it is. These are the “secret keys” of the exchange.

Alice and Bob then calculate a public key which they will exchange. The formulas for this public key are:

Alice: A = g^a mod p

Bob: B = g^b mod p

Bob and Alice can swap these keys in public without fear, because we’re about to employ the magic of MATH!

When we work with modulo exponents, it’s true that (g^xy) mod p = (g^x mod p)^y mod p = (g^y mod p)^x mod p. We can demonstrate the truth of this in any number of ways (incidentally, this is why we need carefully chosen p and g – 0^y = 0^x = 0, so we don’t want g^a or g^b to ever divide evenly by p).

Watch this:

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

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

B^a = A^b

BOOM! We have a shared secret key which no one else can have, because only Alice and Bob know the original values of a and b!

Example

Let’s choose some simple values that are easy for us to calculate, just so we can show how it works:

p=23

g=5

a=9

b=15

Now we have to calculate the values A and B:

A = 5^9 mod 23 = 11

B = 5^15 mod 23 = 19

Finally, let’s calculate the shared secret key:

B^a mod p = 19^9 mod 23 = 10

A^b mod p = 11^15 mod 23 = 10

And, presto! The shared secret key is 10. And, because of how we chose p and g, we can ONLY find the key from A or B if we know the associated secret.

Of course, we want to choose a large p value so that we have more than 23 possible secret keys, but you see how it works.

photo by: