Math 121: Introduction to Computing Handout #17The Demo Programs in Folder Assignment4Strings and CiphersCryptography, derived from the Greek word  meaning hidden, is the science ofcreating and decoding secret messages whose meaning cannot be understood by otherswho might intercept the message. One of the most important episodes in the history ofcryptography was the breaking of the German “Engima” code during World War II. Thebreaking of Enigma not only was essential to the Allied victory in the Battle of theAtlantic, but also was one of the first applications of digital computers. And while theEnigma code itself is beyond the scope of this course, cryptography turns out to be anideal domain for talking about string operations.Two of the demo programs in the folder for Assignment 4 are simple encryption anddecryption programs for ciphers less sophisticated than Enigma. To read them, one needto know some terminology. In cryptography, the message you are trying to send is calledthe plaintext; the message that you actually send is called the ciphertext. Unless youradversaries know the secret of the encoding system, which is usually embodied in someprivileged piece of information called a key, intercepting the ciphertext should not enablethem to discover the original plaintext version of the message. On the other hand, theintended recipient, who is in possession of the key, can easily translate the ciphertext backinto its plaintext counterpart.Caesar ciphersOne of the earliest documented uses of ciphers is by Julius Caesar. In his De VitaCaesarum, the Roman historian Suetonius describes Caesar’s encryption system like this:If he had anything confidential to say, he wrote it in cipher, that is, by sochanging the order of the letters of the alphabet, that not a word could be madeout. If anyone wishes to decipher these, and get at their meaning, he mustsubstitute the fourth letter of the alphabet, namely D, for A, and so with the others.Even today, the technique of encoding a message by shifting letters a certain distance inthe alphabet is called a Caesar cipher. According to the passage from Suetonius, eachletter is shifted three letters ahead in the alphabet. For example, if Caesar had had time totranslate the final words Shakespeare gives him, ET TU BRUTE would have come out asHW WX EUXWH, because E gets moved three letters ahead to H, T gets moved three to W,and so on. Letters that get advanced past the end of the alphabet wrap around back to thebeginning, so that X would become A, Y would become B, and Z would become C.– 2 –Caesar ciphers have been used in modern times as well. The “secret decoder rings”that used to be given away as premiums in cereal boxes were typically based on theCaesar cipher principle. In early electronic bulletin board systems, users often disguisedthe content of postings by employing a mode called ROT13, in which all letters werecycled forward 13 positions in the alphabet. And the fact that the name of the HALcomputer in Arthur C. Clarke’s 2001 is a one-step Caesar cipher of IBM has caused acertain amount of speculation over the years.The CaesarCipher program encodes or decodes a message using a Caesar cipher. Itreads a numeric key and a plaintext message from the user and then displays theciphertext message that results when each of the original letters is shifted the number ofletter positions given by the key. A sample run of the program looks like this:For the Caesar cipher, decryption does not require a separate program as long as theimplementation is able to accept a negative key, as follows:Letter-substitution ciphersAlthough they are certainly simple, Caesar ciphers are also extremely easy to break.There are, after all, only 25 nontrivial Caesar ciphers for English text. If you want tobreak a Caesar cipher, all you have to do is try each of the 25 possibilities and see whichone translates the ciphertext message into something readable. A somewhat betterscheme is to allow each letter in the plaintext message to be represented by an arbitraryletter instead of one a fixed distance from the original. In this case, the key for theencoding operation is a translation table that shows what each of the 26 plaintext lettersbecomes in the ciphertext. Such a coding scheme is called a letter-substitution cipher.The key in such a cipher can be represented as a 26-character string, which shows themapping for each character, as shown in the following example: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 ZQ W E R T Y U I O P A S D F G H J K L Z X C V B N M– 3 –Letter-substitution ciphers have been used for many, many years. In the 15th century,an Arabic encyclopedia included a section on cryptography describing various methodsfor creating ciphers as well as techniques for breaking them. More importantly, this samemanuscript includes the first instance of a cipher in which several different coded symbolscan stand for the same plaintext character. Codes in which each plaintext letter maps intoa single ciphertext equivalent are called monoalphabetic ciphers. More complex codes—like the Enigma machine—in which the representation for a character changes over thecourse of the encryption process are called polyalphabetic ciphers.The LetterSubstitutuionCipher program implements this more general letter-substitution cipher. The program asks the user to enter a 26-letter key and the plaintextmessage. It then displays the ciphertext and, to ensure that the encryption is working,what you get if you decrypt the ciphertext using the same key:Scrabble scoring In most word games, each letter in a word is scored according to its point value, which isinversely proportional to its frequency in English words. In Scrabble, the points areallocated as follows:Points Letters1 A, E, I, L, N, O, R, S, T, U2 D, G3 B, C, M, P4 F, H, V, W, Y5 K8 J, X10 Q, ZFor example, the Scrabble word FARM is worth 9 points: 4 for the F, 1 each for the A andthe R, and 3 for the M. The ConsoleProgram ScrabbleScore reads in words and printsout their score in Scrabble, not counting any of the other bonuses that occur in the game.The program ignores any characters other than uppercase letters in computing the score.In particular, lowercase