第五讲 公钥密码体制.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Chapter 8,Number Theory and RSA,公开密钥密码学,计算机学院,孟博,mengscuec,内 容,数论简介,公钥密码学,RSA,算法,素数和互素,模运算,费尔玛定理,欧拉函数,中国剩余定理,离散对数,数论简介,素数和互素数,数论简介,1.,因子,设,a,，,b(b0),是两个整数，如果存在另一整数,m,，,使得,a=,mb,，,则称,b,整除,a,，,记为,b|a,，,且称,b,是,a,的因子。,2.,素数,称整数,p(p1),是素数，如果,p,的因子只有,1,，,p,。,任一整数,a(a1),都能,唯一,地分解为以下形式,(,这一性质称为整数分解的惟一性,),：,其中,p,1,p,2,p,t,是素数，,a,i,0(i=1,t),。,例如,:,91=713,3.,互素,称,c,是两个整数,a,、,b,的最大公因子，如果,c,是,a,的因子也是,b,的因子，即,c,是,a,、,b,的公因子。,a,和,b,的任一公因子，也是,c,的因子。,表示为,c=,gcd(a,b),。,如果,gcd(a,b,)=1,，,则称,a,和,b,互素。,设,n,是一正整数，,a,是整数，如果用,n,除,a,，,得商为,q,，,余数为,r,，,则,a=qn+r,0rd,。,Euclid,（,f,d,）,1.Xf;Yd,；,2.if Y=0 then return X=,gcd(f,d,),；,3.R=X mod Y,；,4.X=Y,；,5.Y=R,；,6.,goto,2,。,求,gcd(1970,1066),。,1970=11066+904,gcd(1066,904),1066=1904+162,gcd(904,162),904=5162+94,gcd(162,94),162=194+68,gcd(94,68),94=168+26,gcd(68,26),68=226+16,gcd(26,16),26=116+10,gcd(16,10),16=110+6,gcd(10,6),10=16+4,gcd(6,4),6=14+2,gcd(4,2),4=22+0,gcd(2,0),因此,gcd(1970,1066)=2,。,2.,求乘法逆元,如果,gcd(a,b)=1,，则,b,在,mod a,下有乘法逆元（不妨设,ba,），,即存在一,x(x512bits),security relies on hard problems,more generally the hard problem is known,but is made hard enough to be impractical to break,requires the use of very large numbers,hence is slow compared to private key schemes,RSA,by Rivest,Shamir&Adleman of MIT in 1977,best known&widely used public-key scheme,uses large integers(eg.1024 bits),security due to cost of factoring large numbers,nb.factorization takes O(e,log n log log n,)operations(hard),RSA Key Setup,each user generates a public/private key pair by:,selecting two large primes at random:p,q,computing their system modulus n=,p,q,note(n)=(p-1)(q-1),selecting at random the encryption key e,where 1e(n),gcd(e,(n,)=1,solve following equation to find decryption key d,ed=1 mod(n)and 0dn,publish their public encryption key:PU=e,n,keep secret private decryption key:PR=d,n,Figure 9.5,RSA setup,RSA Use,to encrypt a message M the sender:,obtains public key of recipient PU=e,n,computes:C=M,e,mod n,where 0Mn,to decrypt the,ciphertext,C the owner:,uses their private key PR=d,n,computes:M=,C,d,mod n,note that the message M must be smaller than the modulus n(block if needed),Figure 9.5,RSA encryption and decryption,RSA Example-Key Setup,Select primes:p=17&q=11,Compute n=,pq,=17,x,11=187,Compute(n)=(p1)(q-1)=16,x,10=160,Select e:gcd(e,160)=1;choose e=7,Determine d:de=1 mod 160 and d 160 Value is d=23 since 23,x,7=161=10,x,160+1,Publish public key PU=7,187,Keep secret private key PR=23,187,RSA Example-En/Decryption,sample RSA encryption/decryption is:,given message M=88(nb.88187),encryption:,C=88,7,mod 187=11,decryption:,M=11,23,mod 187=88,Figure 9.6 Example of RSA Algorithm,E,和,D,的可逆性,要证明：,D(E(M)=M,M,C,d,(M,e,),d,M,ed,mod n,因为,ed,1 mod(n),，,这说明,ed,t(n)+1,其中,t,为某整数。所以，,M,ed,M,t(n)+1,mod n,。,因此要证明,M,ed,M mod n,，,只需证明,M,t(n)+1,M mod n,。,RSA,算法论证,在,gcd,（,M,，,n,）,1,的情况下，根据数论，,M,t(n),1 mod n,，,于是有，,M,t(n)+1,M mod n,。,在,gcd,（,M,，,n,）,1,的情况下，分两种情况：,第一种情况：,M1,2,3,n-1,因为,n=,pq,，,p,和,q,为素数，,M1,2,3,n-1,，,且（,M,，,n,）,1,。,这说明,M,必含,p,或,q,之一为其因子，而且不能同时包含两者，否则将有,Mn,，与,M1,2,3,n-1,矛盾。,不妨设,M,ap,。,又因,q,为素数，且,M,不包含,q,，,故有（,M,，,q,）,1,，,于是有，,M,(q),1 mod q,。,进一步有，,M,t(p-1)(q),1 mod q,。,因为,q,是素数，,(q),（,q-1,），,所以,t(p-1)(q),t(n),，,所以有,M,t(n),1 mod q,。,于是，,M,t(n),bq+1,，,其中,b,为某整数。,两边同乘,M,，,M,t(n)+1,bqM+M,。,因为,M,ap,，,故,M,t(n)+1,bqap+M,=,abn+M,。,取模,n,得，,M,(n)+1,M mod n,。,第二种情况：,M,0,当,M,0,时，直接验证，可知命题成立。,加密和解密运算的可交换性,D(E(M)=(M,e,),d,=M,ed,=(,M,d,),e,=E(D(M)mod n,所以，,RSA,密码可同时确保数据的秘密性和数据的真实性。,加解密算法的有效性,RSA,密码的加解密运算是模幂运算，有比较有效的算法。,在计算上由公开密钥不能求出解密钥,小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于,O,（,EXP,（,lnNlnlnN,）,1/2,）。,根据这一结论，只要合数足够大，进行因子分解是相当困难的。,假设截获密文,C,，,从中求出明文,M,。,他知道,MC,d,mod n,，,因为,n,是公开的，要从,C,中求出明文,M,，,必须先求出,d,，而,d,是保密的。但他知道，,ed1 mod (n),e,是公开的，要从中求出,d,，,必须先求出,(n),，而,(n),是保密的。,但他又知道，,(n)=(p-1)(q-1),要从中求出,(n),，,必须先求出,p,和,q,，而,p,和,q,是保密的。但他知道，,n=,pq,要从,n,求出,p,和,q,，,只有对,n,进行因子分解。而当,n,足够大时，这是很困难的。,只要能对,n,进行因子分解，便可攻破,RSA,密码。由此可以得出，,破译,RSA,密码的困难性,对,n,因子分解的困难性。,目前尚不能证明两者是否能确切相等，因为不能确知除了对,n,进行因子分解的方法外，是否还有别的更简捷的破译方法。,1,、参数选择,为了确保,RSA,密码的安全，必须认真选择密码参数：,p,和,q,要足够大；,一般应用：,p,和,q,应 512 位,.,重要应用：,p,和,q,应,1,024,位,因为,n=,pq,在体制中是公开的，因此为了防止敌手通过穷搜索发现,p,、,q,，,这两个素数应是在一个足够大的整数集合中选取的大数。如果选取,p,和,q,为,10,100,左右的大素数，那么,n,的阶为,10,200,，每个明文分组可以含有,664,位（,10,200,2,664,），即,83,个,8,比特字节，这比,DES,的数据分组（,8,个,8,比特字节）大得多，这时就能看出,RSA,算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。,RSA,密码的实现,p,和,q,应为强素数,文献指出，只要,(p-1),、,(p+1),、,(q-1),、,(q+1),四个数之一有小的素因子，,n,就容易分解。,p,和,q,的差要大；,（,p-1,）,和（,q-1,）,的最大公因子要小。,如果（,p-1,）,和（,q-1,）,的最大公因子太大，则易受,迭代加密攻击,若,，即,，,则有,，即 ，,所以在上述重复加密的倒数第,2,步就已恢复出明文,m,，,这种攻击法只有在,t,较小时才是可行的。为抵抗这种攻击，,p,、,q,的选取应保证使,t,很大。,设,m,在模,n,下阶为,k,，,由 得,，,所以,k|(e,t,-1),，即,e,t,1(mod k),，,t,取为满足上式的最小值（为,e,在模,k,下的阶）。又当,e,与,k,互素时,t|(k),。,为使,t,大，,k,就应大且,(k),应有大的素因子。又由,k|(n),，,所以为使,k,大，,p-1,和,q-1,都应有大的素因子,。,此外，研究结果表明，如果,en,且,dn,1/4,，则,d,能被容易地确定。,e,的选择,随机且含1多就安全,.,有的学者建议取,e,2,16,+1,65537,d,的选择,d,要足够大,不要许多用户共用一个模,n,；,易受共模攻击,2,、大素数的产生,概率性算法产生,目前最常用的概率性算法是,Miller,检验算法。,Miller,检验算法已经成为美国的国家标准。,确定性算法产生,确定性测试,确定性构造,3,、大素数的运算,反复平方乘算法,快速模乘算法,反复平方乘算法解决了快速乘方取模的问题，仍未解决快速模乘的问题；,Montgomery,算法是一种快速模乘的好算法；,将以上两种算法结合成为实现,RSA,密码的有效方法。,硬件协处理器是提高运算效率的有效方法。,RSA,的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是,NP,问题，也许有尚未发现的多项式时间分解算法。如果,RSA,的模数,n,被成功地分解为,pq,，,则立即获得,(n)=(p-1)(q-1),，,从而能够确定,e,模,(n),的乘法逆元,d,，即,de,-1,mod(n),，,因此攻击成功。,RSA,的安全性,随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如,RSA-129,（即,n,为,129,位十进制数，大约,428,个比特）已在网络上通过分布式计算历时,8,个月于,1994,年,4,月被成功分解，,RSA-130,已于,1996,年,4,月被成功分解。,对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对,RSA-129,的分解。而对,RSA-130,的分解则采用了一个新算法，称为推广的,数域筛法,，该算法在分解,RSA130,时所做的计算仅比分解,RSA-129,多,10%,。将来也可能还有更好的分解算法，因此在使用,RSA,算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于,1024,比特至,2048,比特之间的,RSA,是安全的。,对,RSA,的攻击,RSA,存在以下,7,种攻击，有的并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。,1.,共模攻击,在实现,RSA,时，为方便起见，可能给每一用户相同的模数,n,，,虽然加解密密钥不同，然而这样做是不行的。,设两个用户的公开钥分别为,e,1,和,e,2,，且,e,1,和,e,2,互素（一般情况都成立），明文消息是,m,，,密文分别是,c,1,m,e1,(mod n),c,2,m,e2,(mod n),敌手截获,c,1,和,c,2,后，可如下恢复,m,。,因为,GCD(e,1,e,2,)=1,可以先计算 最后计算,2.,低指数攻击,假定将,RSA,算法同时用于多个用户（为讨论方便，以下假定,3,个），然而每个用户的加密指数（即公开钥）都很小。设,3,个用户的模数分别为,n,i,(i,=1,2,3),，当,ij,时，,gcd(n,i,n,j,)=1,，,否则通过,gcd(n,i,n,j,),有可能得出,n,i,和,n,j,的分解。他们的公钥分别是（,n,1,，,3,），,（,n,2,，,3,），（,n,3,，,3,），,设明文消息是,m,则密文,C,i,=m,3,mod,n,i,，则,c,1,(mod n,1,),m,3,c,2,(mod n,2,)m,3,c,3,(mod n,3,)m,3,由中国剩余定理可求出,m,3,(mod n,1,n,2,n,3,),。,由于,m,n,i,，,m,3,n,1,n,2,n,3,，,可直接由,m,3,开立方根得到,m,。,3.,选择密文攻击,RSA,在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装,(Blind),，让拥有私钥的实体签名。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：,这个固有的问题来自于公钥密码系统的最有用的特征,-,每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有 两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体 意产生的信息解密，不对自己一无所知的信息签名；另一条是决不 对陌生人送来的随机文档签名。,4.,计时攻击,攻击者可以通过记录计算机解密消息所用的时间来确定私钥。,5.,暴力破解,6.,数学攻击,7.,明文数据过短,谢 谢,!,