sa算法及安全性分析.ppt

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这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 利用不动点m