Lecture 04-27-09: EncryptionMatt CarrollDiscussion 2 in 118 Barrows for the rest of semester Exam 2 grades are up.Scores are still pretty high.Recommended reading:• ”The Codebreakers”. History of cryptography starting with romans/greeksthrough WW2.• Whitfield, Diffie and Martin Hellman, ”Privacy and Authentication: AnIntro duction to Cryptography”, Proc. IEEE, 67, 3, March, 1979, pp.397-427.These are not assigned readingA lot of papers are going online as PDFs soon.EncryptionThe main idea is that people are welcome to look, but they can’t understand.Store and transmit information in an encoded form.Encryption/cryptography is not new - has been used since the time of the Ro-mans (”Caesar cypher”).The following diagram demonstrates the basic flow of information through anencyrption scheme:Key1 Key2V Vclear text -> encrypt -> cipher text -> decrypt -> clear textVlistenerThe basic mechanism:• Begin with the information to be protected. This is called the clear text.• Encrypt the clear text so that it’s unintelligible to a listener. This is calledthe cipher text. Encryption is controlled by a secret password or number,called the encryption key.• To make sense of the cypher text, it must be decrypted back into the cleartext. This is done with an algorithm that uses the other secret passwordor number, called the decryption key.1• The cipher text is exposed and incomprihensible to anybody who doesn’tknow how to decrypt it.In order for an encryption scheme to work, three conditions must be met:1. The encryption function can’t easily be inverted (you can’t get from thecipher text to the clear text without the decryption key).2. The encryption must be done in some safe place so the clear text can’tbe stolen. If you’re sitting out doing it on the beach...that’s bad. Recentexample: British Minister of Defence was photographed in public, with ahighly classified document under his arm, and the text visible, resultingin a scandal and his resignation.3. The keys must be secret. Usually, if you know one of the keys, you cancompute the other. The algorithms are publicly known, but if either ofthe keys gets out, a listener can decrypt the cipher text.Typ es of Cryptographic SystemsSubstitution: A function f(x ) maps each letter of the plaintext into f (x). Thisfunction must be 1 to 1, or 1 to many. The Caesar Cipher is a substitutionscheme, where f(x) = x + 1 (the simplest substitution scheme).For example:The quick brown fox jumps over the lazy dog||||||vvvvvv...uifarv...To break this scheme, use frequency analysis of letters, doubles, triples, groups(etc.) Unless you’re trying to do something weird, the top 5 or 10 letters areeasy to identify by computing the frequencies, then doing the substitution. Themost frequent symbol is probably ”e”, then the next most frequent is ”t”, andso on. After you’ve filled in half the letters, you can infer the rest if you knowthe language of the clear text.Using a 1 to many function can disguise the frequency of symb ols, making thescheme harder to break using the above method.Transposition Permute (or transpose) the input in blocks to obtain the output.The following diagram demonstrates a simple transposition scheme:| t | h | e | | q || u | i | c | k | || b | r | o | w | n | ==> tub_jhirfu...| | f | o | x | || j | u | m | p | e |2Here, the input is placed in a 5 by 5 matrix, and the cipher text is producedby ordering the letters as they appear when traversing the matrix vertically,column by column, and from left to right.If you know a transposition cipher is being used, it can be broken by lookingfor permutations that rejoin commonly used letter pairs, such as ”th”. This isnot trivial to figure out.Transpotiion ciphers were the state of the art circa the 17thcentury.Polyalphabetic ciphers These are an extension of substitution ciphers. The cleartext is enco ded with f (i, x), a function of i where i is the sequence number ofthe letter in the text. Typically the function is periodic in i.Example:clear text: t h e q u i c k b r o w n f o xi: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1f(i, x): u j h a s . . .Question: Why make it periodic?Answer: There’s a tradeoff between the complexity of code and ease of enco d-ing/decoding, possibly losing your mapping, things like that. Historically thesewere used prior to computers. A person had to be able to do the encryptionon paper in a finite amount of time. Also, there wasn’t any literature ab outcodebreaking as there is today.Usually, schemes get broken by stealing the code or torturing somebody untilthey tell you, rather than actually breaking the code technically. Example:Enigma machine used by Germany in WW2.To break a polyalphabetic cipher, look for repeated strings, and count the num-ber of symbols between them. Least common denominator between them isusually the period. Or, you can look at the frequency of letters K apart, untilthey look like they should, then K is the period.Once you know the period, you can solve each of the N ciphers as a substitutioncipher.By the 20thcentury, there were coding machines to do polyalphabetic ciphers.They had rotating wheels with a relatively prime number of cogs. The code wasa product of a path through the wheels.Running key cipher Use a long text as the key, but not random, like using abook or something. For example, suppose you want to encrypt The DaVinciCode. Use some other book as the key. Take the key as numbers 1 through 26,and do a mod 26 addition to the key text to get the cipher text. To decrypt,do a mod 26 subtraction of the DaVinci Code from the cipher text.Thus far, we’ve discussed encryption methods that do things to individual let-ters. Now we’ll talk about codes, encryption methods that use groups of letters3(words) as input. A code book is used to map words to output code words.This could even be used with whole phrases as inputs.For example, this was a common method of transmitting messages accross theAtlantic during the early 1900s. Communication was exp ensive, so commercialcodebooks were used to shorten the message to transmit. Another example ofthis typ e is substituting page, line, and word numbers for words in some book.These codes are very hard to break. The approach suggested is to try frequencyanalysis. They can be broken via the plaintext method: if you get a hold of aplaintext, a cipher text, and the codebook, you can determine the encryptionmethod. But this is another example of a code being
View Full Document