中国剩余定理在RSA算法中应用的 研究实验 演讲PPT.ppt
《中国剩余定理在RSA算法中应用的 研究实验 演讲PPT.ppt》由会员分享,可在线阅读,更多相关《中国剩余定理在RSA算法中应用的 研究实验 演讲PPT.ppt(17页珍藏版)》请在三一文库上搜索。
1、主讲:李雪飞,中国剩余定理在RSA算法中应用的研究实验,研究背景,RSA 签名是一种最常用的数字签名方法。然而,RSA 算法中的大数的模幂运算比较费时,这一直是制约着RSA 发展的瓶颈。早期,人们建议使用较小的加密指数或解密指数以加快加密或解密( 签名) 等基本运算,但是,1990 年Wiener提出当私钥d 小于模数N1 /4 时,RSA 密码系统是不安全的。,2019年2月27日,2,中国剩余定理,2019年2月27日,3,孙子算经中的题目:有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总数几何?,中国剩余定理,孙子算经中的解法:三三数之,取数七十,与余数二相乘;五五数之
2、,取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘积相加,然后减去一百零五的倍数。,中国剩余定理,(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内有惟一解。,2019年2月27日,5,中国剩余定理,根据高斯算法,中国剩余定理的解为X=(b1M1y1+b2M2y2+bkMkyk) mod N ,其中N=nln2nk ,Mi=N/ni=n1n2ni-1ni+1nk ,i=1,
3、 2, k, yi满足yi=Mi-1 mod ni。由此可见,中国剩余定理为对高位宽(如1024bit)大数的模幂运算转化成对低位宽(如512bit)相对较小的数进行模幂运算提供了可能。,2019年2月27日,6,中国剩余定理用于RSA,2019年2月27日,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
4、=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,2019年2月27日,8,假定模数N 的二进制长度为k,则其两个素因子p和q的长度分别为k/2,出于安全性考虑,私钥d的二进制长度应与模数N相当,也为k。dp、dq、p-1 mod q、q-1mod p可预先计算好,二进制长度均为k/2。从上述运用中国剩余定理计算模幂的过程可知S 计算过程的主要工作花在
5、计算Cp 和Cq上,最后,一步合成C只是两次乘法和一次加法运算,在计算时间复杂度时可忽略不计。,中国剩余定理用于RSA,2019年2月27日,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) = (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国剩余定理在RSA算法中应用的 研究实验 演讲PPT 中国 剩余 定理 RSA 算法 应用 研究 实验 演讲 PPT
链接地址:https://www.31doc.com/p-2187573.html