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:

  1. Work in pairs or groups of three.
  2. 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.
  3. Write a function to decrypt an encrypted text with a given keyword.
  4. 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.
  5. Decrypt your text using your decryption function to make sure that everything is working correctly. This is a requirement!
  6. 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).
  7. 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.
  8. 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.
  9. 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)

  1. All your program code (well-documented) and instructions for running it.
  2. Your own text (the original) and your keyword.
  3. All the decryptions that you have accomplished (decrypted texts and the keywords).
  4. 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.
  5. If you have written any additional helper functions or programs, please submit those as well.

CSci 4554 course web site.