维吉尼亚密码

something：要考试了，原谅窝再水一个wp(! - !)

注：在同学那里搜罗来了一个维吉尼亚密码的解密网站，不过我还没用过，SL姐姐布置的作业，全靠python水过去了。 维吉尼亚密码是古典密码的一种，从凯撒密码演变而来，用多个凯撒密码组成，是多表密码的简单实现。简单说，就是按照这张表来实现：

差不多就是，原文abc，如果秘钥是xyz，那么加密后得到的是 xzb。如果不了解凯撒的话，百度一下，很好理解的。

数据如下 faprepeapmsstwmcxdfwfaprepeapmsstwmcxdfwfaprepeapmsstwmcxdfwfaprepeapmsstwmcxdfwfaprepeapmsstwmcxdfwdteprdxcrsnlwtghealcegnzyahzeleutgircdgebpawxhpidtogidiqjxaqecixektglhispdwanhavokxoisiwpylixxetthzgctgpbptgtinrttwucrzrtgdwpaqapxodqtkogyfwthxxtlnheypxseleqpwpaahzlahxewfpcdpiztprgapyhsspgmdqtnohpbmythdqeriwpcsttxxowpgibttysuicfqbtgphbnrcmtxrdedxslwspndxhtqlplheweswtoaiiwrslsrzpogxykihffmtthtqpaneleqtdxagdfrdetcgecixsrtpngugpeitwpyxhtqlpljhphaiucenrtelaczdxobtemcjazysitdxicvmcsrxprtxhewicvpvmpcjxhtizrgjteaihitrgcpeyrtdqmthrzrttcewcdcqmrbhelaiisiwdgwhcjemelawlwcdbpeldcraanucsmiwppepisirpcopartdzagxpxyiwlxwphnsmbdyesgtniniajesiwpwtwtqivtgysvphdicgteedxslwspndmsxidvasxnelantqpgdgidhnyxaritgfdpxensjymqjtvriiiphrphnleaulfrxrrmvtcelaiismsxhdypeddididxektisibpawjahipvacsavokxoitwtqvetztgkhepgipatwthatoeqtnohpbhmtwbzveedhirxixeycdefehjctrxhtrgiwlxgdpwoetepvsaxvibjuqsnpgpynwpatyhelmnvdlpkttairetovordyxrtglwspxoxhtqlmlprewsiglrgtajahxaphacxdlkttairiwzqahhzvechprasbtxttsrpodbtpyiwlxiilzylsecsbpqwcrthfptxcxsrthaicipnylpgrsaahlwavdlpkttairndflakteslxkpaiiweleupnxtwpexhtbloeghnvepipfaaadjogisibtcpjiidqwtgxvirhwpwaxsmifdgppepktrgrdainwprinudcwojisoogtlfuidfxfxtwhpapjirhwlzepadswtxrlesxyaiiwnviixnmsbblryhpjmnvisibpawmsidzpivweensisirtuzvewpchtdrzrtgdwmthqtkacstxsidzpivwenaepywjxytrelhlkecrjuudiphbgpkmlxpyjogllvdtstpsdclwspntrgtpcpitgelihbzrtwlsmltheviztcvikpwhohpthiihzertsesoupcahtcvmcztonojgyelxhewaiisimpxytrthdgeciciicnzoowpxehpkpfetcrmvtcelerwlrctizxrndfxtwtqivtgysvpucsmiwptecpwxyhezxwxisxhtptqouwtxtxcrwptrtelipckeihtrtwtrsaahzjagupahpkpfetclfltizwcdgpqogtelacutzedjesfityeliwzygwismsbpjlaktwmtiapxosdhmtwisiqjpwmtndqxhtqlplejedasbtxsiwlxtwtmelaxdsniwppivwewistzjfxulwtdvcemlttkhigpuuxgpqecimythpjwiixdroqxrkegisenegpzidjdfaaadxhtrzrtgdgirhnzzegisibpawelhdsespczjfexeghsxxinhxzricsfwtgntrsxspvshpjmtbpjfecdnsicrthecrpxhpiapantcwfgdxfrpotpsedywogtofypsthahgtzaactoewpgibttyemdcrxhtqlplhbzwtkdnmftgzysrgtxirhelehpximxvsxgduzvtwtavaxhphihwphojiqsriwpfaaamcbtrvlabdyiouisimpxytlpnpvsjhphtdecsmdipedxslwefjttmtce

