You are to write a program called vigenereic.py that takes as input a Vigenre ciphertext, uses the code you wrote in assignment 1 for finding the key length, and then implements the algorithm given below to find the key. Its only output should be the key length and the key itself.

To make this a little easier, here is the A₀ vector referred to in the algorithm in Python format. These contain the frequencies of letters in English:

EnglishFrequencies = [0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.020, 0.061, 0.070, 0.002, 0.008, 0.040, 0.024, 0.067, 0.075, 0.019, 0.001, 0.060, 0.063, 0.091, 0.028, 0.010, 0.023, 0.001, 0.020, 0.001]

From these you can form the the A₁, ..., A₂₅ vectors.

You will have to determine a way to translate character ASCII codes to and from the range 0 to 25.

Try out your program on the Vigenre ciphertext from assignment 1. For input, you can either read it in using the fixed filename a3vigenere.txt or hardcode it into the program.

Code from Assignment 1 to find the key length:

def getKeyLength(ciphertext):

max_shift = -1

max_coinc = -1

for shift in range(1,15):

coinc_count = 0

for i in range(len(ciphertext)):

shifted_index = (i + shift) % len(ciphertext)

if ciphertext[i] == ciphertext[shifted_index]:

coinc_count += 1

print("Shift: {0}, Coincidences: {1}".format(shift, coinc_count))

if coinc_count > max_coinc:

max_shift = shift;

max_coinc = coinc_count

return (max_shift, max_coinc)

v_shift, v_coinc_count = getKeyLength(ciphertext)

print("v_shift: {0}, v_coinc_count: {1}".format(v_shift, v_coinc_count))

ALGORITHM

To summarize, here is the method for finding the key. Assume we already have determined that the key length is n.

For i = 1 to n, do the following:

1. Compute the frequencies of the letters in positions i mod n, and form the vector W.

2. For j = 0 to 25, computeW Aj .

3. Let ki = j0 give the maximum value of W Aj .

The key is probably {k1, ..., kn}.