密码学6非对称密码体制课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 非对称密码体制,信息安全技术,6.1,概述,6.1.1,对称密码体制的缺陷,密钥的安全传递比较困难,n,个用户多点通信所需密钥数为,n(n-1)/2,个,难以提供对主动攻击的抗击,6.1.2,公钥（非对称）密码体制的基本思想,Whitfield,Diffie和Martin,Hellman在1976年,首先提出：用公开的密钥（公钥）加密，用与之对应的不公开的密钥（私钥）解密。,公钥密码体制提出的标志性文献密码学的新方向：,W.Diffie,and,New Directions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654,例：程嘉要传送密信给雷蕾，用雷蕾的公钥对明文进行加密，然后通过公共信道将密文传送给雷蕾，雷蕾用的与自己的公钥对应的私钥（只有雷蕾自己知道）解密得到明文。康威企图知道密信内容，截获到密文，虽然他也知道加密所用的公钥，但他无法通过公钥倒推出相应的私钥，当然就不可能解密出明文。,6.1.2,对公钥密码体制的要求,（,1,）参与方,B,容易通过计算产生一对密钥（公开密钥,KUb,和私有密钥,KRb,）。,（,2,）在知道公钥和待加密报文,M,的情况下，对于发送方,A,，很容易通过计算产生对应的密文：,C=E,KUb,(M),（,3,）接收方,B,使用私钥容易通过计算解密所收到的密文,C,以便恢复原来的明文：,M=D,KRb,(C)=D,KRb,(E,KUb,(M),（,4,）攻击者即使知道公钥,KUb,，要确定其对应的私钥,KRb,在计算上是不可行的。,（,5,）攻击者即使知道公钥,KUb,和密文,C,，要想恢复原来的明文,M,在计算上也是不可行的。,（,6,）加密和解密函数可以以两个次序中的任何一个来使用,:M=D,KRb,(E,KUb,(M),（机密性）,或,M=E,KUb,(D,KRb,(M),（数字签名）,6.1.3,单向陷门函数,公钥密码体制必须设计一个满足下列条件的函数,f,：,正向易算性由消息,x,和密钥,pk,容易计算,y=,f,pk,(x,),反向不可算性在不知道密钥,sk,的情况下，由任意的,y,倒过来计算,x,=f,-1,sk,(y),都是不可行的,陷门依赖性如果给定另一密钥,sk,，则,f,-1,(y),是可以计算的，,sk,与,pk,配对，相当于陷门。,满足,1,、,2,的函数称为单向函数,满足,1,、,2,、,3,的函数被称为带陷门的单向函数,6.1.4,公钥密码体制的特点,无需密钥的安全传递,n,个用户仅需,n,个“公钥-私钥”对,支持对主动攻击的抗击,安全性基于带陷门的单向函数,加密、解密速度比,DES,、,AES,等分组密码体制慢,可用于对称密钥的交换,6.2,数论背景欧拉函数与欧拉定理,欧拉数,设正整数,n，,则欧拉数,(n),定义为小于,n,且与,n,互素的正整数的个数（特殊地，,(1)=1,）。,例如：,(6)=2(,小于,6,且与,6,互素的是,1,和,5);(7)=6(1,2,3,4,5,6);(11)=10(110),素数的欧拉数,对于素数,p,，其欧拉数,(p,)=p-1(1p-1),欧拉数的初等性质,当,p、q,都是素数时，,(pq,)=(p)(q)=(p-1)(q-1),例：,(15)=(3)(5)=2*4=8(1,2,4,7,8,11,13,14),当,e,与,m,互素，则存在正整数,d，,使得,ed=1 (mod m),称,d,是,e,关于模,m,的乘法逆元（简称“模乘逆元”或“模逆元”），记作,e,-1,例如：设,m=13，,则5*8=,40=3*13+1=1(mod 13),故 5,-1,=8,欧拉定理,假设,m、n,互素，则,m,(n,),=1 (mod n),例如：设,m=13，n=7，,则13,6,=4826809=689544*,7+1=1(mod 7),费马小定理欧拉定理的推论,设,p,与,m,互素，且,p,是素数，则,m,p-1,=1 (mod p),（因为,(p,)=p-1,）,基础定理,RSA,的理论基础,设,n,是两个不同的素数,p、q,之积，,x,是小于,n,的非负整数，,k,是非负整数，则有：,x,k(n)+1,=x (mod n),证明：若,x,不是素数,p,的倍数，则,p,与,x,互素，由费马小定理可得：,x,p-1,=1 (mod p)，,于是由前述各式可得：,x,k(n),=x,k(pq),=,x,k(p)(q),=,x,k(p-1)(q-1),=(x,p-1,),k(q-1),=1(mod p)，,故,x,k(n)+1,=x (mod p),若,x,是,p,的倍数，则,x=0 (mod p)，,于是也有：,x,k(n)+1,=0=x (mod p),故存在非负整数,i,，使得,x,k(n)+1,=ip+x (mod p)，,同理存在非负整数,j,，使得,x,k(n)+1,=jq+x (mod q),，,从而可得,ip=jq,又由于,p、q,互素，故,q,i,，,设整商为,t，,即,i=tq，,于是：,x,k(n)+1,=ip+x=tqp+x=tn+x=x(mod n),即最后证得：,x,k(n)+1,=x (mod n),6.3 RSA,算法,6.3.1,概述,发明人,RSA(,Ron,Rivest,AdiShamir,和,Leonard,Adleman,),1977,年在,麻省理工学院开发,1978,年发表,是最典型的公钥密码体制,算法基于单向陷门函数的原理,以模幂运算为基本运算,安全性基于大数因子分解的困难性（将一个充分大的正整数分解成两个素数之积几乎是不可能的）,数学基础是著名的欧拉,(,Euler),数论,6.3.2 RSA,密码体制的创建,选择两个充分大的不同的素数,p,和,q,计算积,n=,pq,及其欧拉数,(n)=(p-1)(q-1),选择一个介于1到,(n),之间且与,(n),互素的正整数,e,即1,e(n),且,GCD(e,(n)=1,求出,d=e,-1,(mod(n),即,e d=1,(mod(n),对明文空间,0,n-1,中的数,x，,例：,P115【,例,6-2】,以,为公钥加密：,y=E(x)=x,e,(mod n),以,为私钥解密：,x=D(y)=y,d,(mod n),解密还原性的证明：,由于,ed=1(mod(n)，,故存在非负整数,k，,使得：,ed=k(n)+1，,于是由基础定理可得：,D(E(x)=(x,e,),d,=x,ed,=x,k(n)+1,=x (mod n),注1：,p,q,从理论上讲也是私钥的组成部分，但因在解密过程中不用，故在确定,e,d,之后应予以销毁,注2:加密前明文,M,需表示为若干,0,n-1,的代码,M,i,实例：对英文字母从126编码，空格为0，对明文双字母编码，如“,its all greek to me”,编码为：0920、1900、0112、1200、0718、0505、1100、2015、0013、0500,设,p=47、q=59，,则,n=2773，(2773)=46*58=2668,因17*157=2669=1,(mod 2668)，,故取公钥为，私钥为,对明文组,M=0920,加密，,C=920,17,=0948,(mod 2773)，,1900,17,=2342,(mod 2773),，其余各组的密文为：,1084、1444、2663、2390、0778、0774、0219、1655,对密文组,C=948,解密，,M=948,157,=920(mod 2773),详见：,RSA,加密解密实例,.doc,6.3.4,计算方法及其程序实现,如何计算模逆元,要在已知,e,、,m,的情况下，求,d,，使得,e*d=1(mod m),也即找整数,k,，使得,e*,d+mk,=1,这相当于求解,d,、,k,都是未知数的二元一次不定方程,e*,d+mk,=1,的最小整数解,扩展,Euclid,算法,输入：正整数,a、b,输出：,GCD(a,b),及满足,ax+by=GCD(a,b),的整数,x、y,例如：设,a=21、b=15，,则,GCD(a,b)=3，x=-2、y=3,算法步骤描述：,置,x,1,=1，x,2,=0，y,1,=0，y,2,=1,计算,q=a/b，r=a%b,若,r=0，,则,GCD(a,b)=b，x=x,2,，y=y,2,，,算法结束；否则做下步,依次令,a=b，b=r，t=x,2,，x,2,=x,1,-qx,2,，x,1,=t，,t=y,2,，y,2,=y,1,-qy,2,，y,1,=t，,然后转2),附：,扩展,Euclid,算法,.CPP,乘法逆元的计算,输入：正整数,e、m,输出：,GCD(e,m),及满足,ed=,GCD(e,m,)(mod m),的整数,d,当,GCD(e,m,)=1,（即,e、m,互素）,，,则,d=e,-1,(mod m),例如：设,e=7、m=17，,则,GCD(7,17)=1，d=5=7,-1,；,因为7*5=35=17*2+1=1(,mod 17),算法：在扩展,Euclid,算法中令,a=e、b=m，,则,ex+my=GCD(e,m)(mod m)，,即,ex=GCD(e,m)(mod m)；,若结果,GCD(e,m)=1，,则,d=e,-1,=x；,否则,e,没有逆元,附：,求乘法逆元,.CPP,解密指数最小正逆元的计算,附：,求,最小正逆元,.CPP,设,d,是,e,的逆元，即,ed=1(mod m)，,由于,e(d+km)=ed+ekm=ed=1(mod m)，,故,d+km,也是,e,的逆元，可见乘法逆元不惟一。,在上述乘法逆元算法中得到的逆元最接近零，但有可能为负。,例如：设,e=3、m=40，,则,GCD(3,40)=1，,但,d=13，,显然不能用作,RSA,算法的解密指数。因此必须将这种负逆元调整为正逆元，才能得到解密指数。,改进后的算法如下：,输入：正整数,e、m,输出：,GCD(e,m),及满足,ed=GCD(a,m)(mod m),的最小正整数,d;,当,CD(e,m)=1，,则,d=e,-1,(mod m),就是所求解密指数,模幂的快速算法,输入：整数,n、,正整数,m、e,输出：,C=n,e,(mod m),算法：,将,e,表示为二进制形式(,b,k,b,k-1,b,1,b,0,),C=1,对于从,k,到0的,i,做,C=C*C(mod m)，,如果,b,i,=1,则再做,C=C*n (mod m),返回,C,附：,快速求模幂,.CPP,素性检测算法之一,Miller-Rabin,算法,对于充分大的正奇数,n，,设,n-1=2,k,m（,其中,k,是非负整数、,m,是正奇数），,若,b,m,=1(mod n),或,b,2,j,m=1,（,其中 0,j i-1），,则称,n,通过以,b,为基的,Miller-Rabin,素性检测,也即,n,以(1-1/4,b,),的概率是素数,输入：大奇数,n、,检测次数,t,输出：确定,n,是合数或者以(1-1/4,t,),的概率是素数。如：,t=5，,则判定,n,是素数的正确性约为：(1-1/4,5,)=0.9990234375,算法：,将,n-1,表示为二进制形式(,b,k,b,k-1,b,1,b,0,),随机选取从1到,n-1,的整数,a,x=1,对于从,k,到0的,i,依次做:,x0=x、x=x,2,(mod n)，,如果,x=1&x01&x0n-1,则返回“是”，算法结束；如果,b,i,=1,则再做,x=x*a (mod n),如果,x 1,则返回“是”，算法结束,转2)直至算法结束或完成,t,回测试，若完成,t,回测试则返回“不是”，即,n,是伪素数,附：,用,M-R,检测素数,.CPP,求,6