Kasiski测试法：：

若用给定的密钥表，周期地对明文加密，则当明文中的相同字母，如果被相同的秘钥字母加密，则会得到相同的密文字母，但是如果只考虑单个字母被加密的情况，可能就过于普遍了。

理解起来其实很简单，在加密后的文本中，出现的重复单词，很可能就是由相同的原文，通过相同的秘钥段加密得到的，而这些重复单词的间距，是秘钥长度的倍数，多个间距的gcd大概率就是秘钥长度。可以找出所有长度超过3的重复单词，统计他们间距的gcd，然后看一看哪一个最合适当公钥长度。只要文本量足够大，就可以提取出足够多的有效信息。

话不多说，上代码（python3）：

原始data进过Kasiski检测，打印出来是：[20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 10, 20, 20, 20, 20, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]，很明显了，秘钥长度是5，而且说明这数据有很多重复。

求得秘钥的关键在于，确定了秘钥长度 k k k 之后，可以把密文的第 1 1 1个，第 k + 1 k+1 k+1个，第 2 k + 1 2k+1 2k+1个…密文字母提取出来组成一个新的文本，这个抽取出来的文本，都是由秘钥的第一个字符加密得到的，就相当于一个凯撒密码。然后利用重合指数法，这个网上有很多说明，也很好理解。我们就把这一串提取出来的文本反向凯撒回去，26个字母一个个试，只要他给的原文文本是有意义的，符合英文文本的正常规律（字母出现的大数据频率）就可以了。

代码（python3）：

运行结果：

请选择秘钥长度：5 apple

然后就是，按照维吉尼亚表进行替换，解密一下，这个也还算好写，转ascii再转char，中间注意mod一下26。

代码（python3）：

运行结果： lrgmgvvrkoyjkroiouaylrgmgvvrkoyjkroiouaylrgmgvvrkoyjkroiouaylrgmgvvrkoyjkroiouaylrgmgvvrkoyjkroiouayjkvktjotmutcnoinvrgekxeuagyqznklkbkxtubghgrrzngzyvuxzykwaovsktzsgqkxgjojgyygeyvxubojkyznkarzosgzkyuiikxkdvkxoktikoyatiutzxurrghrkzuuhomuxpayzyosvreyzavojznkhgrrgryungyozylgtyroqkktmrgtjyjgbojhkiqngshazyulgxznkeykkszungbkhkktuaztashkxkjheixozoiygjojgyygeyznkhgrryvrgynkjcoznmurjiuruxotmoywaozkyosvreznkhkyzgxuatjvkxiktzsuxkgiiaxgzkzngtznkhgrraykjgzlxgtikzngtqyzuskzoiaruayzkyzotmheyioktzoyzyotmkxsgteznkzutmakzcoyzotmtgzaxkulozyiutzktzyiutloxsyzngzznkcuxrjiavhgrrngyiuskgrutmcgelxusznkrkgznkxgtjrgikybgxokzezngzcgyiussutgyxkiktzregyznkyznklkbkxtubgyykixkzgjojgyygeyoyozyxgjoigrreosvxubkjyetzgizoilugsgtjatowakqtozzkjxgyinkrlghxoimobktzngzznoyoyyavvuykjzusgqkznkhgrrlgyzkxgtjvxubojkznklxkkqoiqyvkiogroyzyroqkhkiqngscoznsuxkvuckxozsgetuzhkyaxvxoyotmzngzmugrqkkvkxyroqkhallutgxkatngvveyvgotmugrqkkvkxvkjxuiutzxkxgyygojznkhgorgizyyzxgtmkrecnorkjgtoynqkkvkxznusgyyuxktyktgjsozzkjmruusorezngzozcuarjvxuhghrexkyarzotsuxkyvkizgiargxmugrygygmugrqkkvkxeuangbkzurobkcoznznklgizzngzznksgqkxyixkgzkhgrryluxznkhktklozulyzxoqkxynkygojhkluxkrkgbotmiuvktngmktluxyuaznquxkghazuazlokrjvrgekxyngbkgryuckomnkjotcoznixozoioyssgteygeotmznkhgrroyzuuromnzgtjznkxkluxkngxjzuiutzxurozyhomgtjozyzuuromnzpgvgtypopotkcygmktiewauzkjhxgforogtluxcgxjkjoryutgyygeotmkgxrokxznoysutzncnorkyzxoqkxxobgrjuygojozyugxkjzuulgxcnktqoiqkjpuaxtgroyzygzznksgotvxkyyiktzxkoteuqungsgngbkhkktmobktznkingtikzuzxeuazznklkbkxtubglxusznkvktgrzeyvuzcoznznkgosulnozzotmyvkiogrzgxmkzyotznkmugryulgxlkcngbkhkktghrkzuyiuxksuxkzngtlobkuazulzktgrznuamnznoysgengbkrozzrkzujucoznznkwagrozeulznkhgrrvazfgjsozyzngzznkhgrroyutznkromnzyojkullolgyzumxgsckomnzxkwaoxksktzhazygeyozoytuhommkxzngtvxkbouayhgrryznkiutzxubkxyeubkxznkhgrrgryungygtullvozinjosktyoutotjayzxeotyojkxyygeozsgehktuiuotiojktikzngzvrgekxylxushxgforyvutyuxkjhegjojgyxobgrtoqkngbkhkktgsutmznkhgrrysuyzbuiolkxuayixozoiyznkygsksomnzmuluxznkvxgoykjoynkjuazluxznkhgrrhehkiqngsutkulznksgotvrgekxyaykjzuvxusuzkgjojgykwaovsktz

