Foundations of Computer SecurityLecture 40: Substitution CiphersDr. Bill YoungDepartment of Computer SciencesUniversity of Texas at AustinLecture 40: 1 Substitution CiphersSubstitution CiphersA substitution cipher is one in which each symbol of the plaintextis exchanged for another symbol.If this is done uniformly this is called a monoalphabetic cipher orsimple substitution cipher.If different substitutions are made depending on where in theplaintext the symbol occurs, this is called a polyalphabeticsubstitution.Lecture 40: 2 Substitution CiphersSimple SubstitutionA simple substitution cipher is an injection (1-1 mapping) of thealphabet into itself or another alphabet. What is the key?A simple substitution is breakable; we could try all k! mappingsfrom the plaintext to ciphertext alphabets. That’s usually notnecessary.Redundancies in the plaintext (letter frequencies, digrams, etc.)are reflected in the ciphertext.Not all substitution ciphers are simple substitution ciphers.Lecture 40: 3 Substitution CiphersCaesar CipherThe Caesar Cipher is a monoalphabetic cipher in which each letteris replaced in the encryption by another letter a fixed “distance”away in the alphabet.For example, A is replaced by C, B by D, ..., Y by A, Z by B, etc.What is the key?What is the size of the keyspace? Is the algorithm strong?Lecture 40: 4 Substitution CiphersVigen`ere CipherThe Vigen`ere Cipher is an example of a polyalphabetic cipher,sometimes called a running key cipher because the key is anothertext.Start with a key string: “monitors to go to the bathroom” and aplaintext to encrypt: “four score and seven years ago.” Align thetwo texts, possibly removing spaces:plaintext: fours corea ndsev enyea rsagokey: monit orsto gotot hebat hroomciphertext: rcizl qfkxo trlso lrzet yjouaThen use the letter pairs to look up an encryption in a table(called a Vigen`ere Tableau or tabula recta).What is the corresponding decryption algorithm?Lecture 40: 5 Substitution CiphersVigen`ere TableauA B C D E F G H I J K L M N O P Q R S T U V W X Y ZA 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 ZB B C D E F G H I J K L M N O P Q R S T U V W X Y Z AC C D E F G H I J K L M N O P Q R S T U V W X Y Z A BD D E F G H I J K L M N O P Q R S T U V W X Y Z A B CE E F G H I J K L M N O P Q R S T U V W X Y Z A B C DF F G H I J K L M N O P Q R S T U V W X Y Z A B C D EG G H I J K L M N O P Q R S T U V W X Y Z A B C D E FH H I J K L M N O P Q R S T U V W X Y Z A B C D E F GI I J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK K L M N O P Q R S T U V W X Y Z A B C D E F G H I JL L M N O P Q R S T U V W X Y Z A B C D E F G H I J KM M N O P Q R S T U V W X Y Z A B C D E F G H I J K LN N O P Q R S T U V W X Y Z A B C D E F G H I J K L MO O P Q R S T U V W X Y Z A B C D E F G H I J K L M NP P Q R S T U V W X Y Z A B C D E F G H I J K L M N OQ Q R S T U V W X Y Z A B C D E F G H I J K L M N O PR R S T U V W X Y Z A B C D E F G H I J K L M N O P QS S T U V W X Y Z A B C D E F G H I J K L M N O P Q RT T U V W X Y Z A B C D E F G H I J K L M N O P Q R SU U V W X Y Z A B C D E F G H I J K L M N O P Q R S TV V W X Y Z A B C D E F G H I J K L M N O P Q R S T UW W X Y Z A B C D E F G H I J K L M N O P Q R S T U VX X Y Z A B C D E F G H I J K L M N O P Q R S T U V WY Y Z A B C D E F G H I J K L M N O P Q R S T U V W XZ Z A B C D E F G H I J K L M N O P Q R S T U V W X YLecture 40: 6 Substitution CiphersCryptanalysis on Vigen`ere CipherThe Vigen`ere Cipher selects one of twenty-six different CaesarCiphers, depending upon the corresponding letter in the key.Running key ciphers are susceptible to statistical analysis. Bothkey and plaintext are English language strings and so have theentropy characteristics of English. In particular, the letters A, E, O,T, N, I make up approximately 50% of English text. Thus, atapproximately 25% of indices, these can be expected to coincide.This is an example of a regularity in the ciphertext that would notbe expected merely from chance.Lecture 40: 7 Substitution CiphersAES Substitution StepSubstitution need not only apply to symbols in a text.The Advanced Encryption Standard (AES) contains a substitutionstep; each byte in a 16-byte array is replaced with a correspondingentry from a fixed 8-bit lookup table.Lecture 40: 8 Substitution CiphersLessonsSubstitution is one of the building blocks of encryption.Simple substitution means replacing symbols uniformly byothers. The Caesar Cipher and our pirate example areinstances.Polyalphabetic substitution means that the substitution variesaccording to the position in the text. The Vigen`ere Cipher isan example.Next lecture: Using InformationLecture 40: 9 Substitution
View Full Document