This lesson just requires that you know basic algebra.

Diffie Hellman is probably the easiest "public key" algorithm to understand. As we will see, it is a key exchange protocol, and is not used for encryption. El-Gamal is an example of a public key encryption scheme which uses similar principles.

Let's say I have a secret key, which is just some big number, and I want to talk over an encrypted channel with Bob, who also has a secret key.

Neither of us wants to tell the other his secret key, so we need to establish a shared key, that only we know. We can use the shared key to encrypt our communications using any symmetric encryption such as AES.

In order to establish the shared key, we can only communicate over a public channel that anyone can eavesdrop on.

we use some constant number g which everyone knows. g stands for generator, but don't worry what that means.

my secret key = x

Bob's secret key = y

I send Bob g^x. (that means g raised to the power of x)

He sends me g^y

our shared key is g^(xy)

We now share a key, and no one but us should be able to derive the key, and no one, including us, should be able to derive the other's secret key.

If I know x and g^y, I can get g^(xy) by doing (g^y)^x = g^(xy)

It is impossible to derive g^(xy) if all you know is g^x and g^y. g^x * g^y = g^(x+y), which is worthless.

We are assuming that given g^x, an adversary cannot derive x. This is called the discrete logarithm problem. As long as discrete logarithms are hard, this protocol is secure. I left a little about this out. Rather than sending g^x, you would really send g^x mod n, but we don't need to get into that. That's what makes it a discrete logarithm rather than a regular one. There are wikipedia entries for all of these things.

So now you know. It's a pretty simple idea, and discrete logarithms are the basis for most public key encryption, with RSA being an exception which is based on integer factorization instead.

Challenge:

We're assuming that the adversaries can eavesdrop on the channel, but can't drop messages from the channel, or insert spoofed messages into the channel.

If an attacker can do those things, how can he eavesdrop on the encrypted communication without Bob and I knowing?