Caesar Codes
Mike May, S. J., 1998
(Worksheet 2 for Cryptography and Coding theory)
We start by having our standard message ready.
> message1 :=`AZaz Good morning Mr. Phelps. Your mission for today, should you choose to accept it, is to encode this message. AZaz`; temp[1] := convert(message1, bytes);
The first method of encryption mentioned in the book is the Caesar Code. Caesar encoded his messages by shifting each letter by three. In the book that is done by converting the letters to numbers from 1 to 26 (ignoring upper and lower case), adding 3 (with remainders, so 27 converts to 1), then converting back to letters. We want to write a procedure to do this.
A first attempt at the Caesar cipher
We begin with a naive attempt at the Caesar cipher, shifting every letter by three.
(We use the "map" command in Maple to apply a function to every element of a list.)
> temp[2] := map(x->x+3,temp[1]); convert(temp[2],bytes);
This did not give us quite the desired effect. To begin with, we got rid of all the spaces and now have a single long word. Furthermore, the letter z did not wrap around to c. It was mapped to a special character. The reason is that we have changed the alphabet. When we switched to ASCII we put the 26 letters of the English alphabet into a 256 character alphabet that includes all the characters we would ever want to type into a computer. In particular, spaces and special characters, as well as both upper and lower case letters are now part of our alphabet.
> convert([1,2,3,4,64,65,66,97,98,121,122,123,127,128,97,129,130,256,97,98,99],bytes); convert([97,255,128,97,132,97,164,97,200,97,255,97,255,97,97,254,97,98],bytes); convert([65,255, 66, 256, 67, 257, 68], bytes); convert([65,2,66, 1, 67, 0, 68, -2, 69],bytes);
Recall that the convert function from integer to ASCII assumes the input is between 1 and 255, inclusive. If fed an integer outside that range, it stops. In that case, it does not process the rest of the list.
We want to look at conversion functions that use a standard alphabet as well as ones that use the ascii alphabet.
The first procedure we define uses the ascii alphabet. This procedure shifts the value letter by the value key. Notice that we have to take care that we get the correct results if letter + key is 254, 255, and 256. (Check that the procedure outlined does take those values to 254, 255, and 1 respectively.)
> caesara := proc(letter, key) ((letter + key - 1) mod 255) + 1; end:
Of course, the test of a coding procedure is that it encodes and decodes properly.
> convert(temp[1], bytes); temp[4] := map(caesara,temp[1],120); code[1] := convert(temp[4],bytes);
> temp[5] := map(caesara,temp[4], -120); convert(temp[5], bytes);
Exercises
1) Save the first full paragraph of page 14 of your book as message2. Shift the message by 13 characters. Convert your answer back by shifting -13 characters. Verify that you get the original message back.
>
2) Try shifting the message by 50, 100, 150, and 200 characters. Can the original message be recovered after these shifts?
3) Convert the message to numbers and shift the message by 120 characters, convert to ASCII, then back to numbers, shift the message by -120, then convert back to ASCII. How has the message been changed?
A problem with using the full ASCII alphabet is that we shift to so many special characters that we would have trouble typing the encoded message. We have alsp seen that Maple shifts by a the high ASCII characters by 1 if we convert to characters, then back to numbers. For these reason we also want a coding procedure that rotates the letters but leaves the special characters alone. Recall that the upper case letters are charachters 65 through 90, while the lower case letters are ascii characters 97 through 122.
> caesarb := proc(letter, key) local temp, temp2; temp := letter: if temp > 64 then if temp < 91 then temp := 65 + ((temp - 65 + key) mod 26): fi:fi: if temp > 96 then if temp < 123 then temp := 97 + ((temp - 97 + key) mod 26): fi:fi: temp: end:
Once again, the test is to encode messages.
> convert(temp[1], bytes); temp[6] := map(caesarb, temp[1], 3); convert(temp[6], bytes);
> temp[7] := map(caesarb, temp[6], -3); convert(temp[7], bytes); temp[8] := map(caesarb, temp[6], 23); convert(temp[8], bytes);
Notice that if we shifted by 3 to encode, we can decode by using a shift of either -3 or +23.
We would like to put the procedures above into a simple encoding command
> encodecaesarb := proc(message, key) local temp: #first convert the message to numerical equivalents temp[1] := convert(message, bytes): #then add the key to each letter to scrable the letters temp[2] := map(caesarb, temp[1], key): #then convert back to the ASCII code convert(temp[2], bytes); end:
We will use this procedure on our standard message.
> message1; mess[2] := encodecaesarb(message1,3);
Exercise
4) Use the modified procedure to shift message2, which you defined in exercise 1, by 3, 13, and 15 characters.
We conclude this section by producing a brute force code breaker for the Caesar code. We simply take the message and do all possible shifts. This is best done with a loop.
> breakcaesarb := proc(message) local temp, key; for key from 1 to 25 do temp := encodecaesarb(message, - key): print(`The key of `||key,` produces - `,temp); od; end:
> breakcaesarb(mess[2]);
It is clear that 3 is the key to unlocking the message.
5) Decode the message `Vogsc Mkbbyv ckic "Dgkc lbsvvsq kxn dro cvsfoi dyfo." Mkx iye snoxdspi dro gybu?` and answer the question. Identify the key used to encode it.
