研究生论文加密原理.doc

贵 州 大 学计算机系2002级研究生期末信息技术安全课程论文 课程名：信息技术安全学 生： 教 师： 2003年6月18日信息技术安全密码学摘要 随着网络已经逐步进入我们的生活，网络安全也随之倍受人们的关注，而在网络安全中起着举足轻重作用的正是密码学，文中简单的介绍有关密码学的发展，较为详细的对密码学中极为经典的算法DES和RSA进行解释，通过对这两个算法的理解，来认识当今密码学发展的前沿和动向。关键词 密码学，非对称加密算法，对称加密算法，数字签名， Abstract the security of webnet has been paid more attention When Internet has been involving into our life .The cryptography play a important role in the security of webnet .In this article I will discuss the development of the cryptography and I will thorough interpret these two algorithm about DES and RSA. We will recognize the forward position and tendency about cryptography though understand those two algorithm.Key words Cryptography , No-symmetric encryption algorithm , symmetric encryption algorithm, the digital signature 1、 密码学的发展历程随着信息化和数字化社会的发展，人们对信息安全和保密的重要性认识不断提高，而在信息安全中起着举足轻重作用的密码学也就成为信息安全课程中不可或缺的重要部分，密码学早在公元前400多年就已经产生，正如破译者一书中所说的“人类使用密码的历史几乎与使用文字的时间一样长”。密码学（ Cryptograph）一词来源于古希腊语Kruptos（hidden）+ graphein（to write）准确的现代术语是“密码编制学”简称“编密学”，与之相对的专门研究如何破解密码的学问称之为“密码分析学”。密码学则包括密码编制学和密码分析学这两个相互独立又相互依存的分支。从其发展来看，可分为古典密码以字符为基本加密单元的密码，以及现代密码以信息块为基本加密单元的密码。古典密码有着悠久的历史，在电报特别是无线电报发明以后，得到了深入研究。常用的有单表密码和多表密码，其思路都是改变字母表中字母的顺序。其中单表密码在古代就已经得到了长足的发展，到了现代，密码学文献有一个奇妙的发展历程，当然，密而不宣总是扮演主要角色。第一次世界大战前，重要的密码学进展很少出现在公开文献中，但该领域却和其它专业学科一样向前发展.直到1918年，二十世纪最有影响的密码分析文章之William F. Friedman的专题论文重合指数及其在密码学中的应用作为私立的“河岸（Riverbank）实验室”的一份研究报告问世，其实，这篇著作涉及的工作是在战时完成的。同年,加州奥克兰的Edward H.Hebern申请了第一个转轮机专利，这种装置在差不多50年里被指定为美军的主要密码设备。 然而，第一次世界大战后，情况开始变化，完全处于秘密工作状态的美国陆军和海军的机要部门开始在密码学方面取得根本性的进展。在30年代和40年代，有几篇基础性的文章出现在公开的文献中，有关该领域的几篇论文也发表了，只不过这些论文的内容离当时真正的技术水平相去甚远，战争结束时，情况急转直下，公开的文献几乎殆尽。只有一个突出的例外，那就是仙农(Claude Shannon)的文章保密系统的通信理论出现在1949 年贝尔系统技术杂志上，它类似于Friedman1918年的文章，也是战时工作的产物。这 篇文章在第二次世界大战结束后即被解密，可能是由于失误。从1949年到1967年，密码学文献近乎空白。在1967年，一部与众不同的著作-David Kahn 的破译者出现，它没有任何新的技术思想，但却对以往的密码学历史作了相当完整的记述，包括提及政府仍然认为是秘密的一些事情。破译者的意义不仅在于它涉及到的相当广泛的领域，而且在于它使成千上万原本不知道密码学的人了解密码学。新的密码学文章慢慢地开始源源不断地被编写出来了。到了第二次世界大战时多表密码编制达到了顶点也达到了终点。当年希特勒一上台就试验并使用了一种命名为“谜”的译码机，一份德国报告称：“谜”型机能产生220亿种不同的密钥组合，假如一个人日夜不停地工作，每分钟测试一种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完。希特勒完全相信了这种密码机的安全性。然而，英国获知了“谜”型机的原理，启用了数理逻辑天才、现代计算机设计思想的创始人，年仅26岁的Alan Turing。1939年8月，在Turing领导下完成了一部针对“谜”型机的密码破译机，每秒钟可处理2000个字符，人们给它起了个绰号叫“炸弹（Bomb)”。半年后，它几乎可以破译截获德国的所有情报。后来又研制出一种每秒钟可处理5000个字符的“巨人(Colossus)”型密码破译机，1943年投入使用。至此，同盟国几乎掌握了希特勒德国的绝大多数军事秘密，盟军掌握了德军的许多机密，而德国军方却对此一无所知；太平洋战争中美军破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，导致了太平洋战争的决定性转折，而且不久还击毙了山本五十六。相反轴心国中，只有德国只是在二战的初期在密码破译方面取得过辉煌的战绩，后来就不行了。因此，我们可以说，密码学在战争中起着非常重要的作用。为战争的胜利立了大功。到了1973年美国国家标准局NBS (National Bureau of Standard)正式向社会公开征集加密算法。1974年IBM正式向NBS提交了应征方案，NBS会同美国国家保密局NSA（ National Security Agency)研究发现这是唯一满足各项要求的方案。1977年，美国国家标准局（ANSI）宣布DES作为国家标准用于非国家保密机关，开创了公开全部密码算法的先例。1976年，Diffie和Hellman提出不仅密码算法本身可以公开，而且加密用的密钥也可以公开，只要脱密密钥保密就可以了，这就是加密密钥和脱密密钥不同的非对称密码体系，又称公钥密码体系；1978年，Rivest、Shamir和Adleman三人合作提出了第一个实用的公钥密码算法，即著名的RSA密码算法。直到现在，DES和RSA两个密码算法仍然是现代密码学的经典。2、 经典密码学算法介绍1） DES (data encryption standard )DES (Data Encryption Standard)算法是美国政府机关为了保护信息处理中的计算机数据而使用的一种加密方式，是一种常规密码体制的密码算法，目前已广泛用于电子商务系统中。其基本思想是：加解密双方在加解密过程中要使用完全相同的一个密钥，密钥就经过安全的密钥信道由发方传给收方。（如图）算法思想： DES密码算法以8个8位的字节块(64位)为基本加密单元，使用8个7位的字节块(56位)密钥进行加密和脱密，算法繁琐。首先把56位密钥变换后形成16个48位的子密钥，而64位的明文信息块被视为64个二进制位的集合，通过初始变换重新排列位置后形成左、右两个32位的子块L0和R0，右子块R0变换为48位的块后与相对应的48位的子密钥模2加运算后再变换为32位的块，然后再与L0模2加运算形成新的右子块R1，而R0不作变换作为L1，如此连续使用不同的子密钥运算16次，把L16和R16左右颠倒后连接，经过逆初始变换形成密文。脱密运算相同，只是子密钥使用的顺序不同而已，是一种典型的分组密码算法输入64个二进制位明码文数据区组T=t1t2t64按初始换位表IP进行换位，得到区组B（0）：B（0）=b1(0)b2(0)b64(0)=t58t50t7设B（i）=b1(i)b2(i)b64(i)是第i+1次迭代的64个二进制位输入区组，将B（i）分为左右两个大小相等的部分，每部分为一个32位二进制的数据块L（i）=l1(i)l2(i)l32(i)= b1(i)b2(i)b32(i)R（i）=r1(i)r2(i)r32(i)=b33(i)b34(i)b64(i)把R（i）视为由8个4位二进制的块组成r1(i)r2(i) r3(i)r4(i)r5(i)r6(i) r7(i)r8(i)r29(i)r30(i) r31(i)r32(i)通过循环抄录相邻块的相邻块，把它们再扩充为8个6位二进制的块r32(i)r1(i) r2(i)r3(i) r4(i)r5(i)r4(i)r5(i) r6(i)r7(i) r8(i)r9(i)r28(i)r29(i) r30(i)r31(i) r32(i)r1(i)用E(R（i）)表示这个变换，称为扩充函数。在第i+1次迭代中，用48位二进制的密钥K（i+1）=k1(i+1)k2(i+1)k48(i+1)与E(R（i）)按位相加（逻辑异或），得r32(i)+ k1(i+1) r1(i) +k2(i+1) r5(i) +k6(i+1)r4(i)+ k7(i+1) r5(i) +k8(i+1) r9(i) +k12(i+1)r28(i)+ k48(i+1) r29(i) +k44(i+1) r1(i) +k48(i+1)将以上第j个(1j6位二进制的块（记为Z=zj1 zj2 zj3 zj4 zj5 zj6）输入第个j个替代函数Sj（表4-3）。各替代函数Sj的功能是把6位数变换成4位数，做法是以zj1 zj6为行号，zj2 zj3 zj4 zj5为列号，查找Sj，行列交叉处即是要输出的4位数。八个替代函数Sj(1j8)的输出拼接为32位二进制数据区组y1(i)y2(i)y32(i) 把它作为换位函数P的输入，得到输出X（i）=x1(i)x2(i)x32(i) =y16(i)y17(i)y25(i)我们可以概括的得到DES的算法流程图：DES算法的破译，使用穷举法破译DES 密码问题。设已知一段密码文C及与它对应的明码文M，用一切可能的密钥K加密M，直到得到E（M）=C，这时所用的密钥K即为要破译的密码的密钥。穷举法的时间复杂性是T=O（n），对于DES密码n=25671016，即使使用每秒种可以计算一百万个密钥的大型计算机，也需要算106天才能求得所使用的密钥，因此看来是很安全的。但是Diffie和Hellman（提出公开密钥的两位科学家）指出，如果设计一种一微秒可以核算一个密钥的超大规模集成片，那么它在一天内可以核算8.641010个密钥。如果由一个百万个这样的集成片构成专用机，那么它可以在不到一天的时间内用穷举法破译DES密码。他们当时（1977年）估计：这种专用机的造价约为两千万美元。如果在五年内分期偿还，平均每天约需付一万美元。由于用穷举法破译平均只需要计算半个密钥空间，因此获得解的平均时间为半天。这样，破译每个DES密码的花销只是五千美元。后来，Diffie在1981年又修改了他们的估计，认为以1980年的技术而论，用造价为五千万美元的专用机破译DES密码平均要花两天时间。但是他与Hellman都预计：1990年时，破译DES密码的专用机的造价将大幅度下降。到了1997美国有一程序员采用Sever-Client方式在众多网上志愿者的帮助下利用Internet 96天成功破密获取密钥。因此在后来对DES的设计中，将密钥的长度扩展成为128位或者是256位，以扩大密钥的空间。DES算法存在的问题是：由于加解密双方都要使用相同的密钥，因此在发送、接收数据之前，必须完成密钥的分发。因而，密钥的分发便成了该加密体系中的最薄弱因而风险最大的环节。各种基本的手段均很难保障安全地完成此项工作。从而，使密钥更新的周期加长，给他人破译密钥提供了机会。实际上这与传统的保密方法差别不大。在历史战争中，破获他国情报的纪录不外是两种方式：一种是在敌方更换“密码本”的过程中截获对方密码本；另一种是敌人密钥变动周期太长，被长期跟踪，找出规律从而被破获。在对称算法中，尽管由于密钥强度增强，跟踪找出规律破获密钥的机会大大减小了，但密钥分发的困难问题几乎无法解决。如，设有n方参与通信，若n方都采用同一个对称密钥，一旦密钥被破解，整个体系就会崩溃；若采用不同的对称密钥则需n(n-1) 个密钥，密钥数与参与通信人数的平方数成正比。这便使大系统密钥的管理几乎成为不可能。(2) RSA1976年，W.diffie和M.hellman首次提出了公开密钥密码体制的概念，其中最关键的思想是寻找一个“单向函数”，而所谓“单向函数”是指如果存在一个函数y=f(x),给定一个x可以通过映射y=f(x)求出y,但是反过来，给定一个y通过此函数的反函数y=f-1(x)来求x是不可能实现的。正是基于这种“单向函数”的提出，1977年Rivest、Shamir Adleman 提出了第一个比较完善的公开密钥密码体制，即著名的RSA体制。RSA的算法基本思想是：发送端将要发送的信息用接收端的公钥来进行加密，数据传送到接收端后，接收端用自己的私钥来进行解密，如果加密信息在传送的过程当中被第三方获取，第三方由于没有接收端的私钥，而只有密文和公钥仍然不能将密文解开。RSA算法的基本步骤是：选择两个大质数户和p和q，每个都大于10100；计算n p*q和z= （p一1）*（q一1）；选择一个与z 有关的质数，令其为d ；找到一个e使满足e*d=1（模z)。 d保密。事先计算好这些参数，我们就可以准备加密了。将明码（当作位串看待）划分成块，使得每个明码报文P落在0Pn之间，这可以通过将明码分成每块有k位的组来实现，并且屋是使得zkn成立的最大整数。加密一个报文P，计算C=Pe（mod n） 。解密C，计算P=Cd（mod n）。可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密你需要e和n。为实现解密你需要d和n。所以公钥由（e，n）组成，私钥由（d，n）或只是d组成。现在我们就来看这个简单的例子。我们选择了p=3，q=11，则n=33，g=20。d的一个适合的值是d=7，因为7和20没有公共因子。选定这些值后，e可以通过求解式7e1（模20）得出，即e=3。明码报文P的一个密码C，则由C=P3（模33）将密文解密。图中给出明码“SUZANNE”的加密作为例子。因为我们的质数选择得很小，所以P必须小于33，因此，每个明码块只能包含一个字符。结果形成了一个单一字母表代换密码。明文 密文 解密 字母 序号 P3 P3（MOD 33） C7 C7（MOD 33） 字母 SUZANNE 19212601141405 6859926117576127442744125 28212015526 134929285121801088541128000000178125781258031810176 192126114145 SUZANNE 我们可以知道此例是不安全的，为什么呢？RSA算法的安全性是基于什么？RSA算法的安全性是基于：加密变换：c=E k(m)=me mod n的单向性，即敌方从n 和e中无法求出脱密的密钥d ，产生这种单向性的原因是大整数分解在计算上的困难，如果能有效的分解n p*q那也就知道了z= （p一1）*（q一1）；从而就可以用穷尽的方法来求出脱密的密钥d，为保证足够的安全性，一般认为现在的个人应用需要用384或512比特位的n，公司需要用1024比特位的n，极其重要的场合应该用2048比特位的n。在RSA中需要考虑的另一个问题是如何产生大素数？因为RSA的安全性是建立在分解大整数n=p*q困难的基础上的，所以n 至少应为超过150位的十进制数（512bit）故素数p,q应超过75位十进制。常用的方法是随机产生大整数，然后检测其是否为素数，那就必须考虑素数在整数中的稠密度。依据素数定理：设x为正整数，记（x）为不超过x的素数个数，则有（x）x / ln x。长期以来，素性检测的问题没有有效的确定性算法，解决素性检测问题最有效的算法是概率算法，概率算法是指：算法中要使用随机数，从而对于相同的输入，每次运行得到的输出结果可能不同。Solovay-Sreassen 算法就是这样一个概率算法，它是指如果该算法判定N 是合数，则N必为合数，如果判定N是素数，则N是合数的概率是1/2k,当k足够大时可以认为N是一个素数。3、 现代密码学的发展动向1） PKI技术PKI（Public Key infrastructure，公钥基础设施）也称为数字签名技术，从字面上理解，PKI就是利用公钥理论和技术建立的提供安全服务的基础设施。PKI技术是信息安全技术的核心，也是电子商务的关键和基础技术。由于通过网络进行的电子商务、电子政务、电子事务等活动缺少物理的接触，因而使得用电子方式验证信任关系变得至关重要。而PKI技术恰好是一种适合电子商务、电子政务、电子事务的密码技术，它能够有效地解决电子商务应用中的机密性、真实性、完整性、不可否认性和存取控制等安全问题。数字签名（PKI）是防止网上交易时进行伪造和欺骗的一种有效手段。发送者在自己要公布或发送的电子文档上“签名”，接收者通过验证签名的真实性确认文档是否被篡改过。在公布一份电子文档时，发送者首先对要公布的文档进行哈希（Hash）运算，然后发送者就可以用自己的签名私钥对Hash运算得出的简洁数据进行加密签名；接收者收到签名文档后，用发送者的公钥进行解密，得到解密后的Hash运算结果和文档。此时，接收者只需要计算出该文档的Hash运算结果并与解密得到的Hash运算结果进行比较，即可知道该文档的真伪。在数字签名应用中，发送者的公钥可以很方便地得到，而他的私钥则需要严格的保密。其中对这类HASH函数的特殊要求是： 1接受的输入报文数据没有长度限制； 2对输入任何长度的报文数据能够生成该电文固定长度的摘要(数字指纹)输出； 3从报文能方便地算出摘要； 4极难从指定的摘要生成一个报文，而由该报文又反推算出该指定的摘要； 5两个不同的报文极难生成相同的摘要。 PKI的功能模块 -PKI的核心是信任关系的管理。第三方信任和直接信任是所有网络安全产品实现的基础。所谓第三方信任是指两个人可以通过第三方间接地达到彼此信任。当两个陌生人都和同一个第三方彼此信任并且第三方也担保他们的可信度时，这两个陌生人就可以做到彼此信任。在任何大规模的网络里，基于第三方的信任是必要并且有效的。当在很多人中建立第三方信任时，就需要有一个权威中心来确保信任度。 -CA（Certification Authority）就是这样一个确保信任度的权威实体，它的主要职责是颁发证书、验证用户身份的真实性。我们可以把CA看成是一个国家的护照签发中心。护照是由权威中心（护照签发中心）颁发的一种安全文件，它是护照持有者的一种纸质身份证明，任何信任该国护照签发中心的其他国家也会信任该国护照签发中心所签发的护照。 由CA签发的网络用户电子身份证明证书就像护照一样，任何相信该CA的人，按照第三方信任原则，也都应当相信持有证明的该用户。当然，就像护照需要防伪一样，CA也要采取一系列相应的措施来防止电子证书被伪造或篡改。构建一个具有较强安全性的CA是至关重要的，这不仅与密码学有关系，而且与整个PKI 系统的构架和模型有关。此外，灵活性也是CA能否得到市场认同的一个关键，它必须支持各种通用的国际标准，能够很好地和其他厂家的CA产品兼容。 -RA（Registration Authority）是用户和CA的接口，它所获得的用户标识的准确性是CA颁发证书的基础。RA不仅要支持面对面的登记，也必须支持远程登记，如通过电子邮件、浏览器等方式登记。要确保整个PKI系统的安全、灵活，就必须设计和实现网络化、安全的且易于操作的RA系统。在PKI系统中，制定并实现科学的安全策略是非常重要的，这些安全策略必须适应不同的需求并且能够通过CA和RA技术融入到CA和RA的系统实现中。同时，这些策略应该符合密码学和系统安全的要求，科学地应用密码学与网络安全的理论，并且具有良好的可扩展性和互用性。 -为了确保数据的安全性，定期更新密钥、恢复意外损坏的密钥（比如硬盘等物理介质突然损坏）是非常重要的。设计和实现健全的密钥管理方案，保证安全的密钥备份、更新、恢复，也是关系到整个PKI系统强健性、安全性、可用性的重要因素。 -此外，PKI系统还需要构建一个安全有效的撤销系统。证书是用来证明证书持有者身份的电子介质，它是用来绑定证书持有者身份和其相应公钥的。通常，这种绑定在已颁发证书的整个生命周期里都是有效的。但是，有时也会出现一个已颁发证书不再有效的情况，如果这个证书还没有到期，就需要进行证书撤销。证书撤销的理由是各种各样的，可能包括从工作变动到对密钥的怀疑等一系列原因。因此，需要采取一种有效和可信的方法，能在证书自然过期之前撤销它。证书撤销的实现方法有多种：一种方法是利用周期性的发布机制撤销证书；另一种方法采用在线查询机制，随时查询被撤销的证书。 -目前，关于PKI功能模块的各种新思想、新技术仍在不断出现。比如，为了确保电子交易的不可否认性，基于第三方的时戳（TimeStamp）服务正在引起人们极大的兴趣。在PKI的CA网络模型方面，除了传统的层次结构（Hierarchy）和对等结构（Peer to Peer）以外，还出现了桥CA（Bridge CA）的概念。-网络，特别是Internet网络的安全应用已经离不开PKI技术的支持。网络应用中的机密性、真实性、完整性、不可否认性和存取控制等安全需求只有PKI技术才能满足。中国作为一个网络发展大国，发展自己的PKI技术是很有必要而且是非常迫切的。由于我们目前没有成熟的PKI解决方案，使得某些关键应用领域不得不采用国外的PKI产品。因此，研究和开发我国自主的、完整的PKI系统，以支持政府、银行和企业安全地使用信息资源和国家信息基础设施已是刻不容缓，这对于我国电子商务、电子政务、电子事务的发展将是非常关键和重要的。1） 量子密码学 量子技术在密码学上的应用分为两类：一是利用量子计算机对传统密码体制的分析；二是利用单光子的测不准原理在光纤一级实现密钥管理和信息加密，即量子密码学。量子计算机是一种传统意义上的极大规模并行计算系统，利用量子计算机可以在几秒钟内分解RSA129的公钥，以色列最近公布利用量子计算能在12微秒解开RSA-512，而传统计算机则需要数月时间。 目前Internet的骨干网基本实现了光连接。下一代Internet2体系结构的核心结点是提供高级通信服务的GigaPOP，主要以高速ATM或SONET的形式连接。全光学网络将是今后网络连接的发展趋势，利用量子技术实现传统的密码体制可以光纤一级完成密钥交换和信息加密，其安全性建立在Heisenberg的测不准原理上，即，如果攻击者企图接收并测量信息发送方的信息(偏振)，则将造成量子状态的改变，这种改变对攻击者而言是不可恢复的，而收发双方可容易地检测出信息是否受到攻击。 1999年最新研究显示，量子密钥分配QKD在光纤上的有效距离是48公里，QKD同样可在无光纤的大气中传播48公里，该结果只可用在低轨道卫星和地面站的保密通信，远未达到实际远距离光纤通信的要求，所以，量子密码仍将在实验室进行一段时间的研究。、 学习心得在这个学期的信息安全课程中，我选择密码学作为我的课件内容，通过阅读大量的书和资料，使我对密码学有了一个由浅入深的了解，包括单表编密，多表编密代换编码和转置密码。其中对DES