《RSA算法及安全性分析.ppt》由会员分享，可在线阅读，更多相关《RSA算法及安全性分析.ppt（34页珍藏版）》请在三一办公上搜索。
1、RSA 算法及安全性分析,数论简介,模运算,设n是一正整数,a是整数,若 a=qn+r,0rn,则a mod n=r若(a mod n)=(b mod n),称为a,b模n同余，记为ab mod n称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素,模运算,同余的性质若n|(a-b)，则ab mod n(a mod n)(b mod n),则ab mod nab mod n，则ba mod nab mod n，bc mod n，则ac mod n求余运算a mod n将a映射到集合0,1,n-1,求余运算称为模运算,模运算,模运算的性质(a mod n)+(b mod n
2、)mod n=(a+b)mod n(a mod n)-(b mod n)mod n=(a-b)mod n(a mod n)(b mod n)mod n=(ab)mod n,模运算,例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法,模运算,若x+y=0 mod n,y为x的加法逆元。每一元素都有加法逆元若对x，有xy=1 mod n，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元定义Zn=0,1,.,n-1为模n的同余类集合。,模运算,Zn上模运算的性质交换律（x+w)mod n=(w+x)mod n(xw)mod n=(wx)mod n结合律(x+w)+y mod n=x+(w+
3、y)mod n(xw)y mod n=x(wy)mod n分配律 w(x+y)mod n=wx+wy)mod n,模运算,单位元(0+w)mod n=w mod n(1w)mod n=w mod n加法逆元：对wZn,有zZn，满足w+z=0 mod n,z为w的加法逆元，记为z=-w。加法的可约律(a+b)(a+c)mod n,则bc mod n 对乘法不一定成立，因为乘法逆元不一定存在。,模运算,定理:设aZn,gcd(a,n)=1,则a在Zn有逆元 证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从1得出aZn=Zn,因此存在xZn,使ax=1 mod n设p为素数，Zp
4、中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(ab)=(ac)mod n,b=c mod n,中国剩余定理,如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数定理(中国剩余定理)：设m1,m2,mk是两两互素的正整数，则一次同余方程组 对模M有唯一解,中国剩余定理,中国剩余定理可以将一个很大的数x表示为一组较小的数(a1,ak)例：x1 mod 2,x2 mod 3,x3 mod 5 x5 mod 7,求x解：M2357210，M1=105,M2=70,M3=42,M4=30,(Mi=M/mi),可以求得e1=1,e2=1,e3=3,e4=4,所以x=105117012
5、42333045 mod 210173,费尔玛定理和欧拉定理,费尔玛定理 若p是素数，a是正整数且gcd(a,p)=1，则ap-11 mod p证明：gcd(a,p)=1,则aZp=Zp,a(Zp-0)=Zp-0 a mod p,2a mod p,(n-1)a mod p=0,1,p-1(a mod p)(2a mod p)(n-1)a mod p=(p-1)!mod p(p-1)!ap-1=(p-1)!mod p(p-1)!与p互素，所以乘法可约律，ap-1=1 mod p,费尔玛定理和欧拉定理,欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)定理：若n是两
6、个素数p和q的乘积，则(n)(p)(q)=(p-1)(q-1)欧拉定理若a和n互素,则a(n)=1 mod n,离散对数,求模下的整数幂根据欧拉定理，若gcd(a,n)=1,则af(n)1 mod n。考虑一般am 1 mod n,如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。例：a=7,n=19.71 7 mod 19,72 11 mod 19,73 1 mod 19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同,RSA算法的实现,实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq 和
7、(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，那么：用公钥作业：ME mod N=C 用私钥作业：CD mod N=M,解密正确性证明,cd mod n med mod n m1 modj(n)mod n mkj(n)+1 mod nm与n互素，由欧
8、拉定理 mj(n)1 mod n,mkj(n)1 mod n,mkj(n)+1m mod ngcd(m,n)1,m是p的倍数或q的倍数，设m=cp，此时gcd(m,q)=1,由欧拉定理，mj(q)1 mod q，mkj(q)1 mod q，mkj(q)j(p)1 mod q mkj(n)1 mod q，存在一整数r，使mkj(n)1rq 两边同乘m=cp,mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1m mod n,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
9、;计算d,(d*e)mod 96=1;d=77;私钥sk=77;设:明文m=19 加密：（19）5 mod 119=66 脱密：（66）77 mod 119=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算
10、法中规定n的长度为512至1024比特位之间，但必须是128的倍数国际数字签名标准ISO/IEC 9796中规定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的长度相同；(
11、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,用欧几里德算法可求 r e1+s e2=1假定r为负数，从而可知由Euclidean算法可计算(c1-1)-r c2s=m mod n,对RSA的攻击低指数攻击,令网中三用户的加密钥e均选3，而有不同的模n1,n
12、2,n3，若有一用户将消息x传给三个用户的密文分别为 y1=x 3 mod n1 x n1 y2=x 3 mod n2 x n2 y3=x 3 mod n3 x n3 一般选n1,n2,n3互素(否则，可求出公因子，而降低安全性)，利用中国余定理，可从y1,y2,y3求出 y=x 3 mod(n1 n2 n3)。由xn1,xn2,xn3，可得x3 n1 n2,n3，故有,习题,在用户a对用户b利用RSA公钥密码体制进行消息的加密签名时，若二者使用的模数nanb，为了使脱密正常进行，应该先加密还是先签名？,平方乘算法,P-1因子分解算法,素性检验,引理：如果p为大于2的素数，则方程x21 mod p的解只有和x1和x-1证明:x21 mod p x2-1 0 mod p(x+1)(x-1)0 mod p 所以,p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)存在k,j，x+1=kp,x-1=jp2=(k-j)p,这是不可能的。引理的逆命题：若方程x21 mod p有唯一解x不为+1或-1，p不是素数,素性检验-Miller-Rabin素性概率检测法,作业,1求(160)、(72)。2P985.3，5.4。,