发现啥也看不出来，不过仔细观察一下，很容易看出前面有重复字符lrgmgvvrkoyjkroiouay出现，后面就不在重复了，可惜我并没有产生敏感，这其实就是flag。 不过我面对这堆字符，没办法，就想是不是加密了不只一遍（其实是维吉尼亚基本只能加密一遍，因为再加密的时候，是无意义的密文再加密，不符合英文的基本分布规律。） 我又跑了几遍发现： [20, 20, 20, 20, 20, 20, 20, 4, 20, 20, 20, 20, 20, 20, 4, 4, 3, 6] 请选择秘钥长度：2 gg 请输入秘钥 [20, 20, 20, 20, 20, 20, 20, 4, 20, 20, 20, 20, 20, 20, 4, 4, 3, 6] 请选择秘钥长度：4 gggg 请输入秘钥

然后可以确定是经过凯撒过的东西，于是直接把这一段lrgmgvvrkoyjkroiouay跑个26个凯撒。

代码（python3）：

结果： lrgmgvvrkoyjkroiouay mshnhwwslpzklspjpvbz ntioixxtmqalmtqkqwca oujpjyyunrbmnurlrxdb pvkqkzzvoscnovsmsyec qwlrlaawptdopwtntzfd rxmsmbbxquepqxuouage syntnccyrvfqryvpvbhf tzouoddzswgrszwqwcig uapvpeeatxhstaxrxdjh vbqwqffbuyitubysyeki wcrxrggcvzjuvcztzflj xdsyshhdwakvwdauagmk yetztiiexblwxebvbhnl zfuaujjfycmxyfcwciom agvbvkkgzdnyzgdxdjpn bhwcwllhaeozaheyekqo cixdxmmibfpabifzflrp djyeynnjcgqbcjgagmsq ekzfzookdhrcdkhbhntr flagappleisdelicious gmbhbqqmfjtefmjdjpvt hncicrrngkufgnkekqwu iodjdssohlvgholflrxv jpekettpimwhipmgmsyw kqflfuuqjnxijqnhntzx

根据提示整理 flag{apple_is_delicious}