VignereCoder.html

Vignere encryption tools

ŠMike May, S. J., 2002, maymk@slu.edu

> restart:

We start with our standard message:

> mess[1] := "Good morning Mr. Phelps.
Your mission for today, should you choose to accept it,
is to learn about the Vignere cipher.";

Preparing tools for the Vignere cipher

The Vignere cipher is much like the Caesar cipher in that it is an additive cipher. It differs in that the key rotates through a word or phrase. An infinite code word would be a one time pad.

In setting up the procedures for the Vignere cipher, we first want a procedure that works on a single letter. For input it will need the letter to be encoded, it's position in the message, the key, and the keylength.

>    vignere := proc(letter, count, key, klength)
     local temp,t1;
     temp := letter:
# t1 is which letter of the key is being used.
# it should rotate from 1 to klength
t1 := 1 + ((count -1) mod klength);
   if (letter > 64) and (letter < 91) then
         temp := 65 + ((temp - 65 + key[t1]) mod 26):
     fi:
   if (letter > 96) and (letter < 123) then
         temp := 97 + ((temp - 97 + key[t1]) mod 26):
     fi:
   temp:
  end:

Next we need a procedure that encodes an entire message using the procedure above. The procedure encodevignere works on the original ASCII message. Special characters, spaces, and line feeds are not modified by the procedure. They are also not counted as characters for determining position.

>    encodevignere := proc(message, key, klength)
   #This procedure uses the vignere cipher to encode a string
   #key should be a list of integers from 0 to 25
   #message is an ASCII string. klength is the length of the key
local temp1, messageLength, position, counter:
   #first convert the message to numerical equivalents
temp1 := convert(convert(message, bytes),array):
   #then uses vignere to scrable the letters.
   # c1 is the number of chaqracters in the message.
messageLength:= linalg[vectdim](temp1):
   # counter is the number of letters converted
counter := 0:
for position from 1 to messageLength do
    if (temp1[position] > 64) and (temp1[position] < 91) then
       counter := (counter mod klength) + 1:
       temp1[position] := 65 + ((temp1[position] - 65 + key[counter]) mod 26):
    fi:
    if (temp1[position] > 96) and (temp1[position] < 123) then
       counter := (counter mod klength) + 1:
       temp1[position] := 97 + ((temp1[position] - 97 + key[counter]) mod 26):
    fi:
od:
   #then convert back to the ASCII code
convert(convert(temp1,list), bytes):
end:

We also want a procedures for turning a lower case word into an enciphering key and another procedure for producing a deciphering key.

> wordtoekey := x -> map(a -> a-97, convert(x,bytes)):
wordtodkey := x -> map(a -> 123-a,convert(x,bytes)):

Using Vignere

We are now ready to go.

> message1 :=mess[1]:
vignerekey := wordtoekey("phantom");
keylength := nops(vignerekey);

> ciphertext1 := encodevignere(message1, vignerekey, keylength);

It is often worthwhile to produce the decryption key and to use it to check the process works both ways.

> ciphertext1;

> decryptkey := wordtodkey("phantom");

> encodevignere(ciphertext1, decryptkey, keylength);
convert(encodevignere(ciphertext1, decryptkey, keylength),name);

$`Good morning Mr. Phelps.\nYour mission for today, should you choose to accept it,\nis to learn about the Vignere cipher.`$
$`Good morning Mr. Phelps.\nYour mission for today, should you choose to accept it,\nis to learn about the Vignere cipher.`$
$`Good morning Mr. Phelps.\nYour mission for today, should you choose to accept it,\nis to learn about the Vignere cipher.`$

Exercises:

1) Use the concatenation of your first and last names as a key for a Vignere cipher.

Convert your key to integers.

>

2) Use your key to encode the standard message with your key. Save the encoded message as message2.

>

3) Decrypt your message and save the settings.

>

Evaluating the strength of Vignere

One measure of the improvement of a Vignere encryption over a monoalphabetic cipher is how much it evens out the distribution of letters for a standard English text. To see how good a Vignere encryption is we want a frequency counter and a tool to measure how flat the distribution of letters is.

>

We recall the tools constructed in the Frequency Attack worksheet.

>    specialCharacterStrip := proc(message)
   local messList, letter, messlength, messList2, i;
   messList := convert(message, bytes):
   messlength := linalg[vectdim](messList);
   messList2 := [];
   for i from 1 to messlength do
     letter := messList[i]:
     if (letter > 64) and (letter < 91) then
          messList2 := [op(messList2), letter] fi:
     if (letter > 96) and (letter < 123) then
          messList2 := [op(messList2), letter-32] fi:
   od:
   messList2:
