遗传算法在密码学中的应用毕业论文.doc

遗传算法在密码学中的应用摘 要遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，它是一种利用遗传学发展的手段，即选择、交叉和变异构成对问题解答的算法。其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题。密码学是研究编制密码和破译密码的技术科学。密码分析是研究密码体制的破译问题，即破译者试图在不知道加密密钥的情况下，从截取到的密文恢复出明文消息或密钥。从密码学发展来看，可分为古典密码和现代密码。古典密码即是以字符为基本加密单元的密码。古典密码学主要有两大基本方法：替换密码和置换密码。本文基于遗传算法的基本思想，给出了一种对古典密码学中的替换密码进行密码分析的方法，并验证该方法的有效性。本文首先通过随机获得的一个密钥对一段文章加密为密文，该密钥即为真正的密钥。遗传算法的搜索空间由种群中的个体组成，种群中的每个个体代表一个密钥，根据每个个体对该密文进行解密，以英文字母出现的频率对解密后的明文进行分析，利用遗传操作使这些密钥不断的进化，与真正的密钥越来越接近。【关键词】遗传算法，替换密码，密钥，密文，密码分析The Application of Genetic Algorithm in CryptographyChen Zhaojun(School of mathematics, physics and information, Zhejiang Ocean University 316004)AbstractGenetic algorithm is a kind of random search algorithm based on biological natural selection and natural genetic mechanism. It is a kind of algorithm to resolve problems using genetics, such as selection, crossover and mutation. Its advantages lie in its application of the complex and nonlinear problems which traditional search method cant solve. Cryptography is a science studying the preparation and deciphering of code. Cryptanalysis is to study the deciphering cryptography issues, namely to decipher the encryption key from the interception of the cipher text to restore a specific message or key. Due to the development of cryptography, codes can be classified into two categories: classical codes and modern codes. Classical code is code taking character as basic unit of encryption. Classical cryptography can be talked in two basic methods: the password replacement and password substitution. This thesis based on the ideas of genetic algorithm presents us cryptanalysis in replacing the password by classical cryptography, and the verification of the effectiveness.In this paper, first, we encrypt cipher text by a randomly obtained encryption key, which is the real key. The searching space of genetic algorithm consists of the population of individuals. In the population, each individual is taken as a key. Decrypt the cipher text by individual. Analyze the cipher text through the frequency of the letters, and make the keys continuous evolution by using the genetic manipulation and getting closer and closer to the real key.【Keywords】genetic algorithm, replace password, key, cipher text, cryptanalysis目录摘 要IABSTRACTII1 概述11.1选题背景及意义11.2研究现状11.3研究内容22密码学简介32.1密码的发展历程32.2密码的组成42.3密码学的基础知识42.4几种简单的古典密码42.4.1滚桶密码42.4.2.掩格密码52.4.3凯撒（Caesar）密码52.5加密方法53遗传算法简介及步骤63.1遗传算法简介63.2编码方法73.2.1二进制编码方法73.2.2格雷码编码方法83.2.3浮点数编码方法83.2.4符号编码方法83.3适应度函数83.4选择算子93.4.1比例选择93.4.2最优保存策略93.4.3确定式采样选择93.4.4无回放随机选择93.4.5无回放余数随机选择93.4.6排序选择93.5交叉算子103.5.1单点交叉103.5.2双点交叉和多点交叉113.5.3均匀交叉113.5.4算术交叉113.5.5部分匹配交叉113.6变异算子123.6.1基本位变异123.6.2均匀变异123.6.3边界变异133.6.4非均匀变异133.6.5高斯变异134基于遗传算法的密码分析方法144.1染色体编码和初始种群产生144.2适应度函数的确定与计算154.3选择154.4交叉164.5变异174.6解密175数据分析185.1群体大小的设定185.2种群进化代数的设定195.3交叉概率的设定195.4变异概率的设定206 总结21参考文献22附录一23附录二24251 概述1.1选题背景及意义遗传算法（Genetic Algorithm简称GA）是利用种群的遗传学原理发展而成的，它是一种利用遗传学发展的手段，即遗传（选择），重组（交叉）和突变（变异）构成对问题解答的算法。遗传算法的基本思想：保持一群知识结构，其中的知识结构代表着对目前问题可能的解答。而这些知识结构的集合就相当于生物学中的种群。而种群通过遗传变异而进化，可获得最优化的解答、或者达到学习和检测的目的。从搜索角度看，遗传算法具有许多独特的优点：不必非常明确描述问题的全部特征，通用性和鲁棒性强，能很快适应问题和环境的变化；对领域知识依赖程度低，不受搜索空间限制性假设的约束，不必要求连续性、可导或单峰等。从多点进行搜索，如同在搜索空间上覆盖的一张网，搜索的全局性强，不易陷入局部最优；具有隐并行性，非常适合于并行计算1。密码技术是信息安全技术的核心，它主要由密码编码技术和密码分析技术两个分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议，以满足对数据和信息进行加密或认证的要求。密码分析是研究密码体制的破译问题，即破译者试图在不知道加密密钥的情况下，从截取到的密文恢复出明文消息或密钥。这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展2。随着人工智能的不断发展成熟，与人工智能以及统计学等学科结合使得密码分析学在进行密钥搜索时变得更加有效。因此，在基于实际应用为目的的项目研究中，引入遗传算法作为自适应全局优化概率算法，极大的提高了密码分析的效率。本文就是基于遗传算法的基本思想，给出了一个基于遗传算法进行密码分析的一种方法，并验证了该方法的可行性。1.2研究现状目前遗传算法的应用越来越广泛，比如在煤气管道控制，防避导弹控制，机器人控制等控制领域进行智能识别控制，在图像处理中进行模式识别和特征抽取，进行机器人的路径规划，在信号处理中进行滤波器设计，在人工神经网络中进行权值训练和网络结构生成。密码学最初主要用于军事方面，但随着社会发展，数字信息日益增多，特别是随着互联网的发展，密码技术已经从外交和军事领域走向公开，且已发展成为一门结合数学、计算机科学、电子与通信、微电子等技术的交叉学科。使用密码技术不仅可以保证信息的机密性，而且可以保证信息的完整性和确定性，防止信息被篡改、伪造和假冒。如今，计算机网络环境下，信息的保密性、完整性、可用性和抗抵赖性,都需要采用密码技术来解决。目前人们将密码理论与技术分成两大类，一类是基于数学的密码理论与技术，包括公钥密码、分组密码、序列密码、认证码、数字签名、Hash函数、身份识别、密钥管理、PKI技术、VPN技术等3；另一类是非数学的密码理论与技术，包括信息隐藏、量子密码、基于生物特征的识别理论与技术等。1.3研究内容本文首先通过随机给出的一个密钥对明文进行加密，获得密文；然后利用遗传算法来对密文进行分析。具体步骤如下：一、利用英文中的26个字母作为编码，产生由26个字母不重复出现且长度为26的个体（即密钥）。并由此形成种群。二、通过遗传操作搜索问题解。三、用实例验证利用遗传算法进行密码分析的有效性。2密码学简介密码学是研究编制密码和破译密码的技术科学。密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。进行明密变换的法则，称为密码的体制。指示这种变换的参数，称为密钥4。变明文为密文，称为加密变换；变密文为明文，称为解密变换。2.1密码的发展历程密码学在公元前400多年就早已经产生了，正如破译者一书中所说“人类使用密码的历史几乎与使用文字的时间一样长”。密码学的起源的确要追溯到人类刚刚出现，并且尝试去学习如何通信的时候，为了确保他们的通信的机密，最先是有意识的使用一些简单的方法来加密信息，通过一些（密码）象形文字相互传达信息。接着由于文字的出现和使用，确保通信的机密性就成为一种艺术，古代发明了不少加密信息和传达信息的方法。例如我国古代的烽火就是一种传递军情的方法，再如古代的兵符就是用来传达信息的密令。就连闯荡江湖的侠士，都有秘密的黑道行话，更何况是那些不堪忍受压迫义士在秘密起义前进行地下联络的暗语，这都促进了密码学的发展。事实上，密码学真正成为科学是在19世纪末和20世纪初期，由于军事、数学、通讯等相关技术的发展，特别是两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛的用于军事情报部门的决策。例如在希特勒一上台时，德国就试验并使用了一种命名为“谜”的密码机，“谜”型机能产生220亿种不同的密钥组合，假如一个人日夜不停地工作，每分钟测试一种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完，希特勒完全相信了这种密码机的安全性。然而，英国获知了“谜”型机的密码原理，完成了一部针对“谜”型机的绰号叫“炸弹”的密码破译机，每秒钟可处理2000个字符，它几乎可以破译截获德国的所有情报。后来又研制出一种每秒钟可处理5000个字符的“巨人”型密码破译机并投入使用，至此同盟国几乎掌握了德国纳粹的绝大多数军事秘密和机密，而德国军方却对此一无所知；太平洋战争中，美军成功破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，击毙了山本五十六，导致了太平洋战争的决定性转折。因此，我们可以说，密码学为战争的胜利立了大功。在当今密码学不仅用于国家军事安全上，人们已经将重点更多的集中在实际应用，在你的生活就有很多密码，例如为了防止别人查阅你的文件，你可以将你的文件加密；为了防止窃取你钱物，你在银行账户上设置密码，等等。随着科技的发展和信息保密的需求，密码学的应用将融入了你的日常生活5。从密码学发展历程来看，可分为古典密码（以字符为基本加密单元的密码）以及现代密码（以信息块为基本加密单元的密码）两类。而古典密码有着悠久的历史，从古代一直到计算机出现以前，古典密码学主要有两大基本方法：一是替换密码，就是将明文的字符替换为密文中的另一种的字符，接收者只要对密文做反向替换就可以恢复出明文；二是置换密码(又称易位密码)即明文中的字母保持相同，但顺序被打乱了。2.2密码的组成密码是按特定法则编成，用以对通信双方的信息进行明密变换的符号。换而言之，密码是隐蔽了真实内容的符号序列。就是把用公开的、标准的信息编码表示的信息通过一种变换手段，将其变为除通信双方以外其他人所不能读懂的信息编码，这种独特的信息编码就是密码。2.3密码学的基础知识密码学在希腊文用Kruptos(hidden)+graphein(towrite)表达，现代准确的术语为“密码编制学”，简称“编密学”，与之相对的专门研究如何破解密码的学问称之为“密码分析学”。密码学是主要研究通信安全和保密的学科，他包括两个分支：密码编码学和密码分析学。密码编码学主要研究对信息进行变换，以保护信息在传递过程中不被敌方窃取、解读和利用的方法，而密码分析学则于密码编码学相反，它主要研究如何分析和破译密码。这两者之间既相互对立又相互促进。密码的基本思想是对机密信息进行伪装。一个密码系统完成如下伪装：加密者对需要进行伪装机密信息（明文）进行伪装进行变换（加密变换），得到另外一种看起来似乎与原有信息不相关的表示（密文），如果合法者（接收者）获得了伪装后的信息，那么他可以通过事先约定的密钥，从得到的信息中分析得到原有的机密信息（解密变换），而如果不合法的用户（密码分析者）试图从这种伪装后信息中分析得到原有的机密信息，那么，要么这种分析过程根本是不可能的，要么代价过于巨大，以至于无法进行6。在计算机出现以前，密码学的算法主要是通过字符之间代替或易位实现的，我们称这些密码体制为古典密码。古典密码中包括：易位密码、替换密码（单表替换密码、多表替换密码等）。这些密码算法大都十分简单，现在已经很少在实际应用中使用了。由于密码学是涉及数学、通讯、计算机等相关学科的知识，就我们现有的知识水平而言，只能初步研究古典密码学的基本原理和方法。但是对古典密码学的研究，对于理解、构造和分析现代实用的密码都是很有帮助。2.4几种简单的古典密码2.4.1滚桶密码在古代为了确保他们的通信的机密，先是有意识的使用一些简单的方法对信息来加密。公元六年前的古希腊人通过使用一根叫scytale的棍子，将信息进行加密。送信人先将一张羊皮条绕棍子螺旋形卷起来，然后把要写的信息按某种顺序写在上面，接着打开羊皮条卷，通过其他渠道将信送给收信人。如果不知道棍子的宽度（这里作为密钥）就不容易解密里面的内容的，但是收信人可以根据事先和写信人的约定，用同样的scytale的棍子将书信解密。2.4.2.掩格密码16世纪米兰的物理学和数学家Cardano发明的掩格密码，可以事先设计好方格的开孔，将所要传递的信息和一些其他无关的符号组合成无效的信息，使截获者难以分析出有效信息。2.4.3凯撒（Caesar）密码据记载在罗马帝国时期，凯撒大帝曾经设计过一种简单的移位密码，用于战时通信。这种加密方法就是将明文的字母按照字母顺序，往后依次递推相同的字母，就可以得到加密的密文，而解密的过程正好和加密的过程相反。Caesar 密码7的数学表示设：A the value 0，B 1，C 2， Y 24，Z 25；加密算法：Ek： i - i + k (mod 26) 解密算法：Dk： i - i - k (mod 26) 2.5加密方法密码加密的方法也有很多种，例如RSA算法、四方密码、二方密码、替换密码、换位加密法、会转轮加密法、Kasiski法在此因为本文运用的是替换密码，所以对替换密码做详细介绍。替换密码8是典型的古典密码，虽已很少使用，但对它的研究仍具有很强的理论价值。一种简单的替换密码如下：明码： ABCDEFGHIJKLMNOPQRSTUVWXYZ密钥： DKVQFIBJWPESCXHTMYAUOLRGZN 明文： IFWEWISHTOREPLACELETTERS 密文： WIRFRWAJUHYFTSDVFSFUUFYA 这样的密钥总数为26！，如此多的密钥是个组合爆炸，遗传算法擅长解决组合优化问题。替换密码的基本特点是明文消息的字符替换成另一个字符或符号，考虑到加密和解密的编码解码开销，可以直接使用英文字符作为参数编码，这样系统初始化时随机生成一组由26个各不相同的英文字符串。对于遗传算法来说这一个字符串就构成了一条染色体即一个初始个体pi，使其生成n组，就可以作为初始种群。3遗传算法简介及步骤3.1遗传算法简介遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化算法，其基本思想是基于Darwin的进化论和Mendel的遗传学说9。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来，国际上已经召开了多次遗传算法的学术会议和研讨会，为研究和应用遗传算法提供了国际交流的机会。进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用。五是遗传算法和进化规划以及进化策略等进化计算理论日益结合。它们几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。遗传算法大致上可分为6个步骤，包括编码、设定群体大小、定义适应度函数、选择、交叉、变异操作10。遗传算法的一般运算过程11如图3-1所示：图3-1遗传算法运算过程示意3.2编码方法编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。针对具体应用问题，如何设计一种完美的编码方案一直是遗传算法的难点之一，也是它的一个重要研究方向。而目前还没有一套既严密有完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，De Jong曾提出了两条操作性较强的实用编码原则12 。编码原则一（有意义积木块编码原则）：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。编码原则二（最小字符集编码原则）：应使用能使问题得到自然表示或者描述的具有最小编码字符集的编码方案。需要说明的是，上述编码原则仅仅是给出了设计编码方案时的指导性大纲，它并不适合于所有问题。由于遗传算法应用的广泛性，迄今为止人们提出了很多种不同的编码方案。从具体实现的角度出发主要有以下几种编码方法。3.2.1二进制编码方法二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集0，1，它所构成的个体基因型是一个二进制编码符号集。它具有以下优点：（1）编码、解码操作简单易行。（2）交叉、变异等操作便于实现。（3）符合最小字符集编码原则。（4）便于利用模式定理对算法进行理论分析。3.2.2格雷码编码方法格雷码是这样一种编码方法，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同。格雷码编码的主要优点有：（1）便于提高遗传算法的局部搜索能力。（2）交叉、变异等操作便于实现。（3）符合最小字符集编码原则。（4）便于利用模式定理对算法进行理论分析。3.2.3浮点数编码方法浮点数编码方法是指个体的每个基因值用某一范围内一个浮点数来表示，个体的编码长度等于其决策变量的个数。它的优点是：（1）适合于在遗传算法中表示范围较大的数。（2）适合于精度要求较高的遗传算法。（3）便于较大空间的搜索。（4）改善遗传算法的计算复杂性，提高运行效率。(5)便于遗传算法与经典优化方法的混合使用。（6）便于设计针对问题的专门知识的知识型遗传算子。（7）便于处理复杂的决策变量约束问题。3.2.4符号编码方法符号编码方法是指染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。它的主要优点是：（1）符合有意义积木块编码原则。（2）便于在遗传算法中利用所求解问题的专门知识。（3）便于遗传算法与相关近似算法之间的混合使用。本程序就是利用这种编码方法进行编码的。3.3适应度函数在遗传算法中适应度这个概念是用来度量群体中每个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对较小一些。度量个体适应度的函数称为适应度函数。密码设计者在设计密码系统的过程中，有其一般设计规则或原则。在将所有可能组成的各种基因定序及编码之后，便可依据我们所期望的密码设计原则，准确地用程序逐步定义于适应函数中，在每一代演化后，以此适应函数评估并赋予每一个个体所对应的适应值，用以确定所有物种演化的方向及搜寻的目标。进行演化时，在每一世代评估每个物种的适应值前，先赋予每个运算元一个随机数值，再依据已经由上一代演化后决定本世代的基因，按照设计密码系统时的几个程序：公开密钥产生阶段、密文产生阶段、解密阶段，依序完成后，再做适应值的评估。3.4选择算子遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。选择操作是建立在对个体的适应度进行评价的基础之上。下面介绍几种常用的选择算子操作方法。3.4.1比例选择比例选择方法是一种回放式随机采样的方法，又称赌盘选择方法。其基本思想是：各个个体被选中的概率与其适应度大小成正比。由于是随机操作的原因，这种选择方法的选择误差比较大，有时甚至连适应度较高的个体也选择不上。3.4.2最优保存策略在遗传算法的运行过程中，虽然随着群体的进化过程会产生出越来越多的优良个体，但是由于选择、交叉、变异等操作的随机性，优良个体也有可能被破坏掉，这并不是我们所希望的。要使适应度最好的个体尽可能的遗传到下一代群体中，可以使用最优保存策略进化模型来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。3.4.3确定式采样选择确定式采样选择方法是按照一种确定的方式来进行选择操作。这种选择操作方法可保证适应度较大的一些个体一定能够被保留在下一代群体中，并且操作也比较简单。3.4.4无回放随机选择这种选择操作方法也叫期望值选择方法，它的基本思想是根据每个个体在下一代群体中的生存期望值来进行选择运算。这种选择操作方法能够降低一些选择误差，但操作不太方便。3.4.5无回放余数随机选择无回放余数随机选择可保证适应度比平均适应度大的一些个体一定能够被遗传到下一代群体中，所以它的选择误差比较小。3.4.6排序选择前面所介绍的一些选择操作方法中，其选择依据主要是各个个体适应度的具体数值，一般要求它取非负值，所以在选择操作之前必须先对一些负的适应度进行变换处理。而排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。排序选择方法的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。其具体操作过程是：（1）对群体中的所有个体按其适应度大小进行降序排序。（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排序次序分配给各个个体。（3）以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用比例选择的方法来产生下一代群体。该方法的实施必须根据对所研究问题的分析和理解情况预先设计一个概率分配表，虽然依据个体适应度之间的大小次序给各个个体分配了以个选中概率，但由于具体选中那一个个体仍是使用了随机性较强的比例选择方法，所以排序选择方法仍具有较大的选择误差。因此本文中选择利用赌盘选择和最优保存策略来对群体进行选择。3.5交叉算子遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。交叉算子的设计包括以下两方面的内容：（1）如何确定交叉点的位置？（2）如何进行部分基因交叉？下面介绍几种适合于二进制编码个体或浮点数编码个体的交叉算子。3.5.1单点交叉单点交叉又称简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分基因。单点交叉的重要特点是：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。例如：A：1 0 1 1 0 1 1 1 0 0 A：1 0 1 1 0 1 1 1 1 1 B：0 0 0 1 1 1 0 0 1 1 B：0 0 0 1 1 1 0 0 0 03.5.2双点交叉和多点交叉双点交叉是指在个体编码串中随机设置二个交叉点，然后再进行部分基因交换。双点交叉的操作过程如下：（1）在相互配对的两个个体编码串中随机设置两个交叉点。（2）交换两个个体在所设定的两个交叉点之间的部分染色体。双点交叉操作的示例如下：例如取两个父代个体如下：P1：A B C D E FP2：B D F E C A对第三到第五个字符进行交叉操作后，得到子代个体为：C1：A B F E C FC2：B D C D E A多点交叉是指在个体编码串中随机设置多个交叉点，然后进行基因交换。3.5.3均匀交叉均匀交叉是指两个配对个体的每一个基因座上的基因都以相同的概率进行交换，从而形成两个新的个体。A：x x x x x x x x x x A：x y x y x y x y x y 均匀交叉B：y y y y y y y y y y B：y x y x y x y x y x3.5.4算术交叉算术交叉是指由两个个体的线性组合而产生出两个新的个体。假设在两个个体、之间进行算术交叉，则交叉后运算所产生的两个新个体是：上式中，为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算术交叉。3.5.5部分匹配交叉部分匹配交叉13是由Goldberg在1985年针对TSP提出的基于路径表示的交叉操作。部分匹配交叉操作要求随机选取两个交叉点，以便确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体。如假设TSP的城市数为8，两个父代染色体分别为：fl25036147和f234072516，首先随机选取两个点比如3和6标记为x，那么f1和f2就变为以下形式：fl250x36lx47f2340x725xl6观察两个父代的中段，记录下对应关系，即3一7，6一2，1一5，逐个检查父代的每一个基因，每次找到相匹配的基因，就进行交换：3和7交换：s125076143，s2740325166和2交换：s165072143，s274036512l和5交换：s161072543，s274036152交叉完成，得到sl和s2两个新的城市序列。但在算法实现中发现部分匹配交叉在某些情况下会出现重复，例如：f121x654x3 s12143545f212x435x6 s21265454观察这两个父代的中段，记录下对应关系，即6一4，5一3，4一5，由此对应关系得到的s1和s2出现重复现象。3.6变异算子在遗传算法中使用变异算子主要有两个目的：（1）改善遗传算法的局部搜索能力。（2）维持群体的多样性，防止出现早熟现象。变异算子的设计包括如下两方面内容：（1）如何确定变异点的位置？（2）如何进行基因值替换？3.6.1基本位变异基本位变异操作是指对个体编码串中以变异概率Pm随机指定的某一位或某几位基因座上的基因值作变异运算，它的改变只是在个体编码串中的个别几个基因座上的基因值，并且变异发生的概率也比较小，所以发挥的作用比较慢，作用效果也不明显。3.6.2均匀变异均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。3.6.3边界变异边界变异操作14是均匀变异操作的一个变形，它是随机取基因座的二个对应边界基因值之一去替代原有基因值。3.6.4非均匀变异为了方便对某些重点区域进行局部搜索，而对原有基因值做随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了个轻微的变动，这就是非均匀变异15。它的重点是搜索原个体附近的微小区域。3.6.5高斯变异高斯变异是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法。它在操作时，用符合均值为、方差为2的正态分布的一个随机数来替代原有基因值。4基于遗传算法的密码分析方法根据遗传算法的基本流程，涉及的关键内容有：染色体编码和初始种群的产生、适应度函数的定义和计算、遗传操作和新一代种群的产生等等。常量与变量说明：maxpop 表示最大群体大小MAXSTRING 表示最大字符串长度lchrom 表示个体长度popsize 表示种群规模maxgen 表示最大运行代数pcross 表示交叉概率pmutation 表示变异概率4.1染色体编码和初始种群产生本文首先是通过随机产生的密钥对某段英文文章进行加密，这就可以使用替换密码来解决。本文考虑到密钥是由26个全部大写（或全部小写）的英文字母组成，并且不能出现重复字母，即种群中个体的染色体编码不能出现相同字母，在此可使用check数组来防止重复出现同一字母。设计代码如下：for (i=0;ilchrom;i+)checki=false;for(i=0;ilchrom;i+) while(temp=0) flag=rand()%lchrom; if(checkflag=false) tempcipheri=flag; temp=1; checkflag=true; temp=0;这就实现了对本文中密钥的编码。要产生初始种群只要对上述代码实行循环就可以得到所需的群体。4.2适应度函数的确定与计算在遗传算法当中，适应度函数一般是由待求问题的目标函数转换而成的。针对不同的密码算法或者不同的分析方法，可以确定不同的适应度函数。从大量的英文书籍、报刊的文章中会很容易发现英文字母出现的频率有许多统计规律可循。比如E字母出现的次数最多，其次是T、A、O等字母。若统计的英文篇幅足够长时，会发现各个英文字母的频率相当稳定。根据英文字母的频率可将英文字母分成几类，其中E为极高频率字母类，V、K、J、X、Q、Z为甚低频率字母类。而且，双字母(相邻的两个字母)和三字母(相邻的三个字母)也和单字母一样出现相当稳定的字母分布16。这些统计资料对于密码分析者破译密码是非常重要的信息。本文正是基于英文字符的统计特性，可以选取如下适应度函数：式中：SF(i)为第i个字符在正常的英文使用中出现的频率，DF(i)是经过对密文C进行解密运算后得到的明文M=(m0，m1，m2，mn-1)，对mi出现的频率进行统计计算的结果。而对DF(i) 的计算首先要得到文章中一共有多少字符，如果有空格就会少一个字符，从而得到明文的字符总数。然后对文中的每个字母出现的次数进行统计；最后两者相除就可以算出DF(i)。解密后明文中字符出现的频率越接近正常因为出现的频率，其适应度就越大。本文中还采用了最优保存策略即上一代群体中最优密钥的适应度若是大于本代群体中最差密钥的适应度，则上一代的最优密钥取代本代最差密钥。4.3选择在选择算子中采用的赌轮算法是一种典型的选择算法，其基本思想是首先计算出当前种群所有个体的适应度Fitness，由此产生一个取值范围在0和Fitness之间均匀分布的伪随机数r，则满足条件的第i个个体被选作父代个体（其中F(pi)为第i个个体的适应度，n为种群规模）。选择代码如下：int select()double rand1,partsum; int j; partsum=0.0; j=0; rand1=random1()*sumfitness; do partsum=partsum+oldpopj.fitness; j=j+1;while(partsumrand1)&(jpopsize); return (j-1);4.4交叉选定两个父代个体以后随机产生两个交叉位置，然后根据交叉概率Pc对选中的两个父代个体做部分匹配交叉操作。但是由于替换密码的密钥表是没有重复字符的，所以交叉操作也必须要保证两个子代个体的参数中字符的非重复性，这就需要在选择出两个父代个体后，对它们进行重复性检查。本文中首先在种群里选出两个密钥oldpopmate1和oldpopmate2，再把oldpopmate1和oldpopmate2分别赋值给newpopk5和newpopk5+1。接着在这两个密钥中随机产生两个不同的交叉点jcross1和jcross2，然后对这两个交叉点进行排序，赋值给jcross1为第一个交叉点，jcross2为第二个交叉点。最后把上述两个密钥中两个交叉点间的基因保存在数组ts1和数组ts2中。比较数组ts1和数组ts2中的元素，如果是两者相同，则不用交叉，直接遗传到下一代；否则，进行部分比配交叉。具体操作如下：一、交叉点之前编码处理：如果选出的密钥newpopk5里在jcross1之前的基因newpopk5.cipherj与密钥newpopk5+1里的ts2中基因ts2j2相同时，则对密钥newpopk5进行操作，即把newpopk5里ts1中的基因ts2j2交叉给newpopk5.cipherj。代码如下： for(j=0;jjcross1;j+) for(j2=jcross1;j2=jcross2;j2+) if(newpopk5.cipherj!=ts2j2) continue; newpopk5.cipherj=ts1j2; 二、交叉点之后编码处理：同一类似。for(j=jcross2+1;jlchrom;j+) for(j2=jcross1;j2=jcross2;j2+) if(newpopk5.cipherj!=ts2j2) continue; newpopk5.cipherj=ts1j2; 三、交叉点间基因交换：把ts1和ts2里的基因进行交换。for(j=jcross1;j=jcross2;j+) newpopk5.cipherj=ts2j; newpopk5+1.cipherj=ts1j; 部分匹配交叉会产生重复，本文中若是产生了重复，则重新开始交叉，直到不重复。4.5变异在得到两个子代个体后，可以对它们进行变异操作。首先，根据给定的变异概率Pm与字符出现的频率，选择个体中需要进行变异的字符，在这里不能简单地将该字符替换为别的字符，而是在同一个个体内选择另一个字符与之进行交换。变异代码如下：mutate=flip2(); if(mutate) j1=rand()%lchrom; do j2=rand()%lchrom; while(j1=j2);jj=newpopk5.cipherj2; newpopk5.cipherj2=newpopk5.cipherj1; newpopk5.cipherj1=jj; 4.6解密本文经过以上操作就得到了新的群体，这个新的群体又需要进一步的选择、交叉和变异才能不断的进化，最终得到最优密钥。而在获得新的群体时，就需要利用这个群体中每一个密钥进行解密。考虑到编码串是用0到25的数字表示，所以用base数组进行转换。操作如下：if(ciphertexti-65=oldpopj.cipherk) oldpopj.plaintexti=basek;其中ciphertext指密文，plaintext指明文，base定义了按顺序从A到Z的26个字母。5数据分析数据分析是完善整个程序设计的重要步骤之一。先期工作要对得到明文进行加密：明文为：the capacitated vehicle routing problem cvrp is one class（见附录一）随机产生的密钥为：J K H Z C G O D I B T U W E N Q X R Y M S A P L F V经加密得到密文为：MDC HJQJHIMJMCZ ACDIHUC RNSMIEO QRNKUCW HARQ IY NEC HUJYY NG ARQ JEZ HJE（见附录二）开始数据分析就要对以上密文进行解密，而解密就需要通过遗传算法，下面就分如下几个部分对算法数据进行分析：(1)群体大小的设定(2)种群进化代数的设定（3）交叉概率的设定(4)变异概率的设定5.1群体大小的设定首先把种群大小设定为200，种群进化代数为1000代，交叉概率设为0.9，变异概率设为0.01。运行程序后可以得到最优密钥为J K H Z C G O D E B T U W I N Q X R Y M S A P L F V，经此解密后的明文为：THE CAPACNTATED VEHNCLE ROUTNIG PROBLEM CVRP NS OIE CLASS 而这段明文基本可读。这就说明以上得到的最优密钥已经很接近正确的密钥了。现在别的参数不变的情况下把种群大小设定为150，运行程序后得到最优密钥是J A H Z C G O D I B T U W Y N Q X R E M S K P L F V，经此解密的明文为：THE CAPACITATED BEHICLE ROUTISG PROVLEM CBRP IN OSE CLANN OF BRP ASD CAS很明显这段明文的误差就比种群大小为200时相对高了点。若把种群大小设定为50呢？运行后得到最优密钥为J Q R W C K S H N L X U A