欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

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

    • 资源ID:5541565       资源大小:313.51KB        全文页数:17页
    • 资源格式: PPT        下载积分:10金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

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

    主讲:李雪飞,中国剩余定理在RSA算法中应用的研究实验,研究背景,RSA 签名是一种最常用的数字签名方法。然而,RSA 算法中的大数的模幂运算比较费时,这一直是制约着RSA 发展的瓶颈。早期,人们建议使用较小的加密指数或解密指数以加快加密或解密(签名)等基本运算,但是,1990 年Wiener提出当私钥d 小于模数N1/4 时,RSA 密码系统是不安全的。,2023年7月19日,2,中国剩余定理,2023年7月19日,3,孙子算经中的题目:有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总数几何?,中国剩余定理,孙子算经中的解法:三三数之,取数七十,与余数二相乘;五五数之,取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘积相加,然后减去一百零五的倍数。,中国剩余定理,(CRT)3,4,5设p1,p2,ps是两两互素的正整数,即GCD(pi,pj)=1(ij),对于任意整数d1,d2,ds(0dipi-1,i=1,2,s),同余式方程组 xd1(modp1)xd2(modp2)xds(modps)在0到N=pi内有惟一解。,2023年7月19日,5,中国剩余定理,根据高斯算法,中国剩余定理的解为X=(b1M1y1+b2M2y2+bkMkyk)mod N,其中N=nln2nk,Mi=N/ni=n1n2ni-1ni+1nk,i=1,2,k,yi满足yi=Mi-1 mod ni。由此可见,中国剩余定理为对高位宽(如1024bit)大数的模幂运算转化成对低位宽(如512bit)相对较小的数进行模幂运算提供了可能。,2023年7月19日,6,中国剩余定理用于RSA,2023年7月19日,7,基于中国剩余定理,RSA 模幂运算可转化为以下运算过程:(1)计算Cp=C mod p,Cq=C mod q;(2)计算Mp=CpDp mod p,Mq=CqDqmod q;其中Dp=D mod(p-1),Dq=D mod(q-1),对于给定素数p、q及密钥而言是常数,可以预先计算出来。(3)计算Sp=Mp(q(p-1)mod N)mod N,Sq=Mq(p(q-1)mod N)mod N;其中,q(p-1)mod N 和p(q-1)mod N 是仅仅决定于素数p、q 和模N 的常数,可以预先计算出来。(4)计算M=(Sp+Sq)mod N,中国剩余定理用于RSA,2023年7月19日,8,假定模数N 的二进制长度为k,则其两个素因子p和q的长度分别为k/2,出于安全性考虑,私钥d的二进制长度应与模数N相当,也为k。dp、dq、p-1 mod q、q-1mod p可预先计算好,二进制长度均为k/2。从上述运用中国剩余定理计算模幂的过程可知S 计算过程的主要工作花在计算Cp 和Cq上,最后,一步合成C只是两次乘法和一次加法运算,在计算时间复杂度时可忽略不计。,中国剩余定理用于RSA,2023年7月19日,9,使用传统算法计算Cp 和Cq需要3/2*(k/2)次k/2比特的模乘运算,总共需要s1=2*3/2*(k/2)*(k/2)2=3/8*k3次位操作。如果不用中国剩余定理,直接计算需要s2=3/2*k3次位操作。因此,使用中国剩余定理计算模幂乘比不使用大约快了4倍。,四素数RSA算法,在传统双素数SA 密码算法基础上,把素数个数取为4,算法依然成立,其描述如下:1)随机选取4 个不同的大素数p,q,r和s,计算n=pqrs,(n)=(p1)(q1)(r1)(s1)。2)取加密密钥e=65537,计算出私钥d,满足de1 mod(n)。3)加密解密过程与传统算法一样,仍为:加密算法c=E(m)me mod n解密算法m=D(c)cd mod n,2023年7月19日,10,中国剩余定理用于四素数RSA算法,运用中国剩余定理,对消息摘要D 的数字签名可转换为以下运算过程:1)计算mp=D mod p,mq=D mod q,mr=D mod r,ms=D mod s;2)计算dp=d mod(p1),dq=d mod(q1),dr=d mod(r1),ds=d mod(s1);3)计算M1=mpdp mod p,M2=mpdq mod q,M3=mrdr mod r,M4=msds mod s;4)计算S=(M1(qrs)p1+M2(prs)q1+M3(pqs)r1+M4(pqr)s1)mod n,即得出签名S。,2023年7月19日,11,四素数RSA算法的复杂度,假定模数N 的二进制长度为k,则其四个素因子p、q、r和s的长度分别为k/4,出于安全性考虑,私钥d的二进制长度应与模数N相当,也为k。dp、dq、dr、ds、p-1 mod qrs、q-1mod prs、r-1 mod pqs、s-1mod pqr可预先计算好,二进制长度均为k/4。从上述运用中国剩余定理计算模幂的过程可知S 计算过程的主要工作花在计算Cp、Cq、Cr和Cs上,最后,一步合成C只是16次乘法和3次加法运算,在计算时间复杂度时可忽略不计。使用传统算法计算Cp、Cq、Cr和Cs需要3/2*(k/4)次k/4比特的模乘运算,总共需要s1=4*3/2*(k/4)*(k/4)2=3/16*k3次位操作。,2023年7月19日,12,四素数RSA算法,2023年7月19日,13,RSA算法实现,2023年7月19日,14,RSA算法实现,2023年7月19日,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,3903932 费晓飞,胡捍英.CRT-RSA 算法安全性分析M.微计算机信息,2009.(1-3):37383 武滨,使用中国剩余定理提高RSA算法效率安全性分析及改进方法J.网络与安全技术,2006,(3):7880.4 肖振久,胡驰,陈虹.四素数SA 数字签名算法的研究与实现J.计算机应用,2013,33(5):13741377.5 张宏,刘方园.四素数RSA 加密算法的研究与分析J.为计算机信息,2010,26(5-3):2930.6 李云飞,柳青,赫林,周保林.一种有效的RSA 算法改进方案J.计算机应用,2010,30(9):23932397.7柳青,李云飞,周保林,彭华.基于多素数的批处理RSA算法的研究J.计算机应用研究2011.28(2):714-716 8 贺毅朝,刘建芹,陈维海.中国剩余定理在RSA解密中的应用J.河北省科学院学报,2003,20(3):138143.,2023年7月19日,16,参考文献,2023年7月19日,17,谢谢观看,

    注意事项

    本文(中国剩余定理在RSA算法中应用的 研究实验 演讲PPT.ppt)为本站会员(sccc)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开