第八届认证杯B题论文,三等奖

1、参赛队号#1124第八届“认证杯”数学中国数学建模网络挑战赛承 诺 书我们仔细阅读了第八届“认证杯”数学中国数学建模网络挑战赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们接受相应处理结果。我们允许数学中国网站()公布论文，以供网友之间学习

2、交流，数学中国网站以非商业目的的论文交流不需要提前取得我们的同意。 我们的参赛队号为：参赛队员 (签名) ：队员1： 队员2：队员3： 参赛队教练员 (签名)： 参赛队伍组别：本科组第八届“认证杯”数学中国数学建模网络挑战赛编 号 专 用 页参赛队伍的参赛队号：参赛队号#1124竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：2015年第八届“认证杯”数学中国数学建模网络挑战赛第一阶段论文题 目 B题 替换式密码 关 键 词 破译 凯撒密码 埃特巴什码 希尔密码 加密 摘 要：本文针对单字母加密的密文破译进行研究，并且针对26个英文字母的单字母加密进行

3、研究。由于将密文直接译为明文有一定难度，所以我们由反方向入手，以多个加密方式为研究基础，并在研究透彻后进行反推，较好的解决了题目所提的问题。我们的研究以MATLAB7.0为软件基础，以Win7系统的计算机为运行环境。在研究单字母加密时，我们参考了古典密码学和密码学原理等知识，发现希尔加密与我们问题中的加密方式有较高的关联度，于是我们仔细研究了这种单字母加密的加密方法，并编辑出了相应的算法程序，对其进行反复计算以及多次修改，得到由明文在某种固定的对应法则下转换出密文的程序，然后保证对应法则不变，对程序进行反推，得到密文在固定法则下的程序中被破译为明文的算法程序。我们在研究希尔算法时，我们发现这种

4、算法有一定的局限性，他只能破译在自己的加密方法下加密的密文，这使得破译人员在破译密文时的工作量增大，首先要判断密文的加密类型，然后才能使用相应的对应法则进行破译，为了减少工作量，增强算法的运算范围，使其有更强的实用性，我们将多种算法进行融合重组，我们的算法可以破译这几种加密方式所转换出的密文，而且算法上也做了相应的变化。我们的新算法诞生后，在投入实际运行之前，进行一系列的运算和检验，以确保新算法在实际运行中拥有较大的可信度，且通过检验判断出新算法的破译能力的好坏程度。于是我们决定从新算法的发展基础入手，建立一个衡量标准，即利用希尔密码和埃特巴什码和凯撒密码的算法同时作为衡量标准，检验标准为：当

5、新算法的破译结果与衡量标准的三种算法的破译结果相同，则认为新算法的破译程度较高；当新算法的破译结果与衡量标准的其中一种算法的破译结果相同，则认为新算法的破译程度为中等；当新算法的破译程度与衡量标准的破译结果都不相同时，则认为新算法的破译程度低。经过反复比较，多次检验，发现新算法的破译标准是比较高的，即可信度较高，在投入实际应用中，它适用范围较原始的其他算法更广泛，并且可以减少破译人员的工作量，相对提高了破译的效率。我们在新算法设计完成并检验之后，还对其进行了相应的扩展和改进。以增加其实用性。参赛密码 （由组委会填写）参赛队号: #1124 所选题目: B 题英文摘要窗体顶端In th

6、is paper, single-letter decipher encrypted ciphertext study and conduct research for the 26 letters of the alphabet one letterencryption. Since the ciphertext directly translated i

7、nto plain there are some difficulties, so we start from the opposite direction,to the basis for the study of multiple encryption, and after a thorough study of anti-

8、push, a better solution to the problem raised by the topic.Our study MATLAB7.0 software-based, computer systems running Win7 environment. In examining single-letter encryption, we 

9、refer to the classical principles of cryptography andcryptographic knowledge, discovery Hill encryption and the encryption of our problems have a higher correlation, so we carefully stu

10、died this single letter encrypted encryption method, and edit out the corresponding algorithm program, its repeated calculations and several revisions, obtained from the plaintext  into

11、 the corresponding fixed under certain rules of procedure of the ciphertext, and then ensure that the corresponding rule change, the program counter- push to get the ciphertext in&

