CSci 4554 problem set 2. Vigenere cipher: encryption, decryption, and cryptanalysis.

Due Monday, Feb 6 at 11:59pm (by e-mail), except part 1 of problem 2 which is due Tue Jan 31.

Problem 1, individual: modular arithmetic.

Exercises 1.6 p. 25 (6 points) (note: the problem is asking for multiplicative inverses of these numbers), 1.9 p. 26 (10 points), and 1.14 p. 27 (5 points).

(4 points)
How many possible keys for Affine cipher exist for the following alphabets:

• Italian: 21 letters
• Russian: 33 letters

Problem 1, groups of 2. Vigenere cipher 30 points total (plus extra credit)

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.

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

Description

This problem will be done in the lab in groups of 2. You are asked to implement Vigenere cipher encryption and decryption: your functions will take a string and a keyword and return the encrypted or decrypted text accordingly. A couple of helpful hints:

• You are only working with English alphabet, so you can use the ordering of ASCII codes to determine the letter position. For instance in Java: 'b' - 'a' returns 1, which is the position of 'b' in the alphabet.
• It may be helpful to write a preprocessing function for text that removes all symbols other than letters and converts all letters to lowercase. This way you can copy-paste text into your program and don't need to remove punctuation, spaces, etc. Be careful: make sure that no non-letetr charcaters remain after pre-processing.

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, submit them with your solutions.

Part 1 (due Tuesday January 31 at 11:59pm).

1. 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.
2. Write a function to decrypt an encrypted text with a given keyword.
3. Choose a keyword of at most 8 characters and an English text of at least 450 characters. The text must consist of sentences (i.e. it cannot be a list of names, etc.) It has to be in English, i.e. it cannot contain letters of any other alphabet, and English letters must have their English meaning (i.e. it cannot contain formulas). It has to be taken from a source that's either avaialble online, or is published as a book. The keyword must an English word (i.e. must appear in English dictionary). Encrypt the text using the keyword.
4. Decrypt your text using your decryption function to make sure that everything is working correctly. This is a requirement!
5. Save the plaintext and the key and keep all this information secret. Create a file in the google docs folder with your group name and copy your encrypted text there.

Part 2 (due Friday February 6)

1. Try your method on the following text:

   
   	vqglhnkbwhpcvptziwqzglwkhcakirvpxjvpcaivfvjwakhvumgaesgovhvsqzchrupmt
   	kceqbwprxvzxtqvfqcqscnqifeefxjyijvnppxywvwhtgktnmsiuedyrrplvbmcfmsose
   	qcgzlromubpcauxztccktkeefupphvpdxyxlgzjkicaaiyydrmilhrplgpkyvxtyjvebx
   	vrntwcnjlntnkmjizpjiucvszxigvvalsatxttzpohdepfqhhfcglpuhrtbbhhvvwcnyv
   	vqtkfpcciosikbnhruhwascuqkivvckstjsevzdspzpohrmcnickwzoxalxiwbwtmjeia
   	siuuqbwpzeqifeefkpwxzxmvvsucbilrukvvjegvixumcnbxyiuyqioecnbwlwvhzdtxy
   	gatdslnlxiixqvtzemgbwhxkqlxlmcgiklqpnwklecqvtg
       

2. As other encrypted texts appear on google docs, 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.
3. You need to decrypt the given text and 2 texts from other groups to get full credit. Every additional one that you decrypt gives you 2 points extra credit, up to 10 points.
4. Additionally, you get 4 points of extra credit if no one has decrypted your text, provided it was uploaded on time and is correct.

Problem 3: Vigenere cipher with infinite key length (15 points, up to 15 points extra credit).

Work in groups or individually. Make sure to credit all sources for your ideas.

In this problem you will study and attempt to break a Running key cipher. This cipher works as Vigenere cipher, but with a key that equals in length to the plaintext. The subsection on security of the wikipedia page gives some ideas for breaking the cipher.

Your goal is to attempt to break the following text encrypted using the running key cipher. While you might not be able to decrypt the entire text, you may be able to identify likely words or gain other partial information about the encrypted text and/or the key. Your answer for this problem should contain all approaches that you used (with reasons why you think they might work) and any partial guesses about the plaintext and the key, with justification. Here is some important information:

1. Both the plaintext and the key are English texts (with punctuation, spaces, and other symbols removed, and all letters converted to lower case).
2. Both the plaintext and the key are available online. The plaintext is related to the course material, the key comes from a well-known text. Both are located at the beginning of their source texts.

