第20讲--RSA算法及安全性分析.ppt

RSA 算法及安全性分析 量子密码研究室 王滨 2005.4.13 Euler定理、Fermat定理 Euler定理：设 x 和 n 都是正整数，如果gcd(x，n)＝1，则 x φ(n)≡1 (mod n). Fermat定理:设 x 和 p 都是正整数，如果gcd(x，p)＝1，则 x p-1≡1 (mod p). RSA算法的安全性分析 其它参数的选择要求： (1) |p-q|很大，通常 p和q的长度相同； (2)p-1和q-1的最大公因子要小； (3)e的选择； (4)d的选择； (5)不要许多的用户共用一个n。 下节内容 EIgamal公钥算法 ECC算法 RSA的快速实现 2 作业 1．求φ(160)、 φ(72) 。 2．P98－5.3，5.4。 * * 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} 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，解出秘密的d RSA算法编制 参数T={N}； 私钥SK=D； 公钥PK=E； 设：明文M，密文C，那么： 用公钥作业：ME mod N = C 用私钥作业：CD mod N = 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) mod 96=1; d=77; 私钥sk=77; 设:明文m=19 加密：（19）5 mod 119 = 66 脱密：（66）77 mod 119 = 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/IEC 9796中规定n的长度位512比特位 如果用MIPS年表示每秒钟执行一百万条指令的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。 2048比特 1024比特 768比特 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 不动点分析 定义 如果 则称 m 为RSA的一个不动点。 (1) 此时的密文就是明文，因而直 接暴露了明文。 (2) 利用不动点m可能分解大合数N。 1 *