Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide #9-1 Classical CryptographyCS498SHFall 2006Based on slides provided by Matt Bishop for use with Computer Security: Art and ScienceSlide #9-2Chapter 9: Classic Cryptography•Historical Cryptography•Symmetric Key CryptographySlide #9-3Reading•Chapter 9 from Computer Science: Art and Science•Applied Cryptography, Bruce SchneierSlide #9-4Overview•Classical Cryptography–Cæsar cipher–Vigènere cipher•Symmetric Key Cryptography–DES–AESSlide #9-5Cryptosystem•Is the basic component of cryptography•5-tuple (E, D, M, K, C)–M set of plaintexts–K set of keys–C set of ciphertexts–E set of encryption functions e: M K C–D set of decryption functions d: C K MSlide #9-6Example•Example: Cæsar cipher (The most basic cipher)–M = { sequences of letters }–K = { i | i is an integer and 0 ≤ i ≤ 25 }–E = { Ek | k K and for all letters m,Ek(m) = (m + k) mod 26 }–D = { Dk | k K and for all letters c,Dk(c) = (26 + c – k) mod 26 }–C = MSlide #9-7Attacks•Opponent whose goal is to break cryptosystem is the adversary–Standard cryptographic practice: Assume adversary knows algorithm used, but not the key•Three types of attacks:–ciphertext only: adversary has only ciphertext; goal is to find plaintext, possibly key–known plaintext: adversary has ciphertext, corresponding plaintext; goal is to find key–chosen plaintext: adversary may supply plaintexts and obtain corresponding ciphertext; goal is to find keySlide #9-8Basis for Attacks•Mathematical attacks–Based on analysis of underlying mathematics•Statistical attacks–Make assumptions about the distribution of letters, pairs of letters (diagrams), triplets of letters (trigrams), etc.•Called models of the language•E.g. Caesar Cipher, letter E–Examine ciphertext, correlate properties with the assumptions.Slide #9-9Classical Cryptography•Sender, receiver share common key–Keys may be the same, or trivial to derive from one another–Sometimes called symmetric cryptography•Two basic types–Transposition ciphers–Substitution ciphers–Combinations are called product ciphersSlide #9-10Transposition Cipher•Rearrange letters in plaintext to produce ciphertext•Example (Rail-Fence Cipher)–Plaintext is HELLO WORLD–Rearrange asHLOOLELWRD–Ciphertext is HLOOL ELWRDSlide #9-11Attacking the Cipher•Anagramming–If 1-gram frequencies match English frequencies, but other n-gram frequencies do not, probably transposition–Rearrange letters to form n-grams with highest frequenciesSlide #9-12Example•Ciphertext: HLOOLELWRD•Frequencies of 2-grams beginning with H–HE 0.0305–HO 0.0043–HL, HW, HR, HD < 0.0010•Frequencies of 2-grams ending in H–WH 0.0026–EH, LH, OH, RH, DH ≤ 0.0002•Implies E follows HSlide #9-13Example•Arrange so the H and E are adjacentHELLOWORLD•Read off across, then down, to get original plaintextSlide #9-14Substitution Ciphers•Change characters in plaintext to produce ciphertext•Example (Cæsar cipher)–Plaintext is HELLO WORLD–Change each letter to the third letter following it (X goes to A, Y to B, Z to C)•Key is 3, usually written as letter ‘D’–Ciphertext is KHOOR ZRUOGSlide #9-15Attacking the Cipher•Exhaustive search–If the key space is small enough, try all possible keys until you find the right one–Cæsar cipher has 26 possible keys•Statistical analysis–Compare to 1-gram model of EnglishSlide #9-16Statistical Attack•Compute frequency of each letter in ciphertext:G 0.1H 0.1K 0.1O 0.3R 0.2U 0.1Z 0.1•Apply 1-gram model of English–Frequency of characters (1-grams) in English is on next slideSlide #9-17Character Frequencies0.002z0.015g0.020y0.060s0.030m0.020f0.005x0.065r0.035l0.130e0.015w0.002q0.005k0.040d0.010v0.020p0.005j0.030c0.030u0.080o0.065i0.015b0.090t0.070n0.060h0.080aSlide #9-18Statistical Analysis•f(c) frequency of character c in ciphertext(i) correlation of frequency of letters in ciphertext with corresponding letters in English, assuming key is i(i) = 0 ≤ c ≤ 25 f(c)p(c – i) so here,(i) = 0.1p(6 – i) + 0.1p(7 – i) + 0.1p(10 – i) + 0.3p(14 – i) + 0.2p(17 – i) + 0.1p(20 – i) + 0.1p(25 – i)•p(x) is frequency of character x in EnglishSlide #9-19Correlation: (i) for 0 ≤ i ≤ 250.0430250.066060.0316240.0299180.0325120.019050.0370230.0392170.0262110.025240.0380220.0322160.0635100.057530.0517210.0226150.026790.041020.0302200.0535140.020280.036410.0315190.0520130.044270.04820(i)i(i)i(i)i(i)iSlide #9-20The Result•Most probable keys, based on :–i = 6, (i) = 0.0660•plaintext EBIIL TLOLA–i = 10, (i) = 0.0635•plaintext AXEEH PHKEW–i = 3, (i) = 0.0575•plaintext HELLO WORLD–i = 14, (i) = 0.0535•plaintext WTAAD LDGAS•Only English phrase is for i = 3–That’s the key (3 or ‘D’)Slide #9-21Cæsar’s Problem•Key is too short–Can be found by exhaustive search–Statistical frequencies not concealed well•They look too much like regular English letters•So make it longer–Multiple letters in key–Idea is to smooth the statistical frequencies to make cryptanalysis harderSlide #9-22Vigènere Cipher•Like Cæsar cipher, but use a phrase as key•Example–Message THE BOY HAS THE BALL–Key VIG–Encipher using Cæsar cipher for each letter:key VIGVIGVIGVIGVIGVplain THEBOYHASTHEBALLcipher OPKWWECIYOPKWIRGSlide #9-23Relevant Parts of Tableau G I VA G I VB H J WE L M ZH N P CL R T GO U W JS Y A NT Z B OY E H T•Tableau shown has relevant rows, columns only•Example encipherments(?):–key V, letter T: follow V column down to T row (giving “O”)–Key I, letter H: follow I column down to H row (giving “P”)Slide #9-24Useful Terms•period: length of key–In earlier
View Full Document
Unlocking...