对称密码体制DES及其MATLAB实现

中国石油大学胜利学院本科毕业设计（论文）1对称密码体制DES及其MATLAB实现第一章课题的研究背景和意义1.遗传算法的发展及国内外的研究现状从Holland教授基础遗传算法的思想到现在，遗传算法的发展不过才40多年的历史，总的来说，遗传算法的发展历史可以分为以下阶段：20世纪70年代初Holland教授首次提出遗传算法的思想和基本原理，奠定理论基础。1975年他出版了《自然系统和人工系统的自适应性》一书，该书主要论述遗传算法和人工系统的关系。80年代，他用遗传算法第一个实现了机器学习系统，开创算法学习的新篇章。1.1遗传算法的研究背景遗传算法(GeneticAlgorithm,GA)[.]是由美国Miehigan大学J.H.Holland教授于1975年首次提出的。它遵循Darwin的进化论及Mendel遗传学说，在数学优化算法的基础上,加入自然界的遗传和自然进化选择机制，具有全局优化能力,是一种模仿生物进化的随机搜索算法。遗传算法的处理对象并不是相关参数本身,而是参数编码后的个体。它将问题的可能解表示为染色体，用适应度函数对搜索空间的解进行评价,然后按照遗传学规律进行选择、叉和变异操作，直到达到终止条件为止。本质是一种求解问题的高度并行性全局搜索算法。遗传算法的优化思想,使它能够在搜索过程中,自动获取和积累有关搜索空间的知识,并自适应的控制搜索过程，在全局范围内求得最优解。由于遗传算法并不要求对求解问题有深入的了解，且具有很强的鲁棒性,使得遗传算法能够广泛地应用于很多学科,尤其是对一些NP难问题的求解，表现出优异的性能。中国石油大学胜利学院本科毕业设计（论文）21.2遗传算法的研究发展20世纪60至70年代兴起阶段。遗传算法的产生，要归功于Hofland教授对于自适应的研究。在该研究中，他用一种新的数学模型来描述生物进化过程,得到的结果,使他意识到这种模型，不仅仅是模拟生物进化的数学模型,也是可以用来优化计算的一种数学方法。这一切都发生在二十世纪的六十年代Holland教授将生物进化数学模型化，发现了进化过程与自适应系统的相似性，并将其引入到该系统的设计。Holland的学生Bagley也参与到了该研究中来他于1967年,提出了遗传算子的雏形，并将其整理在他的博士论文中。Holland经过了多年的研究后，在1968年的时候，提出了遗传算法的理论基了础——模式定理。然后，1975年Holland和美国的DeJong博士作出了开创性的成绩。Holland出专著论述了遗传算法和人工自适应系统的相似性。而DeJong博士在模式定理的基础上，通过大量的数值试验，将遗传算子完善,建立了遗传算法的工作框架和五函数测试平台。20世纪80年代发展阶段。二十世纪的八十年代,分类系统(Classifiersystem),作为第一个基于遗传算法的机器学习系统，为分类器的构造提出了一个完整框架Holland作为其实现者，揭开了在机器学习上进行遗传算法的新概念。随后，在1989年Goldberg对遗传算法的一些相关工作进行了总结，包含了遗传算法在这一时期的主要研究成果，从理论和实际应用方面对遗传算法进行了详细的论述,使得遗传算法的基本框架得以形成并将这些内容整理成专著《搜索、优化和机器学习中的遗传算法》，奠定了现代遗传算法的基础。此后，许多学者经过大量的研究，对遗传算法提出了改进，得到了不少成功的遗传算法模型。从而让遗传算法能够在更加广泛的领域得到应用。20世纪90年代高潮阶段。20世纪90年代，人们比较重视遗传算法的一些基本问题。遗传算法作为一种高效、鲁棒性好的全局优化算法，它的发展极为迅速，在许多领域(如机器学习、模式识别、神经网络和工程优化等)得到了广泛的应用，引起了许多学者的注意在最近兴起的人工生命、遗传编程、进化计算领域中，研究人员将遗传算法与计算机技术相结合，试图模拟自然界的自适应!自组织和再生能力，设计出具有“生命”的人工系统。遗传算法的研究领域主要包含以下几类：遗传算法理论与技术、遗传算法优中国石油大学胜利学院本科毕业设计（论文）3化、用遗传算法进行分类系统的机器学习相对于生物学理论，遗传算法的数学理论基础是比较薄弱的。虽然如此，作为一门新发展起来的学科，遗传算法还是呈现给我们一种通用的算法框架，该框架不依赖求解问题的种类，具有较强的全局搜索能力。1.3遗传算法的国内外研究数理方面：作为遗传算法的提出者,Holland提出了遗传算法的基础理论:模式定理。而随后发展的隐含并行性定理和建筑块假设的提出,是前期算法理论上的成就,为遗传算法的发展和应用起到了至关重要的作用。而随着研究的深入,模式理论的拓广和深入成为了理论研究的热点之一；其次,通过马氏链分析遗传算法,也成为了理论研究的一个方向。除此之外,通过收敛理论分析遗传算法也得到了不少学者的青睐。模式理论方面的工作,主要包括模式的进一步讨论和拓广在这个方面,Radeliffe把模式分析进行了一般化,提出了完整的Forma分析理论。李军等通过研究自然数编码,建立了相应的模式定理;明亮等深入研究了模式定理后,推广了模式定理,提出了子模式的存货、互补模式和模式的新建,给出了在模式的新建和存活共同作用下的模式定理。马氏链分析方面,建立起了不同形式的模型,从各种角度刻画了遗传算法的极限行为。其中,Goldber、Rudolph通过对标准遗传算法使用马尔可夫链进行分析,提出了最佳保留遗传算法。在收敛理论方面,早期主要是用Holland的模式定理、隐并行性原理和积木块假说,但是,在后继的研究中,有人发现积木块假说没有给予证明,其它两个理论存在不足和不严格的地方。徐宗本等通过研究,认为已有的关于遗传算法的收敛性和收敛速度估计的结果,具有一定的局限性。虽然如此,Gonealves、陈国胜、王莉等对遗传算法的收敛理论和收敛速度估计进行了研究,还是取得了一定的成绩。此外,在早期的研究中,大多数都是通过马氏链的极限理论来分析遗传算法的收敛性,而现在,用靴方法和迭代的方法,得到了比较系统的结果。其中,徐宗本等用鞍论研究遗传算法的强收敛性,证明了不带“杰出者记录策略”的一大类常用遗传算法,能够以1的概率在有限步内收敛到全局最优解。而在实际应用中,遗传算法的迭代次数和群体规模是有限的。因此,这一研究成果为遗传算法的应用奠中国石油大学胜利学院本科毕业设计（论文）4定了更为坚实的理论基础。1.4本文主要研究内容基通过引入生物进化的遗传、交叉、变异、选择等技术，使得遗传算法成为了一种用来寻找近似解的搜索算法。而在生物学上，变异是对生物遗传物质核普酸的改变。那么在遗传算法一代接一代的进化计算过程中,变异算子是用来维持种群多样性的运算。作为遗传算法的一个基本运算，配合交叉运算，避免种群陷入局部最优。由于函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。而且,在工程应用中，常涉及到最优化问题，对很多问题进行数学建模后，都可以抽象为一个数值函数的优化问题因此,最后通过遗传算法在函数优化上的应用，来检验本文提出的新的遗传算法的性能。中国石油大学胜利学院本科毕业设计（论文）5第二章遗传算法的基本理论1.遗传算法的基本描述1.1遗传算法的数学模型所谓加密，就是将正常情况下可懂的文件数据输入密码机，由密码机变成不可懂的乱码，即将“明文”变成“密文”；所谓解密，就是上述过程的逆过程，即将“密文”变成“明文”。密码机可看作是一个用电子元件实现一种复杂数学运算的机器。复杂数学运算可记为，这里C=密文，p=明文，k=密钥，f是密码算法。K是自变量，C是因变量。不同的K有不同的C，对于某个密码算法f，K的选择范围越大，C的变化就越多，这个密码算法被人破译的难度就越大，保密强度就越高。如何评价K的选择范围大小呢？一般是看K的位数，位数长的（如128位以上）选择范围大，位数短的（如56位）选择范围小。一个国家的密码政策，通常是用位数长的高强度密码（位数可达）保护国家秘密，其它用于保护商业秘密。在数据传输加密过程中，收发双方线路密码机使用的是相同的密码算法，注入了相同的密钥，发方向收方发出明文，经密码机变成密文后送上公网通信线路，到达收方后先经密码机解密再送到收方电脑上。密文在公用通信网上传输时，如果被截收，窃密方收到的是不可懂的乱码，无法窃取信息内容。在文件存储加密中，加密解密卡加解密采用同一种算法和同一个密钥，工作人员用电脑处理文件后先将文件加密再存入磁盘，以防窃密者盗用磁盘窃取文件。工作人员调用该文件时，文件先经解密再从显示器上显示出来以供使用。1.2密码体制密码体制也叫密码系统，是指能完整地解决信息安全中的机密性、数据完整性、认证、身份识别、可控性及不可抵赖性等问题中的一个或几个的一个系统。对一个密码体制的正确描述，需要用数学方法清楚地描述其中的各种对象、参数、解决问题所使用的算法等。刚才讲密码原理时，收发双方密码机的密码算法一致、密钥一致，这在密码体制中叫“秘密密钥体制”或“单密钥体制”，这是一种传统的密码体制，有系统的理论研究和完善的管理机制，技术成熟，性能稳定，国中国石油大学胜利学院本科毕业设计（论文）6内自行研制的产品安全可靠、保密强度高，一般用于文件数据加密存储和传输。密码体制分为私用密钥加密技术(对称加密)和公开密钥加密技术(非对称加密)。对称密码体制是一种传统密码体制，也称为私钥密码体制。在对称加密系统中，加密和解密采用相同的密钥。因为加解密密钥相同，需要通信的双方必须选择和保存他们共同的密钥，各方必须信任对方不会将密钥泄密出去，这样就可以实现数据的机密性和完整性。对于具有n个用户的网络，需要n(n-1)/2个密钥，在用户群不是很大的情况下，对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时，密钥的分配和保存就成了问题。对机密信息进行加密和验证随报文一起发送报文摘要(或散列值)来实现。比较典型的算法有DES(DataEncryptionStandard数据加密标准)算法及其变形TripleDES(三重DES)，GDES(广义DES)；欧洲的IDEA；日本的FEALN、RC5等。DES标准由美国国家标准局提出,主要应用于银行业的电子资金转帐(EFT)领域。DES的密钥长度为56bit。TripleDES使用两个独立的56bit密钥对交换的信息进行3次加密，从而使其有效长度达到112bit。RC2和RC4方法是RSA数据安全公司的对称加密专利算法，它们采用可变密钥长度的算法。通过规定不同的密钥长度,，C2和RC4能够提高或降低安全的程度。对称密码算法的优点是计算开销小，加密速度快，是目前用于信息加密的主要算法。它的局限性在于它存在着通信的贸易双方之间确保密钥安全交换的问题。此外，某一贸易方有几个贸易关系，他就要维护几个专用密钥。它也没法鉴别贸易发起方或贸易最终方，因为贸易的双方的密钥相同。另外，由于对称加密系统仅能用于对数据进行加解密处理，提供数据的机密性，不能用于数字签名。因而人们迫切需要寻找新的密码体制。在实用的互联网络中，各用户通过加密传输可形成一个虚拟的保密互联网。该网要由一个各用户认可的密钥管理中心来生成、管理、分发和销毁密钥，同时各用户可将自己的“公钥”也存放在密钥管理中心。各用户需进行保密通信时，先通过公钥系统进行身份确认（这个过程中密钥管理中心可起到仲裁鉴别作用），双方确认身份后由密钥管理中心分发秘密密钥，双方用得到秘密密钥进行数据或文件的加密传输。这种工作方式不但适用于党政机关内部，也同样适用于电子商务，但电子商务和党政机关不能使用同一个级别的密码设备，党政机关用的是“普中国石油大学胜利学院本科毕业设计（论文）7密”设备，电子商务只能用“商密”设备，二者的保密强度是不一样的。2.分组加密算法2.1加密算法DES介绍数据加密算法（DataEncryptionAlgorithm，DES）的数据加密标准（DataEncryptionStandard，DES）是规范的描述，它出自IBM的研究工作，并在1997年被美国政府正式采纳。它很可能是使用最广泛的密钥系统，特别是在保护金