I’m always really surprised, disappointed, and a bit gassy over how despised anything involving even the simplest of Mathematics is by most Computer Scientists; the mere mention of the word “derivative” is enough to invoke a cringe of repressed childhood-pain from all but the strongest-willed of programmers. However, even if a ‘matrix’ is nothing more to you than a bootleg DVD you torrented when you were 16, you can still enjoy the limitless pleasure provided by a basic understanding of modern mathematics. In fact, after a few simple preliminaries in modular arithmatic (don’t worry – it’s not nearly as scary as it sounds), the algorithm for RSA encryption is actually incredibly simple – so buckle your seatbelt and put on your thinking cap for today’s magical adventure into the strange and wondrous world of mathematics.
1. Modular Arithmetic
If you are still reading this, then either you were misdirected here by the malevolent Internet traffik demon (which means my monetary bribes are working), or you sincerely want to learn how RSA encryption works, in which case I hope our almighty five-legged overlord takes mercy on your soul as it burns in the deepest pits of hell.
Most programmers are familiar with the syntax
18 mod 5
In case you are not, mod (which stands for modulus) simply gives back the remainder from dividing the left number by the right. Since the remainder of 18/5 is 3, this means
18 mod 5 = 3
In mathematics, the syntax is a bit different. Rather than saying “the modulus of 18 by 5 is equal to some number (ie. 3)”, we say “18 is congruent to some number mod 5." It is just as correct to say “3 is congruent to 18 mod 5” as it is to say “18 is congruent to 3 mod 5.”
We would write this latter statement as 18 ≡ 3 (mod 5).
What we are really saying using this notation is that if we take left-hand of the equation and mod it by 5, then take the right-hand side and mod it by 5, we will get the same thing. When we restrict our world to numbers mod 5 like this, 18 and 3 act like the same number.
This new notation allows us to do some very cool symbol-pushing (all of which, I assure you, is completely valid). For instance, it can be shown that the properties of most normal integer operations – addition, subtraction, multiplication, exponentiation – carry over to modular arithmetic, so that, for example,
xa * xb ≡ x(a+b) (mod n)
It is also rather obvious (and, of course, can be proved) that when adding, subtracting, or multiplying, you can replace one number with another it is congruent to; so, for instance, since 18 ≡ 3 (mod 5),
182 ≡ 32 ≡ 9 ≡ 4 (mod 5)
When working with negative numbers mod n, we find congruencies by simply adding n repeatedly until we get a positive number. For example,
-21 ≡ -1 ≡ 19 (mod 20)
This gives us a new trick to put in our bag for determining (without a calculator) some large numbers mod n:
1910 ≡ (-1)10 ≡ 1 (mod 20)
Cool!
In modular arithmetic, we are usually concerned with only integers; this means that numbers don’t have fractional inverses the way they do in regular arithmetic. That is, there is no number you can multiply 5 by (mod 10) to get 1, since we’re not considering 1/5 a number. Nonetheless, there are certain cases† in which numbers in modular arithmetic still have inverses! For instance, notice that 7 * 3 ≡ 21 ≡ 1 (mod 10), so 7 and 3 are inverses (mod 10).
For a final example to show just how powerful modular arithmetic is, let’s calculate the last decimal digit of, say, 3403. Notice that “the last decimal digit” is the same as “its value (mod 10).” Hence, we’re looking to reduce
3403 (mod 10).
The solution is actually quite simple. First, we realize that
34 ≡ 81 ≡ 1 (mod 10)
Then, since 3403 = (34)100 * 33,
3403 ≡ (34)100 * 33 ≡ (1)100 * 33 ≡ 27 ≡ 7 (mod 10)
Thus, in less than a minute, we just determined that the last digit of 3403 is 7, without a calculator!
