Attached
2/9 Breaking the Vigenere Cipher 1. Introduction The original Vigenere cipher • consists of several Caesar ciphers in sequence with different shift values • 26 Caesar ciphers with shift 0 through 25 Each cipher is denoted by a key letter that substitutes the plaintext letter a. Example: a Caesar cipher with shift 3 is denoted d We can consider that the key is a string of letters such that each letter of the plaintext is encrypted by using the Caesar cipher determined by the corresponding character in the key. If the key is shorter than the plaintext, a wrap around in the key will be used. The decryption process will be the reverse operation. In class, we presented two methods for breaking the Viginere Cipher: • Kasikis’ method- actually the original solution to the problem. • The index of coincidence method - an algorithmic approach that is much easier to automate than Kasiki’s. In both cases: • only the lower cases of the English alphabet were considered • The encryption /decryption operations were based on addition Modulo 26. 2. Objective of this assignment The objective of this assignment consists of: • Breaking the Viginere cipher for plaintext consisting of any printable character used by the English language (uppercase and lowercase letters, numeral digits, punctuation, special characters) • Designing a much efficient encryption/decryption algorithm that the addition modulo n. 3/9 3. Review of the Traditional (original) Vigenere cipher Let us review how the addition modulo 26 was used for the encryption/decryption with the original Vigenere cipher. nm CCCC kkkK pppP n m n < =="=" −="" −="" −="" 110="" 110="" 110="" ,,,ciphertext="" ,,,key="" ,,,plaintext="" ="" ="" ="" (="" )="" (="" )="" (="" )(="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" 0="" 1="" 1="" 0="" 1="" 1="" 0="" 0="" 1="" 1="" 1="" 1="" 0="" 1="" 1="" 1="" 2="" 1="" mod="" mod="" ,="" ,="" ,="" ,="" ,="" ,="" ,="" ,="" mod="" 26,="" mod="" 26,="" ,="" mod="" 26="" ,="" mod="" 26,="" mod="" 26,="" ,="" mod="" 26,="" ,="" mod="" 26="" mod="" 26="" m="" n="" m="" m="" m="" m="" m="" m="" i="" i="" m="" i="" i="" i="" m="" c="" e="" k="" p="" e="" k="" k="" k="" p="" p="" p="" k="" p="" k="" p="" k="" p="" k="" p="" k="" p="" k="" p="" c="" k="" pi="" p="" c="" k="" −="" −="" −="" −="" +="" −="" −="=" =="" +="" +="" +="" +="" +="" +="+" =="" −="" ="" ="" ="" ="" ="" ="" 4/9="" 4.="" the="" new="" method="" to="" break="" the="" vigenere="" cipher="" as="" stated="" above,="" this="" new="" approach="" to="" the="" vigenere="" cipher="" will="" not="" be="" restricted="" just="" to="" lowercase="" characters="" of="" the="" english="" alphabet.="" •="" we="" will="" consider="" all="" ascii="" printable="" characters.="" •="" an="" ascii="" character="" j="" is="" a="" printable="" character="" if="" :="" 32="" ≤="" the="" ascii="" code="" of="" j="" ≤="" 127="" •="" a="" plain="" text="" can="" be="" seen="" as="" a="" string="" of="" characters,="" while="" a="" key="" can="" be="" seen="" as="" a="" string="" of="" bytes.="" •="" the="" encryption="" is="" a="" xor="" of="" the="" plaintext="" and="" the="" bytes="" of="" the="" key.="" •="" the="" key="" will="" be="" repeated="" as="" many="" times="" as="" necessary="" if="" it="" is="" shorter="" than="" the="" plaintext.="" example:="" •="" plaintext="" is:="" “hello!”="" •="" key="" is="" oa="" whose="" acsii="" representation="" in="" hexadecimal="" is="" :0x4f41="" the="" ascii="" representation="" of="" hello!="" in="" hexadecimal="" is:="" 48656c6c6f21.="" in="" a="" programming="" language="" like="" c/c++,="" hello!="" is="" translated="" to="" :="" 0x48656c6c6f21.="" therefore,="" given="" the="" above="" plaintext,="" and="" key,="" in="" order="" to="" determine="" the="" ciphertext,="" you="" will="" need="" to="" xor="" the="" following="" two="" quantities:="" plaintext="" 4="" 8="" 6="" 5="" 6="" c="" 6="" c="" 6="" f="" 2="" 1="" xor="" key="" 4="" f="" 4="" 1="" 4="" f="" 4="" 1="" 4="" f="" 4="" 1="" cipher="" text="" 0="" 7="" 2="" 4="" 2="" 3="" 2="" b="" 2="" 0="" 6="" 0="" thus="" the="" resulting="" ciphertext="" is="" 0x0724232b2060="" which="" is="" equivalent="" in="" the="" six-charracter="" ascii="" string:="" $#+="" `="" 5.="" algorithm="" your="" attack="" will="" use="" the="" same="" steps="" as="" in="" the="" methods="" cited="" previously:="" a)="" first,="" the="" algorithm="" must="" determine="" the="" length="" of="" the="" key="" b)="" then,="" the="" algorithm="" must="" determine="" the="" key="" itself,="" hence="" determine="" the="" values="" of="" each="" of="" the="" bytes="" that="" form="" the="" key="" 5/9="" 6.="" the="" length="" of="" the="" key="" even="" though="" we="" are="" considering="" more="" characters="" than="" the="" lowercase="" letters="" of="" the="" alphabet,="" the="" frequency="" of="" the="" plaintext="" will="" still="" play="" a="" crucial="" role.="" let="" us="" denote="" by="" pi="" the="" frequency="" of="" the="" ith="" byte="" in="" the="" plaintext:="" •="" pi="0" if="" i="">< 32="" or="" i="">127 • p99= frequency of c ( ascii code of “c” is 99), etc.… • this distribution of character frequency is very far from the uniform distribution. We will use this property to determine the right size of the key. A. Cipher shifts and key length IF we assume that the key length is m; Then every mth character of the plaintext is part of the same cipher shift. o IF we take every mth character of the ciphertext, and calculate their frequencies, THEN we should get the frequencies of the pi ‘s in a shuffled order. o IF we take every kth character of the ciphertext (where k is not a multiple of m), and calculate their frequencies, THEN we should get a uniform distribution for the frequencies. B. Some hints: Since we are considering all printable ASCII characters, the criteria used by the index of coincidence method need be modified. Let us review traditional method of index of coincidence. Our plaintext is no longer restricted to only the lowercase letters of the English alphabet; therefore the following algorithm is no longer sufficient to determine the length t of the key: For τ = 1, 2… a) Look at the sequence of ciphertext characters c1, c1+τ, c1+2τ, … b) Tabulate q0 …, q25 for this sequence. c) Compute ∑ = = 25 0 2 i iqSτ i. IF τ = t THEN we expect 065.0 25 0 2 25 0 2 ≈== ∑∑ == i i i i pqSτ ii. ELSE IF τ is not a multiple of t THEN we expect that all characters will occur with roughly equal probability in the sequence c1, c1+τ, c1+2τ, …, and so, we expect qi ≈ 1/26 for all i’s , hence, we will also expect that: 038. 26 126 225 0 2 = ×== ∑ =i iqSτ 6/9 iii. where pi is the frequency of the ith lowercase letter of the alphabet in Standard English text. d) The smallest value of τ for which Sτ ≈ 0.065 is thus likely the key length. e) One can further validate a guess τ by carrying out a similar calculation using the second stream c2, c2+τ, c2+2τ, …, etc. C. Hints on how to modify the index of coincidence algorithm We will use the same reasoning as in 6.A , but instead of limiting the characters of the ciphertext to the English lowercase letters, we will think in terms of bytes with value from 0 to 255. The algorithm in 6.B can be modified as follows: For τ = 1, 2, …, f) Look at the sequence of ciphertext characters c1, c1+τ, c1+2τ, … g) Tabulate q0 …, q25 for this sequence. h) Compute ∑ = = 256 0 2 i iqSτ iv. IF τ is not a multiple of t THEN we expect that all characters will occur with roughly equal probability in the sequence c1, c1+τ, c1+2τ, …, v. and so, we expect qi ≈ 1/256 for all i’s , hence, we will also expect that: 256 1 256 1256 2256 0 2 = ×== ∑ =i iqSτ vi. IF τ = t THEN we expect 256 2 0 1 256ii S qτ = ∑= >>>> i) Try all possibilities for the key length, compute ∑ = 256 0 2 i iq j) Look the maximum of these summations. 7. The key At this stage, you have determined that the key size is L. Your task is to determine the values of the L bytes of the key. You can make use of the cipher streams to determine the value of the key. For example: • You can use the ith cipher stream which corresponds to bytes: ci, ci+L, ci+2L,……