第18讲--RSA算法及安全性分析.ppt

数论简介,模运算,设n是一正整数,a是整数,若a=qn+r,0rn,则amodn=r若(amodn)=(bmodn),称为a,b模n同余，记为abmodn称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素,模运算,同余的性质若n|(a-b)，则abmodn(amodn)(bmodn),则abmodnabmodn，则bamodnabmodn，bcmodn，则acmodn求余运算amodn将a映射到集合0,1,n-1,求余运算称为模运算,模运算,模运算的性质(amodn)+(bmodn)modn=(a+b)modn(amodn)-(bmodn)modn=(a-b)modn(amodn)(bmodn)modn=(ab)modn,模运算,例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法,模运算,若x+y=0modn,y为x的加法逆元。每一元素都有加法逆元若对x，有xy=1modn，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元定义Zn=0,1,.,n-1为模n的同余类集合。,模运算,Zn上模运算的性质交换律（x+w)modn=(w+x)modn(xw)modn=(wx)modn结合律(x+w)+ymodn=x+(w+y)modn(xw)ymodn=x(wy)modn分配律w(x+y)modn=wx+wy)modn,模运算,单位元(0+w)modn=wmodn(1w)modn=wmodn加法逆元：对wZn,有zZn，满足w+z=0modn,z为w的加法逆元，记为z=-w。加法的可约律(a+b)(a+c)modn,则bcmodn对乘法不一定成立，因为乘法逆元不一定存在。,模运算,定理:设aZn,gcd(a,n)=1,则a在Zn有逆元证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从1得出aZn=Zn,因此存在xZn,使ax=1modn设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(ab)=(ac)modn,b=cmodn,中国剩余定理,如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数定理(中国剩余定理)：设m1,m2,mk是两两互素的正整数，则一次同余方程组对模M有唯一解,中国剩余定理,中国剩余定理可以将一个很大的数x表示为一组较小的数(a1,ak)例：x1mod2,x2mod3,x3mod5x5mod7,求x解：M2357210，M1=105,M2=70,M3=42,M4=30,(Mi=M/mi),可以求得e1=1,e2=1,e3=3,e4=4,所以x=10511701242333045mod210173,费尔玛定理和欧拉定理,费尔玛定理若p是素数，a是正整数且gcd(a,p)=1，则ap-11modp证明：gcd(a,p)=1,则aZp=Zp,a(Zp-0)=Zp-0amodp,2amodp,(n-1)amodp=0,1,p-1(amodp)(2amodp)(n-1)amodp=(p-1)!modp(p-1)!ap-1=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp,费尔玛定理和欧拉定理,欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)定理：若n是两个素数p和q的乘积，则(n)(p)(q)=(p-1)(q-1)欧拉定理若a和n互素,则a(n)=1modn,离散对数,求模下的整数幂根据欧拉定理，若gcd(a,n)=1,则af(n)1modn。考虑一般am1modn,如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。例：a=7,n=19.717mod19,7211mod19,731mod19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同,RSA算法的实现,实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和(n)=(p-1)(q-1)(3)Bob选择一个随机数e(0e(n)，满足(e,(n)=1(4)Bob使用辗转相除法计算d=e-1(mod(n)(5)Bob在目录中公开n和e作为公钥密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公开的e，解出秘密的d,RSA算法编制,参数T=N；私钥SK=D；公钥PK=E；设：明文M，密文C，那么：用公钥作业：MEmodN=C用私钥作业：CDmodN=M,解密正确性证明,cdmodnmedmodnm1modj(n)modnmkj(n)+1modnm与n互素，由欧拉定理mj(n)1modn,mkj(n)1modn,mkj(n)+1mmodngcd(m,n)1,m是p的倍数或q的倍数，设m=cp，此时gcd(m,q)=1,由欧拉定理，mj(q)1modq，mkj(q)1modq，mkj(q)j(p)1modqmkj(n)1modq，存在一整数r，使mkj(n)1rq两边同乘m=cp,mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1mmodn,RSA算法举例,设p=7,q=17,n=7*17=119;参数T=n=119;(n)=(7-1)(17-1)=96;选择e=5,gcd(5,96)=1;公钥pk=5;计算d,(d*e)mod96=1;d=77;私钥sk=77;设:明文m=19加密：（19）5mod119=66脱密：（66）77mod119=19,RSA算法的安全性分析,密码分析者攻击RSA体制的关键点在于如何分解n若分解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公开的e，解出秘密的d若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来n取1024位或取2048位，这样p、q就应该取512位和1024位。,RSA算法的安全性分析,建议选择p和q大约是100位的十进制素数模n的长度要求至少是512比特EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数国际数字签名标准ISO/IEC9796中规定n的长度位512比特位,如果用MIPS年表示每秒钟执行一百万条指令的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。,RSA算法的安全性分析,为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求（即是强素数）：(1)p-1和q-1分别含有大素因子p1和q1(2)P1-1和q1-1分别含有大素因子p2和q2(3)p+1和q+1分别含有大素因子p3和q3,RSA算法的安全性分析,其它参数的选择要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1的最大公因子要小；(3)e的选择；(4)d的选择；(5)不要许多的用户共用一个n。,不动点分析,定义如果,则称m为RSA的一个不动点。,(1)此时的密文就是明文，因而直接暴露了明文。,(2)利用不动点m可能分解大合数N。,对RSA的攻击共模攻击,每一用户有相同的模数n设用户的公开密钥分别为e1,e2,且e1,e2互素，明文消息为m,密文为因为（e1,e2)=1,用欧几里德算法可求re1+se2=1假定r为负数，从而可知由Euclidean算法可计算(c1-1)-rc2s=mmodn,对RSA的攻击低指数攻击,令网中三用户的加密钥e均选3，而有不同的模n1,n2,n3，若有一用户将消息x传给三个用户的密文分别为y1=x3modn1xn1y2=x3modn2xn2y3=x3modn3xn3一般选n1,n2,n3互素(否则，可求出公因子，而降低安全性)，利用中国余定理，可从y1,y2,y3求出y=x3mod(n1n2n3)。由xn1,xn2,xn3，可得x3nb，为了使脱密正常进行，应该先加密还是先签名？,平方乘算法,P-1因子分解算法,素性检验,引理：如果p为大于2的素数，则方程x21modp的解只有和x1和x-1证明:x21modpx2-10mo