网络与信息安全公钥密码体制.ppt

1,4.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制,第4章公钥密码体制,2,4.1公钥密码体制概述,私钥密码体制的局限性密钥量大：n个用户相互通信,需用个n(n-1)/2密钥.应用范围小：不易实现数字签名公钥密码体制思想的产生1976年,斯坦福大学的博士生W.Diffie和其导师M.E.Hellman提出了公钥密码的新思想W.DiffieandM.E.Hellman,Newdirectionincryptography,IEEETrans.onInformationTheory,1976,IT-22.(6),pp.644-654.1978年,Merkle和Hellman联合提出了基于组合数学中“背包问题”的公钥密码体制(MH背包公钥密码体制).不久被攻破.,3,4.1公钥密码体制概述,公钥密码的基本思想与单向陷门函数的思想密切相关构造公钥密码体制的一般原理如下：(1)从一个困难问题P开始。P问题是不可行的，它是基于计算复杂性，而且最好是计算平均复杂度。(2）取出P中的一个子问题P1。它应该是很容易解决的，一般是多项式时间，最好是线性时间问题。(3)对P1问题进行伪装成P2问题，使P2问题看起来很像原来的P问题，好像P问题一样难。(4）公开P2问题，并把P2问题用作一个加密密钥加密函数；将如何从P2恢复P1问题的信息保密，称该信息为“陷门”。(5）使系统合法用户能通过求解容易问题P1进行解密，而其它用户不得不求解P2，而求P2的过程至少看起来好像是在求解原来困难的P问题,4,目前出现的且具有较高的安全性的公钥密码体制主要基于的困难问题：(1)基于数论中的大整数分解问题（诸如RSA）；(2)基于离散对数问题（如ElGmal、DiffieHellman密钥交换协议）；(3)基于椭圆曲线上的离散对数问题（如ECC）；(4)基于线性编码的解码问题（如MeElice密码体制）；(5)基于自动机与语言理论,5,4.1公钥密码体制概述,公钥密码体制(PKC:publickeycryptosystem)原理密钥K=(PK,SK):加密密钥PK公开;解密密钥SK保密.在计算上由PK推出SK是困难的.加密算法EPk:c=EPk(m)解密算法DSk满足:m=DPk(c)DSK(EPK(x)=x.,6,4.1公钥密码体制概述,公钥密码体制的要求用户：产生密钥对K=(PK,SK)在计算上是可行的发送方：已知公钥与明文，产生密文是容易的接收方：利用私钥解密密文在计算上是可行的攻击者：利用公钥求解私钥在计算上是不可行的攻击者：已知公钥与密文，在不知道私钥的情况下，恢复明文在计算上是不可行的,7,离散对数,指标y=ax(a0,a1)的逆函数称为以a为底的对数，记为x=logay设p为素数，a是p的本原根，则a0,a1,.,ap-1产生1到p-1中所有值，且每个值只出现一次。对任一b1,p-1，都存在唯一的i(1ip)，使baimodp。i称为模p下以a为底b的指标，记为i=inda,p(d),8,离散对数,指标的性质inda,p(1)=0inda,p(a)=1inda,p(xy)=inda,p(x)+inda,p(y)modj(p)inda,p(yr)=rinda,p(y)modj(p)后两个性质基于下列结论若azaqmodp,a和p互素，则zqmodj(p),9,离散对数,设p是素数，a是p的本原根。对b1,p-1,有唯一的i1,p-1,使baimodp。称i为模p下以a为底b的离散对数，记为ilogab(modp)已知a,p,i,求b比较容易，以及a,b,p,求i非常困难,10,公钥密码体制的原理,公钥体制(Publickeysystem)(Diffie和Hellman,1976)每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。,11,公钥体制加密,公钥体制加、解密m=D(c)=DSKB(EPKB(m)安全保障从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是不可行的。由于任一用户都可用用户B的公开钥PKB向他发送机密消息，因而密文c不具有认证性。,12,公钥密码认证体制,用户A以自己的秘密钥SkA对消息m进行A的专用变换DSKA，A计算密文：c=DSKA(m)送给用户B，B验证c：m=EPKA（c）=EPKA(DSKA(m)安全性：由于SkA是保密的，其他人都不可能伪造密文c，可用A的公开钥解密时得到有意义的消息m。因此可以验证消息m来自A而不是其他人，而实现了对A所发消息的认证。,13,公钥密码认证体制,发送者A,加密算法,SKA,密钥源,PKA,解密算法,接收者B,密码分析员,m,c,m,SKA,14,公钥保密和认证体制,15,单向函数,一个可逆函数f：AB，若它满足：1o对所有xA，易于计算f(x)。2o对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为n，计算函数的时间是na的倍数，a为一固定的常数。若计算函数时间是an的倍数，则为不可能做到的。,16,限门单向函数,单向函数是求逆困难的函数，而单向陷门函数(Trapdoorone-wayfunction)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。限门单向函数是一族可逆函数fk，满足Y=fk(X)易于计算（当k和X已知）Xf-1k(Y)易于计算（当k和Y已知）Xf-1k(Y)计算上不可行（Y已知但k未知）研究公钥密码算法就是找出合适的单向限门函数,17,4.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制,第4章公钥密码体制,18,4.2RSA密码体制,1978年,R.Rivest,A.Shamir,L.Adleman提出RSA密码体制R.Rivest,A.Shamir,L.Adleman,Amethodforobtainingdigitalsignaturesandpublic-keycryptosystem,Comm.ACM21(2)(1978),pp.120-126.基于大合数因式分解的困难性安全,易懂.可用于加密与数字签名.ISO,ITU,SWIFT把RSA选为加密标准;Internet的E-Mail的保密系统GPG,国际VISA和MASTER组织的电子商务协议(SET协议)都将RSA作为传送会话密钥和数字签名的标准.,19,4.2RSA密码体制,20,4.2RSA密码体制,RSA密码体制算法密钥生成算法(1)选取两个大素数p,q(2)计算n=pq,(n)=(p-1)(q-1)(3)随机选取e:1e(n)，与(n)互素(4)根据欧几里德算法计算e的逆d=e1:1e(n)，ed1mod(n).(5)公钥:PK=(n,e),私钥:SK=(p,q,d).,21,4.2RSA密码体制,RSA密码体制算法加密算法:消息m:0mn，密文c=EPK(m)=me(modn),解密算法:密文c:0cn，明文m=DSK(c)=cd(modn),22,4.2RSA密码体制,RSA密码体制算法解密算法的正确性,23,4.2RSA密码体制,例4.1设p=11,q=13.令n=1113=143,(n)=(p-1)(q-1)=(11-1)(13-1)=120,取公钥:PK=(n,e)=(143,e=17)，计算:d=e-1=17-1=113(mod120)(因为:17113=1921=16120+1).私钥:SK=(p,q,d)=(11,13,113).对于明文:m=24,密文:c=EPK(m)=2417=7(mod143).对于密文:c=7,解密:m=DSK(c)=7113=24(mod143).,24,4.2RSA密码体制,RSA密码算法的实现模幂算法:me(modn)(高效算法：平方乘算法),25,4.2RSA密码体制,RSA密码算法的实现模幂算法:me(modn)(高效算法：平方乘算法),例4.2设p=17,q=11，有n=1711=187,(n)=(p-1)(q-1)=1610=160,取公钥:e=7，计算私钥:d=23.明文:m=88,计算密文:c=887(mod187).,26,4.2RSA密码体制,例4.2设p=17,q=11，有n=1711=187,(n)=(p-1)(q-1)=1610=160,取公钥:e=7，计算私钥:d=23.明文:m=88,计算密文:c=887=11(mod187).对于密文:c=11,解密:m=1123=7(mod187).,27,4.2RSA密码体制,Zn上的运算:设x和y的二进制表示分别有k和l位(kl).x+y:O(k)x-y:O(k)xy:O(kl)x/y:O(l(k-l)gcd(x,y):O(k3)(Euclidean算法)Zn上的模n运算:设n的二进制表示有k,0m1,m2n-1.m1+m2(modn):O(k)m1-m2(modn):O(k)m1m2(modn):O(k2)(m1)-1(modn):O(k3)(m1)c(modn):O(k2logc)(平方-乘算法).,RSA密码算法的实现,28,对RSA的攻击,攻击方法1：分解n已知n=pq(n)=(p-1)(q-1)a=b-1mod(n).分解n的最新水平:二进制表示有512位.n应为1024,2048位.,攻击方法2：直接计算(n)已知(n)e=d-1mod(n).计算(n)并不比分解n容易.设pq=n,(p-1)(q-1)=(n)p2-(n-(n)+1)p+n=0求出p,q=n/p求出n=pq.例:设n=84773093,(n)=84754668p2-18426p+84773093=0p=9539,q=n/p=8887n=84773093=95398887.,29,对RSA的攻击,攻击方法3：共模攻击如果两个用户A与B使用相同的模n，设A与B的解密密钥分别为dA与dB,加密密钥分别为eA与eB.对明文m加密的两个密文:,攻击者可以恢复明文m！,30,对RSA的攻击,攻击方法4：选择密文攻击(RSA密码不能抵抗！)假设攻击者获得了公钥(n,e),截获到密文c1.设明文为m1，有,攻击者选取一个消息m，计算,攻击者想办法让解密者对c2进行解密，从而获得的明文m2.,攻击者就可以计算出明文m1！,31,对RSA的攻击,攻击方法5：解密指数法如果私钥d已知,则可能分解n.即计算d并不比分解n容易.如果私钥d被泄漏,不能只更换公钥e,必须更换模n.,攻击方法6：低解密指数攻击法当解密指数dn0.5,32,RSA的安全参数,p和q要足够大:n=pq为1024位,或2048位.p和q应为强素数(strongprime).如果素数p满足以下条件,则称为强素数.(1)p-1有大素数因子r;(2)p+1有大素数因子s;(3)r-1有大素数因子t.例如:理想的强素数为:r=2t+1;p=2r+1=4t+3;p=2s-1.,33,RSA的安全参数,|p-q|要大.如果|p-q|较小,则(p+q)/2n1/2,(p-q)/2)2=(p+q)/2)2-n.可求出p和q.例:对于n=164009,有n1/2405.令(p+q)/2=405,(p-q)/2)2=4052-n=16p+q=810,p-q=8p=409,q=401164009=409401.,34,RSA的安全参数,p-1和q-1的最大公因子要小设攻击者截获到密文y1=xemodn迭代加密:yi=yi-1e=xeeemodn(i=2,3,4,)如果有i使得:di=1mod(n),则有:yi=xmodn因此,如果i很小,则容易求得明文x.由Euler定理和di=1mod(n),可得i=(n)=(p-1)(q-1)=D(p-1)(q-1)/(D),其中D=gcd(p-1,q-1).当D小时,(D)就小,从而i大.,35,RSA的安全参数,p-1和q-1的最大公因子要小设p和q是理想的强素数,即p=2a+1,q=2b+1(a,b为奇素数)D=2,(D)=1,i=2(a-1)(b-1).例:设p=17,q=11,n=187,d=7,D=gcd(p-1,q-1)=gcd(16,10)=2.对x=123,有y1=1237=183mod187y2=y17=1837=72mod187y3=y27=727=30mod187y4=y37=307=123(=x)mod187.,36,RSA的安全参数,加密指数d的选择为使加密速度快,应使e的二进制表示中,1的个数尽量小,但不能太小.可取:e=3,216+1=65537(在二进制表示中只有2个1).解密指数d的选择在d的二进制表示中,1的个数尽量小,但不能太小.3dn1/4.,37,4.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制4.3.1ElGamal密码系统4.3.2椭圆曲线密码系统,第4章公钥密码体制,38,4.3.1ElGamal密码系统,循环群设(G,*)是一个有限群,|G|=n,e是G的单位元.如果存在aG，使得a,a2,an=e互不相同,即G=a,a2,an,则称a是G的一个本原元（生成元）.(G,*)称为循环群。有限域设p是一个素数,Fp=GF(p)=0,1,2,p-1.在GF(p)中,加法与乘法按mod(p)进行,则GF(p)称为一个有限域。GF(p)的本原元设Fp*=GF(p)*=1,2,p-1,aGF(p)*,如果a,a2,ap-1=1互不相同,即GF(p)*=a,a2,ap-1,则称a是GF(p)的一个本原元.(Fp*,*)是一个循环群。,39,4.3.1ElGamal密码系统,例：对于GF(5)=0,1,2,3,4,有GF(5)*=1,2,3,4，2,22=4,23=3,24=1GF(5)*=1,2,3,4=24,2,23,22,2是GF(5)的本原元.但是：4,42=14不是GF(5)的本原元！,40,4.3.1ElGamal密码系统,离散对数问题设p是一个素数,a是GF(p)的一个本原元,任给aGF(p)*,存在k(0kp-2),使得b=akmodp,把k称为b的以a为底的模p的对数，记为k=logab.离散对数问题是困难问题对于合理选择的素数p，求解离散对数问题尚无多项式时间算法。,41,4.3.1ElGamal密码系统,离散对数基本算法设GF(p)中两个元素乘积的时间复杂度为:O(1).穷举搜索法:依次计算：a,a2,a3,直到ak=b.时间复杂性为:O(p).二分搜索法:计算表(i,ai)i=1,2,3,p-1:时间复杂度为:O(p).存储空间:O(p).将表(i,ai)按第二坐标排序时间复杂度为:O(plogp).搜索:时间复杂度为:O(1).,42,4.3.1ElGamal密码系统,厄格玛尔(ElGamal)密码体制密钥产生:选择素数p，整数g,x满足0g,xp,计算y=gxmodp.公钥:(p,g,y)私钥:x加密算法:设明文为m(0mp),随机选取k(0kp),计算c1=gkmodp,c2=ykmmodp.密文:c=(c1,c2)解密算法:设密文为c=(c1,c2),则明文为m=c2(c1x)-1modp.,43,4.3.1ElGamal密码系统,例4.3.1,44,4.3.1ElGamal密码系统,ElGamal密码系统的安全性GF(p)上离散对数的困难性p应为150位以上的十进制数p-1应有大的素因子随机数k必须保密如果攻击者获得随机数k,则由c2=ykmmodp,可得m。随机数k必须是一次性的如果用同一个随机数k对m与m加密,密文分别为：c=(c1,c2),c=(c1,c2),c2/c2=ykm/ykm=m/m,当攻击者获得m后，就能得到m。,45,4.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制4.3.1ElGamal密码系统4.3.2椭圆曲线密码系统,第4章公钥密码体制,46,概述,椭圆曲线(ECC)密码体制EllipticCurveCryptography获得同样的安全性，密钥长度较RSA短得多被IEEE公钥密码标准P1363采用,47,椭圆曲线,椭圆曲线的曲线方程是以下形式的三次方程y2+axy+by=x3+cx2+dx+ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为O.,48,椭圆曲线加法的定义,如果其上的3个点位于同一直线上，那么它们的和为O。O为加法单位元，即对ECC上任一点P,有P+O=P设P1=(x,y)是ECC上一点，加法逆元定义为P2=-P1=(x,-y)P1,P2连线延长到无穷远，得到ECC上另一点O,即P1,P2,O三点共线，所以P1+P2+O=O,P1+P2=O,P2=-P1OOO,O=-O,49,椭圆曲线加法的定义,Q,R是ECC上x坐标不同的两点，Q+R定义为：画一条通过Q,R的直线与ECC交于P1(交点是唯一的，除非做的Q,R点的切线，此时分别取P1=Q或P1=R)。由Q+R+P1=O,得Q+R=-P1点Q的倍数定义如下：在Q点做ECC的一条切线，设切线与ECC交于S,定义2Q=Q+Q=-S。类似可定义3Q=Q+Q+Q,上述加法满足加法的一般性质，如交换律、结合律等,50,有限域上的椭圆曲线,曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+bmod(p)(a,bGF(p),4a3+27b20modp)例：p=23,a=b=1,4a3+27b2=80(mod23),方程为y2=x3+x+1mod(p)，图形为连续图形。我们感兴趣的是在第一象限的整数点。设Ep(a,b)表示ECC上点集(x,y)|0xp,0yp,且x,y均为整数并上O.,51,有限域上的椭圆曲线点集产生方法,对每一x(0xp且x为整数），计算x3+ax+bmodp决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两个平方根。（Euler公式测试）,52,4.3.2椭圆曲线密码系统,例4.3.1设E是F5的椭圆曲线y2=x3+x+1.求E5(1,1)的全部元素.解:任给xF5,用Euler公式测试z=x3+x+1(mod5)是否为一个二次剩余.如是,则求得z的平方根是:z(11+1)/4=z3(mod5).E5(1,1)=(0,1),(0,4),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3),O,53,Ep(a,b)上加法,如果P,QEp(a,b)P+O=P如果P(x,y),则(x,y)+(x,-y)OP(x1,y1),Q=(x2,y2),P-Q,P+Q=(x3,y3)x3=l2-x1-x2（modp）y3=l(x1-x3)-y1(modp),54,4.3.2椭圆曲线密码系统,例4.3.2已知椭圆曲线y2=x3+x+1,有E5(1,1)=(0,1),(0,4),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3),O|E|=9,取a=(0,1),计算a的幂(倍数).解:计算2a=(0,1)+(0,1)=(x3,y3),=(302+1)(21)-1=12-1=13=3mod5,x3=32-0-0=4mod5,y3=3(0-4)-1=-13=-3=2mod52a=(4,2).计算3a=2a+a=(4,2)+(0,1)=(x3,y3),=(1-2)(0-4)-1=41-1=4mod5,x3=42-4-0=12=2mod5,y3=4(4-2)-2=8-2=1mod53a=(2,1).结果:a=(0,1),2a=(4,2),3a=(2,1),4a=(3,4),5a=(3,1),6a=(2,4),7a=(0,4),8a=(4,3),9a=O.所以,E是一个循环群,a=(0,1)是生成元。,55,ECC上的密码,ECC上的离散对数问题在ECC构成的交换群Ep(a,b)上考虑方程QkP，P,QEp(a,b),kp.由k和P求Q容易，由P,Q求k则是困难的。由ECC上离散对数问题可以构造Diffie-Hellman密钥交换和Elgamal密码体制,56,Diffie-Hellman密钥交换,取一素数p2180,两个参数a,b,得到Ep(a,b).取Ep(a,b)的一个生成元G(x1,y1),要求G的阶是一个非常大的素数。(阶是满足nG=O的最小正整数n).Ep(a,b)和G公开，A和B密钥交换过程如下A选小于n的整数nA作为秘密钥，并有PA=nAG作为公钥B类似选取自己的秘密钥nB和公开钥PBA和B分别由K=nAPB和KnBPA产生共享的秘密钥攻击者如想获得K，必须由PA和G求出nA或PB和G求出nB,57,ECC实现Elgamal密码体制,选取一条椭圆曲线，得到Ep(a,b)。将明文消息通过编码嵌入曲线上得到点pm取Ep(a,b)的生成元G，Ep(a,b)和G为公开参数用户选取