Modular Arithmetic is a type of maths which falls under the number theory category, and gives us a whole new perspective when looking at numbers. The most common use of this idea is through clocks where after you get to 12 the clock resets back to 1. Which then leads to these strange equations such as:
7 + 9 = 4 Or 9 + 9 = 6
When looking at these equations one might see them as being incorrect, which they are for a normal mathematical equations, but true using clock arithmetic1. For example 10 o’clock is 4 hours before 2 o’clock, so what we are really doing is 2 - 4 = -2 and then adding 12 to that answer.
.˙. 2 - 4 + 12 = 10. This then brings about the idea of congruences, which we will need to use in order to understand some encryption systems.
Looking back on our clock arithmetic we could also write them as congruences using a modulus. A modulus “is a number that is used as a divisor for considering number sets, numbers being considered congruent when giving the same remainder when divided by a particular modulus”2. When in clock arithmetic we are using a modulus of 12. So looking at our past example our equations become:
7 + 9 = 16 ≣ 4 (mod 12) and 9 + 9 = 18 ≣ 6 (mod 12)
So we get 16 is congruent to 4 modulo 12 and 18 is congruent to 6 modulo 12
But we do not always have to use Modulus 12 when doing Modular Arithmetic, we can also use other numbers that are greater than 1. Such as using a Modulo 7:
23 ≣ 2 (mod 7) and 9 ≣ 2 (mod 7)
We can see that the difference between the two numbers can be divided by the modulus. For example 23 - 2 = 21, which can be divided into 7 evenly. 21 ÷ 7 = 3.
It’s this simple way of looking at numbers that gives us a big help when we are dealing with larger numbers. From the larger number, we can reduce it to a smaller number modulo m (m = any integer greater than 1). Such as what we have done with the number 23, we have found that its congruent partner is 2 (mod 7), making it an easier number to work with.
Have you ever wondered how a bank keeps your financial secrets safe and locked away so no one but you can access them? Or even how companies on the internet such as face book, store all of your personal information and keeps it safe? Well, it’s because of the simple idea of cryptography that you can sleep at night knowing that all of your information is safe. Cryptography is defined as “the art of writing or solving codes”3 and is one of the most important areas of study that exists in the world today. Codes aren’t only used to store our personal information, their main use was to assist the military in sending important messages to allies without their enemies finding out what the message said.
Cryptography uses some different terminology that you might not understand, so let’s just go over some of the key words that will come up in this investigation. The uncoded or original message will be referred to as the Plaintext. The act of encoding a message is known as Encryption and the result of all of this is what is called the Ciphertext. The act of changing the Ciphertext back to plain text is called Decrypting. Both the processes of Encrypting and Decrypting both rely on a certain piece of information called the Key. The key is like a password and holds all of the information needed to decrypt and encrypt a message. Without the key decrypting and encrypting is made a lot more difficult, but we call this Breaking the Code4.
When creating codes we write the plaintext in lower case letters (abcd) and we write the ciphertext in upper case letters (ABCD), this is so we can tell which is which.
The first cipher we will look at is a substitution cipher. A substitution cipher is one of the more common and easy to work with ciphers where we simply replace one letter with another letter and do this for every other