Lecture 4 -- Vigenere Cipher and the Kasiski Attack

Let us review the Vigenere encryption method that we discussed in the last class.  Recall that it is a polyalphabetic substitution cipher, in that it does not necessarily always encrypt the same letter the same way.  This, we saw, was necessary in order to avoid letter frequency attacks (which doomed the substitution ciphers earlier in the course).  Instead, we fix a key, and encrypt each letter in the plaintext according to consecutive letters of the key.  We illustrate this now with some sample text

plaintext="theweatherforecastfortomorrowcallsforiceandsleetjustlikethevigenerecipherkeytheforecastrepeatsitselfoverandoverandoveragainatleastforthetimebeingfortunatelyforussummerwilleventuallycome";

key="RADAR";

In order to encrypt the plaintext, we sequentially go through each letter and shift it ahead according to the key letter. Thus the first key value is “R”, which is 17.  That means we shift the “t” at the beginning of the plain text 17 letters ahead, which becomes 19+17=36 ≡ 10 (mod 26), which is k.  The next letter, “h”, is unshifted becaues the next letter of the key is “A”, which is 0 in our encoding.  The next letter of the plain text, “e”, is shifted 3 ahead because the 3rd letter in the key is “D”.  We keep doing this, advancing one letter of the key and plaintext at a time.  When we reach the end of the key, we start over.  Thus the key might be thought of as “RADARRADARRADARRADARRADARRADAR........”.  We use arithmetic modulo the key length (in this case, 5), to automate this

plaintextasnumbers=ToCharacterCode[plaintext]-97;keyasnumbers=ToCharacterCode[key]-97;ciphertextasnumbers=Table[Mod[plaintextasnumbers[[k]]+keyasnumbers[[If[Mod[k,Length[keyasnumbers]]≠0,Mod[k,Length[keyasnumbers]],Length[keyasnumbers]]]],26]+97,{k,Length[plaintextasnumbers]}];ciphertext=ToUpperCase[FromCharacterCode[ciphertextasnumbers]]

There is a bit of a funny expression here with the “If” -- this is because mathematica  gives mod values starting from 0, but indexes arrays starting from 1 (C++, for example, does not do this).  In general this is a nice feature, but it simply means we need to account for it here.

Anyway, we have just produced our cipher text.  The Kasiski attack determines the key length from it (or at least attempts to), which is a crucial piece of information.  We happen to know this is 5 in our case, and I’ll use that to illustrate how it works.  There are relatively few 3-letter combinations (“trigraphs” or “trigrams”) that occur in English.  Even though a given one (such as “THE” or “FOR”) may not always be encrypted the same way, two instances in fact would be if they occured exactly a multiple of 5 positions apart in the original plaintext. This is because by the time we got to the second one, the part of the key used in the encryption would be in the same place.  For a general key, the “5” of course must be replaced by its key length.  

Let us then hunt for three letter combinations that occur more than once in the cipher text, along with the position.  The next command outputs all the 3 letter combinations, and the one after it removes ones that occur more than once.

alltrigraphs=Table[Characters[ciphertext][[Range[k,k+2]]],{k,Length[Characters[ciphertext]]-2}]

uniquetrigraphs=Union[alltrigraphs]

Now I will make a table of how frequently they each occur:

frequencycount=Table[Count[alltrigraphs,uniquetrigraphs[[k]]],{k,Length[uniquetrigraphs]}]

Mostly they each occur only once, but let' s figure out the positions of the ones which occur more than once.  I’ll print out which ones they are, and where they occur (more precisely, the position of the first letter for each occurance):

Do[If[frequencycount[[k]]>1,Print[uniquetrigraphs[[k]]," occurs at position(s) ",Flatten[Position[alltrigraphs,uniquetrigraphs[[k]]]]]],{k,Length[frequencycount]}]

Now, let’s test our hypothesis that these occur a multiple of 5 spaces apart: all except SWF do!  Thus the key length is revealed.

