vigenere密码的破译

Vigenere密码的破译实验目录实验背景…………………………………………………（2）实验概述…………………………………………………（2）实验步骤…………………………………………………（3）实验结果…………………………………………………（8）实验总计…………………………………………………（13）相关程序…………………………………………………（13）改进方案…………………………………………………（21）——张哲201100090101山东大学2011级信息安全September19,2013Vigenere密码的破译2/21【实验背景】Vigenere密码是古典密码中较为复杂的一类密码，它的破译比单表代换密码的破译要难的许多。其破译的过程，总体来说可以分为5个部分，同时这也是我所编写的5个核心程序所要解决的任务（总程序的数量为7个）。【实验概述】一、密钥的长度推算根据kasiski测算的方法，统计一些高频字段出现的位置，并算出其距离，根据距离的最大公约数，推算出密钥的长度。二、密钥长度的确认设置不同的密钥长度（d），从d=1：:20，计算不同的d下的重合指数，根据重合指数与0.065的接近程度，确定d的具体数值，并且舍弃d的倍数，如2d。三、密钥中各字符之间的相对位移的确定根据确定好了的密钥长度d，计算出d*（d-1）/2个密钥字符间的相对位移，如果给的密文教容易破译的话，直接利用其中的d-1个互重合指数即可，得到相邻两个字符间的间距，为了生成密钥方便，我们假设后一个字母比前一个字母要大l，其中l=(key[i+1]-key[i]+26)mod26.四、密钥的生成根据上一步产生的密钥字符间距，从a到z改变首字母，以获得26个可能的密钥。当然，直接观察这些可能的密钥是否是我们所需要的，是不现实的。需要进行待定翻译过程。五、根据生成的密钥进行密码的破译根据产生的26个可能的密钥，分别对密文进行破译，再根据破译的26篇可能的明文进行进一步的分析。不难得到我们所需要的明文。下面，我们以第一段的密文为例进行我们的破译工作：首先我们给出密文：OnlbqevecwidgteokcunltzwseygmlzlpamfztssngarjsijulootagidqihzucslteslflsaklfifjbcccyntecbzkpwovwzsnoxazawozjgkpsvonecsbzkblfwfnacywfteywasztpaxlonrhwlnwlfblneqfmeknuwpsjuyrmjzhpqtgyehobunoqhpwkmaszgxtssmevecczaysffxjosprilgltoavkftovukoqvqkvohszstdsszuunqwlwtcpwvzkrmfwlneckpgsssszwbelzalubpdimraefmajedoblnaeawekneivvkrncdwxoqooamayhquyayralurxdimrayrpayacagglfcsuwtaehiuqtsskazycwlatgdovvcocaasrilyqdrsevmtgrzblmxiyubzkczbnmyizbxsalosnwgtdhpwyacrimqacovvioytzgttdhpwkmaszgxtsfmszeywvyzoosalxojhpwyptqmlnecsjqknowvyyplqmlxagststdnfqhvltbotutswuhkrtothuwpfifjtssjwtersakkrthqfunpptgcfpmljgueviunawzmfmeddimrtzosfofprcwriyonatawoblkmahbgytzdpayogszlnrzkjmzidrmxkaeslvksawbwgnlhbwspeoblxelqpwxycsidoztbolnaedimridqihgbwswxjotbosrlsspsytsfmszeysllnepaxwxocwaxurnslluamrqugtpovvzoafweospvqkjafuplkrafqfiedgqjallbqfsacfqsmeecxsalaocdgsnsvvytssbzxoyspayczbbjulztijxavwastdevmkvinsmkzamzqkniyuifkwvwvvufacewxogszlnepaxaxeevilciwzkzgnrsbzkflqmgltsssfuwyivabecgmtatosahotpvqkyuafmekpzgqlooydimrrpotafedhpszhpkqdrnzhjwgbwsbgytzdbzkjtvivnesoakkeywvzosgwaaundvqkrersvvgrjgbszudougtgevmxxexsvzgvtboyxohbjweoyrpayczbbjulVigenere密码的破译3/21【实验步骤】1、运行“相同字段及次数.exe”文件，可以得到重复出现3次以上的长度在3以上的字符片段。得到的结果如下：同样，我们可以在生成的“相同字段及次数.txt”文件中找到所需的数据[程序改进见附录]：tss*6jul*3bzk*5nec*3sbz*3bzk*4eyw*3asz*3pax*3lne*5fme*3hpw*4kma*3tss*5vqk*4std*3lne*4sss*3dim*5imr*5obl*3wxo*3dim*4imr*4pay*4tss*4ovv*3evm*3bzk*3czb*3sal*3dhp*3hpw*3ytz*3lne*3tbo*4tss*3dim*3imr*3pay*3bws*3tbo*3vqk*3密文中出现频率较高的片段都在上面显示出来，虽然没有对其进行排序，但是一眼便可以找到频率较高的几个片段：tss、bzk、lne、hpw、imr、dim、vqk、pay、tbo等。2、下面我们再运行“相同字段算间距.exe”程序。一次输入几个出现频率较高的片段：tss、bzk、lne、hpw、imr、dim、vqk、pay、tbo。得到kasiski数据.txt.Vigenere密码的破译4/21tss162174186276102bzk3030051090lne114234240162hpw2522430imr54258102276dim54258102276vqk54618084pay288204252tbo162243603、根据程序所计算出来的相同片段的字符间距，不妨计算一下他们的最大公约数：为6.Vigenere密码的破译5/214、既然已经得到了可能的密钥长度为6，我们再用“重合指数计算器.exe”计算一下，这篇密文的重合指数。不难发现，当d=6的时候，重合指数都在0.065左右，这样，我们有足够的自信相信重合指数就是6.（详细数据参见“重合指数数据.txt”）5、既然已经确定了重合指数d=6，下一步，我们就是通过计算d=6的情况下的互重合指数以确定密钥字符间的间距（即相对位移）。运行“重合互质数计算器.exe”在输入界面输入d的值（密文1中的密钥长度为6，我们就输入6）得到数据“重合互质数.txt”Vigenere密码的破译6/21通过数据，我们找到了5组，相对位移：i=0j=1相对位移=20互重合指数=0.069i=1j=2相对位移=11互重合指数=0.064i=2j=3相对位移=3互重合指数=0.067i=3j=4相对位移=20互重合指数=0.073i=4j=5相对位移=10互重合指数=0.0676、根据上一步得到的相对位移，我们手动将这些数据输入到“字符间距.txt”的文件中，以便程序“密钥生成器.exe”使用。7、运行“密钥生成器.exe”程序，得到26个可能的密钥，在“所有可能的密钥.txt”文件中。Vigenere密码的破译7/218、运行“明文test2.exe”(翻译针对已知密钥进行翻译，明文test2可以对26种可能的密钥对密文分别进行26次的翻译工作)在其生成的“明文.txt”文件中，我们可以找到26段可能的明文，根据是否出现英文单词判断明文是否可取。由于篇幅有限，我们给出几段可能的明文：以及正确的明文：[Key]=auficmOtgtosvkxogrgzzgiqutglxksktykzzrksktzznkluaxekgxurjgrogoyigvzaxkjheygxjgaqgxgtjhxuamnzzuznkvrgtkzyigvozgrgxxgqkktcnkxkznkhgxutngxquttktoygzzksvzotmzuzncgxzznklxksktpongjatjkxznkiruykcgzinulznkksvkxuxznkksvkxuxoyyaxvxoykjgzgrogyjklogtikulnoyvuckxgtjnkxiutlojktikotnkxhxuznkxcnusynkxkbkgryzuhkvgargzxkojkygzzngzsusktzatjkxiubkxulgmomgtzoiygtjyzuxsvgargtjnoygxseullxksktgzzgiqznkiozexojotmygtjcuxsygrogqorryznkhgxutjaxotmznkiutlayoutvgarjklkgzyznkygxjgaqgxgtjiutlxutzyznkksvkxuxznxkgzktotmzujkyzxueznkyvoikznkxkhektjotmyvgikzxgbkrgtjixovvrotmhuznosvkxogrvuckxgtjznkhktkmkyykxozotutkhruclkejxgazngingrrktmkyvgarzugqtolkjakrotglotgrgzzksvzzuyzuvnoyubkxznxuchazoyjklkgzkjjkyvozkgtgzzksvzgzzxkginkxexkgrofotmzngzvgaroyigvghrkuljuotmgrrnkngyznxkgzktkjznkksvkxuxoyluxikjzughjoigzkgtjzuvxusoyknoyjgamnzkxvxotikyyoxargtotsgxxogmkzuvgarvgargyiktjyznkznxutknoyiutzxurulgxxgqoygtjznkyvoikkyzghroynotmgtkcqotjulvuckxubkxznkksvoxkzngzcorringtmkznklgikulznkqtuctatobkxykhazjkyvozknoyyavxkskvuyozoutvgarxkgrofkyzngznkcorrtuzhkghrkzuyzuvznkpongjnkngyykktotnoyboyoutynoyrkmktjgxeyzgzaygsutmznklxksktnVigenere密码的破译8/21gbotmmxucthkeutjnoyiutzxur[Key]=bvgjdnNsfsnrujwnfqfyyfhptsfkwjrjsxjyyqjrjsyymjktzwdjfwtqifqnfnxhfuyzwjigdxfwifzpfwfsigwtzlmyytymjuqfsjyxhfunyfqfwwfpjjsbmjwjymjgfwtsmfwptssjsnxfyyjruynslytymbfwyymjkwjrjsonmfizsijwymjhqtxjbfyhmtkymjjrujwtwymjjrujwtwnxxzwuwnxjifyfqnfxijknfshjtkmnxutbjwfsimjwhtsknijshjnsmjwgwtymjwbmtrxmjwjajfqxytgjufzqfywjnijxfyymfyrtrjsyzsijwhtajwtkflnlfsynhxfsixytwrufzqfsimnxfwrdtkkwjrjsfyyfhpymjhnydwninslxfsibtwrxfqnfpnqqxymjgfwtsizwnslymjhtskzxntsufzqijkjfyxymjxfwifzpfwfsihtskwtsyxymjjrujwtwymwjfyjsnslytijxywtdymj