The problem will be graded based on the methods used, their implementation, justification for method choices, and interpretation of the results. Large amount of correctly decrypted text (with the corresponding parts of the key) will give you extra credit. Fully decrypted text (with the sources for both the text and the key) is worth 15 points extra credit. However, don't spend large amounts of time on this problem. Long runs of a program are fine, as long as they are automated and don't affect other users of the lab. Also, you are not allowed to use web crawlers of any sort in your attack or browse anyone's personal files. Browsing internet by hand is ok.

The ciphertext to study/decrypt is as follows:

    varanatmnnrknpgrukpurdsceqrfiuvtpbgrbprvoeaknonbggkvtmczxiukkuoaxz
    lvoipbqrtiavngrquzbaldnytqgqtqqgjymstiwukrghhyglbqistwvgkbzmregnfz
    ubceczelkcprqfppvoiccpkuzxmvulbxdrhayaucglqvgcvbnkkoralrmpresahbuz
    frswngbjnfjaukroacgnlsuxlbxumjbfeqmuzkolpyczcxksfpsetlwzhphzmrjyqr
    wymkeudbaxcnufqgvsvhqrrgpiebvkfayrnjblbxkofuumvghvlhnorkvcefyiymfs
    wijqmdsifgvfsargbuawewpvzfszaatttmlhtmwtieqnqlpjswkraafrffcekzbgzv
    peihvlsjrcacjmsksirvghbwxzdugsplqvryesephyprwbwdxkrzsefhrzeltebeaf
    bgiaackiwuwuaheabmzbrymiqqiyansghgbismiechpnaefqegumgwtleazhkiyxwg
    vroqfovzufrowbuorxxpjasxpnnvzxdrjbapetlaaohyejlntowqkmcbohalrpbovj
    biotkppobrrdmieiqylembvsjzbvxrjfignfirrffbusehafagtpvyfeotaiidvgoe
    seiflremcxbvlhhcmxmpopzexghxzxzwnhicxlgtsmpqtdhoubwrvrfmrpoynyvzxm
    ekirwfnvdbqiyelavmuhbxxrzakgxbjroutymaxjeraaimhgvjwrvocbqoqqorltrv
    pgosjfdffvheaavncydxfgftxzxuihfrbofuduintlevgwrgrejsmwureroepjpaie
    cexosvnswgmltbaylmqwholrqftterxqfohdqiavrfbreusezazvqgkbwegpvvmcea
    bumetlwjvtkbsrfepakbuphxpfxyrpmibfbhzvfvbzpgtsgrpjqrjguznnphdpkzgv
    vattgugzikscedngldibrkfxbbwrztfbgungirkhylnqwprsdfgpvslztjsbjmadmu
    meeiewtmqhjxbqsjmsjbhdxmbkalryayeakhjbyotavximkfbsjschxuxyutspqbnx
    fyomyroyvzigalwjsjcmpbadekcksquornzkzsrbwpyxjzznhjlripnlalrrymvrip
    jachvqvweyqhugnhfwgfhslmkfjdzpfkaaysmaswvmasnbmxebnstujmsgnwiirphx
    kmrngulrwaflgqfrkhrqbnvkpfmcalvozcethtujexmocyjdmfxryhfvhyevbbjrty
    tgtupxdntptnwlghujaazhtnjbtprawbfwhmbukqtwybyrubalchsifqvudhtxirva
    uyutokrurbffavnqnhsauetgsazrwkwyrturufcantpdcitztglpxcgccwmiquehmt
    xtubhmurbugdlbjyrjarflhzptzvvosfwlzrdigjdvipvsvjbifrvjkxspgahqiens
    baykndwsivvyjfswuelukcefjbnglanlfezoskrtlhroaauyepyayevvhgjgyghmxu
    whvixbnxklrhhtpdraxdhqgkxymprldsggulvbbbjltiytveryvhxnesrwtwzpxnbl
    kebielrttzsiolzcyylfnueyroiuxknafbnawyiuxukuknarrjtpvsxompfmmprieg
    igcqttkqndxfmsxcdubrvoogpbfsvvtuycekvxbnarwheatsnfpmlomrffnqjkqduj
    mzmwvnzgprrfietklvvlqrwluawfjbfgqgtixicknrepkdwlbspcmckbacgpebirbd
    kdaxluueumuauwxwmatsplvrkfavfbcjkilrfxvvymsgimhbseakbyomaoiirujpwc
    dfoivfnxdszoypbvnesctwrzghanhcrkbobeyzrefhixzxuisbmcfpseuwhgwbtxze
    fdfnlhlfnthhbvfbydwlwldvgahalnxsekrfjfhbvpaa

What to submit (by e-mail to me, CC your partner)

1. The "paper and pencil part", either in class or by email.
2. All your program code (well-documented) and instructions for running it.
3. Your own text (the original) and your key.
4. All the decryptions that you have accomplished (decrypted texts and the keys) with brief explanations of what you tried, why, and what worked.

CSci 4554 course web site.