An introduction to modular arithmetic¶
Most of my tech-savvy peers have heard of the RSA algorithm or RSA certificates. It is commonly used to generate ssh key pairs, for example.
ssh-keygen -t rsa -f mykey
The command above produces two files, a private and public key.
ll mykey*
.rw------- 2.6k djustice 7 Aug 18:25 mykey
.rw-r--r-- 586 djustice 7 Aug 18:25 mykey.pub
You can share the public key, but the private key must be kept secure (also note the file permission differences).
Public means public, too!
You can see someone's public key on Github by appending .keys to their username.
It may respond with ssh-rsa ... or something else depending on the algorithm used to generate the key (EdDSA is common).
curl https://github.com/some-user.keys
ssh-rsa lots-o-chars...
Many of us in the tech world have seen this base64-encoded soup daily, but have you ever peeked under the hood? I think the RSA algorithm is one of the more tractable subjects in cryptography, and it opens the door to many other ideas in number theory.
The RSA algorithm works because of the properties of prime numbers and modular arithmetic. I will start with the latter, and I hope to work the former into another post as I develop this topic. My goal is to spark an interest, not to provide a rigorous discussion. There is plenty of jargon to discuss, so please try to work through it. There is a reason for many of these terms, and I will do my best to justify them as we go.
We will only be working with integers in this article, so think of the set of whole numbers from -∞ to ∞. For example: {..., -3, -2, -1, 0, 1, 2, 3, ...}. This set is known in mathematical circles as ℤ. The symbol is used because it represents a precise idea in a compact space.
Clock arithmetic¶
Some mathematicians don't like the clock metaphor for modular arithmetic, but I think it is a great starting point. In my own experiences, I have had the most success explaining this subject to other people using clocks, and the comparison doesn't have any sharp edges that will confuse you later on.
Starting with a 12-hour wall clock, we will create a number system called "the integers modulus 12".
That is quite a bit to write several times in a row, so you will often see ℤ mod 12, or simply "mod 12".
This wouldn't be a techy post without some code!
The modulus function is essentially the remainder of division by some number; in the current case, 12.
Most programming languages perform the operation using the binary operator % (binary means it takes two arguments).
for n in range(1, 14):
print("The remainder of {n} divided by 12 is {r}.".format(n=n, r=n % 12))
Those first few lines can trip people up.
Why is 1 the remainder of 1 divided by 12?
It is because 12 * 0 + 1 = 1.
Pay close attention to the last few values.
The remainders don't continue to increment without bound, they roll over back to zero!
Okay, I will admit that it probably isn't that exciting. Most of us should remember these facts from grade school. Continuing our introduction (or refresher), do you recall that we can perform arithmetic in this number system? Ask yourself, if the hour hand is on 5 right now, what time will it be in 37 hours? The answer is
(5 + 37) mod 12 = 42 mod 12 = 6 o'clock
Here is another way to think of it.
37 mod 12 = 1 and 5 + 1 = 6.
Is that a coincidence?
It is not!
What about multiplication; does that work in our modular system?
What does 5 * 9 hours equal?
(5 * 9) mod 12 = 45 mod 12 = 9 o'clock
This may seem a bit contrived, but there are practical applications. It is 2 o'clock when you start your delivery run. You drive 3 hours north to the warehouse, then make 3, 3-hour round-trips to a remote depot and back. What time do you return to the warehouse?
[(2 + 3) + (3 * 3)] mod 12 = (5 + 9) mod 12 = 14 mod 12 = 2 mod 12 = 2
This is fairly basic number theory; things you most likely already know. If we dig a bit deeper, an interesting structure emerges.
Consider the numbers on the ray originating at 4.
{..., -20, -8, 4, 16, 28, 40, ...}
When performing arithmetic in mod 12, we can substitute any of these numbers with each other and achieve the same result.
Mathematicians call this an equivalence class.
The terminology is necessary because we are trying to describe a precise idea.
Clearly, -20 and 40 are not equal to one another.
However, in the mod 12 number system, they are equivalent when we perform computations.
This is typically written as [4] where
[4] = {..., -20, -8, 4, 16, 28, 40, ...}
Each number n in this set is related to ℤ by n mod 12 = 4, or more compactly: {n | n ∈ ℤ, n mod 12 = 4}.
Look at a few more of these equivalence classes:
[0] = {..., -24, -12, 0, 12, 24, 36, ...},
[1] = {..., -23, -11, 1, 13, 25, 37, ...},
[2] = {..., -22, -10, 2, 14, 26, 38, ...},
...
[11] = {..., -13, -1, 11, 23, 35, 47, ...}
Start at any column and make your way down subtracting 1 each time. When you get to the bottom, move one column to the right. Notice anything interesting? Every single number in ℤ is represented in one of these... partitions. Division already has a definition in mathematics, so we will use the phrase partition to describe these collections of numbers. The really neat part is that this system of partitions representing all the integers works in any modular base! My teenage son who has no use for math even admitted that this is pretty cool, so put that in your pipe and smoke it!
Homework¶
This wouldn't be an article on math without some homework. Use your favorite search engine and read about the Caesar cipher. Write an implementation in your favorite language and see if your friends can break it. Just don't send it to me; I am terrible at cryptography. 😂 You can strengthen the cipher by using a random permutation of the alphabet, but both ends of the conversation must use the same permutation. This is still susceptible to frequency attacks, so don't use it to send GPG keys over the internet.
Next steps¶
This subject is inspired by the work I did on my research paper to earn my B.S. in Applied Mathematics. My plan is to translate it in a way that will be consumable by most programmers (really anyone) who have a little bit of mathematics background.
If I don't get hit by a bus, I hope to write:
- Prime numbers, the Extended Euclidean Algorithm, and the GCD.
- The Modular Inverse, an attempt to explain it without hand-waving.
- How RSA works (the math, not the code).
I am going to provide a detailed guide, but it is up to the reader to sit down and draw their own conclusions about how these things work. Math is not a spectator sport!
References¶
Clock photo: https://commons.wikimedia.org/wiki/File:B_%26_HB_Kent_Pocket_Watch_(52584138758).jpg
.jpg){kind=link}