中国剩余定理在RSA算法中应用的 研究实验.docx

华北电力大学中国剩余定理在RSA算法中应用的研究实验摘要RSA算法中模数和运算效率之间一直存在矛盾，目前一些认证机构已采用模数为 2 048 bit 的 RSA 签名方法，这必然会影响签名效率。中国剩余定理对于提高RSA算法的模幂乘运算效率有显著作用，被广泛地应用在加速私钥解密和签名的运算上。在本文中，就中国剩余定理如何提高RSA算法的速度给出详细的描述。但是，直接使用中国剩余定理是不安全的，容易受到出错攻击，本文介绍了出错攻击的方式，并提出了对抗出错攻击的随机小素数改进方法。在此基础上，本文选取了一种四素数RSA算法进行阐述和简单实现，这种算法巧妙地利用了中国剩余定理将传统的RSA算法的速度提升了几倍。关键词：RSA 、中国剩余定理、四素数、加密、信息安全目录中国剩余定理在RSA算法中应用的1研究实验1摘要1第一章 引言1第二章 RSA22.1RSA密码算法22.2 RSA密码算法的实现步骤2第三章 中国剩余定理在RSA算法中的应用33.1中国剩余定理33.2 RSA 中CRT 的引入33.3使用中国剩余定理加速RSA算法效率的安全隐患分析43.4使用随机小素数改进中国剩余定理对抗出错攻击的方法5第四章 四素数RSA数字签名算法64.1 四素数RSA 算法基本原理64.2四素数RSA 算法在数字签名中的应用74.3 中国剩余定理的应用74.4算法对比8第五章 四素数RSA算法的简单实现95.1 密钥产生部分95.2 加密解密部分10第六章 总结13参考文献142第一章 引言随着网络和通信技术的发展，在给人们带来益处的同时，也带来了安全隐患。由于传输过程中存在数据被通信双方之外的第三方伪造或篡改的可能，通信双方无法验证数据来源，就很有可能出现一方抵赖的情况，此时就要求保证传输信息的不可否认性。数字签名就是通信双方在网上交换信息时，基于公钥密码体制来防止伪造和欺骗的一种身份认证技术。在所有公钥密码体制中，应用最为广泛的是RSA( Rivest-Shamir-Adleman) 密码算法，它的特点是安全性高，易于实现，即可用来加密数据，又能用于身份认证。因此，RSA 签名是一种最常用的数字签名方法。然而，RSA 算法中的大数的模幂运算比较费时，这一直是制约着RSA 发展的瓶颈。早期，人们建议使用较小的加密指数或解密指数以加快加密或解密( 签名) 等基本运算，但是，1990 年Wiener提出当私钥d 小于模数N1 /4 时，RSA 密码系统是不安全的，其分析方法本质是利用了连分数中Legendre定理； 随后1999 年，Boneh 和Durfee把弱密钥d 的上界提高到d N0 292。因此，出于安全性考虑，目前RSA 密码系统的模数为1 024 bit 到2 048 bit，如此庞大的模数，其运算效率必然受到影响。针对这一问题，很多学者提出了不同的优化算法，比如基于乘同余对称特性和指数2k 次方组合优化算法、加法链方法、滑动窗口法和模重复平方算法等，这些都是从运算操作的角度去优化； 国外还提出了许多从结构上改进的算法，比如Batch RSA、Mprime RSA、Mpower RSA 和Rebalanced RSA。这些方法都在一定程度上提高了算法运算效率，其中效果比较显著的是利用中国剩余定理( Chinese RemainderTheorem，CRT) 进行解密或签名。本文把融入中国剩余定理的RSA 算法叫作CRT-RSA ( Chinese Remainder Theorem-Rivest Shamir Adleman) 算法。已证明，若不考虑中国剩余定理的计算代价，双素数CRT-RSA 在运算效率上是传统RSA算法的4 倍； 若考虑中国剩余定理的计算代价，双素数CRT-RSA在运算速度上分别是原算法的332 倍( 模为1 024 比特) 和347 倍( 模为2048 比特)。这个速度虽令人满意，却存在安全隐患，传统双素数CRT-RSA 签名算法容易遭受出错攻击，攻击者能够利用错误的签名来分解模数N。本文详细阐述了中国剩余定理的原理作用，以及如何将它利用到RSA中，然后通过对一种四素数CRT_RSA算法的实现对其进行研究。第二章 RSA2.1RSA密码算法随机选取两个不同的大素数p和q,计算它们的乘积N=pq与相应的欧拉函数(N)=(p-1)(q-1)的值,将N公开,而将( N)、p与q保密；显然,如果在不知道N的素因子p与q的前提下,计算(N)的值是属于NP问题,极难实现。再随机选取一个正整数e,使e满足条件：e(N)且GCD(e,(N)=1(即e与(N)的最大公因数是1),根据扩展Euclid算法(Extended Euclidean Algorithm)计算de-1(mod ),即计算满足ed1(mod(N)的d。将e公开,而将d保密,就确定了RSA算法的公开密钥PK=(e,N),私人密钥SK=(d,N),密钥空间：K=(N,p,q,e,d)|N=pq,p与q为不同大素数,ed1(mod (N)。相应地,RSA算法中的单向陷门函数为f(x)=xt(modN)(其中tK且xZN),称为RSA函数。其秘密陷门信息为(N)及素数p、q的值。确定公钥PK=(e,N)和私钥SK=(d,N)之后,RSA算法的加密运算定义为：c=Epk(m)=me(modN),其中1mN-1为明文。解密运算定义为：m=Dsk(c)=cd(modN),其中1cN-1为密文。RSA密码算法的明文m应为1到N-1之间的整数,即m1,N-1。如果明文m太长,可将其转换成N进制的形式,即m=msNs+ms-1Ns-1+,+m1N+m0,于是得到分组后的明文序列m=(m0,m1,ms),其中mi1,N-1,0is。与之相应的密文序列为c(c0,c1,cs),其中c1对应于m1(0is)。2.2 RSA密码算法的实现步骤(1)随机选择两个不同的秘密大素数p与q；(2)分别计算N=pq和( N)=(p-1)(q-1)的值；(3)选择一个小于( N)且与( N)互素的正整数e,定义PK=(e,N)；(4)计算e的乘法逆元d=e-1(mod( N),并定义SK=(d,N)；(5)利用数制转换将明文分组,使每组中明文m的取值范围在1至N-1之间；(6)执行加密运算c=Epk(m)=me(modN),将明文m加密成密文c；(7)执行解密运算m=Dsk(c)=cd(modN),将密文c恢复成明文m。第三章 中国剩余定理在RSA算法中的应用3.1中国剩余定理中国剩余定理（CRT）：已知n1, n2, , nk为两两互素的正整数，则同余方程组Xbi mod niX在0到N内有唯一解，其中i=1, 2, , k，bi为正整数，N=nln2nk。根据高斯算法，中国剩余定理的解为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)相对较小的数进行模幂运算提供了可能。3.2 RSA 中CRT 的引入在RSA 算法中，n=pq, p, q 是两个长度接近的大素数。由于n 是两个素数的乘积，所以可令Cp=md (mod p) ，Cq=md (mod q) ，再根据中国剩余定理求出最终结果。根据费马小定理，计算上面两式仅需计算Cp=md1 (mod p) ，Cq=md2 (mod q) ，其中d1=d mod(p-1)，d2=d mod(q-1)。这样把幂指数d 减少至d1，d2。由于d 的长度接近于n， 而d1, d2 能减少至n 的一半，大大减少了计算次数。基于中国剩余定理，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。显然， 步骤（ 2） 的计算量远远大于其它步骤的计算量，但是，中国剩余定理的运用，使得Mp和Mq的并行计算成为可能。并行执行步骤（ 2） 的模幂运算需要两个n/2 位的乘法器，相比于不采用中国剩余定理的RSA 运算，加速因子接近于4。假定模数N 的二进制长度为k，则其两个素因子p和q的长度分别为k/2，出于安全性考虑，私钥d的二进制长度应与模数N相当，也为k。dp、dq、p-1 mod q、q-1mod p可预先计算好，二进制长度均为k/2。从上述运用中国剩余定理计算模幂的过程可知S 计算过程的主要工作花在计算Cp 和Cq上，最后，一步合成C只是两次乘法和一次加法运算，在计算时间复杂度时可忽略不计。使用传统算法计算Cp 和Cq需要3/2*(k/2)次k/2比特的模乘运算，总共需要s1=2*3/2*(k/2) *(k/2)2=3/8*k3次位操作。如果不用中国剩余定理，直接计算需要s1=3/2*k3次位操作。因此，使用中国剩余定理计算模幂乘比不使用大约快了4倍。3.3使用中国剩余定理加速RSA算法效率的安全隐患分析直接使用中国剩余定理加速2) 运算容易受到出错攻击，只要2) 应用系统在执行签名9 加密时满足以下三个条件：（一）、签名/加密的原始消息已知；（二）、在签名/加密时出现了一个错误；（三）、系统输出了错误的签名/密文；就可能导致应用系统的模数N被分解，从而造成RSA算法被攻破。其攻击原理是：签名方用自己的私钥计算C=Mdmod N，使用中国剩余定理C可通过Cp=C mod p ，Cq=C mod q有效计算出来。假设错误发生在计算Cp时，也就是说计算出了一个错误的值Cp Cp=C mod p ，而Cq被正确计算出来。Cp和Cq就联合产生了一个错误的签名C，这样就会导致如下结果：q=gcd(Ce-M)mod N),N)其中e 是公钥，gcd()表示求最大公约数，即通过上述关系式可以计算出模数N的素因子q，从而达到因子分解N攻破RSA应用系统的目的。（证明略）可以看出，出错攻击是一种非常强的攻击方法，直接使用中国剩余定理进行RSA运算，一旦系统发生了一个错误，将可能导致整个系统的模数被直接分解，致使RSA系统崩溃。因此，在提高RSA算法效率时要慎用中国剩余定理。3.4使用随机小素数改进中国剩余定理对抗出错攻击的方法改进方法原理和过程如下：1. 选择一个随机小素数r（如2，3，5）等，并计算如下两个数：Cpr=Md mod (pr) (mod pr) 和Cqr=Md mod (qr) (mod qr)；2. 判断Cpr=Cqr (mod r)是否成立；3. 如果上式成立，则认为模幂运算计算过程没有出现错误，合并Cpr和Cqr 可得计算结果C：C=(Cpr mod p) (q-1 mod p)q + (Cqr mod q) (p-1 mod q)p mod N4. 如果Cpr=Cqr (mod r)不成立，则认为本次计算发生错误，废除本次操作，重新计算。第四章 四素数RSA数字签名算法在本章中，一种改进的RSA算法四素数RSA算法的原理和具体实现被详细的阐述。通过这个算法我们进一步去了解中国剩余定理在RSA算法速度改进方面的巨大作用。4.1 四素数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下面，本文从数论的角度来证明算法的正确性。证明 假设明文为m，密文c，密钥( d，n) ，公钥( e，n) 。由加密解密过程有: D( c) cd mod n( me ) d mod nmed modn，又因为de1 mod ( n) ，所以de1 + k( n) ，其中k 为正整数，代入上式得D( c) m1 +( n) mod n，若gcd( m，n) 1，根据欧拉定理有: m( n) 1 mod n，故有m1 +( n) m mod n; 若gcd( m，n) 1，由于n = pqrs，故( m，n) 中必含p，q，r，s之一，或者pq，pr，ps，qr，qs，rs 之一，或者pqr，prs，qrs，pqs 之一。由于这几种情况类似，这里只给出gcd( m，n) 只包含p，q，r，s之一的证明过程: 若gcd( m，n) = p，m = cp，1 c qrs，由欧拉定理得: m( q) 1mod q，m( r) 1 mod r，m( s) 1 mod s，因此，对任意k 恒有mk( q1) 1 mod q，mk( q1) ( r1) ( s1) ( p1) 1 mod q，就有mk( q1) ( r1) ( s1) ( p1) 1 + hq，得出mk( n) 1 + hq，因为m = cp，因此得出mk( n) +1 m +cphq，已知p，q，r，s都是素数，故gcd( p，q rs) = 1，gcd( m，qrs) = 1，推出m( qrs) 1 mod qrs，对任意k，总有mk( q1) ( r1) ( s1) 1 mod qrs，所以mk( q1) ( r1) ( s1) ( p1) 1 mod qrs，即mk( n) 1 + hqrs，又因为m = cp，所以mk( n) +1 m + chpqrs，这就证明了mk( n) +1 m mod n，其他同理可证均成立。4.2四素数RSA 算法在数字签名中的应用首先简单介绍一下杂凑函数，它是指将任意长度的消息映射成某一固定长度消息的一种函数，一般用于消息完整性检测和认证。它是一种单项散列函数，也就是说给定一个消息M，用杂凑函数H，生成消息摘要D = H( M) ，这个计算很容易，但反推M 却很难。把杂凑函数运用到数字签名中，一方面是为了提高签名速度，因为，如果直接对消息签名，当消息很长时需要对其分组，再对每组消息用SA 签名，这样签名效率相当低; 另一方面，可以不泄漏要签名的消息，这适用于一些特殊的签名场景10。本文中用的是一种安全性非常高的杂凑函数SHA51211( Secure Hash Algorithm) ，再结合四素数SA 算法，其签名过程如下:1) 用户A 将要发送的消息M 通过杂凑函数H，产生消息摘要D = H( M) ;2) 用户A 用私钥d 对消息摘要进行签名S = Dd mod n;3) 用户A 将消息M 和签名S 一同发送给用户B;4) 用户B 接受到消息和签名后用A 的公钥解密签名S 得到D，再用杂凑函数计算一次消息摘要D，判断D 是否等于D。若相同，则说明消息确实来自于A，并且在传输途中没有被篡改; 否则，很有可能消息不是来自于A。运用以上的签名方法，如果用户A 想否认曾经发送消息M 给用户B，用户B 只需把A 的公钥和签名S 一并出示给公证方，通过正确的计算方法就能证实用户A 确实发送了消息M; 如果用户B 伪造了一个消息M，由于他不知道用户A 的私钥，也就无法出示正确的签名给公证方。这样一来，通信双方都必须真实地反映通信情况，有效地防止了一方抵赖的情况发生。4.3 中国剩余定理的应用运用中国剩余定理，对消息摘要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。在上述计算过程中，先把传统的签名算法S = Dd mod n转换为求解四个同余式: S Dd mod p，S Dd mod q，S Ddmod r 和SDd mod s，再利用中国剩余定理进行求解。在求乘法逆元时，本文没有用扩展欧几里得算法，而是运用了费马小定理: 对任何不被素数p 整除的整数A，恒有Ap1 1 mod p，可得A1 Ap2 mod p，巧妙地通过一个多项式运算来代替其中一个逆元的求解，进一步提高了运算效率。但是，如第三章中提到的，运用中国剩余定理容易使RSA算法遭受出错攻击，所以四素数RSA算法也必须使用随机小素数进行改进，对抗出错攻击。4.4算法对比假定模数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次位操作。因此，算法的特点如下表：复杂度是否可以并行执行安全性传统RSA算法3/2*k3否不易遭受出错攻击二素数CRT-RSA算法3/8*k3是易出现出错攻击，需用随机小素数改进四素数CRT-RSA算法3/16*k3是易出现出错攻击，需用随机小素数改进第五章 四素数RSA算法的简单实现 5.1 密钥产生部分如图所示，输入四个素数，点击生成密钥后，软件自动生成公钥、私钥和模数。密钥生成核心代码如下：void Produce_Key(int p, int q, int r, int s) int ola_num = Count_N_AoLa_Num(p, q, r, s); if (ola_num = 0) return; int e = 0; do e = new Random().Next(1, ola_num); while (!JudgeHomogeny(e, ola_num); textBox3.Text = e.ToString(); int d = Generate_d(e, ola_num); textBox4.Text = d.ToString(); textBox5.Text = (p * q * r * s).ToString(); int Generate_d(int e, int n) int over = e; for (int i = 1; i n; ) over = over % n; if (over = 1) return i; else if (over + e = n) do i+; over += e; while (over + e 0) c = new BigInteger(inBuffer);m = BigInteger.ModPow(c, d, n);outBuffer = m.ToByteArray();outputFile.Write(outBuffer, 0, outBuffer.Length); public void Encrypt(BigInteger e, BigInteger n)int bufferLength = n.ToByteArray().Length;byte inBuffer = new bytebufferLength - 1;byte outBuffer, tmpBuffer;BigInteger m, c;while (inputFile.Read(inBuffer, 0, inBuffer.Length) 0) m = new BigInteger(inBuffer);Array.Clear(inBuffer, 0, inBuffer.Length);c = BigInteger.ModPow(m, e, n);outBuffer = c.ToByteArray(