RSA算法及安全性分析

1、RSA算法及安全性分析1 RSA RSA 算法及安全性分析算法及安全性分析 量子密码研究室量子密码研究室 2005.4.132005.4.13 RSA算法及安全性分析2 Euler 函数函数 所有模所有模m和和r同余的整数组成剩余类同余的整数组成剩余类r 剩余类剩余类r中的每一个数和中的每一个数和m互素的充要条件是互素的充要条件是r和和m互素互素 和和m互素的同余类数目用互素的同余类数目用(m)表示，称表示，称m的的Euler函数函数 当当m是素数时，小于是素数时，小于m的所有整数均与的所有整数均与m互素，因此互素，因此 (m)=m-1 对对n=pq, p和和q 是素数，是素数，(n)=(p)

2、(q)=(p-1)(q-1) RSA算法及安全性分析3 Euler 函数函数举例举例 设设p=3, q=5, 那么那么 （15）=（3-1）* *（5-1）=8 这这8个模个模15的剩余类是的剩余类是： 1，2，4，7，8，11，13，14 RSA算法及安全性分析4 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算法及

3、安全性分析5 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，则可以算出，则可以算出

4、(n)（p-1)(q-1)，然后由公，然后由公 开的开的e，解出秘密的，解出秘密的d RSA算法及安全性分析6 RSA算法编制算法编制 参数参数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 = M RSA算法及安全性分析7 RSA算法举例算法举例 RSA算法及安全性分析8 RSA算法的安全性分析算法的安全性分析 密码分析者攻击密码分析者攻击RSA体制的关键点在于如何

5、分解体制的关键点在于如何分解n 若分解成功使若分解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)， 然后由公开的然后由公开的e，解出秘密的，解出秘密的d 若使若使RSA安全，安全，p与与q必为足够大的素数，使分析者必为足够大的素数，使分析者 没有办法在多项式时间内将没有办法在多项式时间内将n分解出来分解出来 n取取1024位或取位或取2048位，这样位，这样p、q就应该取就应该取 512位和位和1024位。位。 RSA算法及安全性分析9 RSA算法的安全性分析算法的安全性分析 建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数 模模n的长度要求至少是的长度

6、要求至少是512比特比特 EDI攻击标准使用的攻击标准使用的RSA算法中规定算法中规定n的长度为的长度为512至至 1024比特位之间，但必须是比特位之间，但必须是128的倍数的倍数 国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比比 特位特位 RSA算法及安全性分析10 如果用如果用MIPS年表示每秒钟执行一百万条指令年表示每秒钟执行一百万条指令 的计算机计算一年时间的计算量，下表给出了不同的计算机计算一年时间的计算量，下表给出了不同 比特的整数的因子分解所需的时间。比特的整数的因子分解所需的时间。 密钥大小 MIPS年 512比特 768比特

7、1024比特 2048比特 4 3 10 8 2 10 11 3 10 20 3 10 RSA算法及安全性分析11 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算法及安全性分析12 RSA算法的安全性分析算法的安全性分析 其它参数的选择要求：其它参数的选择要求： (1) |p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同； (2)p-1和和q-1的最大公因子要小；的最大公因子要小； (3)e的选择；的选择； (4)d的选择；的选择； (5)不要许多的用户共用一个不要许多的用户共用一个n。 RSA算法及安全性分析13 定义定义 如果如果 mod e mNm 则称则称 m m 为为RSARSA的一个不动点的一个不动点。 RSA算法及