We can try it for another example.

ciphertext="FPYRTGOSIAOHSFZEOCEBVSBKOPYRGETIIRTFRPYGIXFPVTISNULITGOOXIOINUENFANBXIPRCPRCFMVFHIOPICIRUCAOHDFHIDETFHTPXHFTRPTOTMTJSNULAUELMQEOERFGRFETFHERYAMROXAEBVEFRGBKEEMNBKRFETDMVJPWBVTFWTJRGXLEULESXHBXNBXIPROSENZRAUMOOWODSNDIIWIDBRDTSDFHIDETFHCBRLPRGFRDVVEXIASIMFXOOEGSIAUFAUXLFJIFPDPJTIETXERXIHBZEDSMFXOEIDJGAUIAQSRUMOOSFULAUJIFPDBWAGMNBPRFWTJRGQPADIFPVTISSFAHPLESIGBZEULEJVLJZETXHBXTIETOETJSNNMGIXLJZEJXITELUSGFXHFVFJXTJRGBRDQVOQIRULAUAETLOVPDESTIMS";

alltrigraphs=Table[Characters[ciphertext][[Range[k,k+2]]],{k,Length[Characters[ciphertext]]-2}]

uniquetrigraphs=Union[alltrigraphs]

frequencycount=Table[Count[alltrigraphs,uniquetrigraphs[[k]]],{k,Length[uniquetrigraphs]}]

This time I added a command that prints out the gaps

Do[If[frequencycount[[k]]>1,Print[uniquetrigraphs[[k]]," occurs at position(s) ",Flatten[Position[alltrigraphs,uniquetrigraphs[[k]]]]," with differences ",Differences[Flatten[Position[alltrigraphs,uniquetrigraphs[[k]]]]]]],{k,Length[frequencycount]}]

There is much more data here, which is great -- it only helps us.  These are not all multiples of the same number.  However, one notices that a lot of these numbers are divisible by 3.  Another way to say this is that the “Greatest Common Divisor” (GCD) of (the vast majority of) these differences is 3.  You have to ignore a few outliers, but the pattern is clear.

Now we will decode the message.  The idea is to use frequency analysis for each letter that was encrypted the same way.  For example, the 1st, 4th, 7th, 10th, 13th, etc., numbers were all encoded by the first letter of the key.

ciphertextasnumbers=ToCharacterCode[ciphertext]-65

Let' s look at these positions we just mentioned, i.e., those numbers from positions that are 1 (mod 3), and plot its Histogram: :

Table[ciphertextasnumbers[[k]],{k,1,Length[ciphertextasnumbers],3}]

Histogram[Table[ciphertextasnumbers[[k]],{k,1,Length[ciphertextasnumbers],3}],{1}]

This is completely consistent with the first key letter being “A” (i.e., it looks like English without any shift).  For the 2nd, 5th, 8th etc. positions (i.e., those that are ≡ 2 (mod 3) we get this plot:

Histogram[Table[ciphertextasnumbers[[k]],{k,2,Length[ciphertextasnumbers],3}],{1}]

Again, judging by the position of the peak at 5, it looks like English shifted by one letter. So the 2 nd key letter seems to be "B".  Here is the remaining set, for those that are ≡ 0 (mod 3):

Histogram[Table[ciphertextasnumbers[[k]],{k,3,Length[ciphertextasnumbers],3}],{1}]

The peak is a little further to the right, and it is shifted 4 ahead of English.  So the third key letter is E, and the key is “ABE”.  Let’s decode the message now

key="ABE";keyasnumbers=ToCharacterCode[key]-65

FromCharacterCode[Table[Mod[ciphertextasnumbers[[k]]-keyasnumbers[[If[Mod[k,Length[keyasnumbers]]≠0,Mod[k,Length[keyasnumbers]],Length[keyasnumbers]]]],26]+97,{k,Length[ciphertextasnumbers]}]]

... The Gettysburg address!