《【安全课件】第20讲--rsa算法及安全性分析课件.pptx》由会员分享，可在线阅读，更多相关《【安全课件】第20讲--rsa算法及安全性分析课件.pptx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、RSA 算法及安全性分析算法及安全性分析量子密码研究室量子密码研究室2005.4.132005.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
2、,那么那么 （15）=（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=p
3、q 和和(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，解出秘密的，解出秘密的dRSA算法编制算法编制 参数参数T=NT=N；私钥私钥SK=DSK=D；公钥公钥PK=EPK=E；设：明文设：明文M M，
4、密文，密文C C，那么：，那么：用公钥作业：用公钥作业：M ME E mod N=C mod N=C 用私钥作业：用私钥作业：C CD D mod N=M mod N=MRSA算法举例算法举例设设设设 p=7,q=17,n=7*17=119;p=7,q=17,n=7*17=119;p=7,q=17,n=7*17=119;p=7,q=17,n=7*17=119;参数参数参数参数T=n=119;T=n=119;T=n=119;T=n=119;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;选择选
5、择选择选择e=5,gcd(5,96)=1;e=5,gcd(5,96)=1;e=5,gcd(5,96)=1;e=5,gcd(5,96)=1;公钥公钥公钥公钥pk=5;pk=5;pk=5;pk=5;计算计算计算计算d,(d*e)mod 96=1;d=77;d,(d*e)mod 96=1;d=77;d,(d*e)mod 96=1;d=77;d,(d*e)mod 96=1;d=77;私钥私钥私钥私钥sk=77;sk=77;sk=77;sk=77;设设设设:明文明文明文明文m=19m=19m=19m=19 加密：（加密：（加密：（加密：（19191919）5 5 5 5 mod 119=66 mod 1
6、19=66 mod 119=66 mod 119=66 脱密：（脱密：（脱密：（脱密：（66666666）77777777 mod 119=19 mod 119=19 mod 119=19 mod 119=19RSA算法的安全性分析算法的安全性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n若若分分解解成成功功使使n=pq，则则可可以以算算出出(n)（p-1)(q-1)，然后由公开的，然后由公开的e，解出秘密的，解出秘密的d若若使使RSA安安全全，p与与q必必为为足足够够大大的的素素数数，使使分分析析者者没有办法在多项式时间内将没有办法在多项式时间内将n
7、分解出来分解出来 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年表示每秒钟执行一百万条指令年表示每秒钟执
8、行一百万条指令的计算机计算一年时间的计算量，下表给出了不同的计算机计算一年时间的计算量，下表给出了不同比特的整数的因子分解所需的时间。比特的整数的因子分解所需的时间。密钥大小 MIPS年 512比特 768比特1024比特2048比特RSA算法的安全性分析算法的安全性分析 为为了了抵抵抗抗现现有有的的整整数数分分解解算算法法，对对RSA模模n的的素素因因子子p和和q还有如下要求还有如下要求（即是强素数）（即是强素数）：(1)p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (2)P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (3)p+1和和q+1分别含有大素因
9、子分别含有大素因子p3和和q3RSA算法的安全性分析算法的安全性分析其它参数的选择要求：其它参数的选择要求：(1)|p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1和和q-1的最大公因子要小；的最大公因子要小；(3)e的选择；的选择；(4)d的选择；的选择；(5)不要许多的用户共用一个不要许多的用户共用一个n。不动点分析 定义定义 如果如果 则称则称 m m 为为RSARSA的一个不动点的一个不动点。(1)此时的密文就是明文，因而直此时的密文就是明文，因而直接暴露了明文。接暴露了明文。(2)利用不动点利用不动点m m可能分解大合数可能分解大合数N N。下节内容下节内容
10、oEIgamal公钥算法公钥算法oECC算法算法oRSA的快速实现的快速实现 21作业1求(160)、(72)。2P985.3，5.4。1、有时候读书是一种巧妙地避开思考的方法。4月-234月-23Tuesday,April 25,20232、阅读一切好书如同和过去最杰出的人谈话。14:18:4514:18:4514:184/25/2023 2:18:45 PM3、越是没有本领的就越加自命不凡。4月-2314:18:4514:18Apr-2325-Apr-234、越是无能的人，越喜欢挑剔别人的错儿。14:18:4514:18:4514:18Tuesday,April 25,20235、知人者智
11、，自知者明。胜人者有力，自胜者强。4月-234月-2314:18:4514:18:45April 25,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。25四月20232:18:45下午14:18:454月-237、最具挑战性的挑战莫过于提升自我。四月232:18下午4月-2314:18April 25,20238、业余生活要有意义，不要越轨。2023/4/2514:18:4514:18:4625 April 20239、一个人即使已登上顶峰，也仍要自强不息。2:18:46下午2:18下午14:18:464月-2310、你要做多大的事情，就该承受多大的压力。4/25/2023 2:18:46 PM14:18:4625-4月-2311、自己要先看得起自己，别人才会看得起你。4/25/2023 2:18 PM4/25/2023 2:18 PM4月-234月-2312、这一秒不放弃，下一秒就会有希望。25-Apr-2325 April 20234月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Tuesday,April 25,202325-Apr-234月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。4月-2314:18:4625 April 202314:18谢谢大家谢谢大家