end:
shortCounter := proc(messageList)
   local message2, letter, messlength, freqVector, i;
   messlength := linalg[vectdim](messageList);
   freqVector := linalg[vector](27, i->0):
   for i from 1 to messlength do
      letter:= messageList[i] - 64:
      freqVector[letter] := freqVector[letter]+1:
      freqVector[27] := freqVector[27]+1:
   od:
   freqVector:
  end:
freqCounter := message -> shortCounter(specialCharacterStrip(message)):
freqPrinter := proc(freqVector)
     local message2, letter, messlength, freqcount, i, countera,
        temp0, temp1, temp2;
   temp1 := convert(freqVector[27],string):
   print(`The string had `||temp1||
      ` characters from the Latin alphabet.`);
   for countera from 1 to 26 do
     temp0 := convert(convert([64 + countera], bytes),string):
     temp1 := convert(freqVector[countera],string):
     temp2 := convert(evalf(
        freqVector[countera]/freqVector[27]*100.0,4),string):
     print(`The letter `|| temp0 || ` appears `||temp1||` times,`||
        temp2||`% of the time.`);
   od;
end:

We repeat the message from the last worksheet so that we can check frequencies on a real message. Note that we use double double quotes to put a quotation mark in the middle of a string.

> message1 := "Numbers dominate much of our everyday lives in diverse and barely
perceptible ways. Parents are anious to see their children attain
good grades in mathematics, assured that this is a passport to success and
security. The government stipulates that mathematical studies are
compulsory for most of a child's time at school. Intelligence tests contain
particular ingredients to test the candidates' ability to reason mathematically.
Advertisements promising challenging and well-paid employment
invite us to seek further details if we can successfully spot
the next number in puzzling sequences. Students change subjects when
they discover the mathematical content of their course is too
difficult to master. Young children turn out to be extraordinarily talented
in mathematics with abilities outstripping children twice their age,
yet their performance in other subjects is unremarkable. Only
in art and music is such precociousness so impressive. Looking out into
the wider world, we see the cogs of the Western world turned by the
engines of mathematical understanding. Computers programmed with
inexorable logic control our economies and money markets, our aeroplanes
and trains. Our own minds are seen as a fallible ""natural"" form
of intelligence that these computers will ultimately perfect in an
embodiment of ""artificial"" intelligence that is nothing more than a
complicated mathematical algorithm that can be implemented
electronically far faster and less fallibly than by our own feeble brains.
In our universities there is an unspoken suspicion that the further
a discipline lies from mathematics and the smaller the body of
mathematical statements at its core the less rigorous and intellectually
respectible it is.":
freq2 := freqCounter(message1):

We now divide all the counts for the letters by the number of letters.

> freq3 := seq(26.0*freq2[i]/freq2[27], i=1..27);

As expected, e shows up more than three times as often as expected for an even share and q and z are very rare.

The letter e shows up more than 170 times as often as the letter q.

If the distribution were even, the first 26 places would all be 1. One measure of the how far the distribution is from even is to square the difference from the expected values.

> distmeasure := sum((freq3[i]-1)^2,i=1..26);

Compare these results with what happens if we encode with the Vignere cipher.

> ciphertext1 := encodevignere(message1, vignerekey, keylength):
freq2a := freqCounter(ciphertext1):
freq3a := seq(26.0*freq2a[i]/freq2a[27], i=1..27);
distmeasurea := sum((freq3a[i]-1)^2,i=1..26);

In the encoded text, no letter is used more than 5 times as often as any other letter. The distance from a flat distribution has dropped from almost 20 to a little more than 3.

Exercises :

4) Type in a passage of at least 500 characters form your favorite book and save it as message3. Do a frequency count and list the frequencies of the 5 most common letters. As defined above, find the distance the message is from a flat distribution.

Encode your message with a Vignere cipher and a key of "theraininspainfallsmainly". Do a frequency count for the encoded message and give the frequencies of the five most common letters. Find the distance the encoded message is from a flat distribution.

>

5) With a Vignere key of length 5 how close can you get the encryption of you message to flat?

>

Attacking Vignere

To attack the Vignere cipher, we want to figure out the length of the key.
To do that we note that if the key is n characters long, a substring made of every nth characters should have a distribution similar to that of typical English text. (The same will be true of a substring made of every 2-nth character.)

Consider the message above and the ciphertext. We first produce a list of the numeric equivalents of the strings with special characters removed and all letters converted to upper case.

> messList := specialCharacterStrip(message1):
cipherList := specialCharacterStrip(ciphertext1):

Now we want a procedure to find the normed size of the frequency vector associated to each string.

>    normedSize := proc(messageList)
   local freqList:
   freqList := shortCounter(messageList):
   evalf(sum((freqList[i]/freqList[27])^2, i=1..26));
end:

> normedSize(messList);

> normedSize(cipherList);

Note that the ciphertext distribution is much flatter than the normal text distribution. Now we want a tool to extract the nth character from a message list.

