中国剩余定理在RSA算法中应用研究实验演讲.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算法 在传统双素数Ｒ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) ≡ 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 的二进制长度为