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

'主讲：李雪飞中国剩余定理在RSA算法中应用的研究实验 研究背景RSA签名是一种最常用的数字签名方法。然而，RSA算法中的大数的模幂运算比较费时，这一直是制约着RSA发展的瓶颈。早期，人们建议使用较小的加密指数或解密指数以加快加密或解密(签名)等基本运算，但是，1990年Wiener提出当私钥d小于模数N1/4时，RSA密码系统是不安全的。2021年9月2日2 中国剩余定理2021年9月2日3《孙子算经》中的题目：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？ 中国剩余定理《孙子算经》中的解法：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。 中国剩余定理(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内有惟一解。2021年9月2日5 中国剩余定理根据高斯算法，中国剩余定理的解为X=(b1M1y1+b2M2y2+…+bkMkyk)modN，其中N=nl×n2×…×nk，Mi=N/ni=n1n2…ni-1…ni+1…nk，i=1,2,…,k,yi满足yi=Mi-1modni。由此可见，中国剩余定理为对高位宽(如1024bit)大数的模幂运算转化成对低位宽(如512bit)相对较小的数进行模幂运算提供了可能。2021年9月2日6 中国剩余定理用于RSA2021年9月2日7基于中国剩余定理，RSA模幂运算可转化为以下运算过程：（1）计算Cp=Cmodp，Cq=Cmodq；（2）计算Mp=Cp^Dpmodp，Mq=Cq^Dqmodq；其中Dp=Dmod(p-1)，Dq=Dmod(q-1)，对于给定素数p、q及密钥而言是常数，可以预先计算出来。（3）计算Sp=Mp(q^(p-1)modN)modN，Sq=Mq(p^(q-1)modN)modN；其中，q^(p-1)modN和p^(q-1)modN是仅仅决定于素数p、q和模N的常数，可以预先计算出来。（4）计算M=(Sp+Sq)modN 中国剩余定理用于RSA2021年9月2日8假定模数N的二进制长度为k，则其两个素因子p和q的长度分别为k/2，出于安全性考虑，私钥d的二进制长度应与模数N相当，也为k。dp、dq、p-1modq、q-1modp可预先计算好，二进制长度均为k/2。从上述运用中国剩余定理计算模幂的过程可知S计算过程的主要工作花在计算Cp和Cq上，最后，一步合成C只是两次乘法和一次加法运算，在计算时间复杂度时可忽略不计。 中国剩余定理用于RSA2021年9月2日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)=(p－1)(q－1)(r－1)(s－1)。2)取加密密钥e=65537，计算出私钥d，满足de≡1modφ(n)。3)加密解密过程与传统算法一样，仍为:加密算法c=E(m)≡memodn解密算法m=D(c)≡cdmodn2021年9月2日10 中国剩余定理用于四素数RSA算法运用中国剩余定理，对消息摘要D的数字签名可转换为以下运算过程:1)计算mp=Dmodp，mq=Dmodq，mr=Dmodr，ms=Dmods;2)计算dp=dmod(p－1)，dq=dmod(q－1)，dr=dmod(r－1)，ds=dmod(s－1);3)计算M1=mpdpmodp，M2=mpdqmodq，M3=mrdrmodr，M4=msdsmods;4)计算S=(M1(qrs)p－1+M2(prs)q－1+M3(pqs)r－1+M4(pqr)s－1)modn，即得出签名S。2021年9月2日11 四素数RSA算法的复杂度假定模数N的二进制长度为k，则其四个素因子p、q、r和s的长度分别为k/4，出于安全性考虑，私钥d的二进制长度应与模数N相当，也为k。dp、dq、dr、ds、p-1modqrs、q-1modprs、r-1modpqs、s-1modpqr可预先计算好，二进制长度均为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次位操作。2021年9月2日12 四素数RSA算法2021年9月2日13 RSA算法实现2021年9月2日14 RSA算法实现2021年9月2日15 [1]YunfeiLi,QingLiu,TongLi.DesignandImplementationofanImprovedRSAAlgorithm[J],InternationalConferenceonE-HealthNetworking,DigitalEcosystemsandTechnologies,2010,390~393[2]费晓飞，胡捍英.CRT-RSA算法安全性分析[M].微计算机信息,2009.(1-3):37~38[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.2021年9月2日16参考文献 2021年9月2日17谢谢观看'