《【安全课件】第20讲--rsa算法及安全性分析》由会员分享，可在线阅读，更多相关《【安全课件】第20讲--rsa算法及安全性分析（18页珍藏版）》请在装配图网上搜索。
1、RSA 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,那么那么 （1
2、5）=（3-1）*（5-1）=8 这这8个模个模15的剩余类是的剩余类是：1，2，4，7，8，11，13，14 Euler定理、定理、Fermat定理定理oEuler定理：定理：设设 x 和和 n 都是正整数，如果都是正整数，如果gcd(x，n)1，则，则 x(n)1(mod n).oFermat定理定理:设设 x 和和 p 都是正整数，如果都是正整数，如果gcd(x，p)1，则，则 x p-11(mod p).RSA算法的实现算法的实现 实现的步骤如下：实现的步骤如下：Bob为实现者为实现者 (1)Bob寻找出两个大素数寻找出两个大素数p和和q (2)Bob计算出计算出n=pq 和和(n)=
3、(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，解出秘密的，解出秘密的dRSA算法编制算法编制 参数参数T=NT=N；私钥私钥SK=DSK=D；公钥公钥PK=EPK=E；设：明文设：明文M M，密文，密文C C
4、，那么：，那么：用公钥作业：用公钥作业：M ME E mod N=C mod N=C 用私钥作业：用私钥作业：C CD D mod N=M mod N=MRSA算法举例算法举例RSA算法的安全性分析算法的安全性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n若分解成功使若分解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由公开的然后由公开的e，解出秘密的，解出秘密的d若使若使RSA安全，安全，p与与q必为足够大的素数，使分析者必为足够大的素数，使分析者没有办法在多项式时间内将没有办法在多项式时间内将n分解出来分解出来 n取取102
5、4位或取位或取2048位，这样位，这样p、q就应该取就应该取512位和位和1024位。位。RSA算法的安全性分析算法的安全性分析建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特EDI攻击标准使用的攻击标准使用的RSA算法中规定算法中规定n的长度为的长度为512至至1024比特位之间，但必须是比特位之间，但必须是128的倍数的倍数国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比比特位特位如果用如果用MIPS年表示每秒钟执行一百万条指令年表示每秒钟执行一百万条指令的计算机计算一年
6、时间的计算量，下表给出了不同的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。比特的整数的因子分解所需的时间。密钥大小 MIPS年 512比特 768比特1024比特2048比特43 1082 10113 10203 10RSA算法的安全性分析算法的安全性分析 为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对RSA模模n的素因子的素因子p和和q还有如下要求还有如下要求（即是强素数）（即是强素数）：(1)p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (2)P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (3)p+1和和q+
7、1分别含有大素因子分别含有大素因子p3和和q3RSA算法的安全性分析算法的安全性分析其它参数的选择要求：其它参数的选择要求：(1)|p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1和和q-1的最大公因子要小；的最大公因子要小；(3)e的选择；的选择；(4)d的选择；的选择；(5)不要许多的用户共用一个不要许多的用户共用一个n。定义定义 如果如果 modemNm 则称则称 m m 为为RSARSA的一个不动点的一个不动点。下节内容下节内容oEIgamal公钥算法公钥算法oECC算法算法oRSA的快速实现的快速实现 21作业1求(160)、(72)。2P985.3，5.4
8、。9、静夜四无邻，荒居旧业贫。22.7.2922.7.29Friday,July 29,202210、雨中黄叶树，灯下白头人。9:18:579:18:579:187/29/2022 9:18:57 AM11、以我独沈久，愧君相见频。22.7.299:18:579:18Jul-2229-Jul-2212、故人江海别，几度隔山川。9:18:579:18:579:18Friday,July 29,202213、乍见翻疑梦，相悲各问年。22.7.2922.7.299:18:579:18:57July 29,202214、他乡生白发，旧国见青山。2022年7月29日星期五上午9时18分57秒9:18:5
9、722.7.2915、比不了得就不比，得不到的就不要。2022年7月上午9时18分22.7.299:18July 29,202216、行动出成果，工作出财富。2022年7月29日星期五9时18分57秒9:18:5729 July 202217、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。上午9时18分57秒上午9时18分9:18:5722.7.299、没有失败，只有暂时停止成功！。22.7.2922.7.29Friday,July 29,202210、很多事情努力了未必有结果，但是不努力却什么改变也没有。9:18:579:18:579:187/29/2022 9:18:5
10、7 AM11、成功就是日复一日那一点点小小努力的积累。22.7.299:18:579:18Jul-2229-Jul-2212、世间成事，不求其绝对圆满，留一份不足，可得无限完美。9:18:579:18:579:18Friday,July 29,202213、不知香积寺，数里入云峰。22.7.2922.7.299:18:579:18:57July 29,202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2022年7月29日星期五上午9时18分57秒9:18:5722.7.2915、楚塞三湘接，荆门九派通。2022年7月上午9时18分22.7.299:18July 29,202216、
11、少年十五二十时，步行夺得胡马骑。2022年7月29日星期五9时18分57秒9:18:5729 July 202217、空山新雨后，天气晚来秋。上午9时18分57秒上午9时18分9:18:5722.7.299、杨柳散和风，青山澹吾虑。22.7.2922.7.29Friday,July 29,202210、阅读一切好书如同和过去最杰出的人谈话。9:18:579:18:579:187/29/2022 9:18:57 AM11、越是没有本领的就越加自命不凡。22.7.299:18:579:18Jul-2229-Jul-2212、越是无能的人，越喜欢挑剔别人的错儿。9:18:579:18:579:18F
12、riday,July 29,202213、知人者智，自知者明。胜人者有力，自胜者强。22.7.2922.7.299:18:579:18:57July 29,202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2022年7月29日星期五上午9时18分57秒9:18:5722.7.2915、最具挑战性的挑战莫过于提升自我。2022年7月上午9时18分22.7.299:18July 29,202216、业余生活要有意义，不要越轨。2022年7月29日星期五9时18分57秒9:18:5729 July 202217、一个人即使已登上顶峰，也仍要自强不息。上午9时18分57秒上午9时18分9:18:5722.7.29MOMODA POWERPOINTLorem ipsum dolor sit amet,consectetur adipiscing elit.Fusce id urna blandit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis ut cursus.感 谢 您 的 下 载 观 看感 谢 您 的 下 载 观 看专家告诉
【安全课件】第20讲--rsa算法及安全性分析
