第3章公钥密码算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,3,章 公钥密码算法,1,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,2,3.1,问题的提出,密钥管理量的困难,传统密钥管理两两分别用一对密钥时，则,n,个用户需要,C(n,2)=n(n-1)/2,个密钥，当用户量增大时，密钥空间增大如：,n=100,时,C(100,2)=4,995,；,n=5000,时,C(5000,2)=12,497,500,。,数字签名的问题,传统加密算法无法实现抗抵赖的需求。,3,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,4,3.2,公钥加密模型,5,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,6,3.3,什么是公钥密码体制,公钥密码又称为双钥密码和非对称密码，是,1976,年由,Diffie,和,Hellman,在其“密码学新方向”一文中提出的。,见划时代的文献,W.Diffie,and,M.E.Hellman,New,Directrions,in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654,单向陷门函数是满足下列条件的函数,f,(1),给定,x,计算,y=,f(x,),是容易的；,(2),给定,y,计算,x,使,y=,f(x,),是困难的,(,所谓计算,x=f,-1,(Y),困难是指计算上相当复杂已无实际意义,),；,(3),存在,，已知,时,对给定的任何,y,，若相应的,x,存在，则计算,x,使,y=,f(x,),是容易的。,7,注,：,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,是不可行的。,算法代表：背包算法，,RSA(Rivest,Shamir,Adleman,),，椭圆曲线,ECC,（,Eilliptic,Curve,Croptography,),。,8,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,9,3.4,公开密钥的加密,3.4.1,公开密钥密码的重要特性,加密与解密由不同的密钥完成,加密,:X Y,：,Y=E,KU,(X),解密,:Y X:X=D,KR,(Y)=D,KR,(E,KU,(X),知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；,两个密钥中任何一个都可以用作加密而另一个用作解密,(,不是必须的,),X=D,KR,(E,KU,(X)=E,KU,(D,KR,(X),10,3.4.2,基于公开密钥的加密过程,11,3.4.3,基于公开密钥的鉴别过程,12,3.4.4,用公钥密码实现保密,用户拥有自己的密钥对,(KU,KR),公钥,KU,公开，私钥,KR,保密,A-B,：,Y=,E,KUb,(X,),B,：,D,KRb,(Y,)=,D,KRb,(E,KUb,(X,)=X,13,3.4.5,用公钥密码实现鉴别,条件：两个密钥中任何一个都可以用作加密而另一个用作解密,鉴别：,A ALL,：,Y=,D,KRa,(X,),ALL,：,E,KUa,(Y,)=,E,KUa,(D,KRa,(X,)=X,鉴别,+,保密：,A-B,：,Z=,E,KUb,(D,KRa,(X,),B,：,E,KUa,(D,KRb,(Z,)=X,14,3.4.6,公钥密钥的应用范围,加密,/,解密,数字签名,(,身份鉴别,),密钥交换,15,3.4.7,基本思想和要求,涉及到各方：发送方、接收方、攻击者,涉及到数据：公钥、私钥、明文、密文,公钥算法的条件：,产生一对密钥是计算可行的,已知公钥和明文，产生密文是计算可行的,接收方利用私钥来解密密文是计算可行的,对于攻击者，利用公钥来推断私钥是计算不可行的,已知公钥和密文，恢复明文是计算不可行的,(,可选,),加密和解密的顺序可交换,16,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,17,3.5,背包问题,3.5.1,背包问题描述,已知一长度为,b,的背包及长度分别为,a1,a2,an,的,n,个物品，假定这些物品的直径与背包相同，若从这些物品中选出若干个正好装满这个背包，那么究竟是那些物品，,即求解 ；,其中,a,i,和,b,都是正整数，背包问题是著名的,np,完备类困难问题，至今没有好的求解方法，而对,2,n,中可能进行搜索实际上是不可能的。,18,3.5.2,背包问题用于公钥密码学,做法：明文为,X,，,S,为密文,奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能,把易解的背包问题修改成难解的背包问题,公开密钥使用难解的背包问题,私钥使用易解的背包问题,19,3.5.3,易解的背包问题（超递增背包）,满足下列条件的背包，,ai,aj,(j=1,i-1),，这样的背包也被称为简单背包,.,求解过程,从最大的,ai,开始，如果,S,大于这个数，则减去,ai,记,xi,为,1,，否则记,xi,为,0,如此下去，直到最小的,ai,例如,背包序列,2,3,6,13,27,52,求解,70,的背包,结果为,2,3,13,52,所以，密文,70,对应的明文为,110101,20,3.5.4,转换背包,简单背包用作私钥,如何产生相应的公钥,转换,做法：,选择一个整数,m ,ai,(i=1,n),，然后选择一个与,m,互素的整数,w,，然后,a,i,=,wa,i,(mod m)(i=1,n),这里的,a,i,是伪随机分布的。,这样得到的背包是非超递增背包。,21,3.5.5 MH,背包公钥密码,背包公钥密码,选取正整数,a1,a2,an,作为公钥，明文位串为,m=m1m2,mn,。,利用公钥加密问题,c=a1 m1+a2m2+an,mn,。,从密文,c,求明文,m,等价于背包问题。,MH,背包公钥密码,其背包系列,a1,a2,an,是由超递增系列,b1,b2,bn,（）,经,MH(Merkle-Hellman,),变换,a,k,=,wb,k,(mod,m),得到的。虽然，,a1,a2,an,不具有超递增性，但可经变换后成为超递增系列求解。,22,加密,将明文分为长度为,n,的块,X=(x,1,x,n,),然后用公钥,A=(a,1,a,n,),，将明文变为密文,S,S=E(X)=,a,i,x,i,解密,先计算,S=w,-1,S mod m m,大数；,w,、,m,互素,再求解简单背包问题,S=,a,i,x,i,23,3.5.6,例,-,从私钥计算公钥,私钥,2,3,6,13,27,52,N=31,m=105,2*31 mod 105=62,3*31 mod 105=93,6*31 mod 105=81,13*31 mod 105=88,27*31 mod 105=102,52*31 mod 105=37,公钥,62,93,81,88,102,37,24,3.5.7,例,-,加密,消息,=011000 110101 101110,明文,:0 1 1 0 0 0,背包,:62 93 81 88 102 37,密文,:93+81=174,011000,对应于,93+81=174,110101,对应于,62+93+88+37=280,101110,对应于,62+81+88+102=333,25,3.5.8,例,-,解密,解密者知道,2,3,6,13,27,52,n,m,计算,n(n,-1,)=1mod(m),n,-1,=61,174*61 mod 105=9=3+6,对应于,011000,280*61 mod 105=70=2+3+13+52,对应于,110101,333*61 mod 105=48=2+6+13+27,对应于,101110,因此,消息,=011000 110101 101110,26,3.5.9,背包密码系统的意义,是第一个公钥密码系统；,有较好的理论价值；,在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷。,27,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,28,3.6,数论简介,3.6.1,欧拉定理,表述,1,：,将,Z/(n,）表示为,Z,n,，其中,n=,pq,;,p,q,为素数且相异。若,Z*,n,=,g,Z,n,|gcd(g,n,)=1,，易见,Z*,n,为,(n),阶的乘法群，且有,g,(n),1(mod n),，而,(n)=(p-1)(q-1),。,表述,2,：,若整数,g,和,n,互素，则,g,(n,),1(mod n),；其中,(n),为比,n,小，但与,n,互素的正整数个数,称为,(n),的欧拉函数。,29,3.6.1,欧拉定理,表述,3,：,给定两个素数,p,和,q,，以及两个整数,m,、,n,，使得,n=,pq,，且,0mn,，对于任意整数,k,下列关系成立，,30,3.6.2,原根,Euler,定理表明,对两个互素的整数,a,、,n,，,a,(n,),1 mod n,。,素数,p,的原根,(primitive root),定义：如果,a,是素数,p,的原根，则数,a mod p,a,2,mod p,a,p-1,mod p,是不同的并且包含,1,到,p-1,的整数的某种排列。对任意的整数,b,，我们可以找到唯一的幂,I,满足,b,a,i,mod p,，,0=I=(p-1),。,31,3.6.3,离散对数,若,a,是素数,p,的一个原根,则对任意整数,b,，,b0 mod p,，存在唯一的整数,i,1i(p-1),使得,:,ba,i,mod p,，,I,称为,b,以,a,为基数的模,p,的指数,(,离散对数,),，记作,ind,a,p,(b,),。,容易知道,:,ind,a,p,(xy,)=,ind,a,p,(x)+ind,a,p,(y,)mod,(p,),ind,a,p,(x,r,)=,rind,a,p,(x,)mod,(p,),离散对数的计算,:,yg,x,mod p,已知,g,x,p,计算,y,是容易的；,已知,y,g,p,计算,x,是困难的。,32,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,33,3.7,Diffie-Hellman,密钥交换算法,Diffie,和,Hellman,在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也没能找出一个真正带,陷门,的单向函数。,然而，他们给出单向函数的实例，并且基于此提出,Diffie-Hellman,密钥交换算法。,34,这个算法是基于有限域中计算离散对数的困难性问题之上的：,设,F,为有限域，,gF,。并且对任意正整数,x,，计算,g,x,是容易的；但是已知,g,和,y,求,x,使,y=,g,x,，是计算上几乎不可能的。,这一问题称为有限域,F,上的离散对数问题。,35,对,Diffie-Hellman,密钥交换协议描述：,Alice,和,Bob,协商好一个大素数,p,，和大的整数,g,，,1gp,，,g,是,p,的原根。,p,和,g,无须保密，可为网络上的所有用户共享。,当,Alice,和,Bob,要进行保密通信时，他们可以按如下步骤来做：,(1)Alice,送取大的随机数,x,，并计算,Y=,g,x,(mod P),(2)Bob,选取大的随机数,x,，并计算,Y,=,g,x,(mod,P),(3)Alice,将,Y,传送给,Bob,；,Bob,将,Y,传送给,Alice,。,(4)Alice,计算,K=(Y,),x,(mod,P);,(5)Bob,计算,K,(,Y),x,(mod,P),，,易见，,K=K,=,g,xx,(mod P),。,36,由,(4)(5),知，,Alice,和,Bob,已获得了相同的秘密值,K,。双方以,K,作为加解密钥以传统对称密钥算法进行保密通信。,注：,Diffie-Hellman,密钥交换算法拥有美国和加拿大的专利,。,37,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,38,3.8 RSA,公钥算法,RSA,公钥算法是由,Rivest,Shamir,和,Adleman,在,1978,年提出来的（见,Communitions,of the ACM.Vol.21.No.2.Feb.1978,PP.120-126),。该算法的数学基础是初等数论中的,Euler,（欧拉）定理，并建立在大整数因子的困难性之上。,39,3.8.1 RSA,密码体制描述,首先，明文空间,P,密文空间,C=Zn.,密钥的生成,选择,p,q,，,p,q,为互异素数，计算,n=p*q,(n)=(p-1)(q-1),选择整数,e,使,gcd(,(n),e,)=1,1e,(n),计算,d,使,d=e,-1,(mod,(n),公钥,Pk,=,e,n,;,私钥,Sk,=,d,p,q,。,注意：当,0Mn,时,M,(n,),1(mod n),自然有：,M,K,(n)+1,M(mod n),而,ed,1(mod,(n),易见,(,M,e,),d,M(mod,n).,根据：表述,3,40,加密,(,用,e,n,),明文：,Mn,，密文：,C=,M,e,(mod,n).,解密,(,用,d,p,q,),密文：,C,，明文：,M=,C,d,(mod,n).,注意：,加密和解密是一对逆运算。,41,例子：,若,Bob,选择了,p=101,和,q,113,，那么，,n=11413,(n)=100112,11200,；,然而,11200,2,6,5,2,7,，一个正整数,e,能用作加密指数，当且仅当,e,不能被,2,，,5,，,7,所整除。（事实上，,Bob,不会分解,(n,),，而且用辗转相除法（欧式算法）来求得,e,，使（,e,(n,)=1),。,假设,Bob,选择了,e=3533,，那么用辗转相除法将求得：,d=e,-1,6597(mod 11200),于是,Bob,的解密密钥,d=6597.,42,Bob,在一个目录中公开,n=11413,和,e=3533,现假设,Alice,想发送明文,9726,给,Bob,，她计算：,9726,3533,(mod 11413)=5761,，且在一个信道上发送密文,5761,。,当,Bob,接收到密文,5761,时，他用他的秘密解密指数（私钥）,d,6597,进行解密：,5761,6597,（,mod 11413)=9726,43,注,：,RSA,的安全性是基于加密函数,e,k,(x,)=,x,e,(mod,n),是一个单向函数，所以对的人来说求逆计算不可行。,而,Bob,能解密的陷门是分解,n=,pq,，知,(n)=(p-1)(q-1),。从而用欧氏算法解出解密私钥,d.,44,3.8.2 RSA,密码体制的实现,实现的步骤如下：,Bob,为实现者,(1)Bob,寻找出两个大素数,p,和,q,(2)Bob,计算出,n=,pq,和,(n)=(p-1)(q-1).,(3)Bob,选择一个随机数,e(0e,(n),，满足,gcd,（,e,，,(n),）,1,(4)Bob,使用辗转相除法计算,d=e,-1,(mod,(n),(5)Bob,在目录中公开,n,和,e,作为她的公开钥。,45,密码分析者攻击,RSA,体制的关键点在于如何分解,n,。,若分解成功使,n=,pq,，则可以算出,(n,),（,p-1)(q-1),，,然后由公开的,e,，解出秘密的,d,。,（猜想：攻破,RSA,与分解,n,是多项式等价的。然而，这个猜想至今没有给出可信的证明！）,46,若使,RSA,安全，,p,与,q,必为足够大的素数，使分析者没有办法在多项式时间内将,n,分解出来。,建议选择,p,和,q,大约是,100,位的十进制素数。模,n,的长度要求至少是,512,比特。,EDI,攻击标准使用的,RSA,算法中规定,n,的长度为,512,至,1024,比特位之间，但必须是,128,的倍数。,国际数字签名标准,ISO/IEC 9796,中规定,n,的长度位,512,比特位。,47,为了抵抗现有的整数分解算法，对,RSA,模,n,的素因子,p,和,q,还有如下要求：,(1)|p-q|,很大，通常,p,和,q,的长度相同；,(2)p-1,和,q-1,分别含有大素因子,p,1,和,q,1,(3)P,1,-1,和,q,1,-1,分别含有大素因子,p,2,和,q,2,(4)p+1,和,q+1,分别含有大素因子,p,3,和,q,3,48,为了提高加密速度，通常取,e,为特定的小整数，,如,EDI,国际标准中规定,e,2,16,1=65537,ISO/IEC9796,中甚至允许取,e,3,。,这时加密速度一般比解密速度快,10,倍以上。,49,下面研究加解密算术运算,这个运算主要是模,n,的求幂运算。,著名的“平方,-,和,-,乘法”方法将计算,x,c,(mod,n),的模乘法的数目缩小到至多为,2,l,，这里的,l,是指数,c,的二进制表示比特数。,50,3.8.3,对,RSA,的攻击,1,、强力攻击（穷举法）：尝试所有可能的私有密钥,2,、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解,3,、时间性攻击：取决于解密算法的运算时间,51,90,年代大数分解的进程,分解数 尺寸,bits,分解日期 分解算法,MIPS,年,RSA-100 330 1991.4,二次筛法,7,RSA-110 364 1992.4,二次筛法,75,RSA-120 397 1993.4,二次筛法,830,RSA-129 425 1994.4,二次筛法,5000,RSA-130 430 1996.4,数域筛法,500,RSA-140 463 1999.2,数域筛法,RSA-155 512 1999.8,数域筛法,工作量的计算：,MIPS,表示每秒,100,万条指令的处理器运行一年的工作量，既,3*10,13,条指令。,200M PENTIUM CPU,为,50MIPS,52,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,53,3.9,椭圆曲线密码体制,1985,年,N.,Koblitz,和,V.Miller,分别独立提出了椭圆曲线密码体制,(ECC),，,其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。,54,(1),定义：,令,Fq,表示,q,个元素的有限域，用,E(Fq,),表示定义在,Fq,上的一个椭圆曲线,E,。,例如,y,2,=x,3,x,。,55,设,P,Q E,，,L,为联接,P,Q,的直线（若,P=Q,则,L,取过,P,点的切线）；设,R,为,L,与,E,的另一个交点，再取连接,R,与无穷远点的直线,L,，则,L,与,E,的另一个交点定义为,P,Q,。,56,设,P=(x1,y1)Q=(x2,y2)PQ=(x3,y3),，由,PQ,的定义，设,y=,x+,为通过,P,Q,两点直线,L,的方程；可算出,=(y2-y1)/(x2-x1),，,=y1-x1,。,易见直线,L,上的一个点（,x,x+,),是在椭圆曲线,E,上，当且仅当,(x+),2,=x,3,x,；,PQ=(x1,y1)(x2,y2)=(x3,y3),=(x3,-(x3+),57,（,2,）已知,E(Fq,),对点的“,”,运算形成一个,Abel,群，设,pE(Fq,),，若,p,的周期很大，即是,pp,p=,共有,t,个,p,相加,),成立的最小正整数,t,，,希望,t,很大,(t=p,的周期，表示,(p)=t),，,并且对,QE(Fq,),，定有某个正整数,m,使,Q=,mp,=,pp,p(,共有,t,个,p,相加,),。,定义：,m=,p,Q,(m,为以,p,为底,Q,的对数,),。椭圆曲线上的点形成的群,E(Fq,),，相关它的离散对数问题是难处理的。,为无穷远点，平行直线的交点,58,（,3,）建立椭圆曲线密码体制,选取基域,Fq,，,Fq,的椭圆曲线具体给定为确定的形式。在,E(Fq,),中选一个周期很大的点，如选了一个点,P=(,x,p,y,p,),，它的周期为一个大的素数,n,，记,(P)=n (,素数,),。,注意：在这个密码体制中，具体的曲线及点,P,和它的,n,都是公开信息，。,59,a),密钥的生成,Bob(,使用者,),执行了下列计算：,i),在区间,1,n-1,中随机选取一个整数,d,，,ii),计算点,Q,：,=,dP,(d,个,P,相,),，,iii)Bob,公开自己的公开密钥,(,E(Fq),p,n,Q,),，,iv)Bob,的私钥为整数,d,。,60,b)Alice,要发送消息,m,给,Bob,；,Alice,执行,i),查找,Bob,的公钥,(,E(Fq),p,n,Q,),ii),将,m,表示成一个域元素,mFq,iii),在区间,1,，,n-1,内选取一个随机数,k,iv),依据,Bob,的公钥计算点,(x1,y1),：,=,kP(k,个,P,相,),v),计算点,(x2,y2):=,kQ,如果,x2=0,则回到第,iii),步,vi),计算,C,：,=mx2,vii),传送加密数据,(x1,y1,C),给,Bob.,61,c)Bob,的解密过程,Bob,收到,Alice,的密文,(x1,y1,C),后执行,i),使用私钥,d,计算点,(x2 y2),：,=d(x1,y1),再计算,Fq,中,x,2,-1,=?,ii),通过计算,m,：,=Cx,2,-1,，恢复出明文数据,m,。,62,3.1,问题的提出,3.2,公钥加密模型,3.3,什么是公钥密码体制,3.4,公开密钥的加密,3.5,背包问题,3.6,数论简介,3.7,Diffie-Hellman,密钥交换算法,3.8RSA,公钥算法,3.9,椭圆曲线密码体制,3.10ECC,和,RSA,比较,63,3.10 ECC,和,RSA,比较,64,3.10 ECC,和,RSA,比较,65,作业,1,在使用,RSA,公钥系统中如果截取了发送给其他用户的密文,C=10,若此用户的公钥为,e=5,n=35,请问明文的内容是什么？,2,考虑一个常用质数,q=11,原根,a=2,的,Diffie_Hellman,方案，如果用户,A,的公钥为,YA=9,则,A,的私钥,XA,是多少？如果用户,B,的公钥为,YB=3,则共享的密钥,K,是多少？,66,