2015第八届挑战赛一阶段优秀集含abcd特等b1071队题

单字母替单字母替换关键 字典树dfs算 优 对 树dfs算法。照明密文字母出现频率进行分析，得到频率分析算法的正确率为80%。对于字典树dfs算法，首先利用字典库中的单词构建一棵字典树，在深度优先搜索结果；当篇幅介于40-100时，可生成两个左右的结果，可通过人为直接判别出结果；当密文由不到十个词汇组成时，则根据密文所符合的构词规则会生成几个到几百个不定（填写参赛（填写所选题目 英要（选填（ 必须部分，选填可加分，加分不超 总分 Theresearchofmonoalphabeticcipherhasgreatinfluenceonthepasswordcracking.Thispaperstudiesthesimplemonoalphabeticcipherproblems,anddiscreteoptimizationmodelisestablishedandtheexhaustivealgorithm,frequencyysisalgorithm,DFSontrietreealgorithmaredesigned.Forexhaustivealgorithm,itrandomlyselectsonecorrespondingrelationshipfromallpossibleones,andthendecideswhetheritisakey.Ifthekeysatisfytherequirementthentheintextcanbeevaluated;Otherwiseselectsotherrulesofjudgment,whilethispaperisbasedonthecomputationalcomplexityofthealgorithm.Forfrequencyysisalgorithm,accordingtothesingleletterfrequencystatistics,thestatisticalrulesofEnglishword-formationandsyntax,yzeswiththeintextandciphertextletterfrequency,theaccuracyoffrequencyysisalgorithmcanreach80%.AsforDFSontrietreealgorithm,firstlybuiltatrietreeusingallthewordsinthedictionary,atthesametimeofthedepthfirstsearch,recordstheserialnumberofthecurrenttrietreenode,usingthepropertythataddinganewletter"x"cannotreachanyexistednodeofthetrietree,timelypruning--neversearchesapossibilitythatthenextletterofciphertextwordprocessingnowbedecryptedasletter"x".Throughtestingtheprogram,whentheciphertextismorethan100words,itcandirectlygeneratedtheuniqueresult;Whenthelengthisbetween40and100,cangeneratetwoorsoresults,whichcanbetoldbyhumandiscriminant;Whentheciphertextonlyconsistsofabouttenwords,accordingtoconformationtotherulesofword-formation,theciphertextwillgenerateseveraltohundredsofuncertainresults,thereforedrawingappropriateintextcanonlyberealizedbyhumanlaboring.Comparingallthethreealgorithmsondifferenttypesofciphertext,ciphertextbyfrequencyysisalgorithmissuitableforlargescalewhileDFSontrietreealgorithmisnotonlysuitablefortheciphertextoflargescale,butalsofortheciphertextofsmallscalebyonlyaddingasmallamountofartificialjudgment.Finally,thispaperassumesthatcombinedDFSontrietreealgorithmwithfrequencyysisalgorithm,lesshumanlaboringisneeded.PAGEPAGE4一、问题重述问题背景单字母替换的加密方法多种多样，时采取人工获取的密文准确性高，提高自动尝试求钥破译明文的技术可待研究。问题提出假设明文中单词是现代英语词典中通常使用的，本题假设表仅是针对26个字二、问题分析单字母替换规则是随机的，一共有26!种情况，对于随机替换情况需要做一步一步的优对于上述建立模型的方法，在设计算法求解过程中，的是26个字母中有不同适用范围对方法进行破译能力划分。更加贴近实际，并提供有效的单词数据库是本文的一大，通过查阅大量资料与文献，并进行适当的、合理的假设，对单字母替换的方式进行研究。[3]三、模型假设与假设说明假设三：密文没有时效性（即在设计算法时并不考虑运行时间） 四、模型建立与求解算法设计法、字典树剪枝算法[8]，利用C++等编译程序实现问题求解。间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有为描述模型原理，我们暂记密文字母空间1 s*）{a*,b*,,z*}，密文单词空间S2{w1*,w2*,,wn*}实际密文单词空间A{w1,w2,,wn}破译所得明文字母空间1m）{a,b,,z}，明文单词空间M2{w1,w2,,wn}，英文语料库单词空间{w1,w2,,wm}，其中mn,A。暂记目标函数为C（w），对应法则为j的mj视为sj*的最优解（1j26）。（上述符号只用于解释模型，并不通用于后文的算法设计等穷举算法单字母替换加密的普遍加密规则就是2626个字母。在未知字母之间对应规则的情况下，我们用暴搜法循环尝试。建立明文空间unsecured={A,B,C,D,E,F,G,H,...,X,Y,Z}，密文空间encrypted同样为26个字母，用for循环列举出所有的对应关系。运算，若获得的明文不正确，再假设第二次选取密文空间X,YY,Z11C置后，作为一个新的密文空间对密文的情况，我们通过计算可以得到一共有2C方法；再考虑明文空unsecured与密文空encrypted中字母替换规则中只有三个字母被替换的情况，例encrypted={A,B,C,D,...,V,W,Y,Z,X},22三个字母相互替换方法有3种，在此种情况下经过计算得出密文空间共有3*C3一正确的对应规则:算法进行到这里，我们要连接现代常用单词的数据库，按照所生成的33的假设是合理的如果加密规确，长单词的选取可以一次确定26个字母中许多字母ufhkqutkjpfqpfubepcngliubuzhkjkhkpqubthgpofctlzhqcnhgcqpuzhkjkhkpq,lqlurrakbjcrjkbekiuekbuhkjpcfhpzgbkzurqxkrr.kbhgpkficqhepbpfurncfihgpqpuzhkjkhkpqkbzrltphgpofctlzhkcbcnscfxqcnufh,hgpzfkhkzkqicnufh,hgpqhltacngkqhcfacnufh,ubthgpupqhgphkztkqqpikbuhkcbcnufhiuampzgufuzhpfkyptkbhpfiqcnikipqkq(khqfpofpqpbhuhkcbcnfpurkha),zciilbkzuhkcbcnpichkcb,cfchgpf频率分析算法由于穷举算法要对所有的秘钥进行尝试，有多达26！种可能性，运算次数多达约4.03*1026次，机器运行时间过长，因而根据英文在频率上的固有语言破绽，可以设计出根据搜索，我们得到了一份来及Algoritmy的字母频率统计资料另外还有康奈尔大学数学探索项目（MathExplorer’sproject）在统计40000个单词后也得到了大同小异的结果。牛津大学分析简明牛津词典词条后结果依然近序（如图6）。6我们记密文的字母元素空间为S，单词元素空间为SA，英文语料库元素空间为E，S（i）（i1,2,3）f(s，由假设知f(s为一个双射，任何S中的元素（AZ26个字通过SA与找E的对比，分析频率到正确的f(s)，即可视为成功了密文。而密文的检验则依靠SA（j）（j1,2,3）E中元素的对比来完成，我们知道，一除不正确的对应法则，最终得到正确破译的明文SA（k）（jk）。①单词首字母频率高至低排序TOAWBCDS,FMRHIYEGLNOJ,

ESTDNRYFLOGHAKMPU④三字母构词频率高至低排序the,and,for,are,but,not,you,all,any,can,had,was,one,our,out,day,get,has,him,his,how,man,new,now,old,see,two,way,who,boy,did,its,let,put,say,she,too,use第一步，对重复单词进行统计。可推理出现频率最高的三字母单词为the，这样我如向后推理发现错误，再将s4,s5的对应关系对调。第二步，根据步骤一，我们得到了the的对应关系，又由于在加密过程中符号保持问句引导词“how”的出现概率不好判别，而在特殊疑问句中，w开头的引导词出现的PAGEPAGE6f(s1)t，f(s2)h，f(s3)e，f(s4)a，f(s5) f(s6)w，f(s7)r，f(s8)o，f(s9)n，f(s10)第三步，此时我们有10最高概率的个已知对应，已经知道将近半数的秘钥规则。thcan,had,her,was,one,our,out,day,get,has,him,his,how,man,new,now,old,see,two,way,who,boy,did,itslet,put,say,shetoo,usean*d，*seu，a**（后两字母相同）找到l，*an找到c等。此对比过程可以重复进行，以找到的并不会要求检验到的每一个词的拼写构词都符合语料库，而是当错误率达到一定程度80%20%密文中是几个单词，重复的不计入数量统计。字典dfs算尝试使用密文里面的单词与单词表里的单词进行配对,得出密匙之后进行下一个hii这7个单词，可构建字典树如图7。ii图（7）abc，abcd，abd,bbcd，efg，hiiv的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。复进行直到所有节点都被为止。属于盲目搜索。,说明字典树里没有该单词,如果在就在该字母的下一级子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方（即不会加入该条替换关系，也不会继续向下搜索dfsufhkqutkjpfqpfubepcngliubuzhkjkhkpqubthgpofctlzhqcnhgcqpuzhkjkhkpq,lqlurrakbjcrjkbekiuekbuhkjpcfhpzgbkzurqxkrr.kbhgpkficqhepbpfurncfihgpqpuzhkjkhkpqkbzrltphgpofctlzhkcbcnscfxqcnufh,hgpzfkhkzkqicnufh,hgpqhltacnhgpgkqhcfacnufh,ubthgpupqhgphkztkqqpikbuhkcbcnufh.ufhiuampzgufuzhpfkyptkbhpfiqcnikipqkq(khqfpofpqpbhuhkcbcnfpurkha),pvofpqqkcb,zciilbkzuhkcbcnpichkcb,cfchgpfwlurkhkpq.结果为得出两种密钥。仔细比较两种加密规则，得知唯一的不同是：第一种加密方法把f加密为s,w加密为n，时则是把s替换成f，n替换成w;而第二种加密方法把f加密为n,w加密为s，时则是把s替换成w，n替换成f。由于两种后得到的每个“明文单词”正好都在单词表出现过，所以第一种出现许多ow，第二种许多of。但是，由of的使用频率显然ow高，故可以认2是所需明文的概率远远大于方案1。显然dfs算法可以搜出所有可能被加密成密文的原文，但是dfs算法不能对这一句话【siaazqlkba.vazoarfpbluaoar!】，搜出了245种方案。其中最正确的是这组【fleeatonce.Wearediscovered!】如果密文中的单词意外被改变10024随机抽取p%的单词，如果抽取的单词中没有被改变的错误单词，那么很大可能可26个字母的对应关系，且若所得对应关系唯一，则一定是答案；如果不唯随机了Max{ /抽取的单词个数，1000}次。art文本为例，任意改动其中一个单词p=70%X的程序可以运行出答案的那不出的可能性依然存在，因为如下有5条对应关系没有出来五、算法对比与选择dfs算dfsdfsdfsdfs算法可以说是本文所提及的三个算法中运行最快的算更为广泛。但是dfs算法对奇怪拼写，特有名词的程度比较低，换言之，该算法需三种算法在破译结果上的差异：结果的准确率是最高的，因为完整运行的穷举最终完成对秘钥所有可能性的尝试，条件下，一个穷举算法的完全运行需要长达1013年的时间。dfsdfs算法的运行时间是三种算法中最短的，输出的破译结40-50后的“have”2522种破译结果，若对加密后的“here”70多种结果，若是对加密后的“attract”2密文分类C不符合构词的结构的概率并不大，我们这里仅以密文篇幅的长短与A类对比分出BC算法选择分类，选择最优破译方案。ufhkqutkjpfqpfubepcngliubuzhkjkhkpqubthgpofctlzhqcnhgcqpuzhkjkhkpq,lqlurrakbjcrjkbekiuekbuhkjpcfhpzgbkzurqxkrr.kbhgpkficqhepbpfurncfihgpqpuzhkjkhkpqkbzrltphgpofctlzhkcbcnscfxqcnufh,hgpzfkhkzkqicnufh,hgpqhltacnhgpgkqhcfacnufh,ubthgpupqhgphkztkqqpikbuhkcbcnufh.ufhiuampzgufuzhpfkyptkbhpfiqcnikipqkq(khqfpofpqpbhuhkcbcnfpurkha),pvofpqqkcb,zciilbkzuhkcbcnpichkcb,cfchgpfwlurkhkpq.穷举算法：2实际上在得到这个结果时，我们已经可以认为我们得到了一个达标的破译结果，是一个我们所能接受的破译结果了。但是，这时的程序并没有停止运行，而这个人工判别可以接受的破译结果真正的准确性是没有数据支持的，因为这个算法的尝试是没有从结果的可能性进行考虑而排序的，所以说，第1次试探与第26！次试探的正确概率在理论上是相等的。理论上可知，只有我们得到所有26100%正确的破译结果，即使符合语法与构词规则的破译结果只有一个，我们也需要等到程序全部运行完毕才能得知。而一个穷举算法的实现程序的运行时间是我们所不能接受的上图是我们测试的10分钟试探的秘钥数量， 种，10分钟仅为程序运行全部时间7.486*10-18%从这个运行结果，我们可以得知，穷举法在理论上，完全运行后是可以得到最精准的破译结果的，但是实际上，我们并不能接受程序运行的等待时间，也并不希望计算机进行该算法所需的巨大运算量。另外，如果密文短小，得到的符合语料库资料的破译结果较多时，人工判别不可或缺。频率分析算法：0.023但是字典树分析算法对于样本密文的破译却出现了 种结果。这是由于样本密文的篇幅问题致的，样本密文只含有70词。经过测试与计算，我们得到一个大致结果，该算法在密文有40-50以上时，可以得到1到2种破译结果，但是在破译100词以上时，基本可以完美破译六、结AA选择字典树dfs算法与频率分析算法是优于穷举算法的。字典树dfs算法提供了更快的运算时间，破译结果也是可以认为基本精准的B类密文：B类密文属于频率分析算法所不适用的密文类型，所以在这里我们只考虑穷举算法与字典树dfs算法。由于密文简短，穷举的每次试探需要时间较短，且实际dfs算法在短小密文的破译上需要较多的人工选择来排除输出结果中的明所以，对于B类密文字典树dfs算法与穷举算法都是可取的，50词以上，由于已经达到字典树dfs算法的期望能过得到较少破译结果的密文结果，可以考虑字典树dfs算法C类密文：C类密文由其时效性，篇幅又并不很长，显然是运行时间最短的字典树dfs算法最优。但是若此算法不能破译，我们可以选择穷举算法，取其第一个达到我们七、模型的改进根据算法分析与，我们可以看出，字典树dfs算法的运用范围最为广泛，并且具由于该模型没有使用频率分析等方法，所以可以轻松地从英语推广到其他任何语八、模型的评价模型的优点 模型的缺点《单字母替换及实例》，http 《03-密码学基础（二）-古典密码算法》，http 《 cipher》 /scbsolvr.html，2015-4- ，《基于频率分析的代替破译方法及其程序实现》，《福建电脑》，2006年09期《字典树模板及解析》 /link?url=ELyoWB2lDKhAYdFNPA1-字母频率百，2015-4-附附录1//下文中替换规a->ba被替换usingnamespacecharFILEFILEFILE#defineMAXWN //密文中单词个数的上struct{charlex[30];//单个单词长度最大为int //该单词的长int //该单词在密文中是第几个出现int //10表示是单booloperator<(constnode&oth)const//{if(lenn!=oth.lenn)returnelsereturn 24}a[MAXWN];//存密26intF[MAXWN];//F[i]iF[i]个位置，排序后得到，intword_num;//intdictionary_num;//字典中单词总数，由实际从字典文件读入确#define //字典树中结点总个数的上intf[MAXTN][26];//f[i][j]表示若在编号为i的结点，再经过一个字母jintv[MAXTN]; //v[i]=1表示从根结点出发停留在字典树编号为i的结点，顺次经过的字母组int //字典树中结点总个数，主要在构建字典树时用voidadd(char{intinttmp=0;0的根节for(inti=0;i<len;{if(f[tmp][s[i]-'a']==- //如果从tmp出发经过字母s[i]到达的结点还没有f[tmp][s[i]- //新建之，编号为tmp=f[tmp][s[i]-'a'];//经过一个字母s[i],tmp v[tmp]=1;//最后停留在编号为tmp是一个字典里的单4647intvis[26];//a->b(0<=a<26,0<=b<26),vis[a]=b；vis[a]==-1a->?(a被替换成什换成b当前未知)49intstartx,endx;//当前指定的要求的单词为从a[beginx,endx]里所有单50intsuccessful_sol;//成功的方案void{/*如果有替换规则a->b,b->c,c || vvbc for(inti=0;i<26; for(inti=0;i<26;fprintf(f3,"|for(inti=0;i<26;for(inti=0;i<26;for(inti=0;i<word_num;{if //如果是标点符号直接输出标点符 //否则对每个字母后输{ if(i>0&&a[F[i-fprintf(f3," fprintf(f3,"%c",ans[a[F[i]].lex[j]- 88voiddfs(intx,inty,int//当前已到从第x的单词的第y位，第x个单词后停留在字典树的第tmp号结{if(x==endx+1) //第endx个单词也完成，能找到一种替换规则所有被指定的{ if if //到第x个单词的第len(x)位，即已知道第x个单词各字母由什么母加密而{if(v[tmp])//如果按这种规则后的第x个单词是字典中的单 //从第x+1个单词的第0位开始，停留在字典树的0号根节} ////如果单词x的前y-1位加上i构不成任何单词的前缀，则不可能i->单词x的y{if(vis[i]==-1&&ans[a[x].lex[y]-'a']==-//i->??->xy{ 密，当前停留结点编号做相应改vis[i]=-ans[a[x].lex[y]-'a']=-}{ 127intvoid{ 第i个140voidread_passage()//从密文文件中读入所有以空白字符隔开的字符串，处理掉标点符号后以单词形式存a数组{charwhile{ if(cc==' if elseif ififif {ifif iffor(inti=0;i<word_num; 172void{memset(f,255,sizeof(f));//字典树初始 //字典树初始 //字典树初始//从字典文件读入所有的单词，并构建一棵字典while{ 188int{intsize=128<<//G++扩栈asm("movl0,%esp\nr"(p));//G++//如果编译器是C++，应该注释掉上面三句，并在这个程序<cstdio>前加一 //只读方式打开字典文 //只读方式打开密文文f3=fopen("ans.txt","w");//只写方式打开文文 endx=word_num-212附录二//只包含前一个程序所没有的部#definepercent dfs_time;/