Modular Mathematics: Or How Computers Encrypt Messages

Have you ever wondered how cryptation of messages between computers work? It certainly is different than in the old age, when two people would agree on a code in secret, and then send messages with it. Two computers have no way of meeting and agreeing on a code over the Internet without risking that communication being snapped up by others. You would need to have a means of cryptation before you could agree on the cryptation you would use, and that obviously does not work. I am not an expert on technology, but I do study mathematics, and since that is the field which came up with the solution, I am here going to do a simple explanation of the mathematics behind modern encryption.

First, a little bit of theory. Computer encryption rests on number theory, and more specifically, modular math. What is modular math? Consider a clock. It only has numbers from 1 to 12. Addition of two numbers works normally, but if you do 11+3, you get 2. To generalize, when you get above or under the thresholds of 1 or 12, you either add or substract 12 to end up on inside the interval 1-12. This is modular math, the only difference being that we there use 0 instead of 12, so 11+1=0, and the interval is 0-11. This is called mathematics modulo 12, but we can do this for any natural number n. In modulo 3 we have that 1+1=2, 2+1=0 and 2×2=1, for example.

One other part from number theory needs to be understood, although I shall not give the proofs for any of this. We have something called the Euler totient function, denoted here by φ(n), n being any natural number. This function describes how many numbers lower than n are relatively prime to n. To numbers are relatively prime if there is no number larger than 1 that divides them both. 6 and 8 are not relatively prime, as both can be divided by 2. 7 and 9, however, are, as you can test by trying any number lower than 7.

φ(n) counts the number of relatively prime numbers smaller than itself any number has. φ(8)=4, since 1,3,5 and 7 are relatively prime, an 2,4 and 6 are not. φ(14)=6, as 1,3,5,9,11 and 13 are relatively prime, and 2,4,6,7,8,10 and 12 are not. Now, without proof, I shall state a formula of immense importance to encryption, Euler's theorem: if a and n are relatively prime, then a^φ(n)=1 modulo n. So a to the power of φ(n) equals 1 modulo n. From this it follows that a^φ(n)+1=a modulo n, which we get by multiplying by a on both sides.

As a final note, φ(n) can be easily found if you know which prime numbers make up n. This will also be important.

Now we have the tools needed. What we want is a way of encrypting so that knowing how to decrypt does not reveal how to decrypt, to get the original message back. Look at the classic codes, where you would for example replace A with G, B with O and so on. If you knew how to encrypt this, you would know how to reverse the process. But what about something more like a padlock, one of those you can lock without the key? You could send the lock without to your friend, he could lock whatever needed locking, and send it to you, where you use your key. If someone steals the lock, they can only lock things, not open your mail.

And this is modern cryptation. First, you take two prime numbers, large and unknown to anyone else. Multiply them, this is your number n. Find your φ(n), and add 1. Now find two numbers which when multiplied becomes φ(n)+1. This is rather simple thanks to your knowledge of the prime numbers used to make n and the fact that these numbers, e and d, are not prime numbers, but it requires some more theory. One of these numbers, we may call it e, and the number n, becomes your public key, available to anyone. They can encrypt a message with it by turning the message into a number a, and take that to the power of e modulo n. a^e modulo n. This number is sent to you.

As you may know (a^b)^c=a^b×c. So given the number a^e, simply take this to the power of d modulo n, d being a number only known to you, and you have a^b×e modulo n=a^φ(n)+1 modulo n=a modulo n, our original message. Note that this only works if a is smaller than our original prime numbers, but this is easily done by splitting the message up in parts if it gets too big. Now you have your message, and no one who does not know d can decrypt it. This is how cryptation works, mathematically.

The trick to this method is the number n. If you know which two prime numbers n is made of, it is easy to figure out n, and to figure out what e and d is. But to have n and find the two prime numbers is a much more difficult task. There seems to be no easy way to do this, except going through the list of all prime numbers, trying each one.

And finally, an example, but with much lower numbers than computers use. Often the size of only one prime number which composes n can be of the magnitude of 10¹⁰⁰, which ensures that it is almost impossible to guess it just by going through a list of prime numbers. But just to demonstrate, here is an example done with numbers small enough for a calculator.

Let our prime numbers be 3 and 11. n=33, and φ(n) we can calculate to be 20. This can be done by using the prime numbers. So we want two numbers which when multiplied becomes 21. These numbers being so small, we can just inspect the number and find that 3 and 7 fits the bill.

So our public key, the information we give to other computers, is e=7, and n=33. Say someone wants to send the message 5(remember, it must relatively prime from 33). 5⁷ modulo 33= 14. So you get sent 14. Next: 14³ modulo 33= 5, just like it should be. And that is how it is done.