- [Instructor] The Diffie-Hellman key exchange
algorithm solves the problem of key exchange
for symmetric algorithms.
The Diffie-Hellman algorithm was invented in 1976
by three cryptographers.
It was based upon the work of Ralph Merkle,
and turned into a practical algorithm by
Whitefield Diffie and Martin Hellman.
Unfortunately for Merkle, his name was never included
in the popular name used for the algorithm,
and we're left with the Diffie-Hellman algorithm.
I'm going to show you how Diffie-Hellman works
mathematically, but first I want to use an analogy
to share the purpose of the algorithm,
using colors instead of numbers.
It makes the concept a little easier to understand.
Let's say that Alice and Bob would like to agree
on a common, shared secret color
that they don't want other people to know.
Here's one way they might do that.
First, Alice sends a message to Bob
telling him a common color that they might use.
Let's say that Alice selects yellow,
and tells Bob that color by email.
Next, Alice and Bob each select a secret color of paint
that they don't tell each other.
Perhaps Alice selects red, and Bob selects blue.
Alice and Bob then each take the common color, yellow,
and mix it with their secret color.
For Alice, yellow and red make orange;
and for Bob yellow and blue make green.
Alice then sends Bob a message telling him
that she got orange as her result,
and Bob tells Alice that he got green.
Alice and Bob now have the color created
by mixing the shared yellow color
with their partner's secret color.
They then mix their own secret color
with this color received from their partner.
Alice mixes green and red to get brown;
and Bob mixes orange and blue to get brown.
Both of these browns are identical
and were created by mixing together the same three colors,
yellow, red and blue.
Now let's say that Mal is watching all of the messages
that Alice and Bob exchanged.
What would she know?
Well, she'd know that they started with the color yellow.
And she'd know that they exchanged
the colors green and orange.
She would not know either of the two secret colors
that Alice and Bob selected, red and blue,
or the common secret color of brown,
because those were never sent over an insecure channel.
They were never exchanged, at all.
So that's how Diffie-Hellman works with colors.
The math for the real algorithm is a little more complicated
but it's using the same concept.
Instead of choosing a starting common color,
Alice chooses two numbers,
represented by the variables P and G.
P must be a prime number.
Let's say that Alice sends a message to Bob, then,
telling him to use 13 for P and seven for G.
Next, Alice chooses a secret number.
Let's say she chooses five, we'll call that lower case A.
She then computes the value of upper case A,
using the formula upper case A equals G,
to the lower case A power, modulo P.
That's seven to the fifth power, modulo 13,
which gives us a value of 11 for A.
Alice then sends the value of capital A,
which is 11, to Bob.
Bob then selects his own secret number,
we'll call that lower case B.
And let's say he chooses the number eight.
Bob then performs a similar calculation
to determine upper case B, using the formula
upper case B equals G to the lower case B power, modulo P.
Seven to the eighth, modulo 13, which gives us a value
of three for B.
Bob then sends the value of capital B,
which is three, to Alice.
Alice then computes the shared secret S,
using the formula S equals upper case B
to the lower case A power, modulo P.
This works out to three to the fifth power,
modulo 13, which is nine.
Bob can then compute the same shared secret key
using a different formula.
S equals upper case A to the lower case B power, modulo P.
That works out to 11 to the eighth power,
modulo 13, which is nine.
And now Alice and Bob both have the same shared
secret value of nine, which they can use
as a symmetric encryption key.
If Mal watched the entire communication
between Alice and Bob, she wouldn't have
enough information to reconstruct that key,
just like she couldn't figure out
that the shared secret color was brown.
When people use the Diffie-Hellman algorithm
for real communications, they choose much larger values
for P and G to get things started,
and that makes the math much more difficult.
There is also one variant
of the Diffie-Hellman algorithm worth mentioning.
The elliptic curve Diffie-Hellman, or ECDH algorithm,
uses a similar approach, but replaces the prime
factorization difficulty with complexity drawn
from the elliptic curve problem
that I discussed earlier in the course.