b1071队2015第八届挑战赛一阶段优秀论文集1071队B题

参赛队号#1071 第八届“认证杯”数学中国 数学建模网络挑战赛 承诺书 第八届“认证杯”数学中国 数学建模网络挑战赛 承诺书 我们仔细阅读了第八届“认证杯”数学中国数学建模网络挑战赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们接受相应处理结果。 我们允许数学中国网站()公布论文，以供网友之间学习交流，数学中 国网站以非商业目的的论文交流不需要提前取得我们的同意。 我们的参赛队号为：我们的参赛队号为：1071 参赛队员参赛队员(签名签名) ： 队员 1：王怡璐 队员 2：张苗苗 队员 3：姚驍玲 参赛队教练员参赛队教练员 (签名签名)：郑少春 参赛队伍组别（例如本科组）：本科组 ：郑少春 参赛队伍组别（例如本科组）：本科组 参赛队号#1071 第八届“认证杯”数学中国 数学建模网络挑战赛 编 号 专 用 页 第八届“认证杯”数学中国 数学建模网络挑战赛 编 号 专 用 页 参赛队伍的参赛队号：（请各个参赛队提前填写好）：1071 竞赛统一编号（由竞赛组委会送至评委团前编号）： 竞赛评阅编号（由竞赛评委团评阅前进行编号）： 参赛队号#1071 2015 年第八届“认证杯”数学中国 数学建模网络挑战赛第一阶段论文 年第八届“认证杯”数学中国 数学建模网络挑战赛第一阶段论文 题目单字母替换式密码 关 键 词字典树 dfs 算法优化对比 摘要 单字母替换式密码的研究对密码破解有很大的影响， 本文研究了简单的单字母替换 式密码破译的问题，建立了离散优化模型，首先设计了穷举算法、频率分析算法、字典 树 dfs 算法 穷举算法、频率分析算法、字典 树 dfs 算法。 对于穷举算法，从所有可能的对应关系中随机选出一种，然后判断其是否为密钥， 若是其是所求密钥则得出明文，否则选取其他规则进行进行判断，本文从运算复杂度等 因素对该算法进行分析。 对于频率分析算法， 根据单字母高频统计表， 按照英文构词与语法的统计规则入手， 按照明文和密文字母出现频率进行分析，得到频率分析算法解密的正确率为 80%。 对于字典树 dfs 算法，首先利用字典库字典库中的单词构建一棵字典树一棵字典树，在深度优先搜索 的同时记录当前搜索确定的单词前缀在字典树中对应的结点结点，利用该结点新加某字母 x 的不可到达字典树已构建好的任一结点的性质， 及时剪枝不再搜索密文下一位字母 解密后为某字母 x 的可能性。通过程序测试，当密文篇幅大于 100大于 100 单词时，可直接生成直接生成 结果；当篇幅介于 40-10040-100 时，可生成两个左右两个左右的结果，可通过人为直接判别出结果； 当密文由不到十个词汇不到十个词汇组成时， 则根据密文所符合的构词规则会生成几个到几百个不定几个到几百个不定 的结果，此时想要得出合适的明文需要依靠人力完成。 然后本文将三种算法通过对不同类型的密文不同类型的密文进行对比， 得到频率分析算法适合大篇 幅的密文，字典树剪枝算法不仅适合求出大篇幅的密文，也可以通过加上少量人工的判 断可以求出较短篇幅的密文。 最后，本文假设结合频率分析算法与字典树 dfs 算法，预测对于短篇幅的密文的人 工判别的次数将大量减少。 参赛队号:1071 参赛密码 （由组委会填写） 参赛队号#1071 所选题目:B题 英文摘要（选填） （此摘要非论文必须部分，选填可加分，加分不超过论文总分的 5%） The research of monoalphabetic cipher has great influence on the password cracking. This paper studi es the simple monoalphabetic cipher problems, and discrete optimization model is established and the exhaustive algorithm, frequency analysis algorithm, DFS on trie tree algorithm are designed. For exha ustive algorithm, it randomly selects one corresponding relationship from all possible ones, and then d ecides whether it is a key. If the key satisfy the requirement then the plaintext can be evaluated; Other wise selects other rules of judgment, while this paper is based on the computational complexity of the algorithm. For frequency analysis algorithm, according to the single letter frequency statistics, the stat istical rules of English word-formation and syntax, analyzes with the plaintext and ciphertext letter fre quency, the accuracy of frequency analysis algorithm can reach 80%. As for DFS on trie tree algorith m, firstly built a trie tree using all the words in the dictionary, at the same time of the depth first search, records the serial number of the current trie tree node, using the property that adding a new letter x c annot reach any existed node of the trie tree, timely pruning - never searches a possibility that the nex t letter of ciphertext word processing now be decrypted as letter x . Through testing the program, wh en the ciphertext is more than 100 words, it can directly generated the unique result; When the length i s between 40 and 100, can generate two or so results, which can be told by human discriminant; When the ciphertext only consists of about ten words, according to conformation to the rules of word-format ion, the ciphertext will generate several to hundreds of uncertain results, therefore drawing appropriate plaintext can only be realized by human laboring. Comparing all the three algorithms on different typ es of ciphertext, ciphertext by frequency analysis algorithm is suitable for large scale while DFS on tri e tree algorithm is not only suitable for the ciphertext of large scale, but also for the ciphertext of small scale by only adding a small amount of artificial judgment. Finally, this paper assumes that combined DFS on trie tree algorithm with frequency analysis algorithm, less human laboring is needed. 参赛队号#1071 1 一、问题重述一、问题重述 1.1 问题背景问题背景 单字母替换密码的加密方法多种多样，解密时采取人工解密获取的密文准确性高， 但效率低，一旦遇到复杂的加密密文，人工可解性几乎为零。随着计算机技术的发展， 提高自动尝试求解密钥破译明文的技术可待研究。 1.2 问题提出问题提出 假设明文中单词是现代英语词典中通常使用的，本题假设密码表仅是针对 26 个字 母的，每个单词之间的空格，以及标点符号仍然会保留。在设计算法时，为了判断明文 是否正确，需要与数据库中的单词作比较。现在我们获取了一些由单字母加密方法加密 的密文，需要我们 （1）建立合理的数学模型，设计算法，来自动化地破译密文。为了使问题简单化。 （2）由于设计的不同算法计算量不同，适用范围不同，设计一个衡量破译能力的标准， 来评价破译算法的破译能力。 二、问题分析二、问题分析 本题是研究单字母替换密码问题，替换规则多种多样，较为常见的如凯撒密码，仿 射密码，摩斯密码等，但常见的替换规则均有特殊性，不能代表普遍的替换规则。我们 在本题中以随机单字母替换规则建立数学模型，设计算法，并进一步求解。 对于篇幅很大的密文，我们可以用频率分析的方法，根据密文中字母的频率分布推 测加密规则。但是当获取的密文篇幅不是很大时，光凭借频率分析是不足以破译全部密 文的。往往要经过对可能出现的词汇及字母组合进行分析判断，才能完整地破译密文。 单字母替换规则是随机的，一共有 26!种情况，对于随机替换情况需要做一步一步的优 化，使得选取随机的方式更为简单，从而达到大大减少运算量的目的。 对于上述建立模型的方法，在设计算法求解过程中，难以避免的是 26 个字母中有 少量字母的替换规则出错， 尤其是密文篇幅少且单词长度短， 构成正确单词的解有多个， 导致明文的正确度降低。于是，我们需要对所建立的几个模型进行对比，根据不同算法 的不同适用范围对解密方法进行破译能力划分。 此外，本题是个实际问题，现实中需要考虑的因素远远多于题目本身，如何使模型 更加贴近实际，并提供有效的单词数据库是本文面临的一大困难，通过查阅大量资料与 文献，并进行适当的、合理的假设，对单字母替换密码的解密方式进行研究。3 三、模型假设与假设说明三、模型假设与假设说明 3.1 模型假设 假设一：根据题目要求，假设我们得到的密文所用的加密密码表仅针对 26 个字母进行 加密，空格与标点仍然保留。 假设二：设计算法时，假设被加密的明文中并没有（或者数量极少）专有名词和奇怪拼 写。 假设三：密文没有时效性（即在设计算法时并不考虑运行时间）。 3.2 假设说明 对于假设一属于题目要求，为简化算法而存在。 对于假设二、三是为设计算法而提出的，我们可以将其视作密文的一般情况，实际上， 参赛队号#1071 2 假设二、三也符合多数密文的实际状况。对于二三的特殊情况，需要根据实际情况更改 单词库和部分规则。 四、模型建立与求解四、模型建立与求解 4.1 算法设计算法设计 本文将将字母替换破译问题建模为离散优化问题，并设计了穷举算法、频率分析算 法、字典树剪枝算法8，利用 C+等编译程序实现问题求解。 本文的求解算法是从组合优化的思想入手的， 组合优化问题的目标是从组合问题的 可行解集中求出最优解，通常可描述为：令=s1，s2，sn为所有状态构成的解空 间，C(si)为状态 si 对应的目标函数值，要求寻找最优解 s*，使得对于所有的 si，有 C(s*)=minC(si)。 由于密文的破译过程实际上是一个循环试探或者按可能性推理的过程， 破译的目的 是使得密文字母根据秘钥所得明文字母构成的单词最符合英文语料库， 我们可以将其化 为组合最优问题，密文与明文都分成字母空间与单词空间，通过破译出的秘钥的对应法 则得到明文字母空间为密文空间的解空间，两字母空间构成一一对应关系，而最优解的 选择，则依靠字母排列组成的明文单词空间与英文语料库数据的对比，语法规则即为目 标函数， 找到的使得密文单词空间的目标函数值最接近语料库数据的最优解即为正确秘 钥 1。 为描述模型原理，我们暂记密文字母空间z*,b*,a*,*s1S）（，密文单词空间 wn*,w2*,w1*,2S， 实际密文单词空间,2,1Anwww破译所得明文字母 空间,m1Mzba）（，明文单词空间wn,w2,w1,2M，英文语料库单词空 间wm,w2,w1,，其中Anm,。暂记目标函数为）（wC，对应法则为 ）（261m) *( jji jsf。我们要找的就是正确的 f 使得）（）（ ii wminCwC，此时 的 j m 视为*sj的最优解）（26j1。 （上述符号只用于解释模型，并不通用于后文的算法设计等） 4.2 穷举算法穷举算法 单字母替换加密的普遍加密规则就是 26 个字母分别随机的对应与其排列顺序不同 的 26 个字母。在未知字母之间对应规则的情况下，我们用暴搜法循环尝试。建立明文 空间 unsecured=A,B,C,D,E,F,G,H,.,X,Y,Z，密文空间 encrypted 同样为 26 个字母，用 for 循环列举出所有的对应关系。 假设第一次选取密文空间 encrypted=A,B,C,D,.,X,Y,Z,即明文未加密， 进行下一步 运 算 ， 若 获 得 的 明 文 不 正 确 ， 再 假 设 第 二 次 选 取 密 文 空 间 encrypted=A,B,C,D,.,V,W,X,Z,Y,即在明文空间unsecured的26个字母中选出两个字母 X,Y 互换位置成为 Y,Z，如图 1 参赛队号#1071 3 图 1 仅有两个字母替换 作为新生成的密文空间，进行下一步运算。在明文空间中随机选取两个字母互换位 置后，作为一个新的密文空间对密文解密的情况，我们通过计算可以得到一共有 2 26 C 种 方法； 再考虑明文空间 unsecured 与密文空间 encrypted 中字母替换规则中只有三个字母 被替换的情况，例如 encrypted=A,B,C,D,.,V,W,Y,Z,X,如图 2 图 2 三个字母相互替换 三个字母相互替换方法有 3 种，在此种情况下经过计算得出密文空间共有 3 26 C*3中 选取方法。以此类推，在未得到正确明文之前，继续选取 4 个字母相互替换，5 个字母， 6 个字母.一直到 26 个字母相互替换。 正确的对应规则正确的对应规则:算法进行到这里，我们要连接现代常用单词的数据库，按照所生成的 对应规则确定的明文中单词，检索数据库中是否有与之相同单词，我们通常选取较长单 词检索，如图 3 图 3 生成明文单词与单词库中单词的对比 单词中任意一个字母一旦出现不匹配的情况，此种加密规则便被排除，然后再生成下一 种加密规则。在检索过程中，选用的单词越长，判断加密规则是否正确用时越短，这样 的假设是合理的如果加密规则正确，长单词的选取可以一次确定 26 个字母中许多字母 的加密方式；如果加密规则错误，可以快速排除这种加密规则。 通过穷举法模型，设计算法，便可破译我们所得到的密文。现在我们用一段密文: ufh kq u tkjpfqp fubep cn gliub uzhkjkhkpq ubt hgp ofctlzhq cn hgcqp uzhkjkhkpq, lqlurra kbjcrjkbe kiuekbuhkjp cf hpzgbkzur qxkrr. kb hgpkf icqh epbpfur ncfi hgpqp uzhkjkhkpq kbzrltp hgp ofctlzhkcb cn scfxq cn ufh, hgp zfkhkzkqi cn ufh, hgp qhlta cn hgp gkqhcfa cn ufh, ubt hgp upqhgphkz tkqqpikbuhkcb cn ufh. ufh iua mp zgufuzhpfkypt kb hpfiq cn ikipqkq (khq fpofpqpbhuhkcb cn fpurkha), pvofpqqkcb, 参赛队号#1071 4 zciilbkzuhkcb cn pichkcb, cf chgpf wlurkhkpq. 通过程序运行，可得到下图明文，见图 4 图 4 图 4 中，Plaintext 表示输出的结果，key 表示对应的规则，Number of keys checked 表示测试的次数 然而穷举法的运算量大，得出结果的时间很有“碰运气”的意思，如果得出最符合 语法的结果恰好是第 26！次，那么该算法的运行时间将是不可接受的。所以我们进一步 考虑有没有除了穷举法模型外的其他算法。 4.3 频率分析算法频率分析算法 由于穷举算法要对所有的秘钥进行尝试，有多达 26！种可能性，运算次数多达约 26 10*03 . 4 次，机器运行时间过长，因而根据英文在频率上的固有语言破绽，可以设计出 频率分析算法。 根 据 搜索，我们得到了一份来及 Algoritmy 网站的字母频率统计资料 。 图 5（左图为字母频率统计表，右图为按频率高低排序的统计表） 另外还有美国康奈尔大学数学探索项目（Math Explorers project）在统计 40000 个 单词后也得到了大同小异的结果。 牛津大学出版社分析简明牛津词典词条后结果依然近 参赛队号#1071 5 似。 除却字母频率，英文中单词的出现频率也有一定的统计规律，根据英国国家语料库 （BNC）中 86800 个最常用单词的统计，我们得到了一个单词由出现频率从高到低的排 序（如图 6）。 图 6 单词频率排序图 根据英文中如上所述特点，再加上本题中保留空格与符号的简化条件，在假设截取 的密文为符合现在英文语法及构词，密文篇幅长度足够进行频率分析，且标点符号多样 的情况下，进行算法设计。 我们记密文的字母元素空间为S，单词元素空间为SA，英文语料库元素空间为E， 密 文 对 应 明 文 元 素 空 间 为）（3 , 2 , 1Sii， 单 词 元 素 空 间 为 ）（3 , 2 , 1jASj，由于我们考虑的是破译密文，所以记S到）（i S 的映射法则即 秘钥为) s (f，由假设知，) s (f为一个双射，任何S中的元素（即由 A 至 Z 共计 26 个字 母）都唯一的对应）（3 , 2 , 1Sii中的一个元素（亦即 A 至 Z 共计 26 个字母）， 通过SA与找E的对比，分析频率到正确的) s (f，即可视为成功破解了密文。而密文的 检验则依靠）（3 , 2 , 1jASj中的元素与E中元素的对比来完成，我们知道，一 份正确破译的明文应该是符合英文的语法逻辑与构词方法的，所以，我们可以以此来排 除不正确的对应法则，最终得到正确破译的明文）（kjkAS。 这里，我们从英文构词与语法的统计规则入手，搜索到如下统计规则： 单词首字母频率高至低排序T, O,A, W, B, C, D, S, F, M, R, H, I, Y, E, G, L, N, O, U, J, K 单词末字母频率高至低排序 E, S, T, D, N, R, Y, F, L, O, G, H, A, K, M, P, U, W 单词中同字母连用高频方式 SS, EE, TT, FF, LL, MM, OO，DD 三字母构词频率高至低排序 the, and, for, are, but, not, you, all, any, can, had, her, 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 单字母情况只有 I 和 a 问句中特殊疑问词只有 where,what,why,when,who,whose,which,how 此后仍有数个可观察统计到的规则，在此不再一一赘述。 对于得到的密文，我们可以设计算法： 第一步，对重复单词进行统计。可推理出现频率最高的三字母单词为 the，这样我 们就确定了密文元素空间中 3 个元素与 t,h,e 的对应关系， 同时还可以推理所有的单字母 出现的单词只有 I 与 a 两种对应关系，此处不妨记 s1,s2,s3 对应 t,h,e,先记 s4,s5 对应 a,i， 如向后推理发现错误，再将 s4,s5 的对应关系对调。 第二步，根据步骤一，我们得到了 the 的对应关系，又由于在加密过程中符号保持 不变，我们可以找到“？”对应的句子，如果其对应结果为*he*e，*he*，*hat，*h*e， 则我们可以找到与 w,r,o,n,s 的对应密文，此处由于有一般疑问句引导词“has”与特殊疑 问句引导词“how”的出现概率不好判别，而在特殊疑问句中，w 开头的引导词出现的 概率远大于 how， 所以只考虑 w 开头的引导词的对应关系， 且由于引导词部分拼写已知， 单词长度已知，可以更大几率降低将一般疑问句误判。 参赛队号#1071 6 至此，我们已经经过了多次比对（实际上没一步骤并不一定只比对一次），至多可 以得到 ssfnsfosfrsfwsf isfasfesfhsftsf )10()9()8()7()6( )5()4()3()2() 1( ， ， 。 第三步，此时我们有 10 最高概率的个已知对应，已经知道将近半数的秘钥规则。 我们可以回到步骤一种的对三字母单词的统计中，“the, and, for, are, but, not, you, all, any, can, had, her, 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”，我们可以根据 an*找到 d，*se 找到 u， a*（后两字母相同）找到 l，*an 找到 c 等。此对比过程可以重复进行，以找到更多的 对应规则。 第四步，经过步骤三，我们已经得到了大部分的对应对应规则，后面我们可以继续 利用其它对应英语习惯来加以推理，也可以直接进行暴力搜索穷举出明文结果。 注意：由于实际我们截获的密文在第二、三步中可能并不是完全覆盖，所以实际上 我们进行了更多的推理步骤，但是原理相同，在此不多赘述。 最终，我们通过循环，找到了完整的对应法则) s (f，由假设，密文篇幅较长，所以 各种根据英文习惯所得到的统计规则在破译中的准确度比较高， 又因为算法一直是在与 英文语料库进行比较，想要程序的继续进行是需要得到的）（3 , 2 , 1jASj中元 素属于E的， 所以我们最后得到的），）（1,2,3kjkAS中的k并不会很多， 在大 部分情况下只有一个（因为长篇幅明文均符合英文构词规则的情况并不会很多）。 另外，由于密文中可能会出现一些专有名词与奇怪拼写，所以算法需要有一定的容 错率，且算法在经过多次的比对步骤找到多个或者单个对应规则，继而进行全文破译后 并不会要求检验到的每一个词的拼写构词都符合语料库，而是当错误率达到一定程度 时， 一般我们可以认为当正确率达到 80%即错误率未达到 20%时认为破译出的明文是合 理的。这个我们可以再程序设计的最开端，用自定义的比例来计算这个容错率在当前密 文中是几个单词，重复的不计入数量统计。 4.4 字典树字典树 dfs 算法算法 尝试使用密文里面的单词与单词表里的单词进行配对,得出密匙之后进行下一个 单词的配对直到密文结束或所有密匙位置都被确定.而字典树存在的意义是剪枝，将 大部分不可能的替换规则剔除掉，然后再用 dfs 解密，找到一种替换规则解密所有被 指定单词。 字典树，又称单词查找树，Trie 树，是一种树形结构，典型应用是用于统计，排 序和保存大量的字符串，此处只用于保存大量字符串。它有三个基本性质，根节点不 包含字符，除根节点外每一个节点都只包含一个字符，从根节点到某一节点，路径上 经过的字符连接起来， 为该节点对应的字符串， 每个节点的所有子节点包含的字符都 不相同。故在本次解密模型中，字典树用于存放所选单词库中的所有单词。6 在本次解密模型中，字典树用于存放所选单词库中的所有单词，从根结点按单词 中字母出现顺序依次往下走来保存整个单词库。 假设有 abc， abcd， abd, b, bcd， efg， hii 这 7 个单词，可构建字典树如图 7。 参赛队号#1071 7 图（7）由 abc，abcd，abd, b, bcd，efg，hii 七个单词构建的字典树 字典树的优点是：利用字符串的公共前缀来节约存储空间，最大限度的减少无谓 的字符串比较，查询效率比较高。 剪枝，在搜索算法中优化中，就是通过某种判断，避免一些不必要的遍历过程， 形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问 题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。 dfs 是深度优先搜索算法 （Depth-First-Search） ， 是沿着树的深度遍历树的节点， 尽可能深的搜索树的分支。 当节点 v 的所在边都己被探寻过， 搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。 如果还存在未被发现的节点， 则选择其中一个作为源节点并重复以上过程， 整个进程 反复进行直到所有节点都被访问为止。属于盲目搜索。 要查一种替换规则是否是所求密钥， 只需将密文中的单词按此种替换规则替换成 “明 文单词”并检验此“明文单词”是否在字典树中。首先看“明文单词”的第一个字母 是不是在字典的第一层，如果不在,说明字典树里没有该单词,如果在就在该字母的下 一级子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的 方法继续迭代，直至检验完“明文单词”的最后一个字母。若此“明文单词”并不存 在于字典树中，则证明其所对应的替换关系不可能为密钥，替换关系被直接剔除（即 不会加入该条替换关系，也不会继续向下搜索）；若此“明文单词”的最后一个字母 仍满足字典树，则说明这种替换方式有可能是正确的，进入下一个单词的 dfs 搜索。 这个步骤可以将时间复杂度极大地缩短。 i 参赛队号#1071 8 输入密文（一共 70 个单词）： ufh kq u tkjpfqp fubep cn gliub uzhkjkhkpq ubt hgp ofctlzhq cn hgcqp uzhkjkhkpq, lqlurra kbjcrjkbe kiuekbuhkjp cf hpzgbkzur qxkrr. kb hgpkf icqh epbpfur ncfi hgpqp uzhkjkhkpq kbzrltp hgp ofctlzhkcb cn scfxq cn ufh, hgp zfkhkzkqi cn ufh, hgp qhlta cn hgp gkqhcfa cn ufh, ubt hgp upqhgphkz tkqqpikbuhkcb cn ufh. ufh iua mp zgufuzhpfkypt kb hpfiq cn ikipqkq (khq fpofpqpbhuhkcb cn fpurkha), pvofpqqkcb, zciilbkzuhkcb cn pichkcb, cf chgpf wlurkhkpq. 解密结果为： 此处所用单词库是收录绝大多数常见英语单词的 11 万个单词的单词库。 得出两种密钥。仔细比较两种加密规则，得知唯一的不同是：第一种加密方法把 f 加密 为 s,w 加密为 n，解密时则是把 s 替换成 f，n 替换成 w;而第二种加密方法把 f 加密为 n,w 加密为 s，解密时则是把 s 替换成 w，n 替换成 f。由于两种解密后得到的每个“明 文单词”正好都在单词表出现过，所以第一种出现许多 ow，第二种许多 of。 但是，由于单词 of 的使用频率显然比 ow 高，故可以认为方案 2 是所需明文的概率 远远大于方案 1。显然 dfs 算法可以搜出所有可能被加密成密文的原文， 但是 dfs 算法不 能从中筛选出一种或几种最接近英语文本的原文。当密文短时，这种现象更为明显。比 如对这一句话【siaa zq lkba. va zoa rfpbluaoar!】解密，搜出了 245 种方案。其中 最正确的是这组【flee at once. We are discovered!】 参赛队号#1071 9 4.5 如果密文中的单词意外被改变如果密文中的单词意外被改变 假设密文中单词在输入或截取时某个或某些字母出现多余或遗漏、字母顺序混乱等 情况时，考虑一下方案 此处仍采用上述过程所用的 11 万单词的单词库。 通过大量测试 100 个单词的英语小 短文可以发现，单词量为 100 时基本就可以得到至少 24 个字母的对应关系。 随机抽取 p%的单词，如果抽取的单词中没有被改变的错误单词，那么很大可能可 以得到所有 26 个字母的对应关系，且若所得对应关系唯一，则一定是答案；如果不唯 一后文会提供处理方法。 上述反复随机过程（附录 X（x 最后要替换成数字）的程序是 随机了 Max5000000/抽取的单词个数，1000 次。 随机这么多次时， 还可以处理得到所有 26 个字母的对应关系不唯一时 （甚至是得到 不足个字母对应关系）的处理方法。 将所有字母的对应关系视作 26 的置换群并保存下 来，统计它们出现的频率，出现频率最高的对应关系一定最接近答案。以前面给出那段 art 文本为例，任意改动其中一个单词，选择 p=70%，附录 X 的程序可以运行出答案的 那个置换群，并还原出一定程度文本。 需注意，被任意改动的单词是还原不出来的，与此同时，其他单词有部分字母还原 不出的可能性依然存在，因为如下有 5 条对应关系没有出来 结论：如果想要从多种方案中智能提示出最有可能的方案，必须使用频率优化或其他方 法。 五、算法对比与选择五、算法对比与选择 由于不同算法都各有优缺，在运行时间，计算次数，破译准确度，破译适用范围等 方面都具有一定的局限性， 所以我们要针对这几个方面对我们所设计的 3 个算法进行对 比。 5.1 三种算法在原理上的异同。 相同点： 三种算法在原理上的异同。 相同点： 三种算法都运用到了循环结构，无论是穷举算法，频率分析算法还是字典树 dfs 算 法，都运用了试探性循环。从本质上讲，三种算法都考虑秘钥的随机性，选取不同的方 式进行与英文语料库的对比从而得到结果。根本上来说，算法原理都是离散优化模型。 区别对比：区别对比： 穷举算法：穷举算法顾名思义，是对 26！种秘钥进行逐次尝试，然后将破译结果与 语料库进行比对。 频率分析算法： 频率分析算法实质上是一种根据英文破绽的来按秘钥准确概率由高 至低尝试的优化穷举算法。 相比穷举算法其最大的进步就是在发现英文破绽的基础上引 参赛队号#1071 10 入了概率上的分析，极大的提高了进行少次穷举得出结果的概率，从而减少破译时间。 字典树 dfs 算法：字典树 dfs 算法的思想也来自穷举法，但是通过单词去重，将单 词长至短排列，选取长单词用来保证每次试探循环可以确定更多的字母对应，又利用公 共前缀与语料库进行对比检索，极大的缩短了穷举的时间。 5.2 三种算法在应用上的异同： 相同点： 三种算法在应用上的异同： 相同点： 由于三种算法的设计都基于语料库数据， 所以如果密文的正确明文中含有大量特殊 代号，奇怪拼写，或者导入算法的实现程序中的语料库数据不足，都可能造成破译无法 正确实现。 穷举算法：穷举算法在应用上的困难主要集中在破译时间的不稳定上，所以对算法 的程序实现，我们采用程序边运行边输出结果的方式，输出每一次试探的破译结果，然 后与上一次试探结果进行对比，保留或更新破译所得明文。但是基于穷举算法实现破译 的程序的运行时间很长，即使出现了比较合理的结果也不会停止程序的运行。 频率分析算法： 频率分析算法在应用上的困难主要集中在可破译的密文范围具有比 较大的局限性。 本文所采用的频率分析算法并不是最原始的基于英文字母频率统计而设 计的频率分析破译算法，而是考虑了英文语法及构词后，进行优化，考虑了词汇频率的 算法设计。但是仍然需要一定的篇幅才能有效减少试探过程。 字典树 dfs 算法：字典树 dfs 算法可以说是本文所提及的三个算法中运行最快的算 法，虽然此算法仍对密文篇幅有所要求，但是其要求要远低于频率分析算法，所以应用 更为广泛。但是 dfs 算法对奇怪拼写，特有名词的容忍程度比较低，换言之，该算法需 要一个相对穷举算法，频率分析算法更详尽的语料库。不过，在密文篇幅较短时，该算 法会输出不只一种破译结果，用频率分析可以对破译结果进行分析处理。 5.3 三种算法在破译结果上的差异：三种算法在破译结果上的差异： 穷举算法：穷举算法虽然运行时间与计算次数上劣于另外两种算法，但是它的破译 结果的准确率是最高的，因为完整运行的穷举法会最终完成对秘钥所有可能性的尝试， 但是，等待一个穷举算法完全运行的时间长度是我们所不能接受的，在 cpu 为奔腾 4 的 条件下，一个穷举算法的完全运行需要长达 1013 年的时间。 频率分析算法： 频率分析算法由于具有容错率， 所以输出的破译结果可能不只一种， 运行时间在可以接受的范围内，但是并不能说迅速。而且需要对输出的结果进行人工判 别分析。尤其在密文篇幅不足够长的时候，输出结果较多，需要人工筛选。 字典树 dfs 算法：字典树 dfs 算法的运行时间是三种算法中最短的，输出的破译结 果在语料库数据覆盖较大时相对而言比较精准，但是经过计算，在密文篇幅仅有 40-50 词时， 输出的破译结果会有 1-2 个， 在密文篇幅达到 100 以上时可以基本达到精准破译。 另外，该算法的输出结果数量也与英语的构词有关，如密文只有一个单词时，若对加密 后的“have”进行破译，则会得到 2522 种破译结果，若对加密后的“here”进行破译，则会 得到 70 多种结果，若是对加密后的“attract”进行破译，则只有 2 种破译结果。 5.4 密文分类密文分类 本文为了便于对算法进行评定， 将密文按自身特点分为 3 类， 分别记为 A 类、 B 类、 C 类： A 类密文：此类密文具有算法最希望的密文特点，密文篇幅长，被加密的明文符合 语法规则，词汇常规，符合英文字母频率与词汇频率。 B 类密文：因为考虑到密文的实用性，所以被加密成密文的明文中出现奇怪拼写与 不符合构词的结构的概率并不大，我们这里仅以密文篇幅的长短与 A 类对比分出 B 类 密文，即 B 类密文文本篇幅较短，故而英文字母频率与词汇频率的统计意义并不十分明 参赛队号#1071 11 显。 C 类密文：根据密文中有一大部分具有比较强的时效性，当解密时间过长时，破译 就失去了其功用，所以我们假设破译 C 类密文的最大需求是破译速度。 5.5 算法选择算法选择 基于 4.2.1 的密文分类，我们针对密文的 3 种常见情况对本文设计的三种算法进行 分类评级，选择最优破译方案。 首先，我们先对 3 种算法的运行结果进行统计分析。 在这里，我们以如下密文的运行为例进行运行分析： ufh kq u tkjpfqp fubep cn gliub uzhkjkhkpq ubt hgp ofctlzhq cn hgcqp uzhkjkhkpq, lqlurra kbjcrjkbe kiuekbuhkjp cf hpzgbkzur qxkrr. kb hgpkf icqh epbpfur ncfi hgpqp uzhkjkhkpq kbzrltp hgp ofctlzhkcb cn scfxq cn ufh, hgp zfkhkzkqi cn ufh, hgp qhlta cn hgp gkqhcfa cn ufh, ubt hgp upqhgphkz tkqqpikbuhkcb cn ufh. ufh iua mp zgufuzhpfkypt kb hpfiq cn ikipqkq (khq fpofpqpbhuhkcb cn fpurkha), pvofpqqkcb, zciilbkzuhkcb cn pichkcb, cf chgpf wlurkhkpq. 穷举算法：穷举算法： 对于这段密文的破译，穷举算法需要注意到 2 个时长与运算量。 得出如下破译结果的时间为 1.93 秒，试探的秘钥个数为 38806 个。 实际上在得到这个结果时，我们已经可以认为我们得到了一个达标的破译结果，是一个我们所 能接受的破译结果了。但是，这时的程序并没有停止运行，而这个人工判别可以接受的破译结果真 正的准确性是没有数据支持的，因为这个算法的尝试是没有从结果的可能性进行考虑而排序的，所 以说，第 1 次试探与第 26！次试探的正确概率在理论上是相等的。理论上可知，只有我们得到所有 26！ 次的结果中所有符合语法及构词规则的后， 我们才可以进过人工判断找出 100%正确的破译结果， 即使符合语法与构词规则的破译结果只有一个，我们也需要等到程序全部运行完毕才能得知。 而一个穷举算法的实现程序的运行时间是我们所不能接受的。 上图是我们测试的 10 分钟试探的秘钥数量，为 30193498 种，10 分钟仅为程序运行全部时间的 %10*486 . 7 18- 。 从这个运行结果，我们可以得知，穷举法在理论上，完全运行后是可以得到最精准的破译结果 参赛队号#1071 12 的，但是实际上，我们并不能接受程序运行的等待时间，也并不希望计算机进行该算法所需的巨大 运算量。另外，如果密文短小，得到的符合语料库资料的破译结果较多时，人工判别不可或缺。 频率分析算法：频率分析算法： 字典树 dfs 算法：该算法的运行速度是三种算法中最快的，建立字典树只需要大约 0.06 秒，而后的搜索由于其随机性，并不能给出确切时间。但是我们队范例密文进行破 译，仅用了 0.023 秒的时间。 但是字典树分析算法对于样本密文的破译却出现了 2 种结果。这是由于样本密文的篇幅问题导 致的，样本密文只含有 70 词。经过测试与计算，我们得到一个大致结果，该算法在密文有 40-50 词 以上时，可以得到 1 到 2 种破译结果，但是在破译 100 词以上时，基本可以完美破译。 由此可知，该算法的破译结果是全面的，并且破译时间远少于穷举算法。但是该算法的 结果输出并不唯一，即对结果的判选需要人工进行，当文本很小时，得到的结果会有很 多，缺乏准确性。 六、结论六、结论 基于上述分析与密文分类，我们针对不同密文对算法进行评级如下： A 类密文：A 类密文满足了所有算法的期望，所以在这里主要考虑破译结果的准确 性与破译时间，选择字典树选择字典树 dfs 算法与频率分析算法是优于穷举算法的。字典树算法与频率分析算法是优于穷举算法的。字典树 dfs 算 法提供了更快的运算时间，破译结果也是可以认为基本精准的 算 法提供了更快的运算时间，破译结果也是可以认为基本精准的，其中，破译的过程是有 技巧的，假如被加密的原文中有一定的奇怪拼写与专业名词，此算法可以跳过这类词汇 检索其他词汇来进行秘钥搜索， 而被加密原文中的奇怪拼写与专业名词则会影响到密文 中词频与字母频率的准确性，从而影响频率分析算法求得结果的运行时间与准确度。 所以， 对于 A 类密文， 我们认为： 字典树 dfs 算法优于频率分析算法优于穷举算法。 参赛队号#1071 13 B 类密文：B 类密文属于频率分析算法所不适用的密文类型，所以在这里我们只考 虑穷举算法与字典树 dfs 算法。由于密文简短，穷举的每次试探需要时间较短，且实际 上需要 26！ 次才能得到我们能认可的结果的可能性并不大， 所以我们可以尝试运行穷举 算法。而字典树 dfs 算法在短小密文的破译上需要较多的人工选择来排除输出结果中的 明显错误结论，它的运行时间远小于穷举算法，但是人工选择的难度难以界定。 所以，对于 B 类密文字典树 dfs 算法与穷举算法都是可取的，50 词以上，由于已经 达到字典树 dfs 算法的期望能过得到较少破译结果的密文结果，可以考虑字典树 dfs 算 法。 C 类密文：C 类密文由其时效性，篇幅又并不很长，显然是运行时间最短的字典树 dfs 算法最优。但是若此算法不能破译，我们可以选择穷举算法，取其第一个达到我们 可接受标准的输出结果加以人工完善。 七、模型的改进七、模型的改进 根据算法分析与评级，我们可以看出，字典树 dfs 算法的运用范围最为广泛，并且 具有诸多优点，所以我们着重对此算法加以优化改进，与应用推广。但是仅仅使用该算 法可能能搜出多种可能的原文，在密文长度较短时该问题尤其显著。可以通过进一步引 入频率分析等方法来检索出最有可能的原文。 由于该模型没有使用频率分析等方法，所以可以轻松地从英语推广到其他任何语 言。另外，该模型还可由单字符替换推广到双字母或三字母替换，只要将两个或三个相 邻字符视为一个整体字符即可。不过该模型不容易推广至多字母替换，因为多字母替换 时利用字