12、#160;the program under the fixed rules to be decipheredplaintext algorithm program.Hill when we study algorithms, we found that this method has some limitations, he can deciph

13、er the encryption methods in their own encrypted ciphertext, which makes deciphering the staff workload while deciphering ciphertext increases, first To determine the ciphertext encrypt

14、ion type, then you can use the appropriate corresponding rules to decipher, in order to reduce the workload and enhance the scope of the algorithm operation, it has&

15、#160;a more practical,we will carry out a variety of fusion algorithm restructuring, our algorithm These types of encryption can decipher the ciphertext converted, but the algorith

16、m also made correspondingchanges.After the birth of our new algorithm, before being placed into actual operation, carried out a series of calculations and tests to ensure 

17、;that the new algorithm has a greater credibility in theactual operation, and judged by examining the ability of the new algorithm to decipher the good and bad degree.

18、60;So we decided to re-start the development of basic algorithms, to create a measure,namely the use of passwords and algorithms Hill Atbash code and the Caesar cipher, as

19、0;measured at the same time, test standards: When deciphering the results of the new algorithm and metrics the same algorithm to decipher the results of the three, i

20、sconsidered a high degree to decipher the new algorithm; decipher the results when the same measure in which the results of an algorithm to decipher the new algorith

21、m, the new algorithm considersthe degree to decipher medium; when the new algorithm The standard measure of the degree to decipher decipher the results are notthe same,&#

22、160;it is considered a low degree to decipher the new algorithm.After repeated comparison, the number of tests and found that thenew algorithm to decipher the standard is

23、 relatively high, that confidence is high, put into practice, it is compared with the original scope of other algorithms more widely, and can reduce the work to decipher&

24、#160;staff amount, the relative increase efficiency decipher.After we completed and tested in the new.一、问题重述1.1 问题背景历史上有许多密码的编制方法。较为简单的是替换式密码，也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言，最简单的形式是单字母替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者另外的符号。较为复杂的形式是以多个

25、字母为一个单元，整体替换成其它的字符。这个映射方法被称为密码表，拿到密码表的人就能够将密文破译成明文。单字母替换加密是在古代就使用过的一种加密方法，但由于其容易被破解，所以在现代需要加密的场合已经很少使用。单字母替换加密的破译方法有频率分析等。这种密码和破译方法在小说中也经常提到，例如爱伦·坡的金甲虫和柯南·道尔在福尔摩斯系列故事归来记中的“跳舞小人”。但当获取的密文篇幅不是很大时，光凭借频率分析是不足以破译全部密文的。往往还要熟知该种语言的人，经过对可能出现的词汇及字母组合进行分析，才能完整地破译密码。1.2 问题的提出假设明文是由现代通常使用的英语写成的。现在我们获取了

26、一些由单字母加密方法加密的密文。请你建立合理的数学模型，设计一个算法，来自动化地破译密文。并设计一个衡量破译能力的标准，来评价破译算法的破译能力。为了问题简单起见，我们假设密码表仅是针对26 个字母的，每个单词之间的空格，以及标点符号仍然会保留。在设计算法时，如果需要，可以参考英文语料库的数据，例如免费的COCA1等相关资料。二、问题解读2.1问题信息整理首先我们从所给的问题中知道以下三点信息：（1） 本论文研究的是单字母加密的问题，即密文和明文进行一对一的替换，不存在多个字符对应一个字符或是一个字符对应多个字符的情况，虽然实际的加密过程中不只是存在一一对应的情况，但在本论文中，仅需考虑单字母

27、加密的情况；（2） 本论文中所研究问题的对象主要是针对26个英文字母，并且除了字母以外的其他成分全都原样保留；（3） 在设计算法的同时我们要清楚其运作原理，以便我们在后期设计该算法的衡量标准。2.2题目的思考对于这样的问题我们已经知道这是加密问题中一种被简化的情况了，所以我们先参考单字母加密在传统意义上的一些方法，例如希尔密码、凯撒密码、埃特巴士密码等加密方式。考虑到即使是单字母加密，可能存在的加密方式也并不是单一的，可能是简单的移位加密，也可能是通过不同的组合来选出最优的明文结果。所以我们就要想到，我们的算法是不是能够包含我们上述的不同的加密方式，能够使密文被成功且正确的翻译为真实意义的明文

