密码破译的常用算法

第八届“认证杯”数学中国数学建模网络挑战赛承诺书我们仔细阅读了第八届“认证杯”数学中国数学建模网络挑战赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们接受相应处理结果。我们允许数学中国网站()公布论文，以供网友之间学习交流，数学中国网站以非商业目的的论文交流不需要提前取得我们的同意。我们的参赛队号为：参赛队员(签名)：队员1：卢健队员2：孙一队员3：刘娇参赛队教练员(签名)：谭欣欣参赛队伍组别（例如本科组）：本科组第八届“认证杯”数学中国数学建模网络挑战赛编号专用页参赛队伍的参赛队号：1447竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：2015年第八届“认证杯”数学中国数学建模网络挑战赛第一阶段论文题目替换式密码关键词频率统计穷举法语法规则模糊综合评价评价体系层次分析摘要：密码破译是指在不知道密钥的情况下，恢复出密文中隐藏的明文信息的过程。随着信息技术的发展，对数据加密的方法也越来越多，密码的破译也就变得更加困难。本文设计出了基于频率统计的穷举算法和增加语法规则的改进算法，对单字母替换的密文进行破译，另外运用了模糊综合评价的思想建立了一个破译算法的评价体系。对于长密文的破译，本文借助自然语言的统计特性进行破译。查找资料发现英文中各个字母出现的频率相对稳定，并大致可以分为五组。在密码表中，密文与明文是一一对应的关系，所以明文中的统计特性同样会映射到密文中。利用这个性质，对密文中的各个字母进行频率统计，对统计结果进行分组处理，最后采用穷举法遍历所有可能的密钥。通过与数据库的数据交换，找出正确的密码表，从而破译密文。对于短密文的破译，考虑到英语除了具有自然语言的统计特性之外，还具有自身的语法规则。因此本文通过总结出英语中的一些规律，制定相应规则，在规则的约束下对密文进行预处理，减少穷举的数据空间，增加破译的准确度。对于算法评价体系的建立，本文着重考虑了算法的时间复杂度、空间复杂度、算法破译密文的准确度以及鲁棒性这四个因素。首先，利用层次分析法解得这四个因素在评价算法时所占的权重，然后根据模糊综合评判，设定评语集。由于破译算法的多种多样，不同算法的四个因素所能达到的标准也是不一样的。于是本文对标准进行了详细的分类并分别求出四个因素在不同标准下相应的权重，建立出一个合理的评价体系。最后利用这个体系对本文设计的破译算法进行评价，得出的结论是处于较好的这个层次。参赛队号:1447所选题目:B题参赛密码（由组委会填写）AbstractCryptanalysisreferstoaprocessthatinthecaseofnotknowingthesecretkeytorecoverthecipherplaintextmessagehiddeninclearinformation.Thispaperdesignedtheexhaustivealgorithmbasedonfrequencystatisticsandincreasethegrammaticalrulesoftheimprovedalgorithm,todecodetheciphertextofsingleletter,Italsousedtheideasoffuzzycomprehensiveevaluationtoestablishtheevaluationsystemofadecodingalgorithm.Thispaperusethestatisticalfeaturesofnaturallanguagetodecipherforlongcipherdecoding.BylookingoverallkindsofdatebookswefindthatthefrequenciesofallthelettersintheEnglishlanguageisrelativelystable,anditcanberoughlydividedintofivegroups.Inthecodetable,theciphertextandcleariscorrespondingtoeachother,sothestatisticalcharacteristicsoftheclearcanalsobemappedtotheciphertext.Bytakingadvantageofthisfeather,wecanmakethefrequencystatisticsofallthelettersinthispaperandhandlethestatisticalresultatthesametime.Finally,weuseexhaustivemethodtofindallthepossiblesecretkeys.Byexchangingwiththedatabaseandfindingthecorrectpasswordtabletodeciphertheciphertext.Forthedecipheringoftheshortcipher.GiventhatEnglishhasthestatisticalpropertiesofnaturallanguageanditsownrulesofgrammeratthesametime.SoweformulatecorrespondingrulesbyconcludingsomeotherrulesodEnglishinthispaper.Wecanhandlethecipherwiththebindoftherulesandreducetheexhaustivedataspace,besides,wecanincreasetheaccuracyofdecoding.Fortheestablishmentofalgorithmevaluationsystem,weattachgreatimportancetofourfactors,includingtimecomplexityandthespacecomplexityofthealgorithm,theaccuracyofthedecipheringalgorithmandtherobustness.First,weuseAHPtoconcludetheweightofthesefourfactorswhenevaluatingalgorithm.ThenweusetheFuzzycomprehensivejudgementtosetthecommentcollection.Duetothemanifoldofdecodingmethod,thefourfactorshasthedifferentstandard.Soweclassifiedthestandardindetailandobtainthecorrespondedweightofthefourfactorsindifferentstandard.Thenwewillestablishareasonableevaluationsystem.Finally,weusethissystemtovaluethedecodingalgorithminthispaper.Thefinalconclusionisinthebetterlevel.1一、问题重述历史上有许多密码的编制方法。较为简单的是替换式密码，也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言，最简单的形式是单字母替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者另外的符号。较为复杂的形式是以多个字母为一个单元，整体替换成其它的字符。这个映射方法被称为密码表，拿到密码表的人就能够将密文破译成明文。现在有如下问题需要解决：1.假定明文是由现代通常使用的英语写成的。现在有一些由单字母加密方法加密的密文，需要设计一个能够自动破译密文的算法。且为了问题的简便，假设密码表仅是针对26个字母的，每个单词之间的空格，以及标点符号仍然会保留。2.设计完破译算法之后，需要设计一个衡量该破译算法的标准，用来评价算法的破译能力。二、问题分析2.1问题一的分析问题一要求设计一个能自动破译密文的算法，本文中考虑的密文都是单字母替换加密的，所以最简单的办法就是穷举法。但是当字母表的大小为n时，使用穷举法破译的算法时间复杂度为O(n!)(针对本问题，n的取值为26)，对于阶乘阶的算法，当问题规模增大时，算法执行次数的增加将是十分恐怖的，直接使用穷举法显然是不合理的。由于任何自然语言都有其统计特性，因此，本文考虑借助英语的统计特性进行破译。经过文献调研发现，英文中各个字母出现的频率相对稳定。在密码表中，密文与明文是一一对应的关系，所以明文中的统计特性同样会映射到密文中。本文就是利用这个性质，对密文中的各个字母进行频率统计，对统计结果进行分组处理，最后采用穷举法遍历所有可能的密钥，找出正确的密码表，从而破译密文。英语除了具有自然语言的统计特性之外，还具有自身的语法规则。因此本文通过总结出英语中的一些规律，制定相应规则，在规则的约束下对密文进行预处理，减少穷举的数据空间，增加破译的准确度。2.2问题二的分析问题二需要设计一个衡量破译算法的标准，用来评价算法的破译能力。要建立算法的评价体系，首先要先确定影响算法优劣的因素，那么就很自然地联想到算法的时间复杂度、空间复杂度、准确度、鲁棒性这四个重要因素。根据算法的侧重点来求出这四个影响因素的权值。由于评价的体系是针对各个算法的，不同算法的四个影响因素所达到的标准自然也就不同，因此需要对四个因素分别进行单独的评价，最后整合从而建立一个比较客观的评价体系。最后将本文第一问中设计出来的算法带入到建立的评价体系之中，检验算法的优劣。三、模型假设1.假设语言的统计特性同样适用于英语，并且文献中统计的数据真实可信。22.假设所有的密文与明文都是一一对应的关系，不存在一对多或多对一的情况。3.假设影响算法优劣的因素只有时间性能、空间性能、准确度和鲁棒性这四种。4.假设时间复杂度和空间复杂度只考虑三种现实中可行的数量级。5.假设算法的鲁棒性只划分为高中低三个等级。6.假设在构建评价矩阵时，通过文献调研所得到的权值都是合理的。四、符号说明为简化对问题的分析和对数字的处理，我们在以后的文字中将使用如下的符号代表变量：表1：文中的部分变量符号说明符号描述Tn时间复杂度Sn空间复杂度算法的准确度B评价结果矩阵O表示算法复杂度的一种计数法n问题规模fn问题规模的函数形式CI一致性指标RI1-9阶矩阵的平均随机一致性指标CR随机性比率模糊乘法注：上述表格中未提到的符号会在文中有详细说明五、模型的建立与求解5.1模型的准备5.1.1替换加密算法在现代信息技术中，数据加密是一切网络安全技术的核心和基础，要保证数据的安全性，使用密码对其加密是保护信息安全的有效手段。其加密的具体过程如下图：图1：现代信息加密过程从图中可以看出，数据的加密与解密都需要一定的算法，在早期的私匙密码体制中，加密算法解密算法加密密钥解密密钥明文密文明文3典型的有替换(substitution)加密算法，其原理可用一个简单的例子[1]来说明：将a,b,c,d,…,w,x,y,z的自然顺序保持不变，但使之与d,e,f,g,…,z,a,b,c分别对应（即相差3个字符）。即构造出密文字母表，然后用密文字母表中的字母来代替明文字母，各个字母的相对位置不变，但是本身改变了[2]。5.1.2统计分析原理根据大量文献显示[2][3]，任何自然语言都有许多