第4章公钥密码技术-2全解.ppt

第4章公钥密码技术,本章主要内容概述公钥密码提出的背景公钥密码的基本思想公钥密码的应用RSA公钥密码体制ElGamal公钥密码体制,第4章公钥密码技术,4.1概述4.1.1公钥密码提出的背景1密钥管理的困难性问题传统密钥管理任何两个用户要进行报名通信就需要一个密钥，则n个用户需要n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。,第4章公钥密码技术,2系统的开放性问题对称密码体制的密钥分发方法要求密钥共享各方互相信任，因此它不能解决陌生人间的密钥传递问题3数字签名问题对称加密算法难以实现抗抵赖的安全需求。,第4章公钥密码技术,公钥密码学的发展概述,1976年，WhitfieldDiffie和MartinHellman发表了的“Newdirectionsincryptography”。这篇划时代的文章奠定了公钥密码系统的基础。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。自从公钥密码的概念被提出以来，相继提出了许多公钥密码方案，如RSA、背包体制、McEliece、ElGamal体制等。在不断的研究和实践中，有些方案被攻破了，有些方案不太实用。关于最初十年的公钥密码技术的研究和发展，可参见文献W.Diffie.Thefirsttenyearsofpublic-keycryptography.ProceedingoftheIEEE,76(5),1988,560-577.。,公钥密码学的意义公钥密码学的发展是整个密码学发展历史中最伟大的一次革命公钥密码学和以前的传统密码学完全不同首先，公钥算法是基于数学函数而不是基于替换和置换更重要的是，与只使用一个密钥的对称传统密码不同，公钥密码是非对称的，它使用两个独立的密钥。我们将会看到，使用两个密钥在消息的保密性，密钥分配和认证领域有着重要意义。,第4章公钥密码技术,关于公钥密码的常见的几种误区第一种误解是从密钥分析角度看，公钥密码比传统密码更安全。从抗密码分析角度看，原则上不能说传统密码优于公钥密码，也不能说公钥密码优于传统密码第二种误解是，公钥密码是一种通用的方法，所以传统密码已经过时。其实不然，由于现有的公钥密码方法所需要的计算量大，所以取代传统密码似乎不太可能。“公钥密码学仅限于用在密钥管理和签名这类应用中，这几乎是已被广泛接受的事实”,公钥服务器,传统对称加密法,公钥算法,公钥这一概念的真正贡献是，它减少了网络用户必须管理的密钥数。如果使用对称加密法5个用户的网络需要10个保密密钥，每个用户都得记住（并保密）4个密钥。但是在公钥系统中，每个用户只需记住他们自己的私钥，从公共场所查找所需的公钥即可,第4章公钥密码技术,4.1.2公钥密码的基本思想公钥密码也称为非对称密码。使用公钥密码的每一个用户都分别拥有两个密钥：加密密钥与解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算上是不可行的。每一个用户的加密密钥都是公开的。仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的两个密钥中的任何一个都可用来加密，另一个用来解密,基于公开密钥的加密过程,Joy,明文输入,加密算法，如RSA等,解密算法,明文输出,Alice的私钥,Bob的,公钥环,Ted,Alice,Mike,Bob,Alice,加密,基于公开密钥的鉴别过程,Bob,Alice,认证,第4章公钥密码技术,单向陷门函数单向陷门函数可以被定义为如下函数f：（1）给出f的定义域中的任意元素x,f(x)的计算是容易的；（2）给出y=f(x)中的y要计算x时，若知道设计函数f时结合进去的某种信息（该信息称为陷门），则容易计算；若不知道该信息，则难以计算。设计公钥密码体制可以转换为寻找单向陷门函数。目前人们主要是基于如下的数学上的困难问题来设计单向函数和公钥密码体制：（1）大整数分解问题(如公钥密码体制RSA)；（2）有限域上的离散对数问题(如公钥密码体制ElGamal):（3）椭圆曲线上的离散对数问题(如公钥密码体制ECC)。,第4章公钥密码技术,4.1.3公钥密码的应用（1）机密性的实现发送方用接收方的公钥加密消息，接收方用自己的私钥来解密。（2）数字签名发送方用自己的私钥来签名消息，接收方通过发送方对应的公钥来鉴别消息，并且发送方不能对自己的签名进行否认。（3）密钥分发和协商发送方和接收方基于公钥密码系统容易实现在公开信道上的大规模的密钥分发和协商。,费马定理和欧拉定理,欧拉定理,对任意互素的a和n有：a(n)=1modn(n)是小于n且与n互素的整数的个数,费马定理,费马定理可如下描述：若p是素数，a是正整数且不能被p整除，则ap-11（modp）另一种有用的表示形式是：若p是素数且a是任意正整数，则：apa(modp),公钥加密体制:RSA密码体制1978年，MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字，易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制。国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准。在Internet中所采用的PGP(PrettyGoodPrivacy)中也将RSA作为传送会话密钥和数字签字的标准算法。,4.2.1RSA的算法描述（1）密钥的生成1.选择两个大素数p，q，（p，q为互异素数，需要保密），2.计算n=pq，(n)=(p1)(q1)3.选择整数e使gcd(n)，e)=1,1e(n)4.计算d，使d=e1mod(n),得到：公钥为e,n；私钥为d,n（2）加密(用e，n)：明文：Mn，密文C=Me(modn).（3）解密(用d，n)：密文C，明文M=Cd(modn),第4章公钥密码技术,RSA密码体制,1.方案：独立地选取两大素数p1和p2(各100200位十进制数字)，计算n=pq，其欧拉函数值(n)=(p1)(q1)。随机选一整数e，1e(n)，(n),e)=1。因而在模(n)下，e有逆元d=e-1mod(n)，取公钥为n，e。秘密钥为d。(p,q不再需要，可以销毁。)加密：将明文分组，各组在modn下可惟一地表示。各组长达200位十进数字。可用明文集Az=x：1xn,(x,n)=1,密文y=xemodn解密：x=ydmodn证明：yd=(xe)d=xde，因为de1mod(n)而有de=q(n)1。由欧拉定理，(x,n)=1意味x(n)1modn，故有yd=xde=xk(n)+1xxk(n)=x1=xmodn陷门函数：Z=(p,q,d),RSA密码体制(续）,RSA算法举例,(1)选择两个素数p=7,q=17；(2)计算n=p*q=7*17=119;(3)计算(n)=(p-1)(q-1)=(7-1)(17-1)=96(4)选择一个随机整数e=5，且1e=0;i-)d=d*dmodn;If(bi=1)d=(d*a)modn;Returnd;,第4章公钥密码技术,第4章公钥密码技术,（2）如何快速产生大素数现在还没有产生任意大素数的有用技术，通常使用的过程是随机选取一个需要的数量级的奇数并检验这个数是否是素数；如果不是，再重复前面的步骤直到找到了通过检验的素数为止。一个比较高效和流行的素性检测算法是miller-rabin算法，归纳起来，挑选素数的过程如下：随机选择一个奇整数n随机选择一个整数an执行诸如Miller-Rabin之类的概率素数测试若n通过测试足够多次，则接受n；否则转到步骤2.,（3）用私钥进行有效运算我们不能为了计算的效率二简单地选择一个小数值的d，d的值太小容易遭受穷举攻击和其他形式的密码分析，然而中国剩余定理可以加快运算速度。,第4章公钥密码技术,第4章公钥密码技术,4.2.3RSA的安全性RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为其困难性至今还未能证明。若能将n分解为两个素数因子p，q，则可计算(n)=(p1)(q1)，d=e1mod(n)因此，不难得出结论：破译RSA不会比大整数分解更加困难!(1)对模n的长度必须足够长，至少为1024比特(2)p和q的长度应该相差不多；(3)p1和q1都应该包含大的素因子；(4)gcd(p1,q1)应该很小；(5)dn1/4。,RSA的安全性（续）穷举攻击：这种方法试图穷举所有可能的私钥。数学攻击：有多种数学攻击方法，他们的实质都是试图分解两个素数的乘积。计时攻击：这类方法依赖于解密算法的运行时间。选择密文攻击：这种攻击利用了RSA算法的性质,第4章公钥密码技术,第4章公钥密码技术,4.2.4RSA在应用中的问题（1）用户之间不要共享模数n假定用户U1和U2共享模数为n，他们的加密密钥分别是e1和e2，且gcd(e1,e2)=1，则攻击者不需要解密密钥d，就可以恢复出明文，具体过程如下：用户A分别向用户U1和U2发送明文m的加密信息，分别为：c1=me1modn,c2=me2modn设gcd(c1,n)=1，gcd(c2,n)=1，gcd(e1,e2)=1，(概率很大)，则攻击者由扩展的欧几里德算法能找到两个整数s和t，满足：se1+te2=1。S和t有一个是负数，假定s是负数，由欧几里德算法可计算c1-1modn。则(c1-1)-s.c2t=(m-e1)-s.(m-e2)t=m(se1+te2)modn=m,（2）不同的用户选用的素数不能相同（3）一般不能直接应用RSA进行加解密由于RSA算法是决定性算法（即对相同的明文始终会给出相同的密文）和具有特殊的代数结构等原因，用RSA算法进行直接加密在很多环境下是不安全的。故在使用RSA进行加密前，需要对明文做某种预处理，一般是进行随机化的填充。,4.3ElGamal公钥密码体制,4.3ElGamal公钥密码体制ElGamal密码体制是T.ElGamal于1985年提出，是最有名的公钥密码体制之一，它的安全性是基于离散对数问题.1密钥的生成选取大素数p，gZp*是一个本原元（生成元）。p、g作为系统参数所有用户共享。系统中每个用户U都随机挑选一个整数x，2xp2，并计算：y=gx(modp)，y作为用户U的公开密钥，而x作为用户U的秘密密钥,第4章公钥密码技术,4.3ElGamal公钥密码体制（续）2.加密：(1)用户A先把明文M编码为一个在0到(p1)之间的整数m作为传输的明文；(2)用户A挑选一个秘密随机数r(2rp2)，并计算：c1gr(modp)；(3)用户A计算：c2myr(modp)，其中y是用户B的公开