2015第八届数学建模认证杯网络挑战赛 B题优秀论文1386队

参赛队号#1386第八届“认证杯”数学中国数学建模网络挑战赛承诺书我们仔细阅读了第八届“认证杯”数学中国数学建模网络挑战赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们接受相应处理结果。我们允许数学中国网站()公布论文，以供网友之间学习交流，数学中国网站以非商业目的的论文交流不需要提前取得我们的同意。我们的参赛队号为：1386队参赛队员(签名)：队员1：队员2：队员3：参赛队教练员(签名)：数模指导小组参赛队伍组别（例如本科组）：本科组参赛队号#1386第八届“认证杯”数学中国数学建模网络挑战赛编号专用页参赛队伍的参赛队号：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：参赛队号#13862015年第八届“认证杯”数学中国数学建模网络挑战赛第一阶段论文题目替换式密码自动化破译算法关键词频率攻击时间复杂度单字母加密自动化破译摘要：古典密码是密码学的起源，它是由基于字符的密码算法构成，可用并机械操作实现加解密。目前解密行之有效的方法则是频率分析法，但是利用传统频率分析法，拥有运算量大，计算时间长，需要过多的人工干预等缺点。所以本文提出一种创新的全自动解密算法，对单字母加密方法的密文进行解密。模型一：我们对传统频率法进行改进，建立了一种新的全自动化解密模型，不但能大量减少运算时间，而且可精确高效破译密文。首先我们在模型准备中统计出英文固有的各种频率数据，并建立给定字母长度15-24的长单词库群和字母长度1-8字典库群，使模型可实现单词的快速搜索和匹配。模型一的算法分为三个模块：（1）频率攻击：先统计密文中单字母、双字母组合频率并分组，再对分组频率进行匹配，从而确定最高频字母t,h,e。（2）长单词攻击：先将已破译的少量字母代入密文，再从中提取最长的单词代入相应长度的长单词字典库进行匹配，从而逐步破译更多密钥字母。因单词越长，数目越少，故匹配成功后正确率很高。（3）动态逐词攻击：先将已破译密钥字母代入密文，并对密文进行以单词为单位的扫描。再将单词逐个在字典库中进行匹配，得到相似单词组；其次累加记录每个相似单词中匹配的字母密钥，直至获取充足信息量；最终选取累计次数最高的匹配为最终密钥，破译出完整密钥。经多实例统计验证，该解密算法破译大约5万字母数的文章，用时仅2.75s。模型二：为评价模型一中解密算法模型的破译能力，我们从以下两个方面进行考虑：（1）算法破译的准确性：通过统计分析由全自动解密模型算法破译的多篇加密文章，得出密钥字母正确个数稳定在20个左右，密钥字母的正确率均高于80%，全文平均字母正确率稳定在96%；（2）算法破译密文的时间复杂度：首先结合算法三个模块程序的复杂度分析得，时间复杂度F(n)和密文总字母数n的关系为F(n)=(C2+2)n+C1，简记O(n)，其中C1,C2是依赖于字典库总词数的可变常数。其次因为模型算法只需要提取文章中前面部分单词，便可破译出≥24个密钥，文章中剩余单词量并不影响算法破译时间，所以文章越长，单位时间内的破译效率越高。综上所述，该模型能高效准确的解密出密文，算法运行速度快耗时极短，克服了传统频率分析法耗时长，运算效率不高的缺点。另外，我们还对模型的改进和推广方向以及优缺点进行了讨论。参赛队号:1386所选题目:B题参赛密码（由组委会填写）参赛队号#1386AbstractDecryptionmethodisfrequencyanalysis,buttheuseoftraditionalfrequencyanalysismethod,withlargecomputation,thecomputationtimeislong,shortcomingsandsoonneedtoomuchhumanintervention.Sothispaperproposesaninnovativedecryptionalgorithm,encryptionmethodofsinglelettertheencryptedcryptograph.Model1:Wehavetoimprovethetraditionalmethod,anewautomaticdecryptionmodelisestablished,notonlycansubstantiallyreducecomputingtime,andcanbeaccurateandefficientdecodingciphertext.Firstwehavethedataneededtomeasureoutthemodelofthemodel,theletterslengthof15to24longwordsdictionarylibrary1-8ofthedictionary,inthemodel1isdividedintothreesteps:(1)thefrequencyofcipherattackfirst,andthestatisticalfrequencyofsingleletters,doublelettercombinationsandgrouping,andthengroupedfrequencymatching,analysisofbasictodeterminethehighestfrequencyofthelettere,he,th,todeterminet,h,e,(2)longwordsonciphertextattacks,namelyinthecrackofasmallamountofhighfrequencylettersaftergenerationintotheciphertext,extractthelongestwordinlongwordsdictionarylibrarymatchinggraduallydecipheringsecretkeymoreletters.Becauseofthelongerthewords,thelessthenumber,soafterthesuccessofthematchingaccuracyishigher.(3)thelastwillbethekeyletterssubstitutioncipher,andtheciphertextwiththewordfortheunitofthescan.Matchthewordsinadictionaryinthelibraryonebyone,getthesimilarwords;Accumulatedeachsimilarwordmatchingletterssecretkeyagain,untiltherecordnumberofsecretkeyletter=24,eventuallytoeverysecretkeyletters,selectthehighestcumulativenumberofmatchingastheultimatesecretkey,outputthecompletekey.Verifiedbymulti-instancestatistics,thedecryptionalgorithmtodecipherthenumberofarticlesabout50000letters,itonlyneeds2.75s.Model2:Toevaluatethemodeladecryptionalgorithmdecodingabilityofthemodel,wefromthefollowingtwoaspects:(1)consideringtheaccuracyofthealgorithmdecoding;Testedmuchofthearticle,throughtheMatlabstatisticcanbeconcludedthatthekeyletterscorrectnumberstabilityin20,thekeyletterscorrectlyabout80%,averagelettersinfullaccuracyofabout96%(2)breakthetimecomplexityofcipheralgorithm.Thelessasthenumberofletters,decodingtimegrowswiththeincreaseofthenumberofletters.Whilethenumberoflettersafterreachingacertainthreshold,decodingtimetendstobestable.Becausemodelalgorithmonlyneedtoextractthepartialwordsinthearticletheamountofinformationthatcanbedecodedkey.Articletherestoftheworddoesnotaffectthealgorithmdecodingtime,sothelongerthearticles,perunittimedecodingefficiencyishigher.Tosumup,thismodelcanefficientlyaccuratelytodecrypttheciphertext,algorithmfasttimeshortly,overcomesthetraditionalfrequencyanalysismethodtime-consuming,thedisadvantageofoperationefficiencyisnothigh.Inaddition,wealsotheimprovementandpopularizationofdirectionaswellastheadvantagesanddisadvantagesofthemodelarediscussed.Keywords:Frequencyattacks，Timecomplexity，Singleletterencryption，Automaticdecipher参赛队号#138611.1背景一、问题重述当今社会处于信息时代，随着计算机互联网络的高速发展，整个世界被越来越紧密地联系在一起。资讯的发达在为人类社会带来巨大便利的同时，也产生了一系列严重的问题，信息安全就是其中突出的一个。由于网络中存储着许多重要、敏感数据，因此，信息安全已经越来越受到人们的关注。为确保信息的安全性，人们在技术上主要采用密码学的方法。密码学是研究如何进行密写及如何解密的学科,它是一个高度专业化的研究领域,对数据的传送和通信安全有着重大的意义。因此,作为一门新兴学科,引起了数学家和计算机工作者的日益关注。1.2问题的提出假设明文是由现代通常所使用的英语写成的。现在我们从题中所给数据库获取一些由单字母加密方法加密的密文。1.根据题目的要求建立合理的数学模型，设计一个解密的算法，可以自动化地实现破译密文。2.在确定算法并实施算法之后，设计一个衡量破译能力的标准，来评价破译算法的破译能力。二、模型假设①为了简化问题，本文假设密码表仅是针对26个字母的，每个单词之间的空格，以及标点符号仍然会保留。②在长单词攻击时，假设被攻击的长单词均为名词，因此不考虑动词因时态而发生的长度变化。（如动词ing形式和ed形式）③假设在模型一中双字母的低频组合忽略不计。三、符号说明符号符号说明f表示字母在英文语料库中出现的频率i表示26个字母按照字母表顺序的第i个字母表示密文转