Simple Ciphers (2024)

• Simple substitution
• The Caesar cipher, and the ASCII encoding
  • Treating characters as numbers
  • Render unto Caesar

Simple substitution

One of the most common (and very easy to crack) ciphers issubstitution. One sometimes sees these in a newspaper somewhere near thecrossword puzzle. This scheme is also the one used in Poe's story ``The GoldBug'', and the Sherlock Holmes ``Mystery of the Dancing Men''. The idea isstraightforward: choose a rearrangement of the letters of the alphabet, andreplace each letter in the plaintext by its corresponding one.

Such substitutions are very simple to implement in Maple. We will use theCharacterMap function from the StringTools package4.2which does exactly what we want.First, we define two ``alphabets''- one for our plain text, and one for ourencrypted text. The second is a permutation of the first.

>  with(StringTools): Alphabet :="abcdefghijklmnopqrstuvwxyz": Cryptabet:="THEQUICKBROWNFXJMPSVLAZYDG":

>  Scramble := msg -> CharacterMap(Alphabet, Cryptabet, msg): Unscramble:= code -> CharacterMap(Cryptabet,Alphabet, code):

>  Scramble("please do not read this");

>  Unscramble(

Note that our message contains a spaces which are preserved in theencryption process, because the CharacterMap function only modifiesthose characters which are found in the first string. If a character isn'tfound, it is left alone. Thus, if we try to scramble a message containingpunctuation or upper-case letters, they aren't modified by Scramble.Since our Cryptabet is all upper-case, a message which began withmixed case will be distorted.

>  Scramble("He said I need direction; I head for the door."); Unscramble(

It is traditional in pen-and-paper cryptography to use a 26-letter alphabet(that is, to remove spaces and punctuation and ignore any distinctionbetween upper and lower case letters). If you wish to do this, it could bedone4.4using LowerCase (which translates all letters to lower case),and a combination of Select and IsLower to remove anythingthat isn't a letter.

>  Select(IsLower,LowerCase("I don't mind suggestions. Don't give me any more."));

>  Scramble( Unscramble(

In general we won't adhere to this convention in this chapter.Rather, we will treat spaces and punctuation like any othercharacter. This is not a common approach, but one we happen to like.

There are two big drawbacks to such a substitution cipher. One primary problem is that the key for enciphering and deciphering is thepermutation: you need to remember an ordering of the entire alphabet.

A second problem, shared with all such monoalphabetic substitutions(i.e., those that substitute one letter for another), is that theyaren't that hard to break. If you have a long enough message,you can use the fact that certain letters occur much more frequentlythan others to help tease out the original text. In English textthe letter ``e'' is the occurs most frequently, followed by ``t'',``a'', ``n'', ``i'', and so on. Spaces occur about twice as often asthe letter ``e'', assuming they are encrypted, rather than justomitted. Once you guess a few letters, common words like ``the'' and``and'' fall into place, giving more clues.

We will examine some polyalphabetic substitution ciphers in§5.

The Caesar cipher, and the ASCII encoding

A variation on the arbitrary permutation discussed above is the ``Caesarcipher'', named after Julius Caesar, who supposedly invented it himself.This is also what was done by a ``Captain Midnight Secret Decoder Ring'',popular in the 1930s and 40s. Here we convert our alphabet to numericequivalents (with, say A=0, B=1, and so on), add an offset to each numericequivalent (legend has it that Caesar used an offset of 3), then re-encodethe numbers as letters. We do the addition modulo the length of thealphabet; that is, when we shift a Y by 3, we get B, since 24 + 3 = 27,and 27 1(mod26). However, we won't always restrict ourselvesto a 26 letter alphabet-- we may want punctuation, numbers, and to preserveupper- and lower-case distinctions.4.5

While we could easily implement the Caesar cipher without converting ourtext to numbers, doing so makes it easier to understand and sets us up formore complicated ciphers we will need later.

Treating characters as numbers

Computers already have a built-in numeric representation of thealphabet-- the ASCII encoding.4.6At their lowest level, digital computers operate only on numericquantities-- they just manipulate ones and zeros. The smallest pieceof information is the state of a switch: it is off (0) or it is on(1). This is called a bit, which is short for binarydigit. A group of 8 bits is called a byte, and is asingle ``character'' of information.4.7A byte can have 2⁸ = 256 different states:

00000000,00000001,00000010,00000011,...,11111111

So how does a computer represent characters? There is an agreed uponstandard encoding of characters, punctuation, and control codes intothe first 127 integers. This is called ASCII,4.8an acronym for AmericanStandard Code for Information Interchange. Extended ASCII encodesmore characters into the range 128-255 (this is where you would findcharacters for å and ±, for example), although the charactersfound in this range vary a bit. Not all programs can deal successfully withcharacters in the extended range4.9

Maple has a built-in routine to allow us to convert characters to and fromtheir ASCII equivalents. If it is called with a list of numbers, it returnsa string of characters, and if called with a character string, out comes alist of numbers. For example,

>  convert("How do I work this?",bytes);

>  convert([72, 117, 104, 63],bytes);

We can use this to make a list of the ASCII codes. Maple prints a when the ASCII code is not a printable character. We make the tablefor characters up through 127 because the meanings in extended ASCII differ depending on what character set you use. Feel free to make your own tableof all 255 characters. (In the interests of making a nicely formattedtable, we have used a somewhat complicated command. The much simplerseq([i,convert([i],bytes)],i=0..127); would have produced thesame information, just not as neatly.)

>  matrix([ [_,seq(i, i=0..9)], seq([10*j, seq(convert([i+10*j],bytes), i=0..9)], j=0..12)]);

Note that some of the characters (such as ASCII code 10) print as a backslashand a letter, like \n. These are codes for special controlcharacters: \n indicates a newline, \t is a tab, andso on. Since Maple indicates a string by printing it inside doublequotes, it indicates the double quote4.10character (ASCII34) using\'', and the backslash character (ASCII92) with a pair ofbackslashes. While it doesn't print out in Maple, ASCII127 is the controlsequence DEL (sometimes printed as ^?). This sometimes isinterpreted as ``delete the previous character''; if your outputdevice interprets it that way, characters can seem to mysteriously vanish.

Another special character is ASCII code 0: note that it prints as nothing,not even a blank space (ASCII 32 is the space character). This is the null character, and is typically used internallyto indicate the end of a string. If a null occurs in the middle of a string,usually what comes after it won't print out unless you take special steps. To see this foryourself, try a command like convert([73,116,39,115,0,103,111,110,101,33],bytes).You'll see that the characters following the 0 don't print out.

The StringTools package also contains Char which gives thecharacter corresponding to a decimal number, and Ord which gives thenumber corresponding to a character. We'll generally useconvert, although it makes little difference.

Render unto Caesar

Now we are nearly ready to write a version of the Caesar cipher.The basic idea is that for each character of the plaintext, we convert it anumerical representation, add a pre-specified offset modulo 127, thenconvert back to characters. Unlike the Scramblefunction we wrote in §2.1, we needn't declarean alphabet explicitly because we will use the ASCII codes. However, inaddition to the Maple command convert( ,bytes), we will use another new command, map.

>  map(sqrt,[1,2,3,4,5,6,7,8,9,10]);

If the function we wish to apply takes two variables, we cangive the second one as a third argument to map. For example, thecommand

>  map(modp,[1,2,3,4,5,6,7,8,9,10],3);

computes nmod3 as n ranges over the list [1, 2,..., 10].(Recall that nmodp is the remainder after dividing n by p.)

We finally are ready. See if you can understand it before reading theexplanation below. Remember to read from the middle outward.Note that we are defining the function we are mapping directly asthe first argument.

>  Caesar:= (plain, shift) -> convert(map(x -> (x+shift-1) mod 127 + 1, convert(plain,bytes)), bytes): 

Let's give it a try:

>  Caesar("Et tu, Brute?",3);

If you don't see what is going on in Caesar, try to think of it as acomposition of several functions, each of which you DO understand. That is,Caesar works as follows

• First, we convert the input string (called plain) into a list of numbers, using the call convert(plain,bytes). Note that this is done on the third line, the innermost function.
• Next, we apply the function x ->(x+shift-1) mod 127 + 1 to each of numbers in the resulting list using map. This call to map has two arguments: the definition of the shift, and what to apply it to (the innermost function convert(plain,bytes)).
• Finally, we convert the list back to characters again. This is the outermost function: it begins on the second line (immediately after the -> and ends with the final parenthesis.

Note that we didn't really compute ; instead we subtracted onefrom the sum, computed mod127, then added 1 again. Why?Consider what would happen if, for example, our character was ``k''(ASCII code 107) and we shifted by 20. Then (107 + 20)mod127gives 0, which is the code for the null byte, indicating the end ofa string. This would be a problem. So instead, we add 1 afterwardto ensure that our answer is in the range 1,..., 127. And justto avoid confusing ourselves, we subtract the 1 first, so thatshifting by 0 doesn't change anything.

Aside from the fact that this function is a bit confusing toread and offers essentially no cryptographic security, what else is wrongwith it? Consider the following example:

>  Caesar("Who put the benzedrine in Mrs. Murphy's Ovaltine?", 86);

In addition to the fact that the result looks funny, if we were to try todecipher this from printed output, we would have a little (but not much)trouble, because the characters ``.'' and ``?'', after encoding, print outas .4.11 This happens because the numeric values of thesecharacters, after shifting by 86, are 5 and 22, respectively. Neitherof those corresponds to a printing character, so we can't tell them apart.Of course, if we had no intention of dealing with our encoded message inprinted form, this would be no problem. The actual character values aredifferent, they just print out the same.

How can we get around this? We can restrict ourselves to printingcharacters using a variation of the idea in Scramble of§2.1, that is, giving an explicit Alphabetthat we will deal in.

Before doing this, however, it will be helpful to discuss the proccommand, which allows us to construct functions that consist of more thanone Maple command.

Footnotes

... package^4.2

The StringTools package was introduced in Maple7, and the string data type was introduced in MapleV release5. Everything we do in this chapter can easily be implemented without using StringTools- in fact, the original version of this chapter was written for MapleVr4 using names rather than strings. Since Maple6 is still in widespread use (Spring2002), we'll try to include alternatives to using this package when practical.

... functions^4.3

In MapleVr5 and Maple6, we could define CharacterMap as
CharacterMap := (old,new,txt)->cat(seq(new[SearchText(txt[i],old)],i=1..length(txt)));
This will only work if all characters in the txt correspond to onesin old, so a space would have to be added to both Alphabetand Cryptabet to get this example to work.

...done^4.4

How to accomplish this without StringTools is left tothe seriously motivated reader.

... distinctions.^4.5

For example, the title of this chapter (fsqFsHn sGGousG) is actually the result of using a Caesar cipher on its original title. A 53-character alphabet consisting of all the upper-case letters, a space, and all the lower-case letters was used, so the space in the middle may not correspond to a space in the original. The three Gs that occur should be a good hint to decoding it.

... encoding.^4.6

In fact, while most computers these days use ASCII, it is not the only such arrangement. IBM mainframes, for example, primarily use another encoding called EBCDIC. But this makes no real difference to our discussion.

... information.^4.7

The next larger unit in a computer is a word. However, different makes of computers have different sizes of words. Most computers today have 4byte words (32 bits), but word sizes of 2bytes (16 bits) and 8bytes (64 bits) are not uncommon. 8-bit bytes are now essentially universal although in the early days of computing, there were computers which used other sizes, such as 6bit bytes.

...ASCII,^4.8

ASCII is not the only such standard, although it is currently the most commonly used. Prior to the widespread use of personal computers in the 1980s, EBCDIC (Extended Binary Coding for Data Interchange and Communication) tended to be in more common use, because it was what IBM mainframes used. There are many other such assignments.

... range^4.9

In the late 1980s and early 1990s, there was a big push to make programs ``8-bit clean'', that is, to be able to handle these ``unusual'' characters properly. There are a number of distinct assignments of characters to the upper 128 positions. One common one is Latin-1 (ISO8859-1), which contains the characters used in the majority of western European languages. Other assignments include characters for Scandinavian languages, Arabic, Cyrillic, Greek, Hebrew, Thai, and so on. Since the late 1990s, a multi-byte character encoding called Unicode (ISO10646) has been in use; this universal character set allows computers to handle alphabets (such as Chinese) that need more than 255 characters. While use of Unicode is becoming more widespread, single byte character sets like ASCII will likely predominate for quite a long while.

... quote^4.10

The ASCII code does not have distinct codes for the open-quote (``)and close-quote ('') characters used in typesetting. Neither do mostcomputer keyboards. However, the apostrophe (') and grave accent orbackquote(`) characters have distinct ASCII codes (39 and 96, respectively).

....^4.11

Of course, it is easy to make examples where significantparts of the message all come out as . One such is the same messagewith a shift of 50.