四素数RSA数字签名算法的研究与实现

摘要：

RSA算法中模数和运算效率之间一直存在矛盾，目前一些认证机构已采用模数为2048bit的RSA签名方法，这必然会影响签名效率。针对这一问题，提出四素数CRTRSA签名算法，并使用安全杂凑函数SHA512来生成消息摘要，采用中国剩余定理结合Montgomery模乘来优化大数的模幂运算。通过安全性分析和仿真实验表明，该签名算法能抵抗一些常见攻击，并且在签名效率方面具有一定优势。

关键词：

RSA密码算法；四素数；中国剩余定理；蒙哥马利算法；杂凑函数；数字签名

0引言

随着网络和通信技术的发展，在给人们带来益处的同时，也带来了安全隐患。由于传输过程中存在数据被通信双方之外的第三方伪造或篡改的可能，通信双方无法验证数据来源，就很有可能出现一方抵赖的情况，此时就要求保证传输信息的不可否认性。数字签名就是通信双方在网上交换信息时，基于公钥密码体制来防止伪造和欺骗的一种身份认证技术。在所有公钥密码体制中，应用最为广泛的是RSA（RivestShamirAdleman）密码算法[1]，它的特点是安全性高，易于实现，即可用来加密数据，又能用于身份认证。因此，RSA签名[2]是一种最常用的数字签名方法。

然而，RSA算法中的大数的模幂运算比较费时，这一直是制约着RSA发展的瓶颈。早期，人们建议使用较小的加密指数或解密指数以加快加密或解密（签名）等基本运算，但是，1990年Wiener[3]提出当私钥d小于模数N1/4时，RSA密码系统是不安全的，其分析方法本质是利用了连分数中Legendre定理；随后1999年，Boneh和Durfee[4]把弱密钥d的上界提高到d

本文针对目前一些认证机构采用模数为2048bit的RSA密码系统，比如电子商务中的安全电子交易协议（Secure Electronic Transaction，SET）协议采用的模数为2048bit RSA签名算法，从安全性和运算效率方面考虑，提出一种四素数CRTRSA数字签名算法。

6结语

近年来，许多加密技术和大量安全协议都采用了RSA算法，在一些对安全性要求比较高的认证机构中，甚至采用了模数为2048bit的RSA签名算法，这对于本来运算效率就不太高的RSA算法来说无疑是一个巨大的挑战。本文针对这一问题提出了四素数CRTRSA签名算法，结合了Montgomery模指数算法和中国剩余定理对签名过程加以优化，最后在VC6.0的开发环境中进行了仿真实验，对几种签名效率做了比较分析，实验结果证实了四素数CRTRSA签名算法在签名效率方面的优越性。

参考文献：

[1]

RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public key cryptosystems[J]. Communications of the Association for Computer Machinery，1978，21（2）：120-126.

[2]

CAO YINGYU， FU CHONG.An efficient Implementation of RSA digital signature algorithm[C]// 2008 International Conference on Intelligent Computation Technology and Automation. Piscataway： IEEE Press， 2008：100-103.

[3]

WIENER M J. Cryptanalysis of short RSA secret exponents[J].IEEE Transactions on Information Theory，1990，36（3）：553-558.

[4]

BONEH D， DURFEE G.Cryptanalysis of RSA with private key d less than N0.292[J]. IEEE Information Theory Society，2000，46（4）：1339-1349.

[5]

贺克英.改进的RSA算法实现研究[D].成都：电子科技大学，2010.

[6]

PAIXAO C A M. An efficient variant of the RSA cryptosystem[EB/OL].[2010-10-02].http：// www.ime.usp.br/～capaixao/paper.pdf.

[7]

刘承彬，耿也，舒奎，等.有关中国剩余定理在多个素数的RSA解密运算中的加速公示的论证以及加速效率的估算[J].大连工业大学学报，2012，31（5）：372-375.

[8]

杨波.现代密码学[M].北京：清华大学出版社，2007.

[9]

费晓飞，胡捍英.CRTRSA算法安全性分析[J].微计算机信息，2009，25（3）：36-38.

[10]

陈月荣.数字签名技术在电子商务中的应用[D]. 淮北：淮北师范大学，2011.

[11]

STALLINGS W.Cryprography and network security principles and practice[M].5th ed.北京：电子工业出版社，2011.

[12]

王安.RSA公钥密钥算法的快速实现[D].济南：山东大学，2008.

[13]

刘美，王玉柱，何定养，等.SHA512算法及基于生日攻击的安全性分析[J].后勤工程学院学报，2010，26（3）：92-96.

[14]

COUVEIGNES J M，EZOME T，LERCIER R.A faster pseudoprimality test[J]. Rendiconti del Circolo Matematico di Palermo，2012，61（2）：261-278.