收藏 分销(赏)

中国剩余定理在RSA算法中应用的-研究实验-演讲.ppt

上传人:知****运 文档编号:14619786 上传时间:2026-10-21 格式:PPT 页数:17 大小:588.04KB 下载积分:10 金币
下载 相关
中国剩余定理在RSA算法中应用的-研究实验-演讲.ppt_第1页
第1页 / 共17页
中国剩余定理在RSA算法中应用的-研究实验-演讲.ppt_第2页
第2页 / 共17页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,主讲:李雪飞,中国剩余定理在,RSA,算法中应用的研究实验,研究背景,RSA,签名是一种最常用的数字签名方法。然而,,RSA,算法中的大数的模幂运算比较费时,这一直是制约着,RSA,发展的瓶颈。早期,人们建议使用较小的加密指数或解密指数以加快加密或解密,(,签名,),等基本运算,但是,,1990,年,Wiener,提出当私钥,d,小于模数,N,1/4,时,,RSA,密码系统是不安全的,。,2026年10月21日,2,中国剩余定理,2026年10月21日,3,孙子算经,中的题目:有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总数几何?,中国剩余定理,孙子算经,中的解法:三三数之,取数七十,与余数二相乘;五五数之,取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘积相加,然后减去一百零五的倍数。,中国剩余定理,(CRT)3,4,5,设,p,1,p,2,p,s,是两两互素的正整数,即,GCD(p,i,p,j,)=1(i,j),对于任意整数,d,1,d,2,d,s,(0d,i,p,i-1,i=1,2,s),同余式方程组,x,d,1,(modp,1,),x,d,2,(modp,2,),x,d,s,(modp,s,),在,0,到,N=p,i,内有惟一解。,2026年10月21日,5,中国剩余定理用于,RSA,2026年10月21日,8,假定模数,N,的二进制长度为,k,,则其两个素因子,p,和,q,的长度分别为,k/2,,出于安全性考虑,私钥,d,的二进制长度应与模数,N,相当,也为,k,。,d,p,、,d,q,、,p,-1,mod q,、,q,-1,mod p,可预先计算好,二进制长度均为,k/2,。从上述运用中国剩余定理计算模幂的过程可知,S,计算过程的主要工作花在计算,C,p,和,C,q,上,最后,一步合成,C,只是两次乘法和一次加法运算,在计算时间复杂度时可忽略不计。,中国剩余定理用于,RSA,2026年10月21日,9,使用传统算法计算,C,p,和,C,q,需要,3/2*(k/2),次,k/2,比特的模乘运算,总共需要,s1=2*3/2*(k/2)*(k/2),2,=3/8*k,3,次位操作。如果不用中国剩余定理,直接计算需要,s2=3/2*k,3,次位操作。因此,使用中国剩余定理计算模幂乘比不使用大约快了,4,倍。,四素数RSA算法,在传统双素数,SA,密码算法基础上,把素数个数取为,4,,算法依然成立,其描述如下,:,1),随机选取,4,个不同的大素数,p,,,q,,,r,和,s,,计算,n=pqrs,,,(n)=(p,1)(q,1)(r,1)(s,1),。,2),取加密密钥,e=65537,,计算出私钥,d,,满足,de,1 mod,(n),。,3),加密解密过程与传统算法一样,仍为,:,加密算法,c=E(m),m,e,mod n,解密算法,m=D(c),c,d,mod n,2026年10月21日,10,中国剩余定理用于四素数RSA算法,运用中国剩余定理,对消息摘要,D,的数字签名可转换为,以下运算过程,:,1),计算,m,p,=D mod p,,,mq=D mod q,,,mr=D mod r,,,ms=D mod s;,2),计算,d,p,=d mod(p,1),,,d,q,=d mod(q,1),,,d,r,=d mod(r,1),,,d,s,=d mod(s,1);,3),计算,M,1,=m,p,dp,mod p,,,M,2,=m,p,dq,mod q,,,M,3,=m,r,dr,mod r,,,M,4,=m,s,ds,mod s;,4),计算,S=(M,1,(qrs),p,1,+M,2,(prs),q,1,+M3(pqs),r,1,+,M,4,(pqr),s,1,)mod n,,即得出签名,S,。,2026年10月21日,11,四素数RSA算法的复杂度,假定模数,N,的二进制长度为,k,,则其四个素因子,p,、,q,、,r,和,s,的长度分别为,k/4,,出于安全性考虑,私钥,d,的二进制长度应与模数,N,相当,也为,k,。,d,p,、,d,q,、,d,r,、,d,s,、,p,-1,mod qrs,、,q,-1,mod prs,、,r,-1,mod pqs,、,s,-1,mod pqr,可预先计算好,二进制长度均为,k/4,。从上述运用中国剩余定理计算模幂的过程可知,S,计算过程的主要工作花在计算,C,p,、,C,q,、,C,r,和,C,s,上,最后,一步合成,C,只是,16,次乘法和,3,次加法运算,在计算时间复杂度时可忽略不计。使用传统算法计算,C,p,、,C,q,、,C,r,和,C,s,需要,3/2*(k/4),次,k/4,比特的模乘运算,总共需要,s1=4*3/2*(k/4)*(k/4),2,=3/16*k,3,次位操作。,2026年10月21日,12,四素数RSA算法,2026年10月21日,13,RSA,算法实现,2026年10月21日,14,RSA,算法实现,2026年10月21日,15,1 Yunfei Li,Qing Liu,Tong Li.Design and Implementation of an Improved RSA AlgorithmJ,International Conference on E-Health Networking,Digital Ecosystems and Technologies,2010,390393,2,费晓飞,胡捍英,.CRT-RSA,算法安全性分析,M.,微计算机信息,2009.(1-3):3738,3,武滨,使用中国剩余定理提高,RSA,算法效率安全性分析及改进方法,J.,网络与安全技术,2006,(3):78,80.,4,肖振久,胡驰,陈虹,.,四素数,SA,数字签名算法的研究与实现,J.,计算机应用,2013,33(5):1374,1377.,5,张宏,刘方园,.,四素数,RSA,加密算法的研究与分析,J.,为计算机信息,2010,26(5-3):29,30.,6,李云飞,柳青,赫林,周保林,.,一种有效的,RSA,算法改进方案,J.,计算机应用,2010,30(9):2393,2397.,7,柳青,李云飞,周保林,彭华,.,基于多素数的批处理,RSA,算法的研究,J.,计算机应用研究,2011.28(2):714-716,8,贺毅朝,刘建芹,陈维海,.,中国剩余定理在,RSA,解密中的应用,J.,河北省科学院学报,2003,20(3):138,143.,2026年10月21日,16,参考文献,2026年10月21日,17,谢谢观看,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服