RSA算法及安全性分析.ppt

1、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 都是正整数，如果

2、gcd(x，n)1，则 x (n)1 (mod n). Fermat定理:设 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)，然后由公

3、 开的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

4、体制的关键点在于如何分解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年表示每秒钟执行一百万条指令的计算机计算一年时间

5、的计算量，下表给出了不同比特的整数的因子分解所需的时间。,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) 利用不动