Thread by @ErrataRob

So I'm writing a short (a mere 22k words right now) informal, non-math, un-academic guide to crypto. Nonetheless, have a section on 'xor'. And I'm succumbing to the temptation of describing modular arithmetic.

What we know of as "modular arithmetic" wasn't a thing until about the year 1800, but it's been part of crypto since the time of Caesar. If you'll recall, the Caesar Cipher simply shifts all the letters in the alphabet, so that "IBM" shifted one position to the left becomes "HAL"

But what about TWO characters to the left. The alphabet ends at the letter 'A'. How do you shift "IBM" to characters to the left? The answer is that you simply wrap around and start with 'Z', so "IBM" becomes "GZK".

So that's modular arithmetic. Alphabetic ciphers are "modular 26" or "mod 26", which means that when we add, multiply, or do whatever to the letters in the alphabet, what we get as a result is forced back into the 26 letters of the alphabet, instead of a letter outside it.

Now let's talk about code, I mean programming languages. In the middle of a encryption algorithm you might see a line like this:
x += y;
This looks like addition, but it's not. That's because they aren't "numbers" but "32-bit unsigned integers". The operation can overflow.

If adding two 32-bit integers in code overflows, resulting a 33-bit number, it can't be stored, Therefore, the CPU hardware simply lops off the overflowing bits. In normal code, this is often a bug, an "integer overflow". You should choose bigger integers to stop it.

Expressed different, what I'm trying to say is arithmetic in such code is "mod 2³²". We ignore this fact, but it's actually pretty darn important to the cryptos. On random chance, when two numbers are added, both "high bits" will be set one quarter of the time causing overflow.

So far modular arithmetic is an accidental byproduct of the fact we are working alphabets and 32-bit integers. In abstract math, though, it has interesting properties that we can exploit -- exploit hard.

For example, let's take calculating exponential values, like "aᵇ", which is the number 'a' multiplied by itself by 'b' times. For large values, this can become expensive/impractical to calculate.

But "aᵇ mod p", where 'p' is some prime number, isn't expensive. For one thing the result isn't huge, but no bigger than 'p'. Second, there are some tricks that make this relatively cheap to calculate.

Another trick that comes from this is:
(gᵃ mod p)ᵇ mod p = gᵃᵇ mod p
But also:
gᵃᵇ = gᵇᵃ
Hence:
(gᵃ mod p)ᵇ mod p = (gᵇ mod p)ᵃ mod p

The last bit is that while it's cheap to calculate "gᵃ mod p", it's impractical to take that result and calculate the reverse. It's at this point that we've now discovered Diffie-Hellman key-exchange.

The trick is that both sides generate a random private number, transform it, and send the transformed number to the other side. They then take the number they received, and transform it again. Both sides do the same steps, just in the opposite order.

They generate 'a' and 'b', which they share with nobody, but send across the wire "gᵃ mod p" and "gᵇ mod p". A hacker on the wire (like myself) can't figure out the original 'a' or 'b' from what's seen on the wire.

But since the following is true:
(gᵃ mod p)ᵇ mod p = (gᵇ mod p)ᵃ mod p
Both sides have come to the same result, the agreed upon key, with the hacker being able to figure this out.

So it back to the fact that "aᵇ mod p" is both cheap to calculate in one direction (cheaper than just aᵇ), but impractical in the other direction, so I can send the result across the wire and the hacker can't figure out 'b'. From my perspective, it's just code.

In other words, think in terms of JavaScript where I write a function 'magic(x,y)', where for some reason 'magic(a,magic(b,g))' gives the same result as 'magic(b, magic(a,g))' and that 'magic(x,y)' is impractic to reverse (can't predict 'x' and 'y' from the result).