Diffie, Hellman, and Merkle - Cryptography Post #5

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.

picture of  Whitfield Diffie and Martin Hellman with Ralph Merkle

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 modulon addition and subtraction


We do this to keep the operations bounded.

It turns out we can do other operations with modulon. Any possibilities spring to mind? ..... That's exactly right we can do multiplication and division modulon. 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 modulon work in relation to one time pads.

Modulon multiplication is pretty straightforward. Let's say we do multiplication modulo26.
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 modulo26, 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 modulo26 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. 2xmod26. Alice makes a number. Let's call it a 3. Now she plugs this random number into the formula. 23 = 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. 27mod 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).

243mod26 = 18

Then Bob takes the number he received from Alice(8) and plugs it into the formula with his secret number(7)
87mod26 = 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: 2xmod26. 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
(ga)b = gab
Thus making gab = gba and
(ga)b = (gb)a

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

That's why 243mod26 = 87mod26
and they both equal 18.

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

Sort:  

Congratulations @andrewholloway! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of comments

Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here

If you no longer want to receive notifications, reply to this comment with the word STOP

By upvoting this notification, you can help all Steemit users. Learn how here!

Coin Marketplace

STEEM 0.20
TRX 0.12
JST 0.028
BTC 64294.34
ETH 3494.87
USDT 1.00
SBD 2.54