## 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.
After you implement and test basic encryption, 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. The text that you encrypt must be at least 450 characters long. Then they post their encrypted text (and their group) into a google doc folder that will be sent to you by email.
After some encrypted texts are posted, each group attempts to break encryptions posted by other groups. As a minimum, you need to break three encryptions. Each additional one gives you 2 points of extra credit.

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).

Note: 4 points will be taken off for every day late on this part
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
meeiewtmqhjxbqsjmsjbhdxmbkalryayeakhjbyotavximkfbsjschxuxyutspqbnx
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.