Polyalphabetic Substitution Ciphers & Vigenère Cipher PDF

Polyalphabetic Substitution Ciphers A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. A sequence of monoalphabetic ciphers (M 1, M2, M3,..., Mk) is used in turn to encrypt letters. A key determines which sequence of ciphers to use. Each...

Polyalphabetic Substitution Ciphers A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. A sequence of monoalphabetic ciphers (M 1, M2, M3,..., Mk) is used in turn to encrypt letters. A key determines which sequence of ciphers to use. Each plaintext letter has multiple corresponding ciphertext letters. This makes cryptanalysis harder since the letter frequency distribution will be flatter. 1  Vigenère Cipher Simplest polyalphabetic substitution cipher Consider the set of all Caesar ciphers: { Ca, Cb, Cc,..., Cz } Key: e.g. security Encrypt each letter using Cs, Ce, Cc, Cu, Cr, Ci, Ct, Cy in turn. Repeat from start after Cy. Decryption simply works in reverse. 2  Example of Vigenère Cipher Keyword: deceptive key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ 3 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 z 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ Ke 3 4 2 4 15 19 8 21 4 y Mode 26 PT 22 4 0 17 4 3 8 18 2 CT z i c v The key length is 9, the cipher consists of 9 Caesar ciphers. Plaintext letters at positions 0, 0+9, 0+2*9, 0+ 3*9, etc. 4 The key can be BEST 5 Vigenere Cipher Table It consists of all the alphabets written 26 times in different rows. Each alphabet in every subsequent row and column is shifted cyclically to the left. This generates 26 Caesar Ciphers. 7  Security of Vigenère Ciphers There are multiple (how many?) ciphertext letters corresponding to each plaintext letter. So, letter frequencies are obscured (confused) but not totally lost. To break Vigenere cipher: 1. Try to guess the key length. How? 2. If key length is N, the cipher consists of N Caesar ciphers. Plaintext letters at positions k, k+N, k+2N, k+3N, etc., are encoded by the same cipher. 3. Attack each individual cipher as before. 8  Guessing the Key Length Main idea: Plaintext words separated by multiples of the key length are encoded in the same way. In our example, if plaintext = “…thexxxxxxthe…” then “the” will be encrypted to the same ciphertext words. So look at the ciphertext for repeated patterns. E.g. repeated “VTW” in the previous example suggests a key length of 3 or 9: ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ However, the cryptanalysis of Vigenère Ciphers is not easy but it could be with many further computations. The following videos are useful for self studying https://youtu.be/LaWp_Kq0cKs https://www.youtube.com/watch?v=P4z3jAOzT9I 9  Rotor Cipher Machines Vigenere can be broken once somebody finds the key length ! How to have a longer key? ! Idea: ! Multiple rounds of substitution, encryption consists of mapping a letter many times ! Mechanical/electrical wiring to automate the encryption/decryption process ! A machine consists of multiple cylinders (rotors) that map letters several times 10  Rotor Cipher Machines Before modern ciphers, rotor machines were most common complex ciphers in use. Widely used in WW2. Used a series of rotating cylinders. Implemented a polyalphabetic substitution cipher of period K. With 3 cylinders, K = 263 =17,576. With 5 cylinders, K = 265 =12 x 106. What is a key? – If the adversary has a machine – If the adversary doesn’t have a machine 11  Rotor Cipher Machines Each rotor has 26 states (as many as the alphabet) ! At each state there is a substitution cipher: the wiring between the contacts implements a fixed substitution of letters ! Each cylinder rotates to change states according to a different schedule changing the substitution ! A m-cylinder rotor machine has 26m different substitution Most famous rotor machine is Enigma 12  The next major advance in ciphers required use of mechanical cipher machines which enabled to use of complex varying substitutions. A rotor machine consists of a set of independently rotating cylinders through which electrical pulses can flow. Each cylinder has 26 input pins and 26 output pins, with internal wiring that connects each input pin to a unique output pin. If we associate each input and output pin with a letter of the alphabet, then a single cylinder defines a monoalphabetic substitution. After each input key is depressed, the cylinder rotates one position, so that the internal connections are shifted accordingly. The power of the rotor machine is in the use of multiple cylinders, in which the output pins of one cylinder are connected to the input pins of the next, and with the cylinders rotating like an “odometer”, leading to a very13 large number of substitution alphabets being used, eg Assignment Decryption 14 Enigma Rotor Machine 15 The Rotors 16  Transposition Ciphers Also called permutation ciphers. Shuffle the plaintext, without altering the actual letters used. Example: Row Transposition Ciphers 17  Row Transposition Ciphers Plaintext is written row by row in a rectangle. Ciphertext: write out the columns in an order specified by a key. a t t a c k p Key: 3 4 2 1 5 6 7 o s t p o n e d u n t i l t Plaintext: w o a mx y z Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ 18  Product Ciphers Uses a sequence of substitutions and transpositions – Harder to break than just substitutions or transpositions This is a bridge from classical to modern ciphers. 19  Product Ciphers Ciphers using substitutions or transpositions are not secure because of language characteristics Hence consider using several ciphers in succession to make harder, but: – Two substitutions make another substitution – Two transpositions make a more complex transposition – But a substitution followed by a transposition makes a new much harder cipher This is bridge from classical to modern ciphers  Unconditional & Computational Security A cipher is unconditionally secure if it is secure no matter how much resources (time, space) the attacker has. A cipher is computationally secure if the best algorithm for breaking it will require so much resources (e.g., 1000 years) that practically the cryptosystem is secure. All the ciphers we have examined are not unconditionally secure. 21 An unconditionally Secure Cipher Vernam’s one-time pad cipher  Key = k1k2k3k4  (random, used one-time only)  Plaintext = m1m2m3m4   Ciphertext = c1c2c3c4  where ci mi  ki  Can be proved to be unconditionally secure. 22 XOR truth table Input Output A B 0 0 0 0 1 1 1 0 1 1 1 0 11011 XOR 00101 11110 XOR 11011 11110 23  Steganography Hide a message in another message. E.g., hide your plaintext in a graphic image – Each pixel has 3 bytes specifying the RGB color – The least significant bits of pixels can be changed w/o greatly affecting the image quality – So can hide messages in these LSBs Advantage: hiding existence of messages Drawback: high overhead 24  Take a 640x480 (=30,7200) pixel image. Using only 1 LSB, can hide 115,200 characters Using 4 LSBs, can hide 460,800 characters. 25 26  Summary Have considered: – classical cipher techniques and terminology – monoalphabetic substitution ciphers – cryptanalysis using letter frequencies – Playfair cipher – polyalphabetic ciphers – transposition ciphers – product ciphers and rotor machines – stenography 27