Basic Encryption and Decryption II PDF

CHAPTER 3 Basic Encryption and Decryption II Dr. Sayed El-Sayed  Weakness Monoalphabetic Ciphers The weakness of monoalphabetic ciphers: frequency distribution reflects the distribution of the underlying alphabet. Solution : –Flatten the distribution –Use polyalphabetic...

CHAPTER 3 Basic Encryption and Decryption II Dr. Sayed El-Sayed  Weakness Monoalphabetic Ciphers The weakness of monoalphabetic ciphers: frequency distribution reflects the distribution of the underlying alphabet. Solution : –Flatten the distribution –Use polyalphabetic substitution 1  Weakness of Monoalphabetic Ciphers A powerful analysis tool is to look at the frequency of 2-letter and 3-letter combinations Digram Trigram – Two-letter combination – Three-letter combination – TH, ER, ON, and AN are the most – THE, AND, THA, ENT, ING, common pairs of letters, and SS, EE, TT, ION, TIO, FOR, NDE, HAS are and FF are the most common repeats the most common trigrams The countermeasure is to provide multiple substitutes (homophones) for a single letter Two principal methods are used: – One is to encrypt multiple letters of plaintext, – The other is to use multiple cipher alphabets. 2  Playfair Cipher Best-known multiple-letter encryption cipher Treats digrams in the plaintext as single units and translates these units into ciphertext digrams Based on the use of a 5 × 5 matrix of letters constructed using a keyword Invented by British scientist Sir Charles Wheatstone in 1854 Used as the standard field system by the British Army in World War I and the U.S. Army and other Allied forces during World War II 3  Playfair Key Matrix - Encryption Fill in letters of key phrase or keyword (minus duplicates) from left to right and from top to bottom, then fill in the remainder of the matrix with the remaining letters in alphabetic order Using the keyword MONARCHY: M O N A R C H Y B D The letters I and J E F G I/J K count as one letter L P Q S T U V W X Z Plaintext is encrypted two letters at a time, according to the following rules: 1. Repeating letters that are in the same pair are separated with a filler letter, such as x, so that balloon would be treated as ba lx lo on. 2. Two letters that fall in the same row are each replaced by the letter to the right, with the first element of the row circularly following the last. For example, ar is encrypted as RM. 3. Two letters that fall in the same column are each replaced by the letter beneath, with the top element of the column circularly following the last. For example, mu is encrypted as CM. 4. Otherwise, each letter in a pair is replaced by the letter that lies in its own row and the column occupied by the other letter. Thus, hs becomes BP and ea becomes IM (or JM, as you wish). 4  Playfair Key Matrix - Decryption To decrypt the ciphertext message, simply reverse the process: – If the two letters are in different rows and columns, take the letters in the opposite corners of their rectangle. – If they are in the same row, take the letters to the left. – If they are in the same column, take the letters above each of them. Example: Using the keyword MONARCHY, our 5x5 matrix is: M O N A R C H Y B D The letters I and J E F G I/J K count as one letter L P Q S T U V W X Z To decrypt the ciphertext : TLMKXAXA, apply the above rules: TLMKXAXA → TL MK XA XA (break it in digrams) TL → ST, MK → RE, XA → SX (repeated). Plaintext is ST RE SX SX and after removing the filler letter (X) it becomes stress. 5  Polyalphabetic Ciphers Polyalphabetic substitution cipher – Another way to improve on the simple monoalphabetic technique is by using different monoalphabetic substitutions as one proceeds through the plaintext message All these techniques have the following features in common: – A set of related monoalphabetic substitution rules is used – A key determines which particular rule is chosen for a given transformation – Examples are Vigenère cipher and Vernam Cipher. 9  Vigenère Cipher Best known and one of the simplest polyalphabetic substitution ciphers (PASC’s) In this scheme the set of related monoalphabetic substitution ciphers (MASC’s) rules consists of the 26 Caesar ciphers with shifts of 0 through 25 – each row of the Vigenère table corresponds to a Caesar cipher. The first row is a shift of 0, the second is a shift of 1 and the last is a shift of 25. – Vigenère cipher uses this table together with a keyword to encipher a message. Each cipher is denoted by a key letter which is the ciphertext letter that substitutes for the plaintext letter a. 10  Vigenère Tableau 1 Plaintext K 2 e 3 y Ciphertext 11  Vigenère Cipher – Example1 To encrypt a message, a key is needed that is as long as the message. Usually, a repeating keyword. – For example, if the keyword is deceptive, the message “we are discovered save yourself” is encrypted as (Hint: refer to Vigenère Tableau to directly pick ciphertext letters) 12  Vigenère Cipher – Example2 Plaintext: attack at dawn Key phrase: CAT Length of Alphabet: 26 Ciphertext: CTMCCD CT WCWG What do you notice? 13  Vigenère Cipher – Example3 To eliminate the effect of the periodic nature of the key phrase, use a nonrepeating key phrase that is as long as the message itself. – Concatenate the key phrase with the plaintext to get a running key. – This is called an autokey system. For our example, key: deceptivewearediscoveredsav plaintext: wearediscoveredsaveyourself ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA Even this scheme is vulnerable to cryptanalysis (a statistical technique can be applied) – Because the key and the plaintext share the same frequency distribution of letters, 14  Vernam Cipher The ultimate defense of Vigenère cipher against cryptanalysis, such as statistical analysis, is to choose a key phrase that is as long as the plaintext and has no statistical relationship to it. Such a system was introduced by an AT&T engineer named Gilbert Vernam in 1918. His system works on binary data (bits) rather than letters. the ciphertext is generated by performing the bitwise XOR of the plaintext and the key (𝑐𝑖 = 𝑝𝑖 ⊕ 𝑘𝑖 ) and decryption involves the same bitwise operation: 𝑝𝑖 = 𝑐𝑖 ⊕ 𝑘𝑖 15  One-Time Pad Improvement to Vernam cipher proposed by an army officer, Joseph Mauborgne. Use a random key (also called the pad) that is as long as the message so that the key need not be repeated Key is used to encrypt and decrypt a single message and then is discarded Each new message requires a new key of the same length as the new message Continued on next slide 16  One-Time Pad – Cont’ed Scheme is unbreakable – Produces random output that bears no statistical relationship to the plaintext – Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code The security of the one-time pad is entirely due to the randomness of the key. – If the stream of characters in the key is truly random, then the stream of characters in the ciphertext will be truly random. – Thus, there are no patterns or regularities that a cryptanalyst can use to attack the ciphertext. Compare this with Example1 of Vigenère cipher, where VTW pattern is repeated. 17  The “Perfect” Substitution Cipher Example: Assume that the alphabetic letters are combined by sum mod 26 with a stream of random two-digit numbers. Plaintext : V E R N A M C I P H E R Numerical Value : 21 4 17 13 0 12 2 8 15 7 4 17 +random number : 76 48 16 82 44 3 58 11 60 5 48 88 = sum : 97 52 33 95 44 15 60 19 75 12 52 105 mod 26 : 19 0 7 17 18 15 8 19 23 12 0 1 ciphertext : T A H R S P I T X M A B Note: random number 48 happen to fall at the places of repeated letters, accounting for repeated ciphertext A but however highly unlikely. repeated letter t comes from different plaintext letter 18  Binary Vernam Cipher Works just as well as “alphabets”. Example : – This operation is performed on each letter, and within each letter a bitwise XOR is performed. [XOR: 1+1=0, 0+0=0, 1+0=1 and 0+1=1] Pi (Text) Q A T A R Pi (binary) 00010000 00000000 00010011 00000000 00010001 Ki (Binary) 00001110 00000111 00001101 00001100 00010001 Ci (Binary) 00011110 00000111 00011110 00001100 00000000 Ci (Text) E H E M A 19  Summary of One-time Pad Cipher Systems using perfect random, non-repeating keys which is endless and senseless. Random key used once, and only once. Is the only unbreakable cryptography system. Unbreakable in theory: –the key neither repeats, nor recurs, nor makes sense, nor erects internal frameworks –perfect randomness nullifies any horizontal, or lengthwise cohesion Why wouldn't it be used today? – Sender and receiver need to be perfectly synchronized – It would not work for a T1 communication line: If receiver is off by a bit (bit dropped during transmission) the plaintext will not make any sense If bits are altered during transmission (noise hit) those bits will decrypt incorrectly It does not provides authenticity, only confidentiality 20 Cryptanalysis of Polyalphabetic Substitutions There are two ways: – Kasiski Method – Index of Coincidence, IC Kasiski Method for repeated pattens Named for its developer, a Prussian military officer. Is a way of finding the number of alphabets that were used for encryption. -th, -ion, -ed, -tion, and, to, are, appear with high frequency (regularity of English). Index of Coincidence (IC) Index of coincidence (IC) is a measure of the variation between frequencies in a distribution. 21 Cryptanalysis of Polyalphabetic Substitutions Kasiski Method Steps are: 1. Identify repeated patterns of three or more characters. 2. For each patterns write down the position at which each instances of the pattern begins. 3. Compute the difference between the starting points of successive instances. 4. Determine all factors of each difference. 5. If a polyalphabetic substitution cipher was used, the key length will be one of the factors that appears often in step 4. 22  Transpositions (Permutations) The plaintext remains the same, but the order of characters is shuffled around – example: shuffle secret to etcrse Arrangement was classically done with the aid of some type of geometric figure, usually 2-dimensional array (matrix). Transposition is not a permutation of alphabet characters but a permutation of places: – letters retain their identity but lose their position – there is a permutation of the plaintext letters 23  Transpositions (Permutations) Plaintext figure Ciphertext write-in take-off 24  Transpositions (Permutations) Transposition Cipher: Columnar Transposition Encryption: Plaintext is written horizontally into a matrix of fixed width and the ciphertext is read off vertically. Decryption: Ciphertext is written vertically onto the same matrix of identical width and then reading the plaintext off horizontally. – Suppose that the length of the ciphertext is n and the key is k. Then the letters will fill n DIV k full rows, and there will be one partial row at the end with n MOD k letters. Transcribing row-by-row will then yield the plaintext Example : Plaintext is renaissance is written into a 3 x 4 matrix as follows: rena issa nce (i.e., groups of 4 letters) R E N A I S S A N C E the resulting cipher text is RIN ESC NSE AA = RINESCNSEAA 25  Stream vs Block Ciphers Stream cipher – encrypt one symbol of plaintext immediately into a symbol of ciphertext Block cipher – encrypt a group of plaintext symbols as one block. Advantages of stream ciphers: Speed of transmission – each symbol is encrypted alone, each symbol is encrypted as soon as it is read. Low error propagation – an error in the encryption process affects only that character (each symbol is separately encoded). Disadvantages of stream ciphers: Low diffusion where all information of the symbol contained in one symbol of the ciphertext – cryptanalyst consider each ciphertext as a separate entity. Susceptibility to malicious insertion & modification – interceptor who has broken the code can splice together pieces of previous message and transmit a spurious new message that may look authentic. 28  Stream vs Block Ciphers Advantages of block ciphers: Diffusion – one ciphertext block may depend on several plaintext letters. Immunity to insertions – because of block of symbols are enciphered, impossible to insert a single symbol into one block. Disadvantages of block ciphers: Slowness of encryption – block cipher must wait until an entire block of plaintext symbols has been received before starting the encryption process. Error propagation – an error will affect the transformation of all other characters in the same block. 29  Characteristics of “Good” Ciphers Shannon Characteristics The amount of secrecy needed should determine the amount of labor appropriate for the encryption and decryption. The set of keys and the enciphering algorithm should be free from complexity. The implementation of the process should be as simple as possible. Errors in ciphering should not propagate and cause corruption of further information in the message. The size of the enciphered text should be no larger than the text of the original message. 30  Characteristics of “Good” Ciphers Confusion – Interceptor should not be able to predict what changing one character in the plaintext will do to the ciphertext. Diffusion – Changes in the plaintext should affect many parts of the ciphertext. Good diffusion means that the interceptor needs access to much ciphertext to infer the algorithm. 31 THE END 32