网络与信息安全-第4章公钥密码体制

1网络与信息安全公钥密码体制24.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制第4章公钥密码体制34.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背包公钥密码体制).不久被攻破.44.1公钥密码体制概述公钥密码的基本思想与单向陷门函数的思想密切相关构造公钥密码体制的一般原理如下：(1)从一个困难问题P开始。P问题是不可行的，它是基于计算复杂性，而且最好是计算平均复杂度。(2）取出P中的一个子问题P1。它应该是很容易解决的，一般是多项式时间，最好是线性时间问题。(3)对P1问题进行伪装成P2问题，使P2问题看起来很像原来的P问题，好像P问题一样难。(4）公开P2问题，并把P2问题用作一个加密密钥加密函数；将如何从P2恢复P1问题的信息保密，称该信息为“陷门”。(5）使系统合法用户能通过求解容易问题P1进行解密，而其它用户不得不求解P2，而求P2的过程至少看起来好像是在求解原来困难的P问题5目前出现的且具有较高的安全性的公钥密码体制主要基于的困难问题：(1)基于数论中的大整数分解问题（诸如RSA）；(2)基于离散对数问题（如ElGmal、Diffie—Hellman密钥交换协议）；(3)基于椭圆曲线上的离散对数问题（如ECC）；(4)基于线性编码的解码问题（如MeElice密码体制）；(5)基于自动机与语言理论64.1公钥密码体制概述公钥密码体制(PKC:publickeycryptosystem)原理密钥K=(PK,SK):加密密钥PK公开;解密密钥SK保密.在计算上由PK推出SK是困难的.加密算法EPk:c=EPk(m)解密算法DSk满足:m=DPk(c)DSK(EPK(x))=x.74.1公钥密码体制概述公钥密码体制的要求用户：产生密钥对K=(PK,SK)在计算上是可行的发送方：已知公钥与明文，产生密文是容易的接收方：利用私钥解密密文在计算上是可行的攻击者：利用公钥求解私钥在计算上是不可行的攻击者：已知公钥与密文，在不知道私钥的情况下，恢复明文在计算上是不可行的8离散对数指标y=ax(a0,a≠1)的逆函数称为以a为底的对数，记为x=logay设p为素数，a是p的本原根，则a0,a1,...,ap-1产生1到p-1中所有值，且每个值只出现一次。对任一b∈{1,…,p-1}，都存在唯一的i(1≤i≤p)，使b≡aimodp。i称为模p下以a为底b的指标，记为i=inda,p(d)9离散对数指标的性质1.inda,p(1)=02.inda,p(a)=13.inda,p(xy)=[inda,p(x)+inda,p(y)]modj(p)4.inda,p(yr)=[r×inda,p(y)]modj(p)后两个性质基于下列结论若az≡aqmodp,a和p互素，则z≡qmodj(p)10离散对数设p是素数，a是p的本原根。对b∈{1,…,p-1},有唯一的i∈{1,…,p-1},使b≡aimodp。称i为模p下以a为底b的离散对数，记为i≡logab(modp)已知a,p,i,求b比较容易，以及a,b,p,求i非常困难11公钥密码体制的原理公钥体制(Publickeysystem)(Diffie和Hellman,1976)每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。12公钥体制加密公钥体制加、解密m=D(c)=DSKB(EPKB(m))安全保障•从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是不可行的。•由于任一用户都可用用户B的公开钥PKB向他发送机密消息，因而密文c不具有认证性。发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmm’SK’B13公钥密码认证体制用户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所发消息的认证。14公钥密码认证体制发送者A加密算法SKA密钥源PKA解密算法接收者B密码分析员mcmSK’A15公钥保密和认证体制为了要同时实现保密性和确证性，要采用双重加、解密保密公开保密公开用户ADSKAEPKBDSKBEPKA用户Bmm保密认证16单向函数一个可逆函数f：AB，若它满足：1o对所有xA，易于计算f(x)。2o对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为n，计算函数的时间是na的倍数，a为一固定的常数。若计算函数时间是an的倍数，则为不可能做到的。17限门单向函数单向函数是求逆困难的函数，而单向陷门函数(Trapdoorone-wayfunction)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。限门单向函数是一族可逆函数fk，满足1.Y=fk(X)易于计算（当k和X已知）2.X＝f-1k(Y)易于计算（当k和Y已知）3.X＝f-1k(Y)计算上不可行（Y已知但k未知）研究公钥密码算法就是找出合适的单向限门函数184.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制第4章公钥密码体制194.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作为传送会话密钥和数字签名的标准.204.2RSA密码体制214.2RSA密码体制RSA密码体制算法密钥生成算法(1)选取两个大素数p,q(2)计算n=pq,(n)=(p-1)(q-1)(3)随机选取e:1e(n)，与(n)互素(4)根据欧几里德算法计算e的逆d=e1:1e(n)，ed1mod(n).(5)公钥:PK=(n,e),私钥:SK=(p,q,d).224.2RSA密码体制RSA密码体制算法加密算法:消息m:0mn，密文c=EPK(m)=me(modn)解密算法:密文c:0cn，明文m=DSK(c)=cd(modn)234.2RSA密码体制RSA密码体制算法解密算法的正确性()1()()()1(mod())()1(1)()(())()()(mod).(1)gcd(,)1,1(mod),()()1(mod).(2)gcd(,)detnntSKSKPKnnttSKednedtntDcDEmmmmmnmnmnDcmmmmnmn存在如由欧拉定理知如1,000,()00(mod).(3)gcd(,)1,1eedSKmcmDcmnmnm且，如且.(参考教材！)244.2RSA密码体制例4.1设p=11,q=13.令n=1113=143,(n)=(p-1)(q-1)=(11-1)(13-1)=120,取公钥:PK=(n,e)=(143,e=17)，计算:d=e-1=17-1=113(mod120)(因为:17113=1921=16120+1).私钥:SK=(p,q,d)=(11,13,113).对于明文:m=24,密文:c=EPK(m)=2417=7(mod143).对于密文:c=7,解密:m=DSK(c)=7113=24(mod143).254.2RSA密码体制RSA密码算法的实现模幂算法:me(modn)—(高效算法：平方乘算法)264.2RSA密码体制RSA密码算法的实现模幂算法:me(modn)—(高效算法：平方乘算法)例4.2设p=17,q=11，有n=1711=187,(n)=(p-1)(q-1)=1610=160,取公钥:e=7，计算私钥:d=23.明文:m=88,计算密文:c=887(mod187).274.2RSA密码体制例4.2设p=17,q=11，有n=1711=187,(n)=(p-1)(q-1)=1610=160,取公钥:e=7，计算私钥:d=23.明文:m=88,计算密文:c=887=11(mod187).对于密文:c=11,解密:m=1123=7(mod187).284.2RSA密码体制Zn上的运算:设x和y的二进制表示分别有k和l位(kl).x+y:O(k)x-y:O(k)xy:O(kl)x/y:O(l(k-l))gcd(x,y):O(k3)(Euclidean算法)Zn上的模n运算:设n的二进制表示有k,0m1,m2n-1.m1+m2(modn):O(k)m1-m2(modn):O(k)m1m2(modn):O(k2)(m1)-1(modn):O(k3)(m1)c(modn):O(k2logc)(平方-乘算法).RSA密码算法的实现29对RSA的攻击攻击方法1：分解n已知n=pq(n)=(p-1)(q-1)a=b-1mod(n).分解n的最新水平:二进制表示有512位.n应为1024,2048位.攻击方法2：直接计算(n)已知(n)e=d-1mod(n).计算(n)并不比分解n容易.设pq=n,(p-1)(q-1)=(n)p2-(n-(n)+1)p+n=0求出p,q=n/p求出n=pq.例:设n=84773093,(n)=84754668p2-18426p+84773093=0p=9539,q=n/p=8887n=84773093=95398887.30对RSA的攻击攻击方法3：共模攻击如果两个用户A与B使用相同的模n，设A与B的解密密钥分别为dA与dB,加密密钥分别为eA与eB.对明文m加密的两个密文:攻击者可以恢复明文m！).mod()()(1,).mod(),mod(nmmmmccseresreenmcnmcBABABAsereseresBrABABAeBeA所以满足：与存在互素时与当31对RSA的攻击攻击方法4：选择密文攻击(RSA密码不能抵抗！)假设攻击者获得了公钥(n,e),截获到密文c1.设明文为m1，有攻击者选取一个消息m，计算)mod(11nmce)mod(112nmmmcceee攻击者想办法让解密者对c2进行解密，从而获得的明文m2.攻击者就可以计算出明文m1！).mod(/),