网络安全论文-密码学的发展

滨江学院课程报告题目密码学的发展院系专业学生姓名学号指导教师职称二Ｏ一一年十一月十日1密码学的发展1绪论密码学包括两部分，即密码编码学和密码分析学，这两个部分即对立又统一，正是由于其对立性才促进了密码学的发展。一个密码系统的安全性只有通过对该系统抵抗当前各类攻击能力的考查和全面分析才能做出定论。密码体制的安全性分析是一个相当复杂的问题，但有一点是清楚的，那就是掌握现有的分析方法并使用这些方法对相应的体制进行分析以考察其安全强度。在密码编码体制中，有两种最基本也是最古老的编码体制一直沿用至今，它们是代换密码和置换密码，由于历史悠久并且是现代密码体制的基本组成部分，因而在密码学中占有重要的地位。古典密码是密码学发展的一个阶段，也是近代密码学产生的渊源，尽管古典密码大多比较简单，一般可用手工或机械方式实现其加密和解密过程，破译也比较简单，目前已经很少采用，但了解它们的设计原理，有助于理解、设计和分析现代密码。日常生活中，在大多数的情况下，我们不用担心别人偷听，因为即使被人偷听到了他也无法用偷听到的信息做什么坏事。但当我们谈论某些比较敏感的话题时，被别人偷听到的话可能会产生一些负面的影响，对当事人很不利。在文字交流中，一些重要的信息，比如重要决定，人事变动和秘密情报等，当事人是不希望别人看到的，但如何进行交流呢？一个简单的办法就是采用文字编码。例如，将英文中的每个字母固定地换成它后面第5个字母，A换成F，B换成G，…，V换成A，W换成B，…，最后Z换成E。字母编码如下表所示：原文ABCD…VWXYZ密文FGHI…ABCDE因此，消息Iloveyou就变成了Nqtajdtz,消息有明确的信息，而编码后的字符串却是一串乱码，信息隐藏在其中，达到了保密的效果。对于古典密码体制而言，我们有如下的约定：加密解密时忽略空格和标点符号，这可能让人不太适应，但是经过解密后，几乎总是可以正确的还原明文中的这些空缺。如果保留这些空缺，密文会保持明文的结构特点，为攻击者提供便利。本文主要是通过对各类型的古典密码进行算法设计，通过编写程序来深层掌握古典密码的算法技术，通过对各类型古典密码进行详细的分析，分工讨论，在实现系统掌握这些密码算法的同时，也对C语言和C++面向对象进行了复习，有效的巩固了以前的知识，也培养了对专业密码学的学习兴趣。2现代密码代换是古典密码中用到的最基本的处理技巧，它在现代密码学中得到了广泛的应用，内容非常的丰富，人们采用代换密码进行加密时并没有固定的模式。按照一个明文字母是否总是被一个固定的字母代换进行2划分时，代换密码可以分为两大类：单表代换密码：对明文消息中出现的同一个字母，在加密时都用同一个固定的字母来代换，不管它出现在什么地方。移位密码和仿射密码都属于单表代换密码。多表代换密码：明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换，而是根据其出现的位置次序，用不同的字母代换，如维吉利亚密码和Playfair密码。2.1：移位密码明文空间P与密文空间C都是26个英文字母的集合，密钥空间K={0，1，2，…，25}。在实际进行加密解密运算时，把26个字母依次与0，1，2，…，25对应。因而也可以说P=C=K={0,1,…,25}=Z。E={e:Z-Z,e(x)=x+k(mod26)},即对每个K∈Z，相应的加密变换为ek(m)=m+k(mod26),其中m∈Z为明文。D={d:Z-Z,d(x)=x-k(mod26)},即对密钥k,解密变换为dk(y)=y-k(mod26),其中y∈Z为密文。解密之后要把Z中的元素再变换为英文字母。2.2：仿射密码明、密文空间与移位密码相同，密钥空间为K={(k1,k2)|k1,k2∈Z,其中gcd(k1,26=1)}gcd表示两个数的最大公因子，gcd(k1,26)=1,即表示k1还26互素。对任意的k=(k1,k2)∈K,加密变换为e(m)=k1*m+k2*(mod26).相应的解密变化为d(c)=k1^(-1)*(c-k2)(mod26),其中：k1*k1^(-1)=1(mod26).2.3：维吉利亚密码该密码有一个参数n。在加解密时同样把英文字母用数字代替进行运算，并按n个字母一组进行变换。明、密文空间及密钥空间都是n长的字母串的集合，因此可以表示P=C=K=Z^(26).加密变换如下：设密钥k=(k1,k2,…,kn),明文P=（m1,m2,…,mn）,加密函数为e(p)=(c1,c2,…,cn),其中Ci=(mi+ki)(mod26),i=1,2,…,n。对密文c=(m1,m2,…,mn),密钥k=(k1,k2,…,kn),解密变换为：e(c)=(m1,m2,…,mn),其中m1=(c1-k1)(mod26),i=1,2,…,n。其中mi=(ci-ki)(mod26),i=1,2,…,n。2.4：一般的单表代换密码单表代换密码的原理是：以26个字母的集合上的一个置换∏为密钥对明文消息中的每个字母依次进行变换，变换的方法是把明文中的每个字母用它在置换∏下的像去替换。解密时用∏的逆置换进行替换。可描述为P=C={0,1,2,…,25}=Z,K={∏:Z-Z|∏是置换}。密钥∏对应的加密变换e(x)=∏(x),解密变换为d(y)=∏^(-1)(y).前面描述的移位密码和仿射密码都是单表代换密码，而维吉利亚密码不是单表代换密码。32.5：列置换密码置换密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。列置换密码的加密方法如下：把明文字符以固定的宽度m（分组长度）水平地（按行）写在一张纸上，按1，2，3，…，m的一个置换∏交换列的次序位置，再按垂直方向（按列）读出即得密文。解密就是就是将密文按照相同的宽度m垂直的写在纸上，按置换∏的逆置换交换列的位置次序，然后水平的读出得到明文，置换∏就是密钥。2.6：周期置换密码周期置换密码是将明文字符按照一定长度m分组，把每组中的字符按1,2,…,m的一个置换∏重排位置次序来得到密文的一种加密方法。其中的密钥就是置换∏，在∏的描述中包含了分组长度的信息。解密时，对密文字符按长度m分组，并按∏的逆置换∏^(-1)把每组字符重排位置次序来得到明文。3：公钥密码学问题的提出：密钥管理量的困难。传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500传统加密算法无法实现抗抵赖的需求。1976年，WhitfieldDiffie和MartinHellman发表了的“Newdirectionsincryptography”。这篇划时代的文章奠定了公钥密码系统的基础。同时R.Merkle也独立提出了这一体制。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。自从公钥密码的概念被提出以来，相继提出了许多公钥密码方案，如RSA、背包体制、McEliece、ElGamal体制等。在不断的研究和实践中，有些方案被攻破了，有些方案不太实用。关于最初十年的公钥密码技术的研究和发展，可参见文献[W.Diffie.Thefirsttenyearsofpublic-keycryptography.ProceedingoftheIEEE,76(5),1988,560-577.]。目前只有两种类型的公钥系统是安全实用的，即基于大整数分解困难问题的密码体制与基于离散对数困难问题的密码体制。还有一些新的密码体制正在被研究，如基于辫群的密码体制、NTRU、量子密码体制等。3.1：基本概念在公钥密码系统中，首先要求加密函数具有单向性，即求逆的困难性。因此，设计双钥体制的关键是先要寻求一个合适的单向函数。4（1）单向函数定义：一个可逆函数f：AB，若它满足：1对所有xA，易于计算f(x)。2对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“极为困难”是对现有的计算资源和算法而言。Massey称此为视，在困难性(apparentdifficulty)，相应函数称之为视在单向函数。以此来和本质上(Essentially)的困难性相区分[Massey1985]。3.2：公钥加密体制:RSA密码体制1978年，MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字，易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制。国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准。在Internet中所采用的PGP(PrettyGoodPrivacy)中也将RSA作为传送会话密钥和数字签字的标准算法。1.方案：独立地选取两大素数p1和p2(各100～200位十进制数字)，计算n=p1×p2，其欧拉函数值(n)=(p1－1)(p2－1)。随机选一整数e，1e(n)，((n),e)=1。因而在模(n)下，e有逆元d=e-1mod(n)，取公钥为n，e。秘密钥为d。(p1,p2不再需要，可以销毁。)加密：将明文分组，各组在modn下可惟一地表示(以二元数字表示，选2的最大幂小于n)。各组长达200位十进数字。可用明文集Az={x：1xn,(x,n)=1}3.3：RSA的安全性（1）分解模数n。在理论上，RSA的安全性取决于模n分解的困难性，但数学上至今还未证明分解模就是攻击RSA的最佳方法，也未证明分解大整数就是NP问题，可能有尚未发现的多项式时间分解算法。人们完全可以设想有另外的途径破译RSA，如求解密指数d或找到(p1－1)(p2－1)等。但这些途径都不比分解n来得容易。甚至Alexi等[1988]曾揭示，从RSA加密的密文恢复某些bit的困难性也和恢复整组明文一样困难。目前RSA的攻击现状是有关RSA-155分解，其具体情况是1999年8月22日，来自六个不同国家的科学家们在CWI（CWI是在荷兰的一个数学和计算机科学的国家研究学会）的HermanteRiele的带领下，在对RSA-155的攻击中，利用数域筛法（NFS）成功的分解出了512-bitRSA模的素因子。要分解RSA-155所需的CPU时间大约为8400MIPS年（MIPS-年指以每秒执行1000000条指令的计算机运行一年），这大约为分解RSA-140所需时间的4倍。分解RSA-155总共用了7个月的时间。密码分析者估计在3年内分解RSA-155所用到的算法和计算技术至少在科技界将会得到普及，因此RSA-155将不再安全。并且人们预计，在十年内RSA-232也将被攻破。53.4：RSA实现由于RSA是简单且比较成熟的一种公钥密码体制，许多公司及研究团体都对它进行了实现。除RSA公司的产品RSAref以外，主要还有IBM的CCA、Cryptix、Cryptlib、Crypto++、Cryptolib、Python、SSLava、SSLeay及CRYPTOMAThIC的实现等。硬件实现的速度最快也只为DES的1/1000，512bit模下的VLSI硬件实现只达64kb/s。计划开发512bitRSA，达1Mb/s的芯片。1024bitRSA加密芯片也在开发中。人们在努力将RSA体制用于灵巧卡技术中。软件实现的速度只为DES的软件实现的1/100，512bitRSA的软件实现的速率可达11kb/s。RSA多用于密钥交换和认证。如果适当选择RSA的参数，可以大大加快速度。例如，选e为3、17或65537(216+1)的二进制表示式中都只有两个1，大大减少了运算量。X.509建议用65537[1989]，PEM建议用3，而PKCS#1建议用65537，当消息后填充随机数字时，不会有任何安全问题。4：结束语这次我选的课题是密码学的发