Ciphers and Number Theory
Visitors to Mathematical Sciences during our undergraduate Open Days were given a code wheel to introduce how mathematics relates to ciphers. Here, Mathematical Sciences Admissions Tutor Nick Wright explores ciphers and number theory, and if you were given a code wheel, you can add your own coded message in the comments section.
When we think of codes and ciphers this often creates a mental picture of spies, of giant room sized computers and the iconic enigma machine from World War 2. But this history of codes goes back much further than this.
One of the earliest recorded uses of ciphers to hide information was by Julius Caesar. In his time he used numerous different codes. One example was to replace Roman letters (a, b, c, etc.) with Greek letters (α, β, γ, etc.) to confuse the enemy. (For some reason mathematicians also love to use Greek letters!)
However the code that Caesar is perhaps most remembered for is the Caesar shift – and this is where number theory makes its appearance. In this code all letters are moved a fixed number of steps through the alphabet. Caesar himself used a shift of 3: A is replaced by D, B is replaced by E etc. This raises an obvious question: what do we do at the end of the alphabet? W is replaced by Z, but what about X,Y,Z? The obvious answer is to replace these by A,B,C.
| Plaintext | Ciphertext |
| A | D |
| B | E |
| C | F |
| . | |
| . | |
| W | Z |
| X | A |
| Y | B |
| Z | C |
Let’s replace the letters with numbers 1,2,3,…26. For the numbers 1 through 23 the code adds 3. For the numbers 24,25,26 we add 3 but then take off 26 to get back into the range 1,…26.
This is just like what happens with time on a clock. If we start at 11 o’clock and add three hours we get to 14 o’clock. This is fine if we are using a 24 hour clock but otherwise we must subtract 12 to get back into the range 1,…,12. On the 24 hour clock something similar happens if we start at 23:00 and add 3 hours. We get 26 and then subtract 24 to find a time of 2:00. With the 24 hour clock there is one difference: we use the numbers from 0 through 23 instead of 1 though 24.
All these are examples of modular arithmetic: we begin by picking a number n which we call the modulus. For example n might be 26 (the number of letters in the alphabet) or 12 or 24 for the number of hours on a clock, or use your own favourite number. I quite like 29 because it’s a prime number and greater than 26.
We say that two numbers are congruent modulo n if they differ by one or more n‘s, for instance 2 and 14 and 26 are all congruent modulo 12. Every number is congruent to precisely one number from 1 up to n. Or more commonly, following the model of the 24 hour clock, we will say that every number is congruent to precisely one number from 0 up to n – 1.
We’re now ready to do some modular arithmetic: taking two numbers in our preferred range 0,1,…,n – 1, we can add or multiply them. The resulting answer may or may not be in our preferred range, but taking away sufficiently many n‘s we will return to this range. It’s just like when we added 3 to 23 and got the answer 2. We say 23 + 3 = 2 modulo 24.
Returning to our codes, the Ceasar shift is given by adding 3 modulo 26. Different shifts are given by adding different numbers from the range 1,…,25 (since adding 0 is not a very useful code!).
Can we also use multiplication to create codes? Well we have to be a bit more careful. Let’s do an example: 2 × 16 = 32 which is congruent to 6 modulo 26. However 2 × 3 = 6. So multiplication be 2 is not reversible: there would be no way to decode the message.
The problem is that 2 is a factor of our modulus 26. This is why a prime number is advantageous – it has no factors (other than 1 and itself). So let’s augment our alphabet with an additional 3 characters. It doesn’t really matter what they are, but we’ll choose − < and >. The new alphabet
− A B C D E F G H I J K L M N O P Q R S T U V W X Y Z < >
has 29 characters which we label by the numbers from 0 to 29 − 1 = 28.
Now we’re in business to come up with a clever code based on multiplication. If we multiply by 2 (or indeed by any number up to 28) then no answer will be repeated.
1 → 2 → 4 → 8 → 16 → 3 → 6 → 12 …
The jump from 16 to 3 in the middle of this string is explained by the fact that 2 × 16 = 32 which is now congruent to 3 as we’ve chosen our modulus to be 29.
The usual rules of arithmetic still apply in the modular world. For instance
(2 × 16) × 3 = 3 × 3 = 9 and 2 × (16 × 3) = 2 × 19 = 9
(note that 48 = 19 + 29 and 38 = 9 + 29) so we can rearrange formulas as we would in ordinary algebra.
(a + b) + c = a + (b + c), (a × b) × c = a × (b × c), a × (b + c) = (a × b) + (a × c)
This now puts us in a position where we can prove the reversibility of multiplication required to make our multiplicative code work.
We could prove it simply by computing 2 × a for every a from 0 up to 28 and checking that there are no repeats. However that would be dull and would not enlighten us about other cases, such as multiplication by 3 or a different choice of modulus.
Sticking with the times 2 example let us first note that 15 × 2 = 1 modulo 29.
If 2 × a = 2 × b then it must follow that 15 × (2 × a) = 15 × (2 × b). But by our rules of arithmetic this means that (15 × 2) × a = (15 × 2) × b. As 15 × 2 = 1 we see that 1 × a = 1 × b, so the only case where we get a repetition 2 × a = 2 × b is when a is the same as b.
A similar argument proves that multiplication by 3 produces no repeats, since 10 × 3 = 1 modulo 29.
Taking a slight tangent I invite you to consider the following puzzle:
You have a bucket with volume 26 litres and another bucket with volume 9 litres. How can you measure out 1 litre?
Now suppose the buckets have volumes 26 and 10 litres. What is the smallest volume you can now measure out?
Have a think…
Now returning to our modular arithmetic we’d like to know that multiplication is always reversible modulo 29. It worked for 2 and for 3 because we were able to find numbers (15 and 10 respectively) giving a product of 30 – and this is congruent to 1 modulo 29.
In the language of the bucket problem, say we had a bucket of volume 29 litres and another bucket of volume 3. To measure out a single litre we fill our smaller bucket 10 times, and each time pour into the larger bucket. Except that as we pour in the 10th bucket we stop when our bucket of volume 29 becomes full and a single litre will be left in the small bucket.
Mathematically the bucket problem amounts to this: given two numbers a and n what is the smallest positive number that can be written in the form b × a − c × n ?
The answer is the greatest common divisor (or g.c.d. for short) of a and n. The g.c.d. is the largest number while divides both a and n.
This result is called Bezout’s Lemma.
The proof is as follows. Let g be the g.c.d. of a and n and let m = b × a − c × n. Both a and n are divisible by g so m must also be divisible by g. In particular m is at least g.
If m is greater than g then it cannot be a divisor of both a and n, since g is the greatest divisor.
Say a is not divisible by m. Take −a and add m repeatedly until the number becomes positive. Write d for the number of m‘s added. The number dm − a is positive, but less than m and moreover can be written as dm − a = d(ba − cn) − a = (db – 1)a − (dc)n. We have thus found a new number, smaller than m, that can be written as a multiple of a minus a multiple of n. In the language of buckets we’ve found a way to measure out a smaller volume.
Similarly if n is not divisible by m then we can again find a smaller number.
We conclude that the smallest number which can be written in the form b × a − c × n is the greatest common divisor g of a and n.
Now returning to the question of multiplicative codes, if a and n have no common factors other than 1 then by Bezout’s Lemma we can find b and c such that b × a − c × n = 1 or in other words b × a = c × n + 1 which is congruent to 1 modulo n. This makes multiplication by a reversible. When n is a prime number, such as 29, we can use any number from 1 up to n − 1 and get a reversible multiplication.
These multiplicative codes are still quite easy to crack by the technique of frequency analysis. Take a piece of text, such as the previous sentence. What is the most common character appearing in it? If one includes the spaces then these are the most common character so are a bit of a give-away. For this reason spaces are often omitted when writing coded messages.
But there’s another give-away too. The letter E is the most commonly used in the English language and so it tends to pop up much more often than any other letter. Again taking that sentence “These multiplicative codes…” we find the letter E appears 12 times. The next most common is T with 8 appearances followed by I with 7. Here’s the sentence again, written in code.
X<FQFDBZXEYZEUGXEIFUR>FQGJFQXEZZCBEXFFGQA
XRUJGUSNAX<FXFU<KECBFRMMJFCBFKUAGKGZAQEQ
Suppose we didn’t know what the message said and wanted to break the code. A quick count reveals that the most common letter here is F. We would therefore correctly guess that F (the 6th letter of the alphabet) encodes the letter E (letter 5). If we know that this is a multiplicative code then to figure out what we’ve multiplied by all we need to do is solve the equation
a × 5 = 6 modulo 29
As a first step, let’s solve the equation b × 5 = 1 modulo 29. We find that b = 6, since 6 × 5 is congruent to 1. Now multiplying both sides of the equation by 6 we get
6 × (6 × 5) = 6 × 1 = 6 modulo 29
A quick rearrangement gives us
(6 × 6) × 5 = 6 modulo 29
so the answer is a = 6 × 6 = 7 modulo 29. The message was encoded by multiplying all letters by 7.
Of course what we really want to do is to decode the message. As we have seen, decoding is also given by multiplication. Since F should decode to E, the number we need to multiply by is the number c satisfying the equation
c × 6 = 5 modulo 29
Now 5 × 6 = 1 so 5 × 5 × 6 = 5 × 1 = 5. So c = 5 × 5 = 25. The message can now be decoded by multiplying all letters by 25.
Starting with the X (the 24th letter of the alphabet) we need to find 25 × 24. Let’s use another trick. This is (29 − 4) × (29 − 5). Expanding this we get some number of 29’s (which can ignore as we’re doing arithmetic modulo 29) plus 4 × 5 = 20. So the answer is T the 20th letter of the alphabet. Repeating the trick < was the 27th symbol in our alphabet so decodes as (29 − 4) × (29 − 2) = 8 giving us the letter H. Now keep going and we recover our original message.
Of course it’s a bit long-winded doing this all by hand, but that’s where it helps to have a code-wheel which can compute sums and products for you – and also convert between letters and numbers.
Here’s another coded message. See if you can crack it (…and yes it is a multiplication code).
BRL>CBRLQYWQWL>CGCWLWAGFCYLCSCE
…and, if you’re still stuck on the bucket problem…
For the 9 litre case, fill your 9 litre bucket 3 times and use this to fill up the 26 litre bucket. You’ll be left with 1 litre in your 9 litre bucket when the 26 litre bucket is full.
The 10 litre bucket is a bit trickier. You can’t get 1 litre. As 10 and 26 have a factor of 2 in common anything you measure out must have an even volume. You can get 2 litres so this is the smallest volume you can measure. To get 2 litres, you fill the 10 litre bucket 8 times. Each time pour into the 26 litre bucket, but when that gets full empty it out. Once you’ve filled this three times you will have poured a total of 26 × 3 = 78 litres of water from your 10 litre bucket. That’s 7 full buckets and 8 litres from the last one, leaving 2 litres in the bucket!
Leave your own coded messages below.
Dr Nick Wright is an Associate Professor and Admissions Tutor for undergraduate courses in Mathematical Sciences at Southampton.
For more information on undergraduate degree courses in Mathematical Sciences, click here.
Leave a Reply
You must be logged in to post a comment.