《sa算法及安全性分析》由会员分享，可在线阅读，更多相关《sa算法及安全性分析（16页珍藏版）》请在金锄头文库上搜索。
1、RSA 算法及安全性分析算法及安全性分析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 这这
2、8个模个模15的剩余类是的剩余类是： 1，2，4，7，8，11，13，14 Euler定理、定理、Fermat定理定理oEuler定理：定理：设设 x 和和 n 都是正整数，如果都是正整数，如果gcd(x，n)1，则，则 x (n)1 (mod n).oFermat定理定理:设设 x 和和 p 都是正整数，如果都是正整数，如果gcd(x，p)1，则，则 x p-11 (mod p).RSA算法的实现算法的实现 实现的步骤如下：实现的步骤如下：Bob为实现者为实现者 (1) Bob寻找出两个大素数寻找出两个大素数p和和q (2) Bob计算出计算出n=pq 和和(n)=(p-1)(q-1) (3
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，解出秘密的解出秘密的dRSA算法编制算法编制 参数参数T=NT=N；私钥私钥SK=DSK=D；公钥公钥PK=EPK=E； 设：明文设：明文M M，密文密文C C，那么：那么： 用公钥
4、作业：用公钥作业：M ME E mod N = C mod N = C 用私钥作业：用私钥作业：C CD D mod N = M mod N = MRSA算法举例算法举例设设设设 p=7, q=17, n=7*17=119; p=7, q=17, n=7*17=119; p=7, q=17, n=7*17=119; p=7, q=17, n=7*17=119; 参数参数参数参数T=n=119;T=n=119;T=n=119;T=n=119; (n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;选
5、择选择选择选择e=5, gcd(5,96)=1; e=5, gcd(5,96)=1; e=5, gcd(5,96)=1; e=5, gcd(5,96)=1; 公钥公钥公钥公钥pkpkpkpk=5;=5;=5;=5;计算计算计算计算d, ( d*e) mod 96=1; d=77; d, ( d*e) mod 96=1; d=77; d, ( d*e) mod 96=1; d=77; d, ( d*e) mod 96=1; d=77; 私钥私钥私钥私钥sksksksk=77;=77;=77;=77;设设设设: : : :明文明文明文明文m=19m=19m=19m=19 加密：（加密：（加密：（加
6、密：（19191919）5 5 5 5 mod 119 = 66 mod 119 = 66 mod 119 = 66 mod 119 = 66 脱密：（脱密：（脱密：（脱密：（66666666）77777777 mod 119 = 19 mod 119 = 19 mod 119 = 19 mod 119 = 19RSA算法的安全性分析算法的安全性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n若若分分解解成成功功使使n=pq，则则可可以以算算出出(n)（p-1)(q-1)，然后由公开的然后由公开的e，解出秘密的解出秘密的d若若使使RSA安安全全，p与与q
7、必必为为足足够够大大的的素素数数，使使分分析析者者没有办法在多项式时间内将没有办法在多项式时间内将n分解出来分解出来 n取取1024位位或或取取2048位位，这这样样p、q就就应应该该取取512位和位和1024位。位。RSA算法的安全性分析算法的安全性分析建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特EDI攻攻击击标标准准使使用用的的RSA算算法法中中规规定定n的的长长度度为为512至至1024比特位之间，但必须是比特位之间，但必须是128的倍数的倍数国国际际数数字字签签名名标标准准ISO/IEC 9796中中规规定定
8、n的的长长度度位位512比比特位特位 如果用如果用MIPS年表示每秒钟执行一百万条指令年表示每秒钟执行一百万条指令的计算机计算一年时间的计算量，下表给出了不同的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。比特的整数的因子分解所需的时间。 密钥大小 MIPS年 512比特 768比特1024比特2048比特RSA算法的安全性分析算法的安全性分析 为为了了抵抵抗抗现现有有的的整整数数分分解解算算法法，对对RSA模模n的的素素因因子子p和和q还有如下要求还有如下要求（即是强素数）（即是强素数）： (1) p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (
9、2) P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (3) p+1和和q+1分别含有大素因子分别含有大素因子p3和和q3RSA算法的安全性分析算法的安全性分析其它参数的选择要求：其它参数的选择要求：(1) |p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1和和q-1的最大公因子要小；的最大公因子要小；(3)e的选择；的选择；(4)d的选择；的选择；(5)不要许多的用户共用一个不要许多的用户共用一个n。不动点分析 定义定义 如果如果 则称则称 m m 为为RSARSA的一个不动点的一个不动点。 (1) 此时的密文就是明文，因而直此时的密文就是明文，因而直接暴露了明文。接暴露了明文。(2) 利用不动点利用不动点m m可能分解大合数可能分解大合数N N。下节内容下节内容oEIgamal公钥算法公钥算法oECC算法算法oRSA的快速实现的快速实现 21作业1求(160)、 (72) 。2P985.3，5.4。
