CSci 4554 Lab 2. Vigenere cipher: encryption, decryption, and cryptanalysis.
Due Friday, March 5th at 11:59pm (by e-mail)
30 points total (plus extra credit, see below)
Description
This lab is done in groups of 2. Each group chooses a secret key (a word or
a phrase no longer than 8 characters) for
a Vigenere cipher and encrypts an English text of their choice using this key.
Then they post their encrypted text (and their group) on the wiki: http://wiki.umn.edu/view/UMMCSci4554Spring10/VigenereCipherLab.
After some encrypted texts are posted, each group attempts to break
encryptions posted by other groups.
Background
Vigenere cipher is a polyalphabetic cipher. Its key is a word that
is added (modulo 26) to each letter of the ciphertext. The keyword is repeated
as many times as needed to match the length of the plaintext.
Here is a more detailed description:
http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher; see also Ch. 7.3 of the textbook.
Breaking
Vigenere encryption is a harder task than breaking an affine
cipher. Kasiski approach provides the basic idea: frequent letter
combinations have a high probability of being encrypted by the same
portion of the key words. Observing repeated patterns, one may guess the
length of the keyword and even some of its letters.
If the keyword length is known, frequency analysis may be applied to
characters encrypted by the same letter of the keyword:
http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#Frequency_analysis.
Another potentially useful method is Key Elimination
Note that breaking a Vigenere cipher requires a careful
examination of the encrypted text and good guessing. You may have to
try multiple methods and combine them to break encryption. Keep
a log of methods you tried and of ideas that you think are promising.
Tasks for the lab:
- Work in pairs or groups of three.
- Write a program that encrypts an English text using a Vigenere cipher
given a keyword.
The program should ignore all punctuations and spaces and
output the result in upper case letters regardless of the initial
case. The programming language doesn't matter, as
long as you submit well-documented source code and instructions for
how to compile (if needed) and run it.
- Write a function to decrypt an encrypted text with a given keyword.
- Choose a keyword of at most 8 characters and an English text of at
least 1000
characters. The keyword doesn't have to be a dictionary word, but it
must have a meaning (could be a short phrase, for instance).
Encrypt the text using the keyword.
- Decrypt your text using your decryption function to make sure that
everything is working correctly. This is a requirement!
- Save the plaintext and the
key and keep all this information secret (you might want to reset
file permissions accordingly). Post the encrypted text on the wiki: http://wiki.umn.edu/view/UMMCSci4554Spring10/VigenereCipherLab
(mark it with your names).
- As other encrypted texts appear on the wiki, pick one and work on
its decryption. Your goal is to find the keyword and the text. You may use
any cryptographic methods you want. Please keep a log of your ideas and
discoveries (for instance, if you think you have guessed the length of
the key, write your reasoning in your log).
Once you decrypted someone's text, you must post on the wiki
that your group has broken it, but don't post any additional
information.
- You need to decrypt 2 different texts to get full credit. Every
additional one that you decrypt gives you 5 points extra credit, up to
10 extra points.
- Additionally, you get 3 points of extra credit if no-one has
decrypted your text.
What to submit (by e-mail to me, CC your partner)
- All your program code (well-documented) and instructions for
running it.
- Your own text (the original) and your keyword.
- All the decryptions that you have accomplished (decrypted texts
and the keywords).
- A summary of how you have broken encryptions. List all
the methods that you tried and what you have obtained. If you make some
progress on someone's encryption, but haven't completely broken it,
add that to your summary as well, with details.
- If you have written any additional helper functions or programs,
please submit those as well.
CSci 4554 course web site.