第讲rsa算法及安全性分析.ppt

《第讲rsa算法及安全性分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、RSA算法及安全性分析量子密码研究室王滨2005.4.13Euler函数所有模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都是正整数，如果g

2、cd(x，n)＝1，则xφ(n)≡1(modn).Fermat定理:设x和p都是正整数，如果gcd(x，p)＝1，则xp-1≡1(modp).RSA算法的实现实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和φ(n)=(p-1)(q-1)(3)Bob选择一个随机数e(0

3、的e，解出秘密的dRSA算法编制参数T={N}；私钥SK=D；公钥PK=E；设：明文M，密文C，那么：用公钥作业：MEmodN=C用私钥作业：CDmodN=MRSA算法举例设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=19RSA算法的安全性分析密码分析者攻击RSA体制的关键点在于如何分解n若分解成功使n=pq，则可以算

4、出φ(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年表示每秒钟执行一百万条指令的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解

5、所需的时间。密钥大小MIPS年512比特768比特1024比特2048比特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和q3RSA算法的安全性分析其它参数的选择要求：(1)

6、p-q

7、很大，通常p和q的长度相同；(2)p-1和q-1的最大公因子要小；(3)e的选择；(4)d的选择；(5)不要许多的用户共用一个n。不动点分析定义如果则称m为RSA的一个不动点。(1)此时的密文就

8、是明文，因而直接暴露了明文。(2)利用不动点m可能分解大合数N。下节内容EIgamal公钥算法ECC算法RSA的快速实现21作业1．求φ(160)、φ(72)。2．P98－5.3，5.4。