Eric Roberts Handout #34CS 106A February 3, 2010Strings and CryptographyCryptography, 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. My story at the beginning of the hour offers a glimpseof one of the most important episodes in the history of cryptography: the breaking of theGerman “Engima” code during World War II. The story of the Enigma is interesting notonly because it was essential to the Allied victory in the Battle of the Atlantic, but alsobecause breaking the German code was one of the first applications of digital computers.And while the Enigma code itself is beyond the scope of this course, cryptography turnsout to be an ideal domain for talking about string operations of the sort that Mehranintroduced on Friday.Our goal today is to write simple encryption and decryption programs for ciphers thatare less sophisticated than Enigma. Before doing so, it helps to define some terminology.In the language of cryptography, the message you are trying to send is called theplaintext; 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 ciphertextback into 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 so changingthe order of the letters of the alphabet, that not a word could be made out. Ifanyone wishes to decipher these, and get at their meaning, he must substitute thefourth 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.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 first problem today is simply to write a program that encodes or decodes amessage using a Caesar cipher. The program needs to read a numeric key and a plaintextmessage from the user and then display the ciphertext message that results when each ofthe original letters is shifted the number of letter positions given by the key. A samplerun of the program might look like this:– 2 –CaesarCipherThis program uses a Caesar cipher for encryption.Enter encryption key: 3Plaintext: ET TU BRUTECiphertext: HW WX EUXWHFor the Caesar cipher, decryption does not require a separate program as long as theimplementation is able to accept a negative key, as follows:CaesarCipherThis program uses a Caesar cipher for encryption.Enter encryption key: -3Plaintext: HW WX EUXWHCiphertext: ET TU BRUTELetter-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 MLetter-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 codedsymbols can stand for the same plaintext character. Codes in which each plaintext lettermaps into a single ciphertext equivalent are called monoalphabetic ciphers. Morecomplex codes—like the Enigma machine—in which the representation for a characterchanges over the course of the encryption process are called polyalphabetic ciphers.The second problem for today is to write a program that implements this more generalletter-substitution cipher. The program should ask the user to enter a 26-letter key andthe plaintext message. It should then display the ciphertext and, to ensure that theencryption is working, what you get if you decrypt the ciphertext using the same key:LetterSubstitutionCipherThis program implements a letter-substitution cipher.Enter 26-letter key: QWERTYUIOPASDFGHJKLZXCVBNMPlaintext: WORKERS OF THE WORLD UNITECiphertext: VGKATKL GY ZIT VGKSR XFOZTDecryption: WORKERS OF THE WORLD
View Full Document
Unlocking...