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

RSA算法及安全性分析,量子密码研究室王滨2005.4.13,Euler函数,所有模m和r同余的整数组成剩余类r剩余类r中的每一个数和m互素的充要条件是r和m互素和m互素的同余类数目用(m)表示，称m的Euler函数当m是素数时，小于m的所有整数均与m互素，因此(m)=m-1对n=pq,p和q是素数，(n)=(p)(q)=(p-1)(q-1),Euler函数举例,设p=3,q=5,那么（15）=（3-1）*（5-1）=8这8个模15的剩余类是：1，2，4，7，8，11，13，14,Euler定理、Fermat定理,Euler定理：设x和n都是正整数，如果gcd(x，n)1，则x(n)1(modn).Fermat定理:设x和p都是正整数，如果gcd(x，p)1，则xp-11(modp).,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,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)利用不动