【安全课件】第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 1 1 modp RSA算法的实现 实现的步骤如下 Bob为实现者 1 Bob寻找出两个大素数p和q 2 Bob计算出n pq和 n p 1 q 1 3 Bob选择一个随机数e 0 e 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 利用不动