>    nthCharacters := proc(messageList, n)
   local messageLength, shortLength, shortList:
   messageLength := linalg[vectdim](messageList):
   shortLength := iquo((messageLength + n - 1),n):
   shortList := [seq(messageList[1+i*n],i=0..(shortLength-1))]:
end:

Now we find the size of the distribution vector for the plaintext string using every nth character with n going from 1 to 10.

> seq(normedSize(nthCharacters(messList,n)),n=1..10);

All of the norms are obout the sime size, a bit more than .06. Compare what happens when we try the same thing with the ciphertext.

> seq(normedSize(nthCharacters(cipherList,n)),n=1..10);

The distribution with n = 7 gives the correct distribution and is our key size.

Exercises:

6) An encrypted version of message1 is given below. Find the length of the key.

> ciphertext1 :=
"SLQENFFHGRZRDCSZYUMFJRDFRZWWPHDHZVZWXZRGRJRVKJRRGKOEIDDGIULSCXAGCIZJMFTSWVRWBOEISSZSXBHBWWJKLHRFPLAQUVHWOGXSNEKRXRTVSIVWLWANXZJDEWRQFEKXLVHMHUELYYMVRGNTSXJTRAHGSKZTGHBGNRVXVGXAWGCLMVKRESEREJEXVCWCYDFKIVCVNXEFKLHVOGMUFCWWDRVIKFIIFXACYDXFVBOCEQGXKSIJQUMDIJXLVSNXKHYSRUWAXWQCMJNBPILJJXVLCAXSNETDAHVGMQRVLWUEIVNVRWBHBXWXKXKNQNRVNUEWNGNFAQZXBCCEISXFRPJHUIEFKMFJZYCSIMIUCWFIEJEXVYFBQAXZRJLVNPDJEKLWUNRVBVPOYOVHWRGPRHARRLNEZLCSHWLTJIHTTHVLMVVGNHNMDXZJZNQNRKZTGHBGSYDQPWSXHGLWSVBWWIZFWWZRSDNMPASXWHZIRRUJJWWDRRRLXTLDWURWMGAIFCGJLWSKLHHRVWUTMIUCVRQSYYIPJHVGSQTSQCSAXGKKLHRFPSMWJILBHBSVNWJLLIYXLTDEVCSECGZEKFQWYHJJEXXABBYLYFFHNLGVSTIHLWOEMDDKEONBGIVNEQDCVRQSYZGVFWGLSGZPLCWRWGZKWWAWCTASXGKRZQVWSKALLSGLWNIEJNMRXLMVMUYSEJGWDEQLSVRGYYIUBIONWHKWLBIAVWRRVNJPYIGSCCLWOEXSSUQXBWPMKXLGKYFRGGHZSXBBRWKXFMPYFRWKNMIOXCXMFLFYWRBGSLMVALMSEAGWCHZNGRILMVGRPGBJLMVAHBHRVFBFVOMHHVFJUFBCVRIFLZRHBCSQSYYIPJHVGSQLRGNFFXSSUMQPQBQHZKIUBDESYWRQPNRJMLMZRHGCEETQVPRPWPGGSKVRUCHVWHFRRVWRWSSUQRWSLQSWBIWBCHVSJISSUOAIKFEHWAOVRKTLVRFBZMFIJEUNGRIFFJEIJZYMTQVRDCIEEDKFVPXTVRLJCPLPSAGWYYEWCVRWWHFQSDHRVKBZPODZGMEFKIOHDRVXJTXLWOAIEGFHLVSAXGKRVWRTVGAFCMQCSYPALVRFNHUELNJRRCVVRYRFVHCVNRSHFQSUWPELJUQDCVRQSYZGDUOYKGWZXKVHUELHRRENWZTDJDIQCSQIDJTXUXBVGSQCCIJFSEKYVVDWRYIKXWEOUWOPQYYEQKMBYJTNRINSOPWGIELWGVRGZIYQRJRVKNKMHBHUIJJZWDWIAWHTBIQBIFTAHZSQCVNXLMVJXAHUIJFUMVLWCPASVPLNGSVGRDEWQSZELNTWDWRGLWXDEOUSEXZJSSGHCSQSYYIPJHVGSQJXDCSZIFYJEWRHFGGWVXKNZRWKWZKRACHWSSUMQCSYPWHKYDUZLVWXGIFCWOPWNKMV":

>

7) Find the key used to encrypt ciphertext1.

>

8) Encrypt your message3 above with a key of between 5 and 10 letters. Post your message to the bulletin board.

>

9) Break someone else's message from the bulletin board without them telling you the key.

>

You should note that this method of analysis breaks down when the message is not sufficiently long. (All 1 character strings have the same normed size for their frequency vectors.) This method seems to work best if the substrings are at least 50 characters long.

>