# A Simplistic Introduction to Diffie-Hellman Key Exchange

October 4, 2012So, recently, I've been getting into encryption. In that vein, I thought I'd give a quick overview of two topics: simple XOR encryption, and Diffie-Hellman key exchange.

## XOR encryption

The first topic is almost mindnumbingly simple, but it is a simple, cheap, easy to afford encryption algorithm which has several nice features: it's symmetric, composable, and stupid fast.

So, for XOR encryption to work, you need two things: a payload (the
'cleartext') and an encryption key. The algorithm takes the key and uses
it to modify the payload, creating what is known as the 'cyphertext'.

Both the key and payload are typically strings, but anything that can be
converted to binary numbers will work. To make things simple, I'm going
to use numbers in my examples that follow, instead of strings, so as to
avoid encoding concerns, which are really something that shouldn't be
worried about when looking at encryption concepts, as they're more of an
implementation detail.

Alright, so let's start off with an example. Say that I want to encrypt the payload '117' with the encryption key '18'. These are arbitrary numbers chosen for the purpose of this example.

First we start by converting these to binary numbers:

```
payload = 117 = 0b01110101
key = 18 = 0b00010010
```

Then, to create the cypertext, we simply XOR the numbers together:

```
01110101 117 cleartext
XOR 00010010 XOR 18 key
------------ -------
01100111 103 cyphertext
```

So we've successfully encrypted the payload to the cyphertext. Decryption is simply XORing the cyphertext with the same key. This is why it's a so-called symmetric encryption scheme--encryption and decryption are the exact same operation.

```
01100111 103 cyphertext
XOR 00010010 XOR 18 key
------------ -------
01110101 117 cleartext
```

What does it mean then, that this algorithm is composable? Well, what would happen if I were to encrypt the data with one key, and then a second, different key? Would it matter which order I applied the decryption? Composable encryption algorithms work regardless of the order of decryption. That is, the following works:

```
cleartext 117 01110101
key1 18 00010010
--------------------------
cyphertext1 103 01100111
key2 201 11001001
--------------------------
cyphertext2 174 10101110
Decrypt order: key2, key1:
cyphertext2 174 10101110
key2 201 11001001
--------------------------
cleartext1 103 01100111
key1 18 00010010
--------------------------
cleartext 117 01110101
Decrypt order: key1, key2:
cyphertext2 174 10101110
key1 18 00010010
--------------------------
cleartext1 188 10111100
key2 201 11001001
--------------------------
cleartext 117 01110101
```

Cool huh?

## Key Exchange

Now, how do two people get the same key? Surely, one could just tell the other, and trust that they'll keep it secret. But someone could be listening (the walls have ears, you know!). This won't work.

What does work is something called Diffie-Hellman key exchange. It involves both participants agreeing on a "shared secret", which will become part of the key, as well as each individually choosing a secret number that they won't tell anyone, not even each other. They then do some simple XORing on these and swap. Because XOR is composable, as explained above, both participants will be able to generate the same secret key without ever sharing it with the other, allowing them to communicate freely.

How does this work though? Here are the steps (don't worry, there's a textual flowchart of this later in the post):

- Both participants agree on a shared secret. Let's use 34.
- Each participant independently chooses a secret key. Let's use 12 and 21.
- Each participant XORs their secret key with the shared secret. This gives us 46 and 55.
- The participants swap these composed keys.
- The participants XOR their private keys with the coposed keys that they just recieved. This gives us 59 and 59.
- They've generated the same key! They can communicate.

Diagrammed out a bit, here's how it looks:

```
Person 1 Person2
34 shared 34
12 secret 21
46 composed 55
55 swap 46
59 key! 59
```

This does not completely prevent man-in-the-middle attacks, but it does a good bit to make it harder for people to find the encryption key.

Do note, however, that this implementation is highly flawed: Person 1 can glean Person 2's secret key, and vice versa, after the swap! It's a simple matter of XORing by the shared secret. True key exchange mechanisms use stronger encryption schemes that prevent simple means of ascertaining the private keys of other people.

## Some code

As always with these posts, I try to provide some working code to explain what my words can't convey. Here's an example in Io:

Enjoy.