Vigenere加密算法的自动破解方法设计与实现开题报告

1. 研究目的与意义（文献综述）

信息，也称之为消息，被香农定义为“凡是在一种情况下能减少不确定性的任何事物”。人类通过获得、识别自然界和社会不同信息来区别不同事物，同时信息不同于物体，他可以无限复制广泛传播。随着计算机网络的普及，信息的传播呈现出速度快、形态多样和范围广的特性，使得信息成为一种资源，成为推动社会进步和促进经济增长的重要力量。然而，一旦信息落入其竞争对手手中可能会导致企业、政府、国家造成不可估量的损失。因此，保护信息的机密性，对国家，企业，个人都具有重要意义。

从古希腊人使用的棋盘密码到凯撒密码，从美国南北战争时期的“栅栏”式密码，再到近代机械加入后诞生的代换、换位混合型密码……对人类的发展和保护、传递重要信息产生了重大深远的作用。

因此，更好的加密重要信息至关重要。置换密码，在有限集x上建立一个双射函数关系，使字符之间能按固定的规则替换；列置换密码，明文遵照密钥规则按列换位并且按照列读出明文序列得到密文。这些思想以及破译方法反映了密码设计和破译的基本思想，但相对简单，很容易被破解。代换密码的出现使得古典密码体制更进一步，在现代密码学中也有广泛的应用。单表带换密码只明文消息中相同的字母，在加密是都使用同意固定的字母来代换。单表代换密码又分为基于密钥的单表代换密码和仿射密码。但是由于固定对应，只是字符表象与日常通信信息不一样，其本质的规律一致。频率分析法则完美的阐述了其本质规律。在每种语言中，冗长的文章中的字母表现出一种可对之进行分辨的频率，而在密文中分析出相应频率的字符有极大可能对应着日常通信的字符。因此，通过分析每个符号出现的频率而轻易地破译代换式密码。为了使频率分析法失效，多表代换密码应运而生。多表代换密码利用明文字符到密文字符的多个映射隐藏单字母出现的统计特性（频率）。将明文字符划分为长度相同的明文组，然后再对明文组进行替换。这样同一字母在明文序列中的位置不同就具有不同的密文，从而能更好的抵抗统计密码分析。维吉尼亚密码是由法国密码学家blaise de vigenère于1858年提出的一种代换密码，是多表代换密码的典型代表。

2. 研究的基本内容与方案

Vigenere加密算法是对称密码体制中的一种经典加密算法，他的设计综合运用了替代加密的多种设计思想。目前对它的教科书式破解方案需要人工干预，本项目的目标是设计能够无需人工干预的Vigenere密码的自动破解方法，并通过实验仿真对项目设计进行正确性和效率性的验证。

Vigenere加密法也是需要关键字的，但并非是单码加密法的一一替换关系，而是通过关键字与明文关联，从而确定密文。传统的用于分析单码加密的方法对Vigenere加密法没有多大效果。尤其是密文中出现的字母频率都差不多了，便无法通过语言的自身特性来与其匹配。首先要确定Ｖｉｇｅｎｅｒｅ密钥字长度。重合指数法能通过对重合指数的分析得出密钥长度。

FrederickKasiski通过对Vigenere加密法长时间的观察，得到一个简单的结论：密钥的重复部分与明文的重复部分连接，在密文中也产生一个重复部分。在通信中，我们肯定会使用很多重复的单词，例如the、what、dear等，如果与他们对应的关键字也是相同的，则会产生相同的密文。同时，注意到，密文中重复字符串之间的距离反映了密钥重复的次数，既反映了密钥的长度。于是破解过程如下：(1)找到密文中重复的字符部分 (2)计算重复字符之间的字符数 (3)找出从步骤(2)中得到的数的因子（就是最大公约数） (4)最大公约数很可能就是关键字的长度当然，也会有巧合的时候。偶然性的重复字符串会影响对关键字长度的确定，这需要靠我们更多的观察、思考来排除。这也即需要人为干预的地方。找到了关键字长度，我们就可以下手破解了，找出密码字了。在明文中，将与关键字中相同字符关联的明文字符集合到一起，他们其实是单码加密的。比较密钥中的字符关联的明文的放在一起，可以发现它们都是简单的移位加密。于是，在我们知道关键字长度后，破解Vigenere加密法就变成了破解n（关键字长度为n）个不同的单码加密的问题了。我们根据关键字长度，将密文字符串按一定规律分解排布，将1，n 1，2n 1，3n 1，……字符放入第一个集合，将2，n 2，2n 2，3n 2……放入第二个集合，同样操作至结束。每个集合就是一个单码加密的密文，然后我们通过对单码加密的分析法来一一破解。其实对每一个集合，我们可以用低频率分析法来分析，将集合I中的每个字符移位一次得到另一个集合II，再移位一次又能得到新的集合III。。。。。重复这些动作，一共移位25次，我们共得到26个集合，其中有一个集合便是我们需要的明文。但是这个集合是从原始的明文中选取的集合，其中的不可能构成可能的单词，我们便通过标准英语的另外一一些特征来确定它是不是我们需要的明文集合，例如字母j、k、q、x、z这些字符出现的频率和不足2%。最后通过程序模拟来验证破译方法。

3. 研究计划与安排

第1—3周：查阅相关文献资料，明确研究内容，了解 研究所需知识与各项技能。确定方案，完成开题报告，书 写摘要并完成相关英文文献翻译。

第4－6周：前期可行性研究，需求分析，进行系统 的初步设计。

第7－12周：系统具体实现，主要完成代码的编写，调试以及功能的实现。

4. 参考文献（12篇以上）

[1] j. katz and y. lindel.introduction to modern cryptography: principles and protocols. 2008

[2]冯登国,陈成.属性密码学研究密码学报, 2014, 期 1

[3] 曹密码学的新发展四川大学学报：工程科学版, 2015, 期 1浅析古典密码学.2014