Communication On A Channel Without Trust

Both one time pads and the enigma machine helped push cryptography along. However, one of the biggest advancements in cryptography was to take places decades after WW2. This advancement in cryptography was published in 1976 by Whitfield Diffie and Martin Hellman with Ralph Merkle making significant contributions.

The reason their breakthrough was such a .... breakthrough was because as we discussed in previous posts, one time pads and enigma machines rely on both the sender and recipient of the message having a shared key (the thing used to encrypt and decrypt the messages). One time pads had a secret pad. Enigma machines used a book of configurations both for the patch cables that went into the plugboard and the rotors themselves. These keys needed to be created beforehand, and if anyone were to discover these keys, secure communication would not be possible.

The Diffie-Hellman key exchange really shook up the game, though. The reason being, it allowed for two parties to exchange a secret across an untrustworthy communication channel.

When we looked at one time pads, we learned we had to use moduloⁿ addition and subtraction

We do this to keep the operations bounded.

It turns out we can do other operations with moduloⁿ. Any possibilities spring to mind? ..... That's exactly right we can do multiplication and division moduloⁿ. And btw if this all sounds like gibberish to you make sure to check out my other post where I break this down in more detail. By this post, we already cover how one time pads and moduloⁿ work in relation to one time pads.

Moduloⁿ multiplication is pretty straightforward. Let's say we do multiplication modulo²⁶.
If we take the number 6 and multiply it by 2 within the bounds of modulo 26 it would look like this.

2 x 6 = 12
That's less than 26 so I can keep multiplying.
2 x 12 = 24
Still less than 26
2 x 24 = 48 STOP
48 is obviously bigger than 26 so we have to go back around.
So the result of 2 x 24 is actually 22.
2 x 24 = 48
48 - 26 = 22

So basically if the result of your multiplication exceeds the modulo then just subtract to get back in range. We're using modulo²⁶, so we subtract by 26 if the result is outside of the bounds.

These is interesting, because it created a pattern. If I were to keep multiplying by 2 with modulo²⁶ the results would be as follows.
6
12
24
22
18
10
14
2
4
8
16
6
12
24




Pretty boring I know, but did you notice the pattern? If we keep multiplying, we eventually get back to the number that we started with. The Diffie-Hellman key exchange takes advantage of this precise pattern, allowing us to communicate securely in the process. Let's get back to Alice and Bob.

Let's say they want to exchange a shared secret on an insecure communication channel. Before this, they agreed on a formula. 2^x_mod26. Alice makes a number. Let's call it a 3. Now she plugs this random number into the formula. 2³ = 8. This is within the bounds of our modulo so there's no need to do any subtraction. So she says to Bob 8. Now Bob will make up a number. He decides that 7 is a good number. He plugs it into the formula. 2⁷_{mod 26} = 24. Now he says to Alice the number 24.

This is where it gets cool.
Alice takes the number she received from Bob (24) and plugs it into the formula with her secret number(3).

24³_mod26 = 18

Then Bob takes the number he received from Alice(8) and plugs it into the formula with his secret number(7)
8⁷_mod26 = 18

So in other words, they both arrived at the same answer(18) without exchanging the secret numbers they made up at the beginning!

If there were an eavesdropper trying to figure out what they were saying on this insecure channel, they would have the following information. The formula: 2^x_mod26. She would also have the intercepted the numbers 8 and 24. In order for this encryption to be useful we need to make sure that the eavesdropper couldn't figure out the messages with this information alone.

Wait! How did Alice in Bob both arrive at the same answer without revealing their secret numbers to each other.

Algebra my dear friends. I know I know, but I promise it's not a looot of algebra. If you remember from those classes you probably hated that multiplication is commutative. In other words a x b = b x a
Also, if you raise the number g to the power of a and then take that answer and raise it to the power of b, you would get the same answer as if you had taken g and raised it to the power of a times b. In other words
(g^a)^b = g^ab
Thus making g^ab = g^ba and
(g^a)^b = (g^b)^a

It turns out that this holds true for a modulo as well.
(g^a mod_n)^b mod _n = (g^b mod_n)^a mod _n
In a nutshell, the answer that Alice told to Bob, (g^a mod_n), or actually this is what she did 2³ = 8 Bob will be able to take her answer and use it to compute the same answer as she does.

That's why 24³_mod26 = 8⁷_mod26
and they both equal 18.

Why can't an eavesdropper figure out what the secret numbers were?