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.
Your functions will take a string and a keyword and return the encrypted or decrypted text accordingly. A couple of helpful hints (instructions):
-
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.
-
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.
GMEAZPIECBKEPVRFIRSTGKNNQXRZUAFXUQYOPSXLURTRBBIYBMZBUOFEAIIPPYABUSGEPBYNOHRDKAUWOCZBGTRZYBOEYMDCFVVMTPFWRFVRSMRVIRTAUQIUNMYTOBOWBNVEJWBVKETLNDKFVJSMXREXVUKNOHNOGVOMGQYGIIVVYVEIFBUEZSSIIBOGRVZEBXVWTPBQCBUYEFLWTRPJVBYFVVIQBBSWGPOFUEYMOFOSGKUADIEVKQXMGPZUFKEMGGISEZUETAUQIUIEIMGYSINLEOFIALKFDVVJKQPJGMTROSHONGISHONYFWFWLGFROMRVFZRLHHUAVBNGIIZCRGJXHLKBGWZIRYUSEUKAUWVVUGIIEEUEEWVBOYMXEGZBBRFEKEULVAWHFWGQUAISJEGFFZRZEQBCYQLRJRNKUADIABXNUMBVINNTEMLYFGGMJVOXUMSVOHBNZUFEIMXNHICZOFPRRZSBTXBNZUFIIMTGTHRAIEJFRLNRSIQQJAPXGIQRQPNKKVOXUMRNSKRITQGEZWAFDEZXYOVXVVZUFWZIRYPRRACUFVRUUFUSSBNRSINTKKUIEUOABXVWTGPSXXRNDIGPOFTXBZEVTRBBGOPYGBNRTYSNKEJRTITQEINBNBGKEMGGIIEWKFBRQUGEUCEATBSMFQZNCSHBZUFTEWSVOIABINQSFXXVTSAMXFXLBIIGFHNAZEVWGMKFIEIQTTTTRKONMTEQBVMITMYBSARTRXOSJVVEJWBVKETXUCYVUMFVUGTSZCIUDSAKKEOIQEOGIXUMYHGJRZOAHWBNZUFQVONGZFHBCVULGPKFBGEQLVDIFBNRDVHKOSJBVWTNOHGPKQFEGPYBGXUMMEFEGIXZZSSCTXOSJVGAEYAZKPPVQMJIJGGQSFJXJIYGIIFMIBNQBVVEJWBVKETAUWHBSIAWJVTXVVMHJWUQTTNEESYBOXUMOETPRMBRTAUWSGIIPIVBTVRIRYZHRAVVTIQENVMIGPKFFSELOABVLKN
FIRSTCHAPTEROREXCERPTCHAPTERONETHISBOOKDOESNOTCLAIMTOBEANACCOUNTOFFACTSANDEVENTSBUTOFPERSONALEXPERIENCESEXPERIENCESWHICHMILLIONSOFPRISONERSHAVESUFFEREDTIMEANDAGAINITISTHEINSIDESTORYOFACONCENTRATIONCAMPTOLDBYONEOFITSSURVIVORSTHISTALEISNOTCONCERNEDWITHTHEGREATHORRORSWHICHHAVEALREADYBEENDESCRIBEDOFTENENOUGHTHOUGHLESSOFTENBELIEVEDBUTWITHTHEMULTITUDEOFSMALLTORMENTSINOTHERWORDSITILLTRYTOANSWERTHISQUESTIONHOWWASEVERYDAYLIFEINACONCENTRATIONCAMPREFLECTEDINTHEMINDOFTHEAVERAGEPRISONERMOSTOFTHEEVENTSDESCRIBEDHEREDIDNOTTAKEPLACEINTHELARGEANDFAMOUSCAMPSBUTINTHESMALLONESWHEREMOSTOFTHEREALEXTERMINATIONTOOKPLACETHISSTORYISNOTABOUTTHESUFFERINGANDDEATHOFGREATHEROESANDMARTYRSNORISITABOUTTHEPROMINENTCAPOSPRISONERSWHOACTEDASTRUSTEESHAVINGSPECIALPRIVILEGESORWELLKNOWNPRISONERSTHUSITISNOTSOMUCHCONCERNEDWITHTHESUFFERINGSOFTHEMIGHTYBUTWITHTHESACRIFICESTHECRUCIFIXIONANDTHEDEATHSOFTHEGREATARMYOFUNKNOWNANDUNRECORDEDVICTIMSITWASTHESECOMMONPRISONERSWHOBORENODISTINGUISHINGMARKSONTHEIRSLEEVESWHOMTHECAPOSREALLYDESPISEDWHILETHESEORDINARYCH
We use the kasisky test. First step is to guess the key length. We do this by finding a repeated 3-letter sequence then calculating the distance between each. In this case, XUM occurred 5 times and TAU occurred 4 times, so we looked at the distances between each of those: 72, 270, 72, and a few more similar ones. These must be divisible by the key length, so starting backwards from 8, the possible key lengths are 6, 2, and 1. 6 is our first guess. Since XUM is the most commonly repeated 3-letter sequence, and “the” is the most 3-letter word, we use this to guess three letters from the 6-letter key. X=23 - T=19 = E=4, so we know E is in the key. Using this formula, “ENI” is part of the 6-letter key. We look up possible 6-letter words in the dictionary containing “ENI” in that order and try them as the key. Using our code, “BENIGN” was the best matching key.
qjapkofclpgauficevhvujgebkgtdjhzctdssphzrvgnrbvvoccgueecjvolblkezgljejhmfyftspacmrknxwfhoiasvifbkaskseuiecjfeihgutlrqvhvvafdvbsupvqluowhzgspglgmjqjapkofclpgauijikgdkctterqzerpdlqgiohjitgweuiwlaspglgmjoffgrwfcctskutfhzgcfblgnkggheeqjapksvoejgsiejsngnztljetfqrtfujcpywumepwkwnbbgynzbsfdzhaqnkcectysectzqsnaeodaszgghcimhvoxfsrhzqsngffavhdgutyghspacmkkszbunuuskvhvglwdpcxuiusujaebwnakhsekjhzctucfqtkojiekkwckeskuejwfvhvqjapkcytagvaeacugtikveutyseuecjwublhapskssfeoddqikkwckeskuejwfvhvwjkmgzwoeehsvifb
cryptanalysisfromthegreekwordsthatmeanhiddenandtoloosenortountieisthestudyofanalyzinginformationsystemsinordertostudythehiddenaspectsofthesystemscryptanalysisisusedtobreachcryptographicsecuritysystemsandgainaccesstothecontentsofencryptedmessagesevenifthecryptographickeyisunknowninadditiontomathematicalanalysisofcryptographicalgorithmscryptanalysisincludesthestudyofsidechannelattacksthatdonottargetweaknessesinthecryptographicalgorithmsthemselvesbutinsteadexploitweaknessesintheirimplementation
We use the kasisky test. First step is to guess the key length. We do this by finding a repeated 3-letter sequence then calculating the distance between each. In this case, VHV occurred 2 times and QJA occurred 2 times, so we looked at the distances between each of those: 100, 240, 145, and a few more similar ones. These must be divisible by the key length, so starting backwards from 8, the possible key lengths are 5 and 1. 5 is our first guess. USING VHV and QJA to get “the”, we use “VH” from VHV and “A” from QJA to spell “the”, which gives us “car”. Now we need two more letters for the key. As we remember our buddy Oscar, we use his name as the key and it works.
mlpvtkzeeewapmjuxvpehcelmseibdvkhycsehzfbwxegclgweyccsnmxgsrdzfzbglpprmtggpwiwcebexmcqixwmmpnsovbxphppfnmxsieckxgxteadflbxtztclmvsxihcwjneyxjathftfxxbxyksxjxbubgkyilqlkxwesswjxtwpwicyxettrvrzlvsgigbvpiecxxqcxlmelxbbmamdmhhyxfsdxtltbmiomwomxuiprxbdrxremgsttkipvlsjahywhqswhvydmcufnkiyiguptlqfgwcemaiashwkboizyiqffxwlwlstnkvprizptkieltbvztxtztcexlwzgpzcxwufechlfvsxqjbzvtxtscgzlhrpsuhyxfscixbkxkidxxbxtitwmrokbhrdtaoegxhqsghyxyyeygsfyjylriidvhqayiwezkidipftaxvdmcqybgelrssclxasigszgmlpadfcwaegiqsxngiitacibgkeltdfmxrempzfyuytpswezjylriidgxxhsgyjnlmykivvltqptgwevbtwihpvabroujoemnqnsbdlmbrrxwstkxeemdbfymlpwtbvmpscohkfnehpztbkntpwcddvgmlphdciyhvlujoemnqtrisigxxlqdfvlxgfvtqfffyymrokbhrdchhvfbrhlxqybgjzvbokbhrtwhhfkxhlrshitgwxmihvwpmelprmtggphrfpimsrvpdyrlynlpbvmpscowcnxoicgdicwgxmiiflervpeawqxwyyxxzhntreybqffiyeiggsxvsxihqretfwilvzvajfxjfzlfvpessilmltrzkzeellteseuxjzvthnhsicsuwmxsicslocftvemhouwbrrvdpfmlxzmignhkoqsgqvtlmegdbkbgypwicjabjemchftlxzvttihgxqsghyxfsoigbnhkpoxwsixmetptfytlfpichvlmmykivvkhfzxhwetgyxftffylxzvtgzgtvvecgrliiyrhmcotrtepbuvtptjdfebtasigskaxccijgvwyscvtdvtmemptdixwmnxppcxtroqpbltexlwzgkaxdpvdgzqhrpqthvkmazjihreevzfdhjtkipujwgixhhmivrmhapvpbutlicmtgfyvexigojtgheltmdhoiftpbuwhayexgcxlwnecbzgzwsiajvlyscsjhfylxzgzwkxfwthtbkbyctrvwevhvcirhgkbgpwpbumtotrvbfmxsqagcezhvxmhgzgzplftzjwtxlmhhyxgtlwhsuhgxzibdchripwlvfiksnitrkhlxzgzwkxfwlrsqfkkinxbwjmtopwxbzmbewxtgklhjeltffuhxdlpjvuxiywjqtxlwqyasehnksjdfnteqlvihfxqtlrshyxbvcsqckyeipxicrghxsigtzoxdpvdgkhkiderffllxsirclgmvjfjgzgxwdmcgzwxvciecimlxsmhsoitrdmdbnbepmircdieieisppmaiprscwctrfegmkphdpvdcexxmrlikybeicihsrkvlpvhvroxqlrpuvwmsnvtokxjylriidvhqayisilmlpcpfvtepmyayptghzramnhkotrhdvvbewmosuxgztvdbdxgxdxwsixysciivvynxfvtcwjneyxjathftfxxbxftctrrzlwxxsiprfimmzrdtremicrphzoxwesivvlrweibgtnkvprizpuxmykrfvtmiomcqlmmmyktrxxeemsgokhkmpwivvitxsjdfntkhxenpvmavzyvvkaxgciphzhgsqwestbtptdtrthftfxtftabtdgpdrueizjuievmmzrxbxebopujoemnqnsbdlmxvdfjhjtgweltgktmizjivvtkxnsbdfgxrewivflxwjwisdlkibyxfvmaibypbknfgzqeikbgkcikccnmmzrrclewewwdkveefpkxbnbmleltomxkeriesilhrlgrsjlbrrefirgmyxgdagnmicxwffnzllgaclwliczxqvlngsehhyhlitfboewzszkasytoinvtokxwmelxbbrhycivczgzxzwtsxxgiceaomtbplfxzzmrsqwxaletxzvhoewxqfpphfklxseioixnwpjjzzgmlprtlkmpsqsjfdhgxswhozwaycptmjmbpwxwcjxlcdxtajphywhyijmuiltaotxaswhtfwhkxsigsrewilplvzvalpwtsjtkvtzxbxbgxsiccklhhtwioemyyeygszphywhacmxmsditolgbzpvhocjneyxjathftfxtfrotmweqzvtlilvawvktwelgsvmhjtztmvtkwzyioewbfppxsmxmllxrclewfptdgjbupp
THEREWILLALWAYSBEREASONSTOTEMPEROUROPTIMISMAROUNDANYNEWTECHNOLOGICALADVANCESTILLIAMINCREDIBLYEXCITEDABOUTTHEPOTENTIALPOSITIVEOUTCOMESOFQUANTUMCOMPUTINGFROMFINDINGNEWCURESTODISEASESTOHELPINGDISCOVERNEWPARTICLESITHINKTHISISTHEMOSTEXCITEDIHAVEBEENINMYENTIRECAREERWESHOULDBEFOCUSINGOURENERGYASMUCHONTHEPOSITIVEOUTCOMESASWECURRENTLYARETHENEGATIVEONESSOCALLEDQUANTUMCOMMUNICATIONSISONEOFTHEMOREINTERESTINGAPPLICATIONSPLANNEDFORTHEFUTUREOFQUANTUMCOMPUTINGRESEARCHERSINCHINAANDELSEWHEREINTHEWORLDHAVEBEGUNEXP
We use the full kasisky test. First step is to guess the key length. We do this by finding a repeated 3-letter sequence then calculating the distance between each occurrence. ELT occurs 6 times, and the distances are: 176, 528, 680, and 200. Common divisors are: 8, 4, 2, and 1. We will guess that the key is 8 letters. Next we run frequency analysis tests on every ith letter in the encryption, where n=8. Here is how many times each most frequent letter occurs: x-33, i-39, p-43, i-40, t-41, s-34, v-35, x-41. If we assume that “e” is the most commonly used letter in English, and “e” is at position 4 in the alphabet and the first most frequent letter “x” is at position 23, 23-4=19 which is the letter “t”. Using this analysis for each of the 8 letters in the key, it converts to “teleport”.
caeehiohknmzhrkatcfhvmcqojsgkiiounhfzmkzgjcahakwidrbosxqzdeghqvjmawvqxyayabguefjjernumcqlavglpvwxwmslxcgugwylovoknizdozfmplvqkjmvwwjhkfsrkrtwlvjkwwbqmjlnwxjheiwzkinflgdgpjbuqrkzdildvvfusgnopvvojxuhxisjaardvvlgepbumeyzdinwprfzegjrvblnwxpdrwazexohwklxumajxfzkhtlrydsqawrqwvglplrzsidjpsxhigquqmaisiekzeagielknxnlrvvzdvbxkyonwxryiiekzmhpcfmlerqpsjlikrthrzsrbseryihxergpexsferrdruganieheuwxahvwmffysinuitgtpmaxmeyzkhryskwskrgkwfxxatbuxzfmwrqzvzlojkgrgiwgpiclitwyhmxhnfknqetuivfylvbimcwojxulwzkyqibixiwgoyebwvuxaxnuckaskxubkvazdrrueevxkfruxucglpnqwrkyawfpielubxuharjojesjlrfooxnqjfjzdijhfjazainflusesicusumiahbciekubtbvxjstwplcmeyhninnmeyjazrosgekjxflrggrexvfwsmyerrvwtmrpyehxvunjsyrkpstzsgkiikaxnrfxjkuiibixywshsajxzeklvrrgtmvwxvrrjglplrdxcstpmprxywxojnlvcqtaagrecdubyfdwzoxexrrrfmxomghmtstoirssjlylscsmeyalflmedwybeyosnkgxshwxnazpieecrfjnijvycdoreadffmzplriykmxassjepkojxuhqzdopeebeevhuxnqiyayegbdxvkgxshwxywskvnogfmxwkrrjtabepjdvxwtavnokvgxciuhriqzdszdwnzgpqnwxvjypshvmesrhxuhafjqplnwavvukrjkekwbavcoekxunqzdcgjkoiawmkkkhjvvxywwqeylxpstzgbqwviaarphswstehrdeevzdipoeiazueagtfoknsslxjwdlvrvwzgtsiohpzwbaeagavtkhmryikzgpcbxfvdoazrwlrlubxuhqrfewrqsvfdobiedxzfmiinqwwgxyszpyeaiwxvqksamehrdwffkkjgkidgypisiitlorinqhkzknisrvveuoxrqhljojkvvjzuzesa
WEAREEXPERIMENTINGBUSILYINOTHERWORDSWITHANYNEWTECHNOLOGYTHATEMERGESINTHISEXTRAORDINARILYFERTILEERAIFITLOOKSLIKEWEREMAKINGTHINGSUPASWEGOALONGTHEREASONISTHATWEARETOEACHPLATFORMASTHEYARENOWCALLEDINTHETRADEWEARETAILORINGTHEATLANTICWORKTHATCANFITITBESTTRY
We use the full kasisky test. Like from earlier, we find a gcd which is 8. Then, we assume e is the most commonly used letter, so we get the most frequent letter at every nth position in the encryption where n is the key length. First, k is the most commonly used letter, so k:10 - e:4 = g:6 and so on, we spell “gwenders”.
wsrrrbdrwllhuegfpvvlgveezyckxuludsjolfddpfafttsbuuwppfarwllrhtnwpbbewteazldyifhjadmgouthvlayhrjbybduiavuioijhqilhoyyckwqveavajogazxgochjvrlawvayzaglipogcnpbbbebxfaftdvraawalnajxlwvuudlmaycblqoyycjibmyhovbbbcvavaghalragblssugvoxgoyialrnppcifhjanecplvdmqlcklvlvltsigzddyxuoghzteprtprgocroyejflhcchrwzxbnjxkinublljnppxlwgoyikseblqfxulrgptylftjeglqilezmpdtxulnglwruatvjgochbrsvjavavueshvxuchzpvrcpkvrhkcvanycuysypacvxntmjzifoyashvzrjyfgoghoeysmllhuvshlmntqtuxjprwivbvkqljbycivwjlcealrkshafrogckxulbdvvbicgvrgopdbkuaftoshzcvpzrnyioieplvsmtorqfxulbthhnubsysjzwupvrlttycrsdpuhshggfwcygillbwyhsmtorpzfvybuyszipxlvnubiomfkgiacnmrtyqrzgcneakbpugrpriymcwgcnplagihrvhdxywgycwleezcnvyezmcnflymilxblyroabybpdeeijxukavrtoeakgcoeakuxalshggfkehatdmysutzmanyckfylqhalvznahgrvztysaumlbrgpjioioycprsskynalevsvoxupqwvyflcpjlshggfwgyynasgocqlwgipxkiolblppydclompoznbwfoyasfylqhlholyckxulghzyraftyipycpairccgzlnsjqljbyrjueglqdzlnsjpspgocrvycschalelctcieapjlmasmkprticpuhgocqssgzmuuegbptzlnubhoeysldamaaftpvvzqjlwghlsuiilpbvproyglpvwldywphpcvvzhpzwvbkgvpshzqjjlnzyglhrznxziqplchxvcgifwuhjabtburwlmejfxshellqlavafiomfmgtshqlurvrflaghxrlttycshggfxnrcwpwthgihrqlyrowrccghppoybiieijtzwgopdbkuafxztnsyrlavafhdiranthgrhlsalrvuclvbmgiiprzrtciezfpspvuqpmigfptzxgygehanfkpriavqihczlcitinsjqffelyzvjqhwebgxpdllwuhbddwuhttvjsllslhgogcrfharwpwnubpspvzktuhrkrwhxlvswhzrisizphtztyiqocglaupjtalrzckpwvvlhkmqhneleehlsalvzuthonubxkprafttiavkdyilpcakmanzjaeqycptkruralwqvldavrwptoiakgufshwygksadclppytcckeakyhpezhlwvrrzrebgxpdlllnccjuinyltkphjicvagvqrhtraftziewccawgvlvbijluxspzhithqrubhlvrsmcniyzcioicbazhpvhprhpyzmvvsqugvoxhurdfshhjanmilktfshyfpuhfpdllfrmpxlrqzyckvbigczlnsjglwgvpthqrubh
pucknowthehungrylionroarsandthewolfbehowlsthemoonwhilsttheheavyploughmansnoresallwithwearytaskfordonenowthewastedbrandsdoglowwhilstthescreechowlscreechingloudputsthewretchthatliesinwoeinremembranceofashroudnowitisthetimeofnightthatthegravesallgapingwideeveryoneletsforthhisspriteinthechurchwaypathstoglideandwefairiesthatdorunbythetriplehecatesteamfromthepresenceofthesunfollowingdarknesslikeadreamnowarefrolicnotamouseshalldisturbthishallowedhouseiamsentwithbroombeforetosweepthedustbehindthedooroberonthroughthehousegivegatheringlightbythedeadanddrowsyfireeveryelfandfairyspritehopaslightasbirdfrombrierandthisdittyaftermesinganddanceittrippinglytitaniafirstrehearseyoursongbyrotetoeachwordawarblingnotehandinhandwithfairygracewillwesingandblessthisplaceoberonnowuntilthebreakofdaythroughthishouseeachfairystraytothebestbridebedwillwewhichbyusshallblessedbeandtheissuetherecreateevershallbefortunatesoshallallthecouplesthreeevertrueinlovingbeandtheblotsofnatureshandshallnotintheirissuestandnevermoleharelipnorscarnormarkprodigioussuchasaredespisedinnativityshallupontheirchildrenbewiththisfielddewconsecrateeveryfairytakehisgaitandeachseveralchamberblessthroughthispalacewithsweetpeaceandtheownerofitblestevershallinsafetyresttripawaymakenostaymeetmeallbybreakofdaypuckifweshadowshaveoffendedthinkbutthisandallismendedthatyouhavebutslumberedherewhilethesevisionsdidappearandthisweakandidlethemenomoreyieldingbutadreamgentlesdonotreprehendifyoupardonwewillmendandasiamanhonestpuckifwehaveunearnedlucknowtoscapetheserpentstonguewewillmakeamendserelongelsethepuckaliarcallsogoodnightuntoyouallgivemeyourhandsifwebefriendsandrobinshallrestoreamends
We use the full kasisky test. Like from earlier, we find a gcd which is 5. Then, we assume e is the most commonly used letter, so we get the most frequent letter at every nth position in the encryption where n is the key length. First, l is the most commonly used letter in the first position (32 times), so l:11 - e:4 = h:7 and so on, we spell “hyphen”.