【文档说明】【安全课件】第20讲--rsa算法及安全性分析.pptx，共(16)页，68.470 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-288647.html

以下为本文档部分文字说明：

RSA算法及安全性分析量子密码研究室王滨2005.4.13Euler函数▪所有模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定理、Ferma

t定理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，解出秘密的dRSA算法编制▪参数T={N}；▪私钥SK=D；▪公钥PK=E；设：明文M，密文C，那么：用公钥作业：MEmodN=C用

私钥作业：CDmodN=MRSA算法举例▪设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=19RSA算法的安全性分析▪密码分析者攻击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大约是10

0位的十进制素数▪模n的长度要求至少是512比特▪EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数▪国际数字签名标准ISO/IEC9796中规定n的长度位512比特位如果用MIPS年表示每秒钟执行一百万条指令的计算机计

算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。密钥大小MIPS年512比特768比特1024比特2048比特431082101131020310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和q3RSA算法的安全性分析其它参数的选择要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1的最大公因子要小；(3)e的选择；(4)d的

选择；(5)不要许多的用户共用一个n。不动点分析定义如果modemNm=则称m为RSA的一个不动点。(1)此时的密文就是明文，因而直接暴露了明文。(2)利用不动点m可能分解大合数N。下节内容EIgamal公钥算法ECC算法RSA的快速实现21作业1

．求φ(160)、φ(72)。2．P98－5.3，5.4。