28、。在建立衡量我们所设计的算法破译密文水平的标准时，我们就可以利用我们以上提到的加密方式进行检验，再判断算法的破译程度的好坏。3、 模型建立3.1模型雏形我们的模型是以希尔密码的加密方式为基础，是运用基本矩阵论原理进行密文和明文的替换。Lester S. Hill于1929年提出的一种密码体制。设是被定义为一正整数，希尔密码的主要思想是利用线性变换方法，不同的是这种变换是在矩阵上运算。每个字母当作26进制数字： 一串字母当成维向量，跟一个的矩阵相乘，再将得出的结果模26。而我们要注意的是用作加密的矩阵（即密匙）必须是可逆的，否则就不可能译码，只有矩阵的行列式和26互质，才是可逆的。为了贴合我们所

29、学知识，我们的算法将以MATLAB软件为载体进行编辑和运行。3.2模型雏形的启发我们可以从希尔密码的加密方式中了解，该种算法的运行方式是建立在以矩阵为基础的行列式运算中的，所以我们在设计算法时，也可以采用这样的运算形式，一来矩阵的行列式运算是我们所能熟练掌握的知识成分，二来相比于其他的运算方式例如微分方程的运算，矩阵的行列式运算较为简易，同时也不易出错，方便使用和理解。我们在设计破译密文变为明文的过程中，如果直接想要得到密文翻译成明文的算法难度比较大，所以我们应该换一个思考方式，先将不同加密方式的明文到密文的转化分析清楚，在可行的情况下尽可能的让其变为我们所要求得算法的反向算法。这样，我们模型

30、建立的算法不仅贴近问题，而且还能使我们设计算法时更加方便，同时容错度也会大大降低。3.3模型假设（1） 假设模型中：元素属于的方阵模可逆的充要条件是：和没有公共素数因子，即和互素；（2） 假设模型中问题都满足算法中所设计的对应法则；（3） 假设实验对象是26个英文字母，在转换时其他变量不做改变；（4） 假设该算法将明文转化成密文后和我们实际问题所求的算法互为可逆算法；（5） 假设在面对此类问题时，所用的实验仪器和软件环境与设计本算法时均相同。3.4符号系统及对应法则 设明文,密文，密钥为上的阶可逆方阵，则 （1）希尔密码的对应法则：表一：字母ABCDEFGHIJKLMASCII65666768

31、697071727374757677表值12345678910111213字母NOPQRSTUVWXYZASCII78798081828384858687888990表值141516171819202122232425263.5模型算法设计（1）明文的加密过程：1、选择一个密钥矩阵，确定密钥是否可逆，如若密钥不可逆，则无法完成希尔密码的转换。2、利用上表的对应法则，将明文转换为相应的表值，然后将转化后的数值进行分组，每个分为一个组，不足个补充到个。3、利用此加密公式：密文，即可得到相应密文。注：此地的mod26，是将得到的数值，将其对26求余，为所求的余数。4、将得到的值，查表，即可知对应的密

32、文。(本论文以我爱人民我爱华夏英文大写首字母为明文进行操作检验）（2）密文的解密过程：若要得到明文，显然只需要将我们如何计算密文的方法倒推回去即可，但是此时的公式为 ， （2）显然第一步即是求 。一个一般的 阶方阵可逆的充要条件为 但在模 26 意义下矩阵可逆与一般的矩阵可逆有所不同记整数集合， 为一正整数，模 可逆定义如下：定义1：对于一个元素属于集合 的 阶方阵，若存在一个元素属于集合的方阵，使得 称 为模 可逆，为的模 逆矩阵，记为。的意义是，每一个元素减去 的整数倍后，可以化成单位矩阵。例如： 定义2：对的一个整数，若存在的一个整数，使得，称为的模倒数或乘法逆，记作。可以证明，如果与无

33、公共素数因子，则有唯一的模倒数(素数是指除了 1 与自身外，不能被其他非零整数整除的正整数)，反之亦然。例如， 利用这点，可以证明下述命题：命题：元素属于的方阵模可逆的充要条件是，和没有公共素数因子，即和 互素。显然，所选加密矩阵必须符合该命题的条件，才能够得到最优解，即：1、选择一个密钥矩阵 确定密钥是否可逆，如若密钥不可逆，则无法完成希尔密码的转换。2、先计算 的值，在左乘密文矩阵，即可得到明文的矩阵形式3、查表，找出表中对应的数值的字母，此时得到的即是明文。【1】（针对此算法，利用明文转换成密文的密钥，得到明文为我爱人民我爱华夏的英文大写首字母）3.6新算法设计在现实当中，希尔加密并不是

34、全能的，所以我们在此基础上进行了一些改进和拓展，现建立如下模型：（1）模型一 密钥， 即未知，且。以 为例，由此可知： （3）检验密钥的可行性： ，当 时，密钥 可行，由此可得： 由上述的算法，只要对上述的密钥进行相应的数值带入，即可得到埃特巴什码。 （2）模型二 ， （4）检验密钥的可行性： 当时，密钥可行，由此可得： 检验密钥可行性： 即 则由上述的算法（1）和（2），对密钥进行相应的数值带入计算，就可以得到凯撒算法的结果。 统而言之，对于本论文设计的新算法，只要对密钥公式(3)、(4)进行相应的数值带入，不仅可以得到希尔密码，还可得到艾尔巴什码和凯撒密码。3.7模型运行及结果 （1）改进

35、前的结果与分析 图一：改进前的明文转换成密文图二：改进前的密文转换成明文由上述的结果就可以了解到，本论文以我爱人民我爱华夏的英文首字母为明文得到了相应密文，在将此密文带入到密文转换为明文的程序中，得到了上述的明文。（2） 改进后的结果与分析图三：改进后的明文转换成密文图四：改进后的密文转换成明文 由上述的结果证实了本论文结果的可行性，本论文由新的算法，不仅破译了我们原基础上的希尔密码，还可以根据密钥矩阵，破译出埃特巴什码和凯撒密码，从而说明了本论文设计的算法是可行的，并且有较高的可信度。并且在实际应用中，使得破译工作的效率有了相应的提高。四、模型检验4.1模型检验的必要性虽然我们的算法是建立在

36、已经存在的单字母加密体系之上，但是我们为了提高该算法在实际操作中的可行性，我们必须对算法进行输入检查、运行调试以及结果检验。其中，最核心的问题便是关于结果的检验，检验结果以判定该算法的破译程度的好坏，对该模型在日后的实际运行中提供了重要的依据，让我们对该算法的可信度有一个较为明确的了解。4.2检验标准我们的算法是建立在希尔加密以及埃特巴什码算法的原理之上，所以我们可以通过这两种加密方式的算法对我们的新算法进行检验，标准如下：（1） 若新算法的运行结果与希尔加密以及埃特巴什码加密的程序运行结果相同，则其破译能力记为“高”，此时表示该算法译出的明文可信度高；（2） 若新算法的运行结果与希尔加密以及

37、埃特巴什码加密的程序运行结果的其中一种相同，则其破译能力记为“中”，此时表示该算法译出的明文可信度一般；（3） 若新算法的运行结果与希尔加密以及埃特巴什码加密的程序运行结果都不同，则其破译能力记为“低”，此时表示该算法译出的明文可信度低。4.3实际检验结果假设密文为“”，明文为“”，用新算法以及检验标准中的算法分别得到希尔算法和艾尔巴什码的最终结果，不仅如此，还可以通过对密钥矩阵的改变，得到凯撒密码，从而认为此算法拥有较高的可信度。五、模型推广与改进5.1模型的推广我们所的的新算法在本论文中仅是针对26个英文字母进行破译，但是在本论文中所用的算法，不仅单纯的可以求解一种密码，在实际运用中，根据

38、问题所需，设计出不同的密钥，同时求解希尔密码，凯撒密码和埃特巴什码。但是在投入实际运作后，我们还应当编制更多密文和明文的对应法则，即在前文模型假设中被忽略的成分。因此综合分析，本算法的适应性相对来说，是比较广泛的。5.2模型的改进我们在运算中发现算法在运行时有时会发生错误，经检验后发现是因为一些符号疏漏导致的，对此我们进行了严密的检验，并进行了改进。在算法方面，因在运行时会涉及到加密方式的不同所要选择的算法不同，我们对此进行了改进，设计了我们的新算法，初始算法仅是以了希尔加密算法为基础，建立埃尔巴什码加密算法和凯撒算法的模型，得到这两种加密方式的明文。简而言之，以此新的算法为基础，我们就可以求

39、解得到上述的三种算法。从理论出发，这在算法的设计上是一种继承，也是一种创新；从实际出发，它提高了破译密码的使用性，使得破译人员的工作效率有了相对的提高。六、参考文献1 冯登国，密码学原理与实践（第3版），北京：电子工业出版社，20092 吴世忠 祝世雄 张文政，应用密码学（第二版），北京：机械工业出版社，20143 胡向东 魏琴芳，应用密码学教程，北京：电子工业出版社，20054 薛山，MATLAB基础教程，北京：清华大学出版社，20115 马小婷，深入简出密码学，北京：清华大学出版社，20126 麦克康奈尔，代码大全（第二版），北京：电子工业出版社，20067 孙祥，MATLAB7.0基础教

40、程，北京：清华大学出版社，20058chenliwuxia,exp6古典密码与破译,七、附录附录一：明文转换成密文function hilldisp('输入密钥(矩阵)的维数')n=input('')disp('输入密钥(矩阵,按行输入)')key=input('')d=det(key) %求矩阵的行列式?if d=0 error('密钥矩阵不可逆，无法实现Hill密码');ende=input('输入明文?n','s') %e=messagem=size(e); %第一个元素是矩阵

41、的行数，第二个元素是矩阵的列数m=m(2);if mod(m,n)=0 error('输入错误，明文长度应为矩阵维数的倍数')endx=char(e)-64;i=1;while i<m+1 B=x(i:i+n-1)' a=key*B; A(i:i+n-1)=a' i=i+n;endfor i=1:m if A(i)>26 A(i)=mod(A(i),26); end A(i)=A(i)+64;endstr=char(A)fprintf('%s',str)附录二：密文转换成明文function hilldisp('输入密钥(矩阵

42、)的维数')n=input('')disp('输入密钥(矩阵,按行输入)')key=input('')d=det(key) %求矩阵的行列式?if d=0 error('密钥矩阵不可逆，无法实现Hill密码');ende=input('输入密文?n','s') %e=messagem=size(e); %第一个元素是矩阵的行数，第二个元素是矩阵的列数m=m(2);z=26;while size(key)=2 2key=input('输入一个2×2的矩阵，格式：a11 a12

43、;a21 a22: ')enda=det(key);bb=key;if gcd(z, a)=1disp('该矩阵不可逆')else for i=1:z if mod(a*i, z)=1 antkey=i; endendastar=key(2,2) -key(1,2);-key(2,1) key(1,1);invaa=mod(antkey*astar,z);endif mod(m,n)=0 error('输入错误，明文长度应为矩阵维数的倍数')endx=char(e)-64;i=1;while i<m+1 B=x(i:i+n-1)' a=in

44、vaa*B; A(i:i+n-1)=a' i=i+n;endfor i=1:m if A(i)>26 A(i)=mod(A(i),26); end A(i)=A(i)+64;endstr=char(A)fprintf('%s',str)附录三：改进后的明文转换成密文function hilldisp('输入密钥(矩阵)的维数')n=input('');e=input('输入明文?n','s') %e=messagem=size(e); %第一个元素是矩阵的行数，第二个元素是矩阵的列数m=m(2);if mod(m,n)=0 error('输入错误，明文长度应为矩阵维数的倍数')endx=char(e)-64;A=ones(1,m);key=ones(2,2);B=ones(2,2);i=1;while i<m key(1)=(x(i+3)*(x(i+1)*x(i+2)-x(i+3)*x(i)-x(i+2)*(x(i+1)*x(i+3)-x(i+2)*x(i)/(x(i)*(x(i+1)*x(i+2)-x(i+3)*x(i); key(3)=(