Lecture 5 -- Vigenere Cipher, Index of Coincidence, and the Friedman Attack

In the last lecture we discussed the Kasiski attack, which finds the key length of a Vigenere text based on the pattern of repeated trigraphs (that is, 3 letter combinations).  Today we discuss a more potent, modernized attack that ultimately uses letter frequency.  Of course, the Vigenere cipher was designed to scramble letter frequency up, by encrypting each letter differently.

We began our discussion with an example of tossing a loaded coin, which lands heads (H) with probability p, and tails (T) with probability q = 1-p.  The probability of getting two consecutive heads (HH) or two consecutive tails (TT) is (p^2)+(q^2), whereas the probability of getting mixed results (TH or HT) is 2pq.  The difference between these two quantities is (p^2)-2 pq+(q^2) = (((p-q))^2), which is never negative since it is a square of a real number.  Thus it is more likely to get HH or TT than not.  This is a bet you can win with a loaded coin, even if you don’t know which way it is loaded: bet that consecutive tosses will come out the same.  The worst you would do in that bet is break even, which happens when p = q = 1/2.  This is because those two probabilies are equal only when (p-q) = 0, which means p=q.

Something is similar with rolling two loaded dice (e.g., in monopoly).  If (Subscript[p, 1]), (Subscript[p, 2]), (Subscript[p, 3]), (Subscript[p, 4]), (Subscript[p, 5]), (Subscript[p, 6]) are the probabilities of getting 1, 2, 3, 4, 5, or 6 (respectively) with a particular loaded die, then the probability of “doubles” (two consecutive rolls coming out the same) is (Subscript[p, 1]^2)+(Subscript[p, 2]^2)+(Subscript[p, 3]^2)+(Subscript[p, 4]^2)+(Subscript[p, 5]^2)+(Subscript[p, 6]^2).  This is in fact never less than 1/6 (we’ll show this below), and that 1/6 happens only when it is a fair die (which means each probability is exactly 1/6).  

Indeed, more generally, if there are n possible outcomes, with probabilities (Subscript[p, 1]), (Subscript[p, 2]), ..., (Subscript[p, n]) of happening, the odds of getting the same outcome in two consecutive outcomes is (Subscript[p, 1]^2)+(Subscript[p, 2]^2)+...+(Subscript[p, n]^2).  We saw in class from the Cauchy-Schwarz inequality that this number is always at least ((((Subscript[p, 1])+(Subscript[p, 2])+...+(Subscript[p, n])))^2)/n.  (Proof: apply Cauchy-Schwartz to the vector dot product  ((Subscript[p, 1]),(Subscript[p, 2]),...,(Subscript[p, n])).(1,1,...,1) and it pops right out).

We can apply this to English, which has uneven letter frequencies (e.g., “e” and “i” occur much more often than “q”, “z”, and “x”).  The upshot is that two randomly chosen letters from the English language are equal with a rather large probability (about 6.8%), vs the probability 1/26 (roughtly 3.8%) that would happen if each letter occured exactly as often as any other.  That’s because “ee” and “ii”, for example, occur much more often than other letter combinations.  

This can be measured using the Index of Coincidence: what proportion of letters of a text a given spacing apart are the same.  Define I(k) to be (the number of pairs of letters that are k spaces apart that are equal)/(length of the text - k), the denominator being the number of such pairs of letters.  Friedman’s attack is based on the idea that if k is a multiple of the key length, I(k) for a Vigenere message should be roughly the 6.8% we see in English.  That’s because those letters that are encrypted with the same part of the key are encrypted the same way.  They may not be actual English (in that, say, a “z” may be much more common than “e”), but two letters are the same exactly when their unencrypted counterparts are.  So we expect I(k) in that situation to be just like it is in English.  On the other hand, if k is not a multiple of the key length, then Friedman pointed out that I(k) should be more like the 3.8% we see in English. 

Let’s illustrate this from the Gettysburg Address example we had last time, where the key was “ABE”.

ciphertext=ToCharacterCode["FPYRTGOSIAOHSFZEOCEBVSBKOPYRGETIIRTFRPYGIXFPVTISNULITGOOXIOINUENFANBXIPRCPRCFMVFHIOPICIRUCAOHDFHIDETFHTPXHFTRPTOTMTJSNULAUELMQEOERFGRFETFHERYAMROXAEBVEFRGBKEEMNBKRFETDMVJPWBVTFWTJRGXLEULESXHBXNBXIPROSENZRAUMOOWODSNDIIWIDBRDTSDFHIDETFHCBRLPRGFRDVVEXIASIMFXOOEGSIAUFAUXLFJIFPDPJTIETXERXIHBZEDSMFXOEIDJGAUIAQSRUMOOSFULAUJIFPDBWAGMNBPRFWTJRGQPADIFPVTISSFAHPLESIGBZEULEJVLJZETXHBXTIETOETJSNNMGIXLJZEJXITELUSGFXHFVFJXTJRGBRDQVOQIRULAUAETLOVPDESTIMS"];

This table now lists the index of coincidence for all k up to 30.  You can try this for your own example by replacing the ciphertext above.

Table[{shift,Sum[If[ciphertext[[k]]==ciphertext[[k+shift]],1./(Length[ciphertext]-shift),0],{k,1,Length[ciphertext]-shift}]},{shift,1,30}]//TableForm

Here is a plot, in which we can see the peaks every 3.  I’m plotting a red line at 3.8% and a green line at 6.8%, to see how the above theory fits this data sample.

Show[Plot[{1/26,.068},{x,1,30},PlotStyle->{Red,Green}],ListPlot[Table[{shift,Sum[If[ciphertext[[k]]==ciphertext[[k+shift]],1./(Length[ciphertext]-shift),0],{k,1,Length[ciphertext]-shift}]},{shift,1,30}],Joined->True],PlotRange->All]

Indeed, the lines match pretty well.  Here is the other example we did last time, whose key was “RADAR”.  Because there are repeated letters in the key, it actually takes longer for the peaks to kick in -- it is muddled for smaller k due to this.  For that reason I’ll draw these plots further than 30 out.

ciphertext=ToCharacterCode["KHHWVRTKEIWOUETRSWFFITRMFIRRWTRLOSWFRLCVRNGSCVEWJLJTOIBVTKEMZGHNVIEFIGYEUKVPTKEWFRHCRJTUEGVAWSZKSHLWFVHRREDRVVIAQDFMEUAXRIQAKCEDSKWOUTYVTLMVSELNXWOUTLEAWECPFRRLJSXMDVRZICCEYEEKUDLCPCRMV"];

Table[{shift,Sum[If[ciphertext[[k]]==ciphertext[[k+shift]],1./(Length[ciphertext]-shift),0],{k,1,Length[ciphertext]-shift}]},{shift,1,60}]//TableForm

Show[Plot[{1/26,.068},{x,1,60},PlotStyle->{Red,Green}],ListPlot[Table[{shift,Sum[If[ciphertext[[k]]==ciphertext[[k+shift]],1./(Length[ciphertext]-shift),0],{k,1,Length[ciphertext]-shift}]},{shift,1,60}],Joined->True],PlotRange->All]

Indeed, the peaks eventually come about every 5, thought not always.  The value at 40 is abnormally low, but the value at 45 is abnormally high.  This happens with random data.  The point is that with enough data, the spacing of 5 between these peaks is apparent, and that indicates the key length is 5.

The lesson is that even encrypting every letter differently doesn’t necessarily shred letter frequency attacks.