Exercises 1.6 p. 25 (6 points), 1.9 p. 26 (10 points), and 1.14 p. 27 (5 points).
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.
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.
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:
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