Table 4.16 gives a Vigen`ere ciphertext for you to analyze from scratch. It is p
ID: 3855162 • Letter: T
Question
Table 4.16 gives a Vigen`ere ciphertext for you to analyze from scratch. It is probably easiest to do so by writing a computer program, but you are welcome to try to decrypt it with just paper and pencil.
(a) Make a list of matching trigrams as we did in Table 4.3. Use the Kasiski test on matching trigrams to find the likely key length.
Trigram - Appears at places - Difference
avl - 117 and 258 - 141 = 3 · 47
bjo - 86 and 121 - 35 = 5 · 7
dlr - 4 and 25 - 21 = 3 · 7
gdl - 3 and 24 - 16 = 24
Table 4.3: Repeated trigrams in the ciphertext given
(b) Make a table of indices of coincidence for various key lengths, as we did in Table 4.4. Use your results to guess the probable key length.
Key Average Individual Indices
Length Index of Coincidence
4 0.038 0.034, 0.042, 0.039, 0.035
5 0.037 0.038, 0.039, 0.043, 0.027, 0.036
6 0.036 0.038, 0.038, 0.039, 0.038, 0.032, 0.033
7 0.062 0.062, 0.057, 0.065, 0.059, 0.060, 0.064, 0.064
8 0.038 0.037, 0.029, 0.038, 0.030, 0.034, 0.057, 0.040, 0.039
9 0.037 0.032, 0.036, 0.028, 0.030, 0.026, 0.032, 0.045, 0.047, 0.056
Table 4.4: Indices of coincidence of Table 4.2 for various key lengths
(c) Using the probable key length from (a) or (b), make a table of mutual indices of coincidence between rotated blocks, as we did in Table 4.5. Pick the largest indices from your table and use them to guess the relative rotations of the blocks, as we did in Table 4.6.
(d) Use your results from (c) to guess a rotated version of the keyword, and then
try the different rotations as we did in Table 4.7 to find the correct keyword
and decrypt the text.
mgodt beida psgls akowu hxukc iawlr csoyh prtrt udrqh cengx
uuqtu habxw dgkie ktsnp sekld zlvnh wefss glzrn peaoy lbyig
uaafv eqgjo ewabz saawl rzjpv feyky gylwu btlyd kroec bpfvt
psgki puxfb uxfuq cvymy okagl sactt uwlrx psgiy ytpsf rjfuw
igxhr oyazd rakce dxeyr pdobr buehr uwcue ekfic zehrq ijezr
xsyor tcylf egcy
Table 4.16: A Vigen`ere ciphertext for Exercise 4.18
Explanation / Answer
What makes the Vigen`ere cipher difficult to break (at first sight) is that the frequencies of the encrypted text are do not match any permutation of the frequencies of English. That is, there is no simple substitution cipher that has the same frequencies as a message encrypted with a Vigen`ere cipher. This is illustrated in Table 2 where I have written out the top 5 frequencies of letters in the King James Bible and the top 5 frequencies of letters when the King James Bible is encrypted with the keyword ’STATISTICS’. If all of the frequencies were the same, then we could break the Vigen`ere cipher by finding a simple substitution cipher with the same frequencies. Plain: 0.127 0.098 0.087 0.085 0.075 Vigen`ere: 0.077 0.067 0.063 0.061 0.060 Table 2: Top 5 frequencies of plain text and Vigen`ere encrypted text. The Vigen`ere cipher does have a weakness, however. Its weakness is its 1 periodicity. To see this, let us write out a formula that represents the Vigen`ere cipher’s encryption system. Suppose our keyword is k = (k1, . . . , km), then the vigenere cipher with keyword k can be expressed as (C1, C2, . . . , Cn) = Vk ((t1, t2, . . . , tn)) = ((t1 + k1)%26,(t2 + k2)%26, . . . ,(tr + kr%m)%26, . . . ,(tn + kn%m)%26). The periodicity of the Vigen`ere cipher can be seen when we look at the following substring of the ciphertext C1, C1+m, . . . , C1+rm, . . . , C1+bn/mcm = (t1 + k1)%26,(t1+m + k1%26), . . . ,(t1+rm + k1)%26, . . . ,(t1+bn/mcm + k1)%26 = Tk1 (t1, t1+m, . . . , t1+rm, . . . , t1+bn/mcm) . That is, the substring (C1, C1+m, . . . , C1+rm, . . . , C1+bn/mcm of the ciphertext is just the substring (t1, t1+m, . . . , t1+rm, . . . , t1+bn/mcm) of the plain text encrypted with a shift cipher with shift k1. Similarly for each 2 i m, the substring (Ci , Ci+m, . . . , Ci+rm, . . . , Ci+bn/mcm of the ciphertext is just the substring (ti , ti+m, . . . , ti+rm, . . . , ti+bn/mcm) of the plain text encrypted with a shift cipher with shift ki . Therefore, if we knew the length of the keyword k was m we can break the cipher textC = (C1, . . . , Cn) up into m separate substrings of cipher text C˜ i = (Ci , Ci+m, . . . , Ci+rm, . . . , Ci+bn/mcm . Then, on each C˜ i we can use the tools at our disposal that will break the individual shift ciphers. This leads us to an estimate of the keyword ˆk = (ˆk1, . . . , ˆkm) where ˆki is our estimate of the shift parameter used in obtaining C˜ i . In Table 3 we tried this strategy when we knew the length of the keyword was 10. We have started with 100 characters, 150 characters than 200 characters. Even with only 200 characters, breaking the text into individual cipher texts gives perfect recovery of the keyword ’STATISTICS’.
2 Guessing keyword length: Kasiski attack The Vigen`ere cipher proved to be very difficult to break for many years. The first attack was developed by a Polish mathematician called Kasiski. He took advantage of the Vigen`ere’s weakness – its periodicity. What Kasiski noticed 2 Length of text Estimated keyword ˆk Decrypted Text 100 ITAIIXEIJW Dhe neiirth auedtddn uasng auo io Inosioeii Bnor is ehdh: Il uyur aumeola sn Ical aifeded eo owe wa 150 TTAIIXTICS She neitral puedtdon behng auo to Prdsioeit Busg is ehds: Is ynur aumpose hn Ical limised eo ohe dertrfcoion oe alw ios prerene aid potdnttag weapnns 200 STATISTICS The central question being put to President Bush is this: Is your purpose in Iraq limited to the destruction of all its present and potential weapons of mass destruction? Or is your goal ”regime change” ? Table 3: Attack on Vigen`ere cipher with progressively more text, known key length 10. was that if a trigram (three letters in a row) appeared an integer multiple of the key length m apart in the plain text, then they will encrypt to the same trigram in the cipher text. An example of this is given in Table 4. Therefore, some repeated trigrams in the cipher text will be an integer multiple of the key length apart. It is not necessarily true that all of the repeated trigrams will be an integer multiple of the key length apart. An example of this, albeit slightly artificial, is given in Table 5. However, if we have enough data, it seems reasonable to believe that most of the trigrams will come about as Kasiski believed they would. Once we find repeated trigrams in the cipher text we have to compute the distance between these repeated trigrams and look for a common factors of many of these repeated trigrams. The reason we look for common factors of the distances between these repeated trigrams is that any trigrams arising `a la Kasiski will have the keyword length as a factor. Key: K E Y K E Y K E Y K E Y K E Plain: T H E P E A R I S T H E R E Cipher: D L C Z I Y B M Q D L C B I Table 4: Repeated trigrams exploited by Kasiski’s attack. To see how this works in practice, when we look at the first 200 characters of the article in Table 6 there are only 2 repeated trigrams ’WAG’ and ’MFM’, and they appear at distances of 40 and 30, respectively. Thus, we might guess that the key length is 10, as we know it is, in this case. Once we have diguessed the 3 Key: K E Y E Z L L K E Y E Z L Plain: T H E P E A R I S B L U E Cipher: D L C T D L C S W Z P T P Table 5: Repeated trigrams not falling into Kasiski’s scheme. keyword has length 10, we can use the attack described in the previous section. One weakness of this attack is that it may be the case, as in this example, that there are very few repeated trigrams. What if the distances had been 36 and 35? Plain text Cipher text THE CENTRAL QUESTION BEING PUT TO PRESIDENT BUSH IS THIS: IS YOUR PURPOSE IN IRAQ LIMITED TO THE DESTRUCTION OF ALL ITS PRESENT AND POTENTIAL WEAPONS OF MASS DESTRUCTION? OR IS YOUR GOAL ”REGIME CHANGE” ? LAE VMFMZCD INELBAHV DWAGG ICL MW RJWLIWMFM JWKZ BS MPAL: QU QGNR ICJIWUW AG IKII EQOALXD MW LAM FWKMRNKLBWP GX TLE QLL XTWKXNM IFW XQLWGTBID PMCHGGS HN ETAU VWLTKCUMQQF? GK IL GGNZ IGSE ”RXOAFM EZSGGX” ? Table 6: Plain text and Vigen`ere encrypted text with keyword ’STATISTICS’. Repeated trigrams are in small bold.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.