Mathematics

Cryptography is nothing more than applied mathematics. You don't have to trust other people to tell you that something is secure. You can know it for yourself.

Inverse functions

To prove my identity, I can generate two functions. One function will be the inverse of the other. That means that if I were to compute a value with one function, I could compute the original input with the inverse.

I can use this to prove my identity like this. I give you one function, but I keep the inverse to myself. Then you can make up a secret and run it through the function I gave you. Only I, with my inverse function, could turn it back into the original secret.

Modulo arithmetic

Have you ever used a secret decoder ring? It maps each of the 26 letters of the alphabet to another letter. The mapping depends upon how far you turn the ring. But the ring only has 26 settings. Once you go past the last setting, you wrap around to the beginning.

Let's number those settings starting at zero. Setting 0 is the way the ring came out of the box. Move it one space, and you are at setting 1. Move it another space and you are at setting 2. Keep going. Once you get to setting 25, you've gone through all 26 settings. If you move one more after that, you'll be back at 0.

That operation is called addition modulo 26. At each step, we added one within the modulus of 26. The only numbers in our universe are 0-25. All of our mathematical operations have to map back to that very limited set of numbers.

We can do not just addition in a modulus, but also subtraction, multiplication, and exponentiation. But we can't do division. That's because more than one number could lead to any given result.

Suppose we wanted multiply 2 times 24 modulo 26. 2 times 24 is usually 48, but in modulo 26, we can't count that high. So we subtract 26 to bring it back in range. That gives us 48-26, or 22.

So what about 2 times 11 modulo 26? Shouldn't that also be 22? Yes, in fact, it is.

So that's why we can't divide in modulo math. What would 22 divided by 2 give us? 11? 24? Both are equally valid.