中国剩余定理在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参考文献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、MprimeRSA、MpowerRSA 和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必威体育官网网址,就确定