CSci 4554 problem set 2. Affine ciphers: encryption, decryption, and cryptanalysis.

Due Monday, Sept 16 at 11:59pm (by e-mail), except part 1 of problem 2 which is due Wedn. Sept 11.

Problem 1, individual: modular arithmetic.

Exercises 1.6 p. 25 (6 points), 1.9 p. 26 (10 points), and 1.14 p. 27 (5 points).

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

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: https://wiki.umn.edu/UMMCSci4554Wiki/ProblemSetOneMaterials. 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.

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.

Part 1 (due Wedn Sept 11).

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 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.
  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 (you might want to reset file permissions accordingly). Post the encrypted text on the wiki: https://wiki.umn.edu/UMMCSci4554Wiki/ProblemSetOneMaterials (mark it with your names).

Part 2 (due Monday Sept 16)

  1. 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.
  2. You need to decrypt 2 different texts to get full credit. Every additional one that you decrypt gives you 4 points extra credit, up to 8 extra points.
  3. Additionally, you get 4 points of extra credit if no one has decrypted your text.

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 punctaution, spaces, and other symbols removed, and all letters converted to upper case).
  2. Both the plaintext and the key are avaialable online.
  3. The plaintext is related to the material of this course. The key is vaguely related to the material of the course :-)

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 (I will use my discretion on this one). 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:

OQFMCIDTEZUNSPPBKFPCLPWCOCXQWQLDWFMSTGFMOGTIELAUIGTNYGJARRLUHVVZIWYBUKUONSSOXZEX
CMRXHPNPMABEDBBNHPWMOMYEGOQVEPNRAFAEVARRUHARVLZMNTRNSJBIAOWHOWPNOXBIEGORUEHFOGGD
VEWZKBRUEZZWNINXJBGUUDHVILCYEEKEDEMPIRHNWZQGJXWLDISBSSRVUXHVPGTFOWQFVJHRLGZCMWXR
VUKNMFSCJZIOLTVAYGRRSZTLDRMKAAPWIYENZGABDORQHFZKTXSVWXKSECHMWSVWPXIIWNSDFLXXYHEK
XMWEZZATQFAEIQOGARZWSRVYZTMENTCECVSNQFXFYMLAALXDDNGMCRWTZINVHEWZHFLOKWGHUEODBVWZ
GFPPVMIXWIUISEZLOEZCLMTOOLEIHRLYWPMICNUGGAAFPWBHGBTWMHBVOCFMFIEGVVZWHEXVGHQTLZPF
AUMNREMMVXAHNPBALAVZGRHGIQMQARAYLRWYZAIHSCKMXMIQOSVPAYJACATKSETAEOCFYCKIATZBFLOA
ONIOELDXAQSINGGQHCJAFKFOSFALWOASOMKFHVHQGPGWKEITGPPOPHBHTWTAHBUXTMSTTVDSNUJIFACN
SISEHLPYPYUJCNVDIYGLJLBFNGIKYAMDRCGSMHJWKHGWFRIVVVMIVEYBEMIYJPEOXLIFKEKWHYUDKMEI
KWOCHLFHHRSGIFHZMMKCGXYKLTTGQVKMWVSWUIZPPWVRIKUMQQNQMFRGRRVVWMGBGDCWKAETBOIDXSNQ
NTRNGHQFVYILMARENWKXMFDFHLEDGDHXKMVZWZPLYWLVWPXWNFWMVXAOMOVDSZRDEVXSILMHNOOEMZYM
GLWSAWNGRVFFASDLAAWRVQRLIAGKLWTMYTNVLCKFMTWWWAOFLVRISEWCXXDXWCWXSIOTXWFBTAEPRHSF
NPHRWPRWLXPZZTHLUULMWFNDSGFCZQJGHVLSCOFPXOMWAESJTISQVSYALRAEHNPMSLFIVWMCKNINTFGP
XWBIUEBWVHBZOEGVSXBHTHZTRPDAMPJKHUEGHQXIVXMVMVJXLMRDXASFDTCUIXWUGEGYHONRNVOXYWEA
FWAZUJLTMRDQAMLVMFIBLGLTOXVVSCGMTWITRABIZCOZJGFSYXAWJMTTWZLESIEGKHRXXRLMSWVJKCSP
HEEUBQFGPXHSYVPLQHGZXMIFHUJWXKYSXETAVQSPRNRERHAXKBOSFIMERMQKLDIHIIFMSWFIMKIRPLDU
OVTSKLVSBBIRILFENFTICQNHNVRTPNIPNMWMGHSIUBTBUCAIEGWVHLFUMFXNVUINODEGXSEJKWTVVEHK
HGVWKNQEMHIPRXIFSFWPJZVSWPRGFPPUGBIAEJIVPWPSZZIYIFNEAWSPUMINNPBHFWXYWRQNUMTEBAVN
AWOVCNIXFHMTRCGAFHMQMNHEKVTSUIKZXHPMKGUIELSNUFIJYZQPWJZQRMTMSSMVOBEIFWZSEVKPVMSR
NPUWYHVHIPSFZIKLCETRWIEVZKAYMPSCMAUVYCQECCKHTIPXCWJKPHSWETPMLQUMTLPOXIBGVATRPMEU
JTISTUUBRGVZFOJARQDWVFCNFZLKXBZEOIOGNYGPJXKKOWMWAFMTKCFWICMTAPYETQSVMZTRLEUEAKMH
UQJHZAFYRDZTAOLZHJEAXIGEUXMMIYVPOIOIGSLIRKAHYDEFQNFAIALMRYWWKAKBIOMJANBNIQYEHCAH
LTRIETLWAICZTRBELWULLTSJICJWXLWQFKTVSVBRFDYBJBVZOIACZGABHPCHRCRYJQQCMFRTVXUPRNBA
DMXDZIWNWNBRUOTJETQGBDAECWMLIPFGGCACVSKZYJACRSGRRDFJMRVRUMVAGCZTEIURTDRWAAVBUGVO
WOIIWIMLBWWMEUOLLHZTSMTAHEXUHZFXYPHDRXATTSPVBHRKVQUAHNTJWWGPFIKEXHYSEHHXZYONNTUH
AUMWZGXTJQOLBFBCDLKJWPMDPHLWKGSWSGRGTUJFMTYGVABDVGTMITBWVQVGMHMEGXVSEOYHYWDPIWRO
HSRGVNMIXMIIMHGIEZARRASRTRLIJVFGTRZNTFHFOFQKYXUKEWPNZKODZWUQBKVHOYMEEQBXEMPFVQPE
FSFIWVVFWHAMXAXGKGYIIFGAIJTCLJOJVAXMDEKBWEITQQULPZBAGHYCCRQHMIFABLAZNDMLSFSXEGKS
GRPIUIYTUERIFBNEDJXTRPVYJVMIDYHGMJIGKEZQPOMYOHLTLSTTICLTWUAVVREETCNXIZLMGJOTDEWU
LLESMWWSAYSUGSLWBEYZPDDLCVLSFRPKYJYJWDFIIFIBGKMWTECUHWPWGTIKIEIKNFBAYIPYKXIWUISY
WDMALVEKVBDBISJADOHWZSMIBPSNOEVGMCATVJKZGWEXZSDHDSWDPTVRLIBQHMFCWPQKIHRIUYNOAVXE
UBEEDWQTUEEQCSCCMXDMTCHOAMFIDDCBMTTKYGGQBMXWQQGCFKMKBWWNSQDVGKSJKEWIKWVUMHMTUBPW
TCXHRJFSVAHNVMPARVVIQEUOEOUSXYZQDMPGMHBSQPYLQBQHQWTPWZEPCDMACELDMQUEFXKCZXEYMAZQ
FAUPOSTAOMDEPOGQYJVBIHJMHFRBSZVKMPCQECDKHCFOUTWNWGMAVDSZFXWQLDHHWRJFJSGSRRDBZTRG
KUUDTFKCNVPSULCUSQPDIPGJRHHAKKECVPWQIQMMEURBQGSXLZYLTBSUXBUEEPJZIXQWSFYPRXBRQEBW
AIPMVBIYRCMXRFFYHYLVDPLHMOVQYTNKWHZDLIAJIYEVVPSMMQNIAGSYWAYSVVJOXVQZJHPMXSGWLIBP
CDIYFOZQPYEHCYTESKLETGGARXTKMEKKZRXIGZQYFVTKMBHHVFWLXUGRTQXJDIHIPUGAGDPBSECVZKOI
WEZJMDNBRTAIOUAYEGLQWXXGULVPVVVYUSRBDRMZAXEUFWQTSBLLPLCSEEMVGQBUHRRGTLHAFFTJOYZA
JYHFSOCZLFSIZNIUBZGTVBQPHNEDWKLAQMWPFWMJERXTROKXJYDWMGJJLVYMMWLGLDQSFKZCJLTVNRXE
HCIIDVXNWHEEKMMTEIEYYGRAPOFSIEQZRLGYVPJTAMPUICFACFDWCXXEJRVJUMAUESMLTBMXHAGKHPWL
IZLJENBNRGVBGVGPQMZLIKHMXXKWTASEKMUASZHAHYMJVYEMMXOEHRDXZANELLLFETXXFWUVIKFZHVCE
MHEZZQZJYXOFOMIAWIIJZCBWBAKUIEZSJZATJXXVHFFVIDUZAEOMTYHRSXUTWIAVVLGRRQCWBAQUEBRD
VEAFNYHLBOAGQTOUEEOMKATAYGEJKIDETVTFZVRNJYKPGAGLHXDKVFOYXDRXJHJTPWMYEMSEWPFIENXU
MKBEOZCQTTOOYILAVMLTLTGEPVGVAFIEKKRXRRDVZQNIEWWVXHSTLMZUEKYJXGQRNERVGHEBSCUZQZPT
HPSDESUKVFEJQIAWYIRQMPQCUKADHWARENZZVFXVEGNRGVOTIWOLFDGEWELMBDSESEFOLBRVOTWWLTZM
WIYSKUDUXNKMKKXYHYMVSMSRZZAOWYEVIPNGCMAOSMLRZLWYNTYZCZMPRRKFLAKGXIANIHRBITASAMDR
GDHHMGMNDVRXXVGWZWSOXANBUKSTAJIHVOGQIUAAPRBPAJAZZHBGKJCQRCRGZZVNHAOFDIOLRFWOPRQG
IAAULNTKHRUTCGYTIGGTHSWXXGQMIYVFCKXGZXQILMSQZSMKIYANREWGZMTDMNMIAMHMXUXAYIFUSEYV
RPWDPIXKPHBYQOULQIYINMINNQMSETXYDVFONNBZHIKKEGUHASUVLJTNPCGXCSBJGBWSCMHDDRYLEAWV
ILWHPAQESYKFXUCJXWDHHYCVZSOELUUAXEUAWUQTYECIVMVWABQVHWMLLIKWFVPDDTGRRWTAOXYTGOWP
QQFXTAKSRWPKRBMPCAUJRWEYVIQTGLPHASCFUAKJQXVEDGTKJFJKWLBQHDMGVXSIFBUEDYITTVZVHSYK
WRDCOMEEFFJFGTSEQHGIVIHVGQEPHKFXVVRQMMEEHTMPCULMGKPQLNYHJPOISIJOXEKHMOPVOVFXYMZU
TZLLICORIPTCTFHNFRWTWGWAMRFQDCADPSPIWKQHVLQVWLKPQCEITPXQKHNVBDVRBHTYCKYOLCVWPENL
GLHWIVMLAUWXUXGVMKEYHVXUOGLTIFFBFPNTKFTMPMUHHMHECUDSYMGADHKNCECSITTXFBVVHLJVVXKV
HTYGAEKMGUWUHGHWVGEVVKSAMOKMGBDKVCVCHAMFMVUWSEKIRKCHMGCEOSWSKEKIXPHRGKFRPHSEHWUR
YGGPMNUAVLEARPRXHPCRXSWHNNIJIELGEUCUMVPXYPVVHSZIYHHWMYIRLZIOHVPXDSRURWIMZXNJLIJW
ETCTDELADMWYYFJEPOTALYLFLHWCXKQGFPAEAMEOSULPACDGXPNTTVZHUFSNKWCMVHSFYYOABVGRIODM
FLHBRZRMKZBACSFEGPBYJHXS

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 K1, K2.
  4. All the decryptions that you have accomplished (decrypted texts and K1, K2) with brief explanations of what you tried, why, and what worked.

CSci 4554 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.