{"id":250,"date":"2016-06-28T15:06:00","date_gmt":"2016-06-28T15:06:00","guid":{"rendered":"http:\/\/blog.soton.ac.uk\/fshs\/?p=250"},"modified":"2016-07-08T11:44:04","modified_gmt":"2016-07-08T11:44:04","slug":"ciphers-and-number-theory","status":"publish","type":"post","link":"https:\/\/blog.soton.ac.uk\/fshs\/2016\/06\/28\/ciphers-and-number-theory\/","title":{"rendered":"Ciphers and Number Theory"},"content":{"rendered":"

Visitors to Mathematical Sciences during our undergraduate Open Days were given a code wheel to introduce how mathematics relates to ciphers. \u00a0Here, 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.<\/p>\n

\"Enigma<\/a>
Enigma code machine<\/figcaption><\/figure>\n

 <\/p>\n

<\/p>\n

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.\u00a0 But this history of codes goes back much further than this.<\/p>\n

One of the earliest recorded uses of ciphers to hide information was by Julius Caesar.\u00a0 In his time he used numerous different codes.\u00a0 One example was to replace Roman letters (a, b, c, etc.) with Greek letters (\u03b1, \u03b2, \u03b3, etc.) to confuse the enemy.\u00a0 (For some reason mathematicians also love to use Greek letters!)<\/p>\n

However the code that Caesar is perhaps most remembered for is the Caesar shift \u2013 and this is where number theory makes its appearance.\u00a0 In this code all letters are moved a fixed number of steps through the alphabet.\u00a0 Caesar himself used a shift of 3: A is replaced by D, B is replaced by E etc.\u00a0 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?\u00a0 The obvious answer is to replace these by A,B,C.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
Plaintext<\/td>\nCiphertext<\/td>\n<\/tr>\n
A<\/td>\nD<\/td>\n<\/tr>\n
B<\/td>\nE<\/td>\n<\/tr>\n
C<\/td>\nF<\/td>\n<\/tr>\n
.<\/td>\n<\/td>\n<\/tr>\n
.<\/td>\n<\/td>\n<\/tr>\n
W<\/td>\nZ<\/td>\n<\/tr>\n
X<\/td>\nA<\/td>\n<\/tr>\n
Y<\/td>\nB<\/td>\n<\/tr>\n
Z<\/td>\nC<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Let’s replace the letters with numbers 1,2,3,…26.\u00a0 For the numbers 1 through 23 the code adds 3.\u00a0 For the numbers 24,25,26 we add 3 but then take off 26 to get back into the range 1,…26.<\/p>\n

This is just like what happens with time on a clock.\u00a0 If we start at 11 o’clock and add three hours we get to 14 o’clock.\u00a0 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.\u00a0 On the 24 hour clock something similar happens if we start at 23:00 and add 3 hours.\u00a0 We get 26 and then subtract 24 to find a time of 2:00.\u00a0 With the 24 hour clock there is one difference: we use the numbers from 0 through 23 instead of 1 though 24.<\/p>\n

All these are examples of modular arithmetic: we begin by picking a number n<\/em> which we call the modulus<\/strong>.\u00a0 For example n<\/em> 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.\u00a0 I quite like 29 because it’s a prime number and greater than 26.<\/p>\n

We say that two numbers are congruent modulo<\/strong> n <\/em>if they differ by one or more n<\/em>‘s,<\/em> for instance 2 and 14 and 26 are all congruent modulo 12.\u00a0 Every number is congruent to precisely one number from 1 up to n<\/em>.\u00a0 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<\/em> – 1.<\/p>\n

We’re now ready to do some modular arithmetic: taking two numbers in our preferred range 0,1,…,n<\/em> – 1, we can add or multiply them.\u00a0 The resulting answer may or may not be in our preferred range, but taking away sufficiently many n<\/em>‘s we will return to this range.\u00a0 It’s just like when we added 3 to 23 and got the answer 2.\u00a0 We say 23 + 3 = 2 modulo 24.<\/p>\n

Returning to our codes, the Ceasar shift is given by adding 3 modulo 26.\u00a0 Different shifts are given by adding different numbers from the range 1,…,25 (since adding 0 is not a very useful code!).<\/p>\n

Can we also use multiplication to create codes?\u00a0 Well we have to be a bit more careful.\u00a0 Let’s do an example: 2 \u00d7 16 = 32 which is congruent to 6 modulo 26. However 2 \u00d7 3 = 6.\u00a0 So multiplication be 2 is not reversible: there would be no way to decode the message.<\/p>\n

The problem is that 2 is a factor of our modulus 26.\u00a0 This is why a prime number<\/strong> is advantageous \u2013 it has no factors (other than 1 and itself).\u00a0 So let’s augment our alphabet with an additional 3 characters.\u00a0 It doesn’t really matter what they are, but we’ll choose \u2212 < and >.\u00a0 The new alphabet<\/p>\n

\u2212 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 < ><\/p>\n

has 29 characters which we label by the numbers from 0 to 29 \u2212 1 = 28.<\/p>\n

Now we’re in business to come up with a clever code based on multiplication.\u00a0 If we multiply by 2 (or indeed by any number up to 28) then no answer will be repeated.<\/p>\n

1 \u2192 2 \u2192 4 \u2192 8 \u2192 16 \u2192 3 \u2192 6 \u2192 12 \u2026<\/p>\n

The jump from 16 to 3 in the middle of this string is explained by the fact that\u00a0 2 \u00d7 16 = 32 which is now congruent to 3 as we’ve chosen our modulus to be 29.<\/p>\n

The usual rules of arithmetic still apply in the modular world.\u00a0 For instance<\/p>\n

(2 \u00d7 16) \u00d7 3 = 3 \u00d7 3 = 9\u00a0\u00a0 and\u00a0\u00a0 2 \u00d7 (16 \u00d7 3) = 2 \u00d7 19 = 9<\/p>\n

(note that 48 = 19 + 29 and 38 = 9 + 29) so we can rearrange formulas as we would in ordinary algebra.<\/p>\n

(a<\/em> + b<\/em>) + c<\/em> = a<\/em> + (b<\/em> + c<\/em>),\u00a0\u00a0 (a<\/em> \u00d7 b<\/em>) \u00d7 c<\/em> = a<\/em> \u00d7 (b<\/em> \u00d7 c<\/em>),\u00a0\u00a0 a<\/em> \u00d7 (b<\/em> + c<\/em>) = (a<\/em> \u00d7 b<\/em>) + (a<\/em> \u00d7 c<\/em>)<\/p>\n

This now puts us in a position where we can prove<\/strong> the reversibility of multiplication required to make our multiplicative code work.<\/p>\n

We could prove it simply by computing 2 \u00d7 a<\/em> for every a<\/em> from 0 up to 28 and checking that there are no repeats.\u00a0 However that would be dull and would not enlighten us about other cases, such as multiplication by 3 or a different choice of modulus.<\/p>\n

Sticking with the times 2 example let us first note that 15 \u00d7 2 = 1 modulo 29.<\/p>\n

If\u00a0 2 \u00d7 a<\/em> =\u00a0 2 \u00d7 b<\/em> then it must follow that 15 \u00d7 (2 \u00d7 a<\/em>) = 15 \u00d7 (2 \u00d7 b<\/em>).\u00a0 But by our rules of arithmetic this means that (15 \u00d7 2) \u00d7 a<\/em> = (15 \u00d7 2) \u00d7 b<\/em>.\u00a0 As\u00a0 15 \u00d7 2 = 1 we see that 1 \u00d7 a<\/em> = 1 \u00d7 b<\/em>, so the only case where we get a repetition\u00a0 2 \u00d7 a<\/em> =\u00a0 2 \u00d7 b<\/em> is when a is the same as b<\/em>.<\/p>\n

A similar argument proves that multiplication by 3 produces no repeats, since 10 \u00d7 3 = 1 modulo 29.<\/p>\n

Taking a slight tangent I invite you to consider the following puzzle:<\/p>\n

You have a bucket with volume 26 litres and another bucket with volume 9 litres. How can you measure out 1 litre?<\/em><\/p>\n

Now suppose the buckets have volumes 26 and 10 litres.\u00a0 What is the smallest volume you can now measure out?<\/em><\/p>\n

Have a think…<\/p>\n

Now returning to our modular arithmetic we’d like to know that multiplication is always reversible modulo 29.\u00a0 It worked for 2 and for 3 because we were able to find numbers (15 and 10 respectively) giving a product of 30 \u2013 and this is congruent to 1 modulo 29.<\/p>\n

In the language of the bucket problem, say we had a bucket of volume 29 litres and another bucket of volume 3.\u00a0 To measure out a single litre we fill our smaller bucket 10 times, and each time pour into the larger bucket.\u00a0 Except that as we pour in the 10th<\/sup> bucket we stop when our bucket of volume 29 becomes full and a single litre will be left in the small bucket.<\/p>\n

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 <\/em>\u00d7 a <\/em>\u2212 <\/em>c<\/em> \u00d7 n ?<\/em><\/p>\n

The answer is the greatest common divisor (or g.c.d. for short) of a <\/em>and n<\/em>.\u00a0 The g.c.d. is the largest number while divides both a <\/em>and n<\/em>.<\/p>\n

This result is called Bezout’s Lemma.<\/p>\n

The proof is as follows.\u00a0 Let g<\/em> be the g.c.d. of a <\/em>and n and let m =\u00a0 b<\/em> \u00d7 a <\/em>\u2212 <\/em>c<\/em> \u00d7 n<\/em>. Both a <\/em>and n <\/em>are divisible by g <\/em>so m <\/em>must also be divisible by g<\/em>.\u00a0 In particular m<\/em> is at least g<\/em>.<\/p>\n

If m<\/em> is greater than g<\/em> then it cannot be a divisor of both a<\/em> and n<\/em>, since g<\/em> is the greatest divisor.<\/p>\n

Say a<\/em> is not divisible by m<\/em>. Take \u2212a<\/em> and add m repeatedly until the number becomes positive. \u00a0Write d for the number of m<\/em>‘s added. The number dm \u2212 a<\/em> is positive, but less than m<\/em> and moreover can be written as dm \u2212 a <\/em>=\u00a0 d<\/em>(ba \u2212 cn<\/em>) \u2212 a<\/em> =\u00a0 (db <\/em>– 1)a \u2212 <\/em>(dc<\/em>)n<\/em>.\u00a0 We have thus found a new number, smaller than m<\/em>, that can be written as a multiple of a <\/em>minus a multiple of n<\/em>.\u00a0 In the language of buckets we’ve found a way to measure out a smaller volume.<\/p>\n

Similarly if n<\/em> is not divisible by m<\/em> then we can again find a smaller number.<\/p>\n

We conclude that the smallest number which can be written in the form b \u00d7 a <\/em>\u2212 <\/em>c \u00d7 n<\/em> is the greatest common divisor g<\/em> of a<\/em> and n<\/em>.<\/p>\n

Now returning to the question of multiplicative codes, if a<\/em> and n<\/em> have no common factors other than 1 then by Bezout’s Lemma we can find b<\/em> and c<\/em> such that b<\/em> \u00d7 a <\/em>\u2212 <\/em>c<\/em> \u00d7 n<\/em> = 1 or in other words b<\/em> \u00d7 a<\/em> = c<\/em> \u00d7 n<\/em> + 1 which is congruent to 1 modulo n<\/em>.\u00a0 This makes multiplication by a<\/em> reversible.\u00a0 When n<\/em> is a prime number, such as 29, we can use any number from 1 up to n <\/em>\u2212<\/em> 1 and get a reversible multiplication.<\/p>\n

These multiplicative codes are still quite easy to crack by the technique of frequency analysis.\u00a0 Take a piece of text, such as the previous sentence.\u00a0 What is the most common character appearing in it?\u00a0 If one includes the spaces then these are the most common character so are a bit of a give-away.\u00a0 For this reason spaces are often omitted when writing coded messages.<\/p>\n

But there’s another give-away too.\u00a0 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.\u00a0 Again taking that sentence \u201cThese multiplicative codes…\u201d we find the letter E appears 12 times.\u00a0 The next most common is T with 8 appearances followed by I with 7.\u00a0 Here’s the sentence again, written in code.<\/p>\n

X<FQFDBZXEYZEUGXEIFUR>FQGJFQXEZZCBEXFFGQA<\/p>\n

XRUJGUSNAX<FXFU<KECBFRMMJFCBFKUAGKGZAQEQ<\/p>\n

Suppose we didn’t know what the message said and wanted to break the code.\u00a0 A quick count reveals that the most common letter here is F.\u00a0 We would therefore correctly guess that F (the 6th<\/sup> letter of the alphabet) encodes the letter E (letter 5).\u00a0 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<\/p>\n

a<\/em> \u00d7 5 = 6 modulo 29<\/p>\n

As a first step, let’s solve the equation b<\/em> \u00d7 5 = 1 modulo 29.\u00a0 We find that b<\/em> = 6, since 6 \u00d7 5 is congruent to 1.\u00a0 Now multiplying both sides of the equation by 6 we get<\/p>\n

6 \u00d7 (6 \u00d7 5) = 6 \u00d7 1 = 6 modulo 29<\/p>\n

A quick rearrangement gives us<\/p>\n

(6 \u00d7 6) \u00d7 5 = 6 modulo 29<\/p>\n

so the answer is a<\/em> = 6 \u00d7 6 = 7 modulo 29.\u00a0 The message was encoded by multiplying all letters by 7.<\/p>\n

Of course what we really want to do is to decode the message.\u00a0 As we have seen, decoding is also given by multiplication.\u00a0 Since F should decode to E, the number we need to multiply by is the number c<\/em> satisfying the equation<\/p>\n

c<\/em> \u00d7 6 = 5 modulo 29<\/p>\n

Now 5 \u00d7 6 = 1 so\u00a0 5 \u00d7 5 \u00d7 6 = 5 \u00d7 1 = 5.\u00a0 So c<\/em> =\u00a0 5 \u00d7 5 = 25.\u00a0 The message can now be decoded by multiplying all letters by 25.<\/p>\n

Starting with the X (the 24th<\/sup> letter of the alphabet) we need to find 25 \u00d7 24.\u00a0 Let’s use another trick.\u00a0 This is (29 \u2212 4) \u00d7 (29 \u2212 5).\u00a0 Expanding this we get some number of 29’s (which can ignore as we’re doing arithmetic modulo 29) plus 4 \u00d7 5 = 20.\u00a0 So the answer is T the 20th<\/sup> letter of the alphabet.\u00a0 Repeating the trick < was the 27th<\/sup> symbol in our alphabet so decodes as (29 \u2212 4) \u00d7 (29 \u2212 2) = 8 giving us the letter H.\u00a0 Now keep going and we recover our original message.<\/p>\n

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 \u2013 and also convert between letters and numbers.<\/p>\n

 <\/p>\n

Here’s another coded message.\u00a0 See if you can crack it\u00a0 (…and yes it is a multiplication code).<\/p>\n

BRL>CBRLQYWQWL>CGCWLWAGFCYLCSCE<\/p>\n

…and, if you’re still stuck on the bucket problem…<\/p>\n

For the 9 litre case, fill your 9 litre bucket 3 times and use this to fill up the 26 litre bucket.\u00a0 You’ll be left with 1 litre in your 9 litre bucket when the 26 litre bucket is full.<\/p>\n

The 10 litre bucket is a bit trickier.\u00a0 You can’t get 1 litre.\u00a0 As 10 and 26 have a factor of 2 in common anything you measure out must have an even volume.\u00a0 You can get 2 litres so this is the smallest volume you can measure.\u00a0 To get 2 litres, you fill the 10 litre bucket 8 times.\u00a0 Each time pour into the 26 litre bucket, but when that gets full empty it out.\u00a0 Once you’ve filled this three times you will have poured a total of 26 \u00d7 3 = 78 litres of water from your 10 litre bucket.\u00a0 That’s 7 full buckets and 8 litres from the last one, leaving 2 litres in the bucket!<\/p>\n

Leave your own coded messages below.<\/p>\n

Dr Nick Wright<\/a> is an Associate Professor and Admissions Tutor for undergraduate courses in Mathematical Sciences at Southampton.<\/p>\n

For more information on undergraduate degree courses in Mathematical Sciences, click here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Visitors to Mathematical Sciences during our undergraduate Open Days were given a code wheel to introduce how mathematics relates to ciphers. \u00a0Here, 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.  <\/p>\n","protected":false},"author":74545,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[882349,428163,1],"tags":[882349,374,440,428163,882350,65],"class_list":["post-250","post","type-post","status-publish","format-standard","hentry","category-cipher","category-maths","category-uncategorized","tag-cipher","tag-code","tag-mathematics","tag-maths","tag-number-theory","tag-southampton","column","twocol"],"_links":{"self":[{"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/posts\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/users\/74545"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":5,"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/posts\/250\/revisions"}],"predecessor-version":[{"id":263,"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/posts\/250\/revisions\/263"}],"wp:attachment":[{"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/media?parent=250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/categories?post=250"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.soton.ac.uk\/fshs\/wp-json\/wp\/v2\/tags?post=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}