Lecture 04 27 09 Encryption Matt Carroll Discussion 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 greeks through WW2 Whitfield Diffie and Martin Hellman Privacy and Authentication An Introduction to Cryptography Proc IEEE 67 3 March 1979 pp 397 427 These are not assigned reading A lot of papers are going online as PDFs soon Encryption The 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 Romans Caesar cypher The following diagram demonstrates the basic flow of information through an encyrption scheme Key1 Key2 V V clear text encrypt cipher text decrypt clear text V listener The 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 called the 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 clear text This is done with an algorithm that uses the other secret password or number called the decryption key 1 The cipher text is exposed and incomprihensible to anybody who doesn t know 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 the cipher text to the clear text without the decryption key 2 The encryption must be done in some safe place so the clear text can t be stolen If you re sitting out doing it on the beach that s bad Recent example British Minister of Defence was photographed in public with a highly classified document under his arm and the text visible resulting in a scandal and his resignation 3 The keys must be secret Usually if you know one of the keys you can compute the other The algorithms are publicly known but if either of the keys gets out a listener can decrypt the cipher text Types of Cryptographic Systems Substitution A function f x maps each letter of the plaintext into f x This function must be 1 to 1 or 1 to many The Caesar Cipher is a substitution scheme 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 are easy to identify by computing the frequencies then doing the substitution The most frequent symbol is probably e then the next most frequent is t and so on After you ve filled in half the letters you can infer the rest if you know the language of the clear text Using a 1 to many function can disguise the frequency of symbols making the scheme 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 u i b r f j u e c o o m k w x p q n e tub jhirfu 2 Here the input is placed in a 5 by 5 matrix and the cipher text is produced by 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 looking for permutations that rejoin commonly used letter pairs such as th This is not trivial to figure out Transpotiion ciphers were the state of the art circa the 17th century Polyalphabetic ciphers These are an extension of substitution ciphers The clear text is encoded with f i x a function of i where i is the sequence number of the 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 x i 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 f 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 encoding decoding possibly losing your mapping things like that Historically these were used prior to computers A person had to be able to do the encryption on paper in a finite amount of time Also there wasn t any literature about codebreaking as there is today Usually schemes get broken by stealing the code or torturing somebody until they 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 number of symbols between them Least common denominator between them is usually the period Or you can look at the frequency of letters K apart until they look like they should then K is the period Once you know the period you can solve each of the N ciphers as a substitution cipher By the 20th century there were coding machines to do polyalphabetic ciphers They had rotating wheels with a relatively prime number of cogs The code was a product of a path through the wheels Running key cipher Use a long text as the key but not random like using a book or something For example suppose you want to encrypt The DaVinci Code 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 letters Now we ll talk about codes encryption methods that use groups of letters 3 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 the Atlantic during the early 1900s Communication was expensive so commercial codebooks were used to shorten the message to transmit Another example of this type 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 frequency analysis They can be broken via the plaintext method if you get a hold of a plaintext a cipher text and the codebook you can determine the encryption method But this is another example of a code being broken via some means other than cryptanalysis There are other approaches that may not break the code per se but the security of the communication can be considered compromised An …
View Full Document
Unlocking...