中国剩余定理在RSA算法中应用的研究实验摘要RSA算法中模数和运算效率之间一直存在矛盾，目前一些认证机构已采用模数为2 048 bit 的RSA 签名方法，这必然会影响签名效率。

中国剩余定理对于提高RSA算法的模幂乘运算效率有显著作用，被广泛地应用在加速私钥解密和签名的运算上。

在本文中，就中国剩余定理如何提高RSA算法的速度给出详细的描述。

但是，直接使用中国剩余定理是不安全的，容易受到出错攻击，本文介绍了出错攻击的方式，并提出了对抗出错攻击的随机小素数改进方法。

在此基础上，本文选取了一种四素数RSA算法进行阐述和简单实现，这种算法巧妙地利用了中国剩余定理将传统的RSA算法的速度提升了几倍。

关键词：RSA 、中国剩余定理、四素数、加密、信息安全目录中国剩余定理在RSA算法中应用的 (1)研究实验 (1)摘要 (1)第一章引言 (1)第二章RSA (2)2.1RSA密码算法 (2)2.2 RSA密码算法的实现步骤 (2)第三章中国剩余定理在RSA算法中的应用 (3)3.1中国剩余定理 (3)3.2 RSA 中CRT 的引入 (3)3.3使用中国剩余定理加速RSA算法效率的安全隐患分析 (4)3.4使用随机小素数改进中国剩余定理对抗出错攻击的方法 (5)第四章四素数RSA数字签名算法 (6)4.1 四素数RSA 算法基本原理 (6)4.2四素数RSA 算法在数字签名中的应用 (7)4.3 中国剩余定理的应用 (7)4.4算法对比 (8)第五章四素数RSA算法的简单实现 (9)5.1 密钥产生部分 (9)5.2 加密解密部分 (10)第六章总结 (13)参考文献 (14)第一章引言随着网络和通信技术的发展，在给人们带来益处的同时，也带来了安全隐患。

由于传输过程中存在数据被通信双方之外的第三方伪造或篡改的可能，通信双方无法验证数据来源，就很有可能出现一方抵赖的情况，此时就要求保证传输信息的不可否认性。

数字签名就是通信双方在网上交换信息时，基于公钥密码体制来防止伪造和欺骗的一种身份认证技术。

在所有公钥密码体制中，应用最为广泛的是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在运算速度上分别是原算法的3．32 倍( 模为1 024 比特) 和3．47 倍( 模为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)计算d≡e-1(mod ),即计算满足ed≡1(mod(N))的d。

将e公开,而将d保密,就确定了RSA 算法的公开密钥PK=(e,N),私人密钥SK=(d,N),密钥空间：K={(N,p,q,e,d)|N=pq,p与q为不同大素数,ed≡1(mod (N))}。

相应地,RSA算法中的单向陷门函数为f(x)=x t(modN)(其中t∈K且x∈Z N),称为RSA函数。

其秘密陷门信息为(N)及素数p、q的值。

确定公钥PK=(e,N)和私钥SK=(d,N)之后,RSA算法的加密运算定义为：c=E pk(m)=m e(modN),其中1≢m≢N-1为明文。

解密运算定义为：m=D sk(c)=c d(modN),其中1≢c≢N-1为密文。

RSA密码算法的明文m应为1到N-1之间的整数,即m∈[1,N-1]。

如果明文m太长,可将其转换成N进制的形式,即m=msNs+ms-1Ns-1+,+m1N+m0,于是得到分组后的明文序列m=(m0,m1,…,m s),其中m i∈[1,N-1],0≢i≢s。

与之相应的密文序列为c(c0,c1,…,c s),其中c1对应于m1(0≢i≢s)。

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=E pk(m)=m e(modN),将明文m加密成密文c；(7)执行解密运算m=D sk(c)=c d(modN),将密文c恢复成明文m。

第三章中国剩余定理在RSA算法中的应用3.1中国剩余定理中国剩余定理（CRT）：已知n1, n2, …, n k为两两互素的正整数，则同余方程组X≡b i mod n iX在0到N内有唯一解，其中i=1, 2, …, k，b i为正整数，N=n l n2…n k。

根据高斯算法，中国剩余定理的解为X=(b1M1y1+b2M2y2+…+b k M k y k) mod N ，其中N=n l×n2×…×n k，Mi=N/n i=n1n2…n i-1…n i+1…n k，i=1, 2,…, k, y i满足y i=M i-1 mod n i。

由此可见，中国剩余定理为对高位宽(如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）计算C p=C mod p ，C q=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。

显然，步骤（2）的计算量远远大于其它步骤的计算量，但是，中国剩余定理的运用，使得Mp和Mq的并行计算成为可能。

并行执行步骤（2）的模幂运算需要两个n/2 位的乘法器，相比于不采用中国剩余定理的RSA 运算，加速因子接近于4。

假定模数N 的二进制长度为k，则其两个素因子p和q的长度分别为k/2，出于安全性考虑，私钥d的二进制长度应与模数N相当，也为k。

d p、d q、p-1 mod q、q-1mod p可预先计算好，二进制长度均为k/2。

从上述运用中国剩余定理计算模幂的过程可知S 计算过程的主要工作花在计算C p和C q上，最后，一步合成C只是两次乘法和一次加法运算，在计算时间复杂度时可忽略不计。

使用传统算法计算C p和C q需要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=M d mod N，使用中国剩余定理C可通过C p=C mod p ，C q=C mod q有效计算出来。

假设错误发生在计算C p时，也就是说计算出了一个错误的值C p’≠C p=C mod p ，而C q被正确计算出来。