RSA算法及安全性分析课件

RSA RSA 算法及安全性分析算法及安全性分析量子密码研究室量子密码研究室王滨王滨2005.4.132005.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定理定理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) 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，那么：，那么： 用公钥作业：用公钥作业：M ME E mod N = C mod N = C 用私钥作业：用私钥作业：C CD D mod N = M mod N = MRSA算法举例算法举例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/IEC 9796中规定中规定n的长度位的长度位512比比特位特位如果用如果用MIPS年表示每秒钟执行一百万条指令年表示每秒钟执行一百万条指令的计算机计算一年时间的计算量，下表给出了不同的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。比特的整数的因子分解所需的时间。密钥大小 MIPS年 512比特 768比特1024比特2048比特43 1082 10113 10203 10RSA算法的安全性分析算法的安全性分析 为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对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) |p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1和和q-1的最大公因子要小；的最大公因子要小；(3)e的选择；的选择；(4)d的选择；的选择；(5)不要许多的用户共用一个不要许多的用户共用一个n。 定义定义 如果如果 modemNm 则称则称 m m 为为RSARSA的一个不动点的一个不动点。 下节内容下节内容oEIgamal公钥算法公钥算法oECC算法算法oRSA的快速实现的快速实现 21作业1求(160)、 (72) 。2P985.3，5.4。