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

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

  1. 1、本文档共20页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
中国剩余定理在RSA算法中应用 地研究实验 演讲PPT.ppt

主讲:李雪飞 中国剩余定理在RSA算法中应用的研究实验 研究背景 RSA 签名是一种最常用的数字签名方法。然而,RSA 算法中的大数的模幂运算比较费时,这一直是制约着RSA 发展的瓶颈。早期,人们建议使用较小的加密指数或解密指数以加快加密或解密( 签名) 等基本运算,但是,1990 年Wiener提出当私钥d 小于模数N1 /4 时,RSA 密码系统是不安全的。 * * 中国剩余定理 * * 《孙子算经》中的题目:有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总数几何? 中国剩余定理 《孙子算经》中的解法:三三数之,取数七十,与余数二相乘;五五数之,取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘积相加,然后减去一百零五的倍数。 中国剩余定理 (CRT)[3,4,5]设p1,p2,…,ps是两两互素的正整数,即GCD(pi,pj)=1(i≠j),对于任意整数 d1,d2,…,ds(0[di[pi-1,i=1,2,…,s),同余式方程组 x≡d1(modp1) x≡d2(modp2) … x≡ds(modps) 在0到N=∏pi内有惟一解。 * * 中国剩余定理 根据高斯算法,中国剩余定理的解为X=(b1M1y1+b2M2y2+…+bkMkyk) mod N ,其中N=nl×n2×…×nk ,Mi=N/ni=n1n2…ni-1…ni+1…nk ,i=1, 2,…, k, yi满足yi=Mi-1 mod ni。由此可见,中国剩余定理为对高位宽(如1024bit)大数的模幂运算转化成对低位宽(如512bit)相对较小的数进行模幂运算提供了可能。 * * 中国剩余定理用于RSA * * 基于中国剩余定理,RSA 模幂运算可转化为以下运算过程: (1) 计算 Cp=C mod p , Cq=C mod q ; (2) 计算 Mp=Cp^Dp mod p , Mq=Cq^Dqmod 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 * * 假定模数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 * * 使用传统算法计算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算法 在传统双素数RSA 密码算法基础上,把素数个数取为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) ≡ me mod n 解密算法m = D( c) ≡ cd mod n * * 中国剩余定理用于四素数RSA算法 运用中国剩余定理,对消息摘要D 的数字签名可转换为 以下运算过程: 1) 计算mp = D mod p,mq = D mod q,mr = D mod r,ms = D mod s; 2) 计算dp = d mod ( p-1),dq = d mod ( q-1),dr =d mod ( r-1),ds = d mod ( s-1) ; 3) 计算M1 = mpdp mod p,M2 = mpdq mod q,M3 = mrdr mod r,M4 = msds mod s; 4) 计算S = ( M1( qrs) p-1 + M2( prs) q-1 + M3( pqs) r-1 + M4( pqr) s-1 ) mod n,即得出签名S。 * * 四素数RSA算法的复杂度 假定模数N 的二进制长度为

文档评论(0)

克拉钻 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档