CSC 316 Chapter 2b, Spring 2004

Chapter 2 Basic Encryption and Decryption (part B) V. Sawma, Computer Security 2 2.4 Transpositions (Permutations) Transposition: an encryption in which the letters of the message are rearranged Also known as permutations Compare the goals:  Substitution  confusion  Transposition  diffusion V. Sawma, Computer Security 3 Confusion vs Diffusion Confusion: making it difficult to determine how a message and key were transformed into ciphertext.  Changing one character from plain text does NOT reveal encryption algorithm and/or key. Diffusion: spreading the information from the message or the key out widely across the ciphertext.  Changing one character from plain text affects MANY parts of cipher text. See p.62 for more discussions. V. Sawma, Computer Security 4 Columnar Transpositions A rearrangement of the plaintext characters into columns. The ciphertext is generated from the columns. Example: p.53 V. Sawma, Computer Security 5 Complexity of Columnar Transpositions Time: proportional to the length of the message, that is, O(n) or at the order of function n. Space: depends on the length of the message. Output cannot be produced until all characters of the message have been read. Initial delay varies, depending on the length of the message. C.f., constant initial delay in the previous (substitution) algorithms. V. Sawma, Computer Security 6 Digrams, Trigrams, & Other Patterns Digrams: groups of two letters Trigrams: groups of three letters Table 2-2 (p.54): Most common English Digrams and Trigrams. V. Sawma, Computer Security 7 Digrams, Trigrams, and Other Patterns Pair of adjacent letters-digrams Group of three letters-trigrams V. Sawma, Computer Security 8 Cryptanalysis by Digram Analysis 1. To compute the letter frequencies o Clue: The fact that all letters appear with their normal frequencies implies that a transposition has been performed. 2. To find where in the ciphertext a pair of adjacent columns lies (that is, to determine the width of a row in the original table used for encryption) o The ‘moving window’ method (next) V. Sawma, Computer Security 9 Positions of adjacent letters in Ciphertext Cryptanalysis by Digram Analysis V. Sawma, Computer Security 10 The moving window method 1. Pick a window size, say n. 2. Compare every Ci, 1  i  n ,in the window to Ci+n and determine if the two form a common digram 3. Do most of the digrams look reasonable? Example: Figure 2-5, p.56 V. Sawma, Computer Security 11 Moving Window Example T S S O H O A N I W H A A S O L R S T O V. Sawma, Computer Security 12 Good Encryption Algorithms The level of secrecy needed depends on the effort The keys and encryption algorithm should be free from complexity The algorithm and the key implementation should be easy Errors occurred during encryption should not effect the rest of the message Size of the cipher text message should not be larger than the original message V. Sawma, Computer Security 13 Trustworthy Encryption Systems It should be based on sound mathematics It should have been analyzed by competent experts and found to be sound It has stood the “test of time” V. Sawma, Computer Security 14 Stream versus Block Ciphers Stream ciphers: The plaintext characters are encoded by the sender letter-by-letter as sent to the receiver.  Example: substitution ciphers Block ciphers: Blocks of plaintext are encoded into ciphertext before being sent.  Example: columnar transposition V. Sawma, Computer Security 15 Stream Ciphers One symbol of plaintext is converted immediately into a symbol of ciphertext  Substitutions are examples of stream ciphers Y Encryption ISSOPMI Plaintext wdhuw…. Ciphertext Keystream V. Sawma, Computer Security 16 Stream Ciphers Fast Little storage space Low error propagation, meaning that encoding errors affect just one character in the ciphertext low diffusion, meaning that individual characters in the ciphertext can be analyzed using frequency distribution, digram analysis, IC and the Kasiski method Susceptibility to malicious insertions and modifications V. Sawma, Computer Security 17 Block Ciphers Encrypts a group of plaintext symbols at a time Transpositions are examples of block ciphers IH Encryption Plaintext Ciphertext Keystream KN OI TP YR CN ES ba qc kd em mc po V. Sawma, Computer Security 18 Block Ciphers Slow Require more storage space Error propagation High diffusion High immunity to insertions V. Sawma, Computer Security 19 4 cryptanalysis cases & 5 approaches 1. Ciphertext only Ciphertext-only attack 2. Full or partial plaintext Known plaintext attack Probable plaintext analysis 3. Ciphertext of any plaintext Chosen plaintext attack 4. Algorithm + Ciphertext Chosen ciphertext attack V. Sawma, Computer Security 20 Summary: Transpositions It is a method where letters of the message are rearranged  Goal here is diffusion rather than confusion  Information is spread widely across the ciphertext Columnar transposition is an easy one  Characters are rearranged into columns V. Sawma, Computer Security 21 Summary: Transpositions (Cont’d) Encipherment/Decipherment Complexity  Algorithm is constant in the amount of work per character  Time is proportional to length of message  Space required is directly proportional to message length  Output characters cannot be produced until all characters are read in  Delay depends on the length of the message  Not appropriate for long messages V. Sawma, Computer Security 22 Summary Two basic methods of encryption: substitutions and transposition Common cryptanalytic tools:  Frequency distribution, Digram/trigram study, IC, Repeated patterns, Probable letters Four cryptanalysis cases & 5 approaches V. Sawma, Computer Security 23 Summary: A crypto-analytic’s job Compute Index of coincidence  If >0.068 then (monoalphabetic)  Compute frequency of distribution  If highest freq is for letter ‘e’ then Transposition  Else substitution (either Caesar or Scrambled Permutation)  Else Polyalphabetic  Use Kasiski’s method to determine key length  Group Cipher text in columns (based on chosen Key Length)  Solve for each column as Monoalphabetic