Math595/609: Project 1
Vigenere Ciper
Keyword k[0] k[1] ... k[r-1]
Plantext: p[0] p[1] ...
Ciphertext: c[0] c[1] ...
Encrypt: E(p[i]) = c[i]
where let j = i mod r, N be the alphabet size and:
E(a) = a + k[j] mod N
Project Description
Write a suite of programs to break Vigenere ciphers.
Following is a series of hints as to how to proceed.
- Write a program to produce plaintext. The program
should input "found" text and map it to our alphabet,
which is only the letters a through z. It is reasonable
to do this by lowercasing any letter A-Z and dropping
all other characters.
- (Optional) Write program to generate plaintext according
to a given frequency distribution. This might be useful
for testing. I would suggest that the input be letter-frequency
pairs, so that the program be useful in the most general context.
- Write a program to do Vigenere encipherment
- Write a program to crack a Vigenere cipher:
- Determine the key length. Given a guess about the proper
index of coincidence, you could find the first index which
approximates this number. There are certainly more robust
ways of doing this.
- Determine the shift amount for each column. Use the dot-product
approach given in the text.
- Output the keyword and the decrypted text.
- Additional notes: We mentioned in class another method
to determine the key-length.
- Collect pairs (offset, num_of_coincidences).
- Sort by num_of_coincidences descending.
- Look at the gcd of the first two offsets, then the first three,
etc., in the above sorted order.
- The key-length should be among these gcd's.
One idea is to count of the number a gcd appears and then
rank key-length candidates by this count.
Program fragments