Thread by @ErrataRob

1/n This is a common "no-math" explanation of Diffie-Hellman key exchange. I think I prefer the "high school math" version.

https://twitter.com/pwrcycle/status/1217963904015273984

2/ I know you've forgotten most of it, but here is the list of basic rules for exponentiation that you learned in high school. Diffie-Hellman is simply the item on the list "Power of power".
mathinsight.org/exponentiation…

3/ "Exponentiation" is to "multiplication" what multiplication is to addition.
3 + 3 + 3 + 3 + 3 = 5 × 3
5 × 5 × 5 × 5 = 5⁴

4/ The "power of power" ruleis when that's done a second time, as in:

5/ One thing we know about "multiplication" is that we can reverse the order of numbers, so:

4×7 = 7×4

6/ We can combine that with the Power-of-power rule as so:

7/ Diffie-Hellman starts with Alice or Bob choosing a number, let's say '5', and making this public, shouting at the top of their lungs "OUR NUMBER IS FIVE", so that everybody in earshot knows this number.

8/ Alice then picks a random number, let's say '4'. Nobody will ever know this number, not even Bob. It's not the sort of secret you share with only your best friend, but a deeply private secret that you'll take to your grave.

9/ Alice then calculates 5⁴ getting the number 625. She sends that to Bob.

Bob does the same, choosing 7 as his private random number, calculates 5⁷, and sends the resulting 78125 to Alice.

10/ Alice doesn't know Bob's number, but she knows 78125. So she calculates 78125⁴ and gets a very big number of 37,252,902,984,619,140,625.

Bob calculates 625⁷and, because of the power-of-power rule, gets the same number as Alice.

11/ We start with the number 5 being "public", everyone knows it, the number '4' being "private", nobody but Alice knows it, and '7' being private to Bob. Both Alice and Bob know the result, 37,252,902,984,619,140,625, but nobody else does.

12/ Now since the only two people in the world who know this secret number are Alice and Bob, they can use it for other things, such as encrypting raunchy love letters that frankly, nobody really wanted to read anyway.

https://twitter.com/haroldsmith3rd/status/1217938244588986371

13/ This Diffie-Hellman is sometimes called "key agreement". That's because neither side picked the secret key there were going to use to encrypt their love letters. Instead, they came to an agreement on the key together by each side picking a random number.

14/ Wait, there's more high-school math ahead. We now know the math for agreeing upon a secret encryption key, but we don't know why somebody can't reverse the operation. Eve, jealous of Bob stealing her girlfriend, can easily work backward from 625, especially knowing 5.

15/ The high-school math we are going to discuss for this is:
- prime numbers
- factorization
- remainder (modulus) of division

16/ Let's talk about the hardest concept, the "modulus". As you know, when you divide two numbers, you don't always get a nice clean result. If you calculate 13÷5, you get the answer '2', but a remainder of '3'.

17/ There is something called 'modulus arithmetic' where at the end of every step we apply this sort of division by the "modulus" in order to get a "remainder", such as:
(6+7)÷5 = 3
where '5' is the modulus of whatever math we are doing.

18/ This is getting confusing and stupid, so let's instead think of the 12 numbers on the clock (modulus=12). Alice and Bob want to meet up at a secret time to Neflix and chill. Whatever complicated math they do must result in an hour o'clock.

19/ Thus, if the result they come up with is 27, then 27 modulo 12 becomes 5 o'clock, and that's the time they meet up.

20/ Modular arithmetic of this sort has two useful properties for our purposes here.

The first is that it makes calculation easier. The exponentiation we do for crypto would result in numbers so big that they couldn't otherwise be calculated or fit within computers.

21/ I mean, in the above example, I started with the tiniest of numbers and quickly reached a humongous 37,252,902,984,619,140,625. It gets only worse with big numbers.

22/ The second advantage is that it makes going backwards harder. When it's 5 o'clock, modulo 12, the number they started with could've been 5, 17, 29, 41, or so on. You can't be sure precisely which one.

23/ So Alice doesn't calculate:
5⁴= 625
She instead calculates:
5⁴ modulo 23 = 4
and sends Bob '4'. Bob calculates:
4⁷ modulo 23 = 8

So Bob goes to meet her at 8am.

24/ Likewise, Bob calculates:
5⁷ modulo 23 = 17
and sends Alice '17'. She calculates:
17⁴ modulo 23 = 8
And goes to meet Bob at 8am.

25/ I mean, assuming both were paying attention in their high-school math class with Mrs. Mueller. Charlie didn't pay attention, so missed out on her date with Bob, which is why they broke up.

27/ So Eve wants to find out the time of their date, and you know, show up unannounced with a laptop to actually watch Netflix to disrupt the proceedings. She saw the numbers '5', '23', '4', and '17', because Alice and Bob were posting these publicly on the school bulletin board.

28/ So Eve writes a little computer code to just work backwards from those number, guessing everything they could've been, and successfully disrupts the date.

29/ Alice and Bob realize that with such smaller numbers, it's easy to guess things, especially with a computer that can guess billions of combinations per second. Therefore, for their next date, they choose really huge numbers.

30/ The number '5' is probably still good for the base (in real world crypto, it's been as small as 3, sometimes 17, and sometimes 65535). But the random numbers they pick as their private key need to be huge, like 300 digits long, to prevent Eve from figuring it out.

31/ (Oops, I messed up with Eve and Charlie. Okay, so now there's two people wanting to interfere with Alice and Bob hooking up)

32/ So, if you listened in math class, you find tricks that help you work backwards from numbers multiplied together and exponentiation, like factorization. So even big numbers won't help Alice and Bob unless they are the right big numbers.

33/ The right big numbers are prime numbers. Unfortunately, showing you why prime numbers work and non-prime numbers don't with high-school math is beyond my abilities.

34/ But primes have lots of cool properties. For example, let's say you wanted to print out the numbers [0..9] in a pseudo-random order. Start with the number 1 and keep adding 23 modulo 10, and you'll get the sequence:
3 6 9 2 5 8 1 4 7 0
Each number appears exactly once

35/ This is because the number 23 is prime that I can do this trick. The standard pseudo-random number generator built into a lot of programs use this trick.

36/ You know how you play video games and it generates random "levels" for you to play? It's probably using a random number generator "modulo p", meaning modulo some prime.

37/ So if Alice and Bob choose ~300 digit numbers that are prime, then they are safe from Eve. At least today. As computers get faster and faster, the numbers have to get larger and larger.

38/ By the way, "working backwards" from "exponentiation" is called finding the "logarithm". You also learned about logarithms in math class, like teaching you how slide rules worked, which you didn't pay attention to, because ok boomer.

39/ Only in this case, it's "modular exponentiation", so finding the reverse is "discrete logarithms". Finding logarithms is easy, finding discrete logarithms is hard.

40/40 So what I'm saying, millennials, is stay in school and pay attention in math class or you'll never get a date. This stuff is important.