现代密码学-第4章公钥密码体制-20091110

1现代密码学21世纪高等学校计算机规划教材ModernCryptography彭代渊信息科学与技术学院[e-mail]2009.9-2010.1作者：何大可彭代渊唐小虎何明星梅其祥出版社：人民邮电出版社2现代密码学ModernCryptography彭代渊信息科学与技术学院[e-mail]2009年11月第4章公钥密码体制34.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制第4章公钥密码体制44.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背包公钥密码体制).不久被攻破.54.1公钥密码体制概述公钥密码体制(PKC:publickeycryptosystem)原理密钥K=(PK,SK):加密密钥PK公开;解密密钥SK保密.在计算上由PK推出SK是困难的.加密算法EPk:c=EPk(m)解密算法DSk满足:m=DPk(c)DSK(EPK(x))=x.64.1公钥密码体制概述公钥密码体制的要求用户：产生密钥对K=(PK,SK)在计算上是可行的发送方：已知公钥与明文，产生密文是容易的接收方：利用私钥解密密文在计算上是可行的攻击者：利用公钥求解私钥在计算上是不可行的攻击者：已知公钥与密文，在不知道私钥的情况下，恢复明文在计算上是不可行的74.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制第4章公钥密码体制84.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作为传送会话密钥和数字签名的标准.94.2RSA密码体制104.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).114.2RSA密码体制RSA密码体制算法加密算法:消息m:0mn，密文c=EPK(m)=me(modn)解密算法:密文c:0cn，明文m=DSK(c)=cd(modn)124.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且，如且.(参考教材！)134.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).144.2RSA密码体制RSA密码算法的实现模幂算法:me(modn)—(高效算法：平方乘算法)154.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).164.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).174.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密码算法的实现18对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.19对RSA的攻击攻击方法3：共模攻击如果两个用户A与B使用相同的模n，设A与B的解密密钥分别为dA与dB,加密密钥分别为eA与eB.对明文m加密的两个密文:攻击者可以恢复明文m！).mod()()(1,).mod(),mod(nmmmmccseresreenmcnmcBABABAsereseresBrABABAeBeA所以满足：与存在互素时与当20对RSA的攻击攻击方法4：选择密文攻击(RSA密码不能抵抗！)假设攻击者获得了公钥(n,e),截获到密文c1.设明文为m1，有攻击者选取一个消息m，计算)mod(11nmce)mod(112nmmmcceee攻击者想办法让解密者对c2进行解密，从而获得的明文m2.攻击者就可以计算出明文m1！).mod(/),mod()()(2122nmmmnmmmmcm11deed所以因为21对RSA的攻击攻击方法5：解密指数法如果私钥d已知,则可能分解n.即计算d并不比分解n容易.如果私钥d被泄漏,不能只更换公钥e,必须更换模n.攻击方法6：低解密指数攻击法当解密指数dn0.292时，攻击者可以计算出解密指数d为安全起见，建议选取dn0.522RSA的安全参数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.23RSA的安全参数|p-q|要大.如果|p-q|较小,则(p+q)/2n1/2,((p-q)/2)2=((p+q)/2)2-n.可求出p和q.例:对于n=164009,有n1/2405.令(p+q)/2=405,((p-q)/2)2=4052-n=16p+q=810,p-q=8p=409,q=401164009=409401.24RSA的安全参数p-1和q-1的最大公因子要小设攻击者截获到密文y1=xemodn迭代加密:yi=yi-1e=xee…emodn(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大.25RSA的安全参数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.26RSA的安全参数加密指数d的选择为使加密速度快,应使e的二进制表示中,1的个数尽量小,但不能太小.可取:e=3,216+1=65537(在二进制表示中只有2个1).解密指数d的选择在d的二进制表示中,1的个数尽量小,但不能太小.3dn1/4.274.1公钥密码体制概述4.2RSA公钥密码体制4.3离散对数公钥密码体制4.3.1ElGamal密码系统4.3.2椭圆曲线密码系统第4章公钥密码体制284.3.1ElGamal密码系统循环群设(G,*)是一个有限群,|G|=n,e是G的单位元.如果存在aG，使得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},aGF(p)*,如果a,a2,…,ap-1=1互不相同,即GF(p)*={a,a2,…,ap-1},则称a是GF(p)的一个本原元.(Fp*,*)是一个循环群。294.3.1ElGamal密码系统例：对于GF(5)={0,1,2,3,4},有GF(5)*={1,2,3,4}，2,22=4,23=3,24=1GF(5)*={1,2,3,4}={24,2,23,22},4是GF(5)的本原元.但是：4,42=14不是GF(5)的本原元！304.3.1ElGamal密码系统离散对数问题设p是一个素数,a是GF(p)的一个本原元,任给aGF(p)*,存在k(0kp-2),使得b=akmodp,把k称为b的以a为底的模p的对数，记为k=logab.离散对数问题是困难问题对于合理选择的素数p，求解离散对数问题尚无多项式时间算法。314.3.1E