公钥密码一.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,6,章：,公钥密码,一、公钥密码的基本概念,二、公钥密码,RSA,三、背包公钥密码,四、公钥密码,Rabin,学习要点,了解非对称密码体制的提出背景、基本思想,了解非对称密码体制的基本应用方向,了解三种典型的公钥密码体制,DH,密钥交换算法,RSA,ECC,6,1,概述,问题的提出：,密钥管理困难,传统密钥管理两两分别用一对密钥时，则,n,个用户需要,C(n,2)=n(n-1)/2,个密钥，当用户量增大时,密钥空间急剧增大,。如,:,n=100,时,C(100,2)=4,995,n=5000,时,C(5000,2)=12,497,500,陌生人间的保密通信问题,数字签名的问题,传统加密算法无法实现抗抵赖的需求,公钥密码的基本概念,双钥密码体制(公钥密码体制),于1976年由,W.,Diffie,和,M.Hellman1976,提出，同时,R.Merkle1978,也独立提出了这一体制。可用于保密通信，也可用于数字签字。,这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。,公钥体制的基本原理是,陷门单向函数,。,注,：,1,*,.,仅满足,(1),、,(2),两条的称为单向函数；第,(3),条称为陷门性，,称为陷门信息。,2,*.,当用陷门函数,f,作为加密函数时，可将,f,公开，这相当于公开加密密钥。此时加密密钥便称为公开密钥，记为,Pk,。,f,函数的设计者将,保密，用作解密密钥，此时,称为秘密密钥，记为,Sk,。,由于加密函数是公开的，任何人都可以将信息,x,加密成,y=f(x),，,然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有,Sk,，,他自然可以解出,x=f,-1,(y),。,3,*,.,单向陷门函数的第,(2),条性质表明窃听者由截获的密文,y=f(x),推测,x,是不可行的。,是满足下列条件的函数,f,：,(1),给定,x,，,计算,y=f(x),是容易的,(2),给定,y,计算,x,使,y=f(x),是困难的,(3),存在,，,已知,时,对给定的任何,y,，,若相应的,x,存在，则计算,x,使,y=f(x),是,容易的,陷门单向函数,对公钥密码体制的要求,（,1,）参与方,B,容易通过计算产生一对密钥（公开密钥,K,Ub,和私有密钥,K,Rb,）。,（,2,）,在知道公开密钥和待加密报文,M,的情况下，对于发送方,A,，,很容易通过计算产生对应的密文：,C,E,KUb,（,M,）,（,3,）,接收方,B,使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：,M,D,KRb,（,C,）,D,KRb,（,E,KUb,（,M,）,（,4,）,敌对方即使知道公开密钥,K,Ub,，,要确定私有密钥,K,Rb,在计算上是不可行的。,（,5,）敌对方即使知道公开密钥,K,Ub,和密文,C,，,要想恢复原来的报文,M,在计算上也是不可行的。,（,6,）加密和解密函数可以以两个次序中的任何一个来使用,:,M,D,KRb,（,E,KUb,（,M,）,M=,E,KUb,(D,KRb,(M,),单向函数举例,离散对数,DL,。,给定一大素数,p,（比如，,p,在,2,1024,数量级），,p,1,含另一大素数因子,。,称,log,2,p,为素数,p,的长度。,1,2,p,-1,关于,mod,p,乘法构成了一乘群,Z,p,*,，,它是一个,p,1,阶循环群。该循环群的生成元一共有,(,p,-1),个。,设一个生成元为整数,g,，1,g,p,1。,设一个整数,x,，1,x,p,1。,设,y,满足,y=,g,x,mod,p,。,单向函数举例,已知,x,，,g,，,p,，,求,y=,g,x,mod,p,容易。,这是因为，采用折半相乘，只需要不超过,2log,2,p,次的,mod,p,乘法运算。,（实际上只需要不超过,2log,2,x,次的,mod,p,乘法运算。如,x,=15=1111,2,，,g,15,mod,p,=(,g,),2,g,),2,g,),2,g,mod,p,，,要用6次,mod,p,乘法）,单向函数举例,若已知,y,，,g,，,p,，,求,x,满足,y=,g,x,mod,p,，称为求解离散对数问题。记为,x,=,log,g,y,mod,p,。,求解离散对数问题的“最笨的方法”当然就是穷举，对每一个,x,0,1,2,p,1,检验是否,y=,g,x,mod,p,。穷举求解法的运算次数约为,(,p,1)/2,。许多求解离散对数问题的算法比穷举快得多，比如,Shanks,算法，,Pohlig-Hellman,算法等。最快求解法的运算次数约为数量级,单向函数举例,这个计算量称为亚指数计算量。这是什么概念呢？我们知道,p,的长度,是,log,2,p,。,看以下的不等式,。,当,log,2,p,1024,时，,亚指数计算量不小于,2,100,数量级。至少在在当前的计算水平之下是不能实现的。,单向函数举例,大整数分解,FAC,。,设有二大素数,p,和,q,。设,n=,pq,。,若已知,p,和,q,，求,n=,pq,只需一次乘法。,但若已知,n,，,求,p,和,q,满足,n=,pq,，则称为大整数分解问题。迄今为止，已知的各种算法的渐近运行时间约为：,试除法：,n,/2,。,二次筛(,QS),：,椭圆曲线(,EC),：,数域筛(,NFS),：,单向函数举例,背包问题。,已知向量,A,=(,a,1,a,2,a,N,)，,a,i,为正整数，,称其为,背包向量,，称每个,a,i,为物品重量。给定向量,x,=(,x,1,x,2,x,N,),，,x,i,0,1，,求和式（称为背包重量）,S,=,a,1,x,1,+,a,2,x,2,+,a,N,x,N,容易，只需要不超过,N,1,次加法。但已知,A,和,S,，,求,x,则非常困难，称其为背包问题，又称作,子集和,(,Subset-Sum),问题。一般只能用穷举搜索法，有2,N,种可能。,N,大时，相当困难。,单向函数举例,背包问题的特例：超递增背包问题。,将物品重量从小到大排列：,a,1,，,a,2,，,a,3,，,，,a,N,。称该背包问题为,超递增背包问题,，,如果：,a,1,a,2,；,a,1,+,a,2,a,3,；,a,1,+,a,2,+,a,3,a,4,；,a,1,+,a,2,+,a,3,+,a,N,-1,a,N,。,（超递增背包问题是容易解决的。）,单向函数举例,定理,设超递增背包重量为,S,。,如果,k,满足,a,k,S,a,k,+1,，则,a,k,是背包中的最大物品重量。,定理的证明,首先，背包中没有大于,a,k,的物品重量。,其次，背包中确有等于,a,k,的物品重量。,证明完毕。,注意到，寻找,k,满足,a,k,S,a,k,+1,只需要对比,N,次。,单向函数举例,超递增背包问题的解决方法,解决方法是可行的。设背包重量,S,，步骤如下。,（,1,）穷举：找,k,满足,a,k,S,0,，则令,S,:=,S-,a,k,，返回（,1,）。如果,w,=0,，则到（,4,）。,（,4,）输出前面存储的所有的,k,，停止。,单向函数举例,格的最小向量问题,(SVP),。,若干个,N,维向量组成的集合，如果满足,“集合中任何若干个向量的,整数线性组合,仍是集合中的一个向量。”,则该结合称为一个格。,关于格有以下的性质和概念。,如果格中存在这样的几个向量，满足,它们（实数）线性无关；,格中的任何其它向量都能唯一地表示为这几个向量的整数线性组合。则这几个向量构成的向量组称为基。,基中的向量的个数称为格的维数。,格的维数总是不超过,N,。,单向函数举例,给定一个格的一组基。寻找格中的“尺寸最小”的向量（即模最小的向量），称为格的最小向量问题,（,shortest vector problem,；,SVP,）。又称为格归约。,实际上，,格归约的传统算法为,LLL,算法，以后又有各种改进的算法。,当,格的,维数比较大时（比如，维数大于,200,），当前的所有格归约算法都不是有效算法。,公开密钥密码系统的分析方法,强行攻击,(,对密钥,),。,公开密钥算法本身可能被攻破。,可能报文攻击,(,对报文本身的强行攻击,),。,公钥密码系统的应用类型,加密,/,解密,数字签名,会话密钥交换,例子：简单数字签名,例子续：安全数字签名,二、公钥密码,RSA,公钥密码,RSA,1977,年由美国麻省理工学院的三位教授,Ronald,R,ivest,Adi,S,hamir,Leonard,A,dleman,联合发明,二、公钥密码,RSA,RSA,的密钥生成,选择两个大的素数,p,和,q,。,选择两个正整数,e,和,d,，满足：,ed,是,(,p,-1)(,q,-1),的倍数加,1,。,计算,n=,pq,。,Bob,的公钥是（,n,，,e,），对外公布。,Bob,的私钥是,d,，自己私藏。,至于（,p,，,q,），可以是,Bob,的另一部分私钥，也可以是对所有人（包括,Bob,）都保密的。,二、公钥密码,RSA,基本,RSA,的加密过程：,Alice,欲发送明文,m,给,Bob,，其中,0,m,n,。,Alice,用,Bob,的公钥（,n,，,e,），计算密文,c,为,c,=,m,e,(mod,n,),。,基本,RSA,的解密过程：,Bob,收到密文,c,后，用自己的公钥（,n,，,e,）和私钥,d,，计算,c,d,(mod,n,)=,m,ed,(mod,n,)=,m,。,（因为,ed,是,(,p,-1)(,q,-1),的倍数加,1,，所以,m,ed,(mod,n,)=,m,。这是数论中的一个基本结论）,二、公钥密码,RSA,基本,RSA,的安全性,攻击者,Eve,已经知道了,Bob,的公钥是（,n,，,e,）。,如果,Eve,还知道（,p,，,q,），则他容易知道,Bob,的私钥,d,。此时,Eve,只需要用推广的辗转相除法寻找,d,，满足,ed,=1(mod(,p,-1)(,q,-1),。,由,n,的值求解（,p,，,q,）的值，即求解,n,的大整数分解,n,=,pq,，是一个公认的数学难题（虽然至今并没有证明），暂时还没有有效的算法。,二、公钥密码,RSA,目前普遍使用的参数范围是,2,511,p,2,512,，,2,511,q,2,512,。,如果,Eve,欲穷举,p,的所有可能值，则穷举的次数约为,(2,512,-2,511,)/2=2,510,（次）。,（因此，基本,RSA,似乎是足够安全的）,二、公钥密码,RSA,基本,RSA,的一个安全性漏洞,设攻击者,Eve,获得了两组明文,/,密文对,(,m,1,，,c,1,),，,(,m,2,，,c,2,),。,如果,Bob,新截获了一个密文,c,，并发现：,（,1,）,c,=,c,1,c,2,(,mod,n,),，则,c,所对应的明文一定是,m,=,m,1,m,2,(,mod,n,),；,（,2,）,c,=,c,1,/,c,2,(,mod,n,),，则,c,所对应的明文一定是,m,=,m,1,/,m,2,(,mod,n,),；,（,3,）,c,=,c,2,/,c,1,(,mod,n,),，则,c,所对应的明文一定是,m,=,m,2,/,m,1,(,mod,n,),。,（模除运算,/,(,mod,n,),是一个数论运算）,二、公钥密码,RSA,基本,RSA,的这个安全性漏洞称为,可传递性,。,这个漏洞使得攻击者,Eve,对某些新的密文能够轻而易举地找到其对应明文。,这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。（将在后面介绍）,为了克服基本,RSA,的这个安全性漏洞，人们将基本,RSA,进行改造，引入,Hash,函数。（将在后面介绍）,要求：若使,RSA,安全，,p,与,q,必为足够大的素数，使,分析者没有办法在有效时间内将,n,分解出来。建议选择,p,和,q,大约是,100,位的十进制素数。模,n,的长度要求至少是,512,比特。,为了抵抗现有的整数分解算法，对,RSA,模,n,的素因子,p,和,q,还有如下要求：,(1)|p-q|,很大，通常,p,和,q,的长度相同；,(2)p-1,和,q-1,分别含有大素因子,p,1,和,q,1,(3)gcd(p,1,-1,q,1,-1),应该很小。,为了提高加密速度，通常取,e,为特定的小整数，如,EDI,国际标准中规定,e,2,16,1,，,ISO/IEC9796,中甚至允许取,e,3,。,这时加密速度一般比解密速度快,10,倍以上。,RSA,密钥的生成,例：,p=47,q=61,(n)=(47-1)(61-1)=2760,时，,SK=167,是否为,秘密密,钥的候选者？用欧氏算法计算：,gcd(2760,167)=1,即可证明。,Q,X1,X2,X3,Y1,Y2,Y3,1,0,2760,0,1,167,16,0,1,167,1,16,88,1,1,16,88,1,17,79,1,1,17,79,2,33,9,8,2,33,9,17,281,7,1,17,281,7,19,314,2,3,19,314,2,74,1223,1,用,RSA,算法加密与解密的过程：,例：明文,=,“,RSA ALGORITHM,”,(1),明文用数字表示 空白,=00,，,A=01,B=02,Z=26(,两位十进制数表示,),1819 0100 0112 0715 1809 2008 1300,(2),利用加密变换公式,C=,m,PK,mod r,即,C=1819,1223,mod 2867=2756,PK=1223=10011000111,=2,10,+2,7,+2,6,+2,2,+2,1,+2,0,=1024+128+64+4+2+1,C=1819,1223,(mod 2867),=1819,1024,1819,128,1819,64,1819,4,1819,2,1819,1,(mod 2867),=2756,2756 2001 0542 0669 2347 0408 1815,选择两个大素数,p,和,q,，,通常要求每个均大于,10,100,。,计算,n,p,q,和,z,(,p,1)(,q,1),。,选择一与,z,互素的数、令其为,d,。,找到一个,e,满足,e,d,1(mod,z,),。,选好这些参数后，将明文划分成块，使得每个明文报文,P,长度,m,满足,0,m,n,。,加密,P,时，计算,C,P,e,(mod,n,),，,解密,C,时计算,P,C,d,(mod,n,),。,由于模运算的对称性，可以证明，,在确定的范围内，加密和解密函数是互逆的。,为实现加密，需要公开,(e,n),，,为实现解密需要,(d,n),。,RSA,算法归纳,如何计算,a,b,mod n,？,如何判定一个给定的整数是素数？,如何找到足够大的素数,p,和,q?,问题,要点,1,：,(a x b)mod n=(a mod n)x(b mod n)mod n,要点2：,a,16,=,aaaaaaaaaaaaaaaa,=a,2,a,4,a,8,a,16,更一般性的问题：,a,m,m,的二进制表示为,b,k,b,k-1,b,0,则,计算,a,m,mod n,a,m,mod n=,a,(2,i,),mod n,=,a,(2,i,),mod n,b,i,0,b,i,0,如何计算,a,b,mod n,？,快速取模指数算法计算,a,b,modn,c 0;d 1,for i k,downto,0,do c 2,c,d (d d)mod n,if bi=1,then c c+1,d (d a)mod n,return d,快速取模指数算法：例子,i,9,8,7,6,5,4,3,2,1,0,bi,1,0,0,0,1,1,0,0,0,0,c=0,1,2,4,8,17,35,70,140,280,560,d=1,7,49,157,526,160,241,298,166,67,1,7,560,mod561=1,Miller and Rabin,WITNESS,算法,WITNESS(a,n),判定,n,是否为素数，,a,是某,个,小于,n,的整数,1.,令,b,k,b,k-1,b,0,为,(n-1),的二进制表示，,2.d,1,3.for i k,downto,0,4.do x d,5.d (d d)mod n,6.if d=1 and x 1 and x n-1,7.then return TRUE,8.if b,i,=1,9.then d (d a)mod n,10.if d 1,11.then return TRUE,12.return FALSE,返回值：,TRUE:n,一定,不是素数,FALSE:n,可能是素数,应用：,随机选择,a n,计算,s,次，,如果每次都返回,FALSE,，,则这时,n,是素数的概率为,(1-1/2,s,),如何判定一个给定的整数是素数？,1.,随机选一个奇数,n(,伪随机数发生器,),2.,随机选择一个整数,a n,3.,执行概率素数判定测试,如果,n,未测试通过,则 拒绝数值,n,转向步骤,1,4.,如果,n,已通过足够的测试,则接受,n,否则转向步骤,2;,说明：,随机选取大约用,ln(N)/2,的次数，如,ln(2,200,)/2=70,好在生成密钥对时才用到，慢一点还可忍受。,确定素数,p,和,q,以后，只需选取,e,满足,gcd(e,(n,),=1,计算,d=e,-1,mod,(n),（,扩展的欧拉算法）,如何找到足够大的素数,p,和,q?,p,和,q,在长度上应仅差几个数位，即,p,和,q,应是,10,75,到,10,100,（,p-1,）,和（,q-1,）,都应包含一个较大的素数因子,gcd(p-1,q-1),应比较小,如果,en,且,d,a,1,+,a,2,+,a,3,+,a,n,；,M,U,；,Ua,1,M,；,M,与,U,互素，因此可以用辗转相除法计算出,U,关于,(,mod,M,),的逆元,U,-1,。,三、背包公钥密码,计算：,b,1,=,Ua,1,(mod,M,),，,b,2,=,Ua,2,(mod,M,),，,b,3,=,Ua,3,(mod,M,),，,，,b,n,=,Ua,n,(mod,M,),。,（此时,a,1,=,U,-1,b,1,(mod,M,),，,a,2,=,U,-1,b,2,(mod,M,),，,a,3,=,U,-1,b,3,(mod,M,),，,，,a,n,=,U,-1,b,n,(mod,M,),。,）,三、背包公钥密码,b,1,，,b,2,，,b,3,，,，,b,n,是,n,个物品重量。因为,Ua,1,M,Ua,1,(mod,M,)=,b,1,，,Ua,2,Ua,1,M,Ua,2,(mod,M,)=,b,2,，,Ua,3,Ua,1,M,Ua,3,(mod,M,)=,b,3,，,，,Ua,n,Ua,1,M,Ua,n,(mod,M,)=,b,n,，,所以通常,b,1,，,b,2,，,b,3,，,，,b,n,不,具有,超递增性,。,b,1,，,b,2,，,b,3,，,，,b,n,是公钥。,a,1,，,a,2,，,a,3,，,，,a,n,，,M,，,U,都是私钥。,三、背包公钥密码,背包公钥密码的加密,设明文,m,=(,m,1,m,2,m,3,m,n,),是长度为,n,的比特串。使用公钥,b,1,，,b,2,，,b,3,，,，,b,n,计算密文,c,：,c,=,m,1,b,1,+,m,2,b,2,+,m,3,b,3,+,m,n,b,n,。,密文,c,是一个正整数。,（密文,c,是背包重量，由,n,个物品重量,b,1,，,b,2,，,b,3,，,，,b,n,中的某些,物品重量相加而成。若截获了,密文,c,，又知道,n,个物品重量,b,1,，,b,2,，,b,3,，,，,b,n,，求解,明文,m,就是,背包问题。,）,三、背包公钥密码,背包公钥密码的解密,使用私钥,a,1,，,a,2,，,a,3,，,，,a,n,，,M,，,U,，计算变换课文,C,：,C,=,U,-1,c,(mod,M,),=,U,-1,(,m,1,b,1,+,m,2,b,2,+,m,3,b,3,+,m,n,b,n,)(,mod,M,),=,m,1,a,1,+,m,2,a,2,+,m,3,a,3,+,m,n,a,n,(mod,M,),=,m,1,a,1,+,m,2,a,2,+,m,3,a,3,+,m,n,a,n,。,根据定理中的方法，容易解出,明文,m,。,三、背包公钥密码,变换课文,C,是背包重量，由,n,个物品重量,a,1,，,a,2,，,a,3,，,，,a,n,中的某些,物品重量相加而成。若已知,变换课文,C,，又知道,n,个物品重量,a,1,，,a,2,，,a,3,，,，,a,n,，求解,明文,m,就是超递增,背包问题。,四、公钥密码,Rabin,Rabin,的密钥生成,选择两个大的素数,p,和,q,，要求,p,和,q,都是,4,的倍数加,3,。,计算,n=,pq,。,Bob,的公钥是,n,，对外公布。,Bob,的私钥是（,p,，,q,），自己私藏。,四、公钥密码,Rabin,Rabin,的加密过程,Alice,欲发送明文,m,给,Bob,，其中,0,m,n,。,Alice,用,Bob,的公钥,n,，计算：,c,=,m,2,(mod,n,),。,c,为密文。,四、公钥密码,Rabin,Rabin,的解密过程,Bob,收到密文,c,后，用自己的私钥（,p,，,q,）计算,四、公钥密码,Rabin,计算,4,个数,m,(1,1),，,m,(1,2),，,m,(2,1),，,m,(2,2),，满足：,0,m,(1,1),n,；,0,m,(1,2),n,；,0,m,(2,1),n,；,0,m,(2,2),n,；,m,(1,1)(mod,p,)=,m,p,；,m,(1,1)(mod,q,)=,m,q,；,m,(1,2)(mod,p,)=,m,p,；,m,(1,2)(mod,q,)=,q,-,m,q,；,m,(2,1)(mod,p,)=,p,-,m,p,；,m,(2,1)(mod,q,)=,m,q,；,m,(2,2)(mod,p,)=,p,-,m,p,；,m,(2,2)(mod,q,)=,q,-,m,q,。,四、公钥密码,Rabin,（,4,个数的计算使用孙子定理（中国剩余定理）。）,于是，真正的明文,m,一定就是,4,个数,m,(1,1),，,m,(1,2),，,m,(2,1),，,m,(2,2),之中的一个。,观察,4,个数，排除那些没有意义的“乱码课文”。哪个是有意义的课文，哪个就是真正的明文,m,。,解密完毕。,四、公钥密码,Rabin,Rabin,的解密原理,因为,n=,pq,是两个不同的素数的乘积，所以，关于未知数,x,的二次方程,c,=,x,2,(mod,n,),恰好有,4,个不同的根,x,，分别有以下形状：,一个根,的,(,mod,p,),、,(,mod,q,),值是,m,p,、,m,q,；,一个根,的,(,mod,p,),、,(,mod,q,),值是,m,p,、,q,-,m,q,；,一个根,的,(,mod,p,),、,(,mod,q,),值是,p,-,m,p,、,m,q,；,一个根,的,(,mod,p,),、,(,mod,q,),值是,p,-,m,p,、,q,-,m,q,。,四、公钥密码,Rabin,4,个根中有一个是,明文,m,。,如果把,(,mod,p,),、,(,mod,q,),值为,m,p,、,m,q,的,根叫做,m,，则,(,mod,p,),、,(,mod,q,),值为,p,-,m,p,、,q,-,m,q,的,根就是,n,-,m,。,另外两个根的和也等于,n,。即如果把一个叫做,m,，则另一个就是,n,-,m,。,那么，,4,个不同的根怎样计算呢？如果仅仅知道,n,，而不知道分解式,n=,pq,，则无法计算,m,p,和,m,q,，因而无法计算这,4,个不同的根。,四、公钥密码,Rabin,如果知道了,n,的分解式,n=,pq,，则能够计算,m,p,和,m,q,。再由,m,p,和,m,q,计算,4,个根,，使用的是著名的孙子定理（中国剩余定理）（略）。,最后，要判断哪一个根是真正的明文。一般，真正的明文都具有语言含义，而其它的根则是没有语言含义的“乱码课文”。当然也有例外，比如当明文是一副图象的编码时，明文也是没有语言含义的“乱码课文”。,四、公钥密码,Rabin,Rabin,的安全性原理,攻击者,Eve,截获了密文,c,。,Eve,还知道,Bob,的公钥,n,，也知道明文,m,满足方程,c,=,m,2,(mod,n,),。,但是他,不知道,n,的分解式,n=,pq,，无法计算,m,p,和,m,q,，进一步无法计算,4,个根。,求,n,的分解式,n=,pq,是大数分解问题。,四、公钥密码,Rabin,RSA,与,Rabin,比较,比较项目,RSA,Rabin,公钥,(,n,e,),n,私钥,d,(,p,q,),加密算法,c,=,m,e,(mod,n,),c,=,m,2,(mod,n,),解密算法,m,=,c,d,(mod,n,),若干步,安全基础,大数分解问题,的困难性,大数分解问题,的困难性,