高磊 周金治

摘 要：数字签名是网络信息安全的有力保障，对实现身份验证、数据完整性、不可抵赖性等功能以及解决伪造、抵赖、冒充和篡改等问题都有重要应用。文中分析了RSA算法和数字签名的实现原理，提出了基于多重密钥的改进RSA数字签名方案，提高了数字签名的安全性，该方案包括数字签名的生成和验证。为了提升数字签名的效率，文中采用中国剩余定理来优化大数的模幂运算。最后通过仿真实验，将传统RSA算法，ElGamal算法，MD5算法与改进算法的数字签名时间进行对比，实验结果表明，改进后的算法对签名效率有一定程度的提升。

关键词：数字签名；身份验证；RSA算法；多重密钥；中国剩余定理；签名效率

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2018）04-00-03

0 引 言

随着互联网与信息化社会的不断发展，计算机网络通信技术的应用领域和应用深度也不断扩大，这在给人们带来益处的同时，也带来了诸多信息安全方面的挑战，譬如网络通信中敏感数据和机密信息的安全问题。因此许多针对解决这类问题的技术与方案应运而生，其中用来保证信息完整性且能够解决消息传输过程中的否认、伪造、篡改及冒充等问题的安全技術——数字签名技术就成为人们研究的课题之一。由于数据在传输过程中存在被通信双方之外的第三方伪造或篡改的可能性，通信双方无法验证数据的真实来源，导致某一方否认或抵赖的情况出现，因此保证传输信息的不可抵赖性尤为重要。数字签名是基于公钥密码体制，防止通信双方在网上进行信息交换时伪造和欺骗的一种身份认证技术。在通信过程中，双方无需进行密钥交换，有着良好的保密性。数字签名可以用来验证消息来源的唯一性和不可否认性，同时，数字签名也可用来验证存储的消息或程序的完整性。虽然传统的使用散列函数产生数字摘要的算法[1]可以避免某些攻击，但如果系统参数不合适，亦存在安全风险。

目前，常见的数字签名算法包括RSA签名算法[2]，Schnorr算法[3]，ElGamal算法[4]以及DSA算法[5]。文献[6][7]提出了基于改进RSA算法的数字签名方案，旨在增强签名的安全性，并未对签名效率作出优化。RSA算法中的大数模幂运算一直是影响其运算速度的重要因素，目前提出了譬如SMM算法[8]和指数2k次方组合优化算法[9]等改进算法，虽然相对于传统RSA算法在签名效率上有所提升，但效果甚微。

本文提出了一种基于多密钥指数的RSA签名方案，为了优化签名效率，采用中国剩余定理（Chinese Remainder Theorem， CRT）对RSA算法签名过程加以改进，实验结果表明，该算法相比传统算法，签名效率得到了一定程度的提升。

1 相关技术研究

1.1 RSA算法

非对称加密算法中最著名的是由美国MIT的Rivest，Shamir和Adleman于1978年发表的RSA算法[10]，它是目前应用最为广泛的公钥加密算法，现被国际标准化组织（International Organization for Standardization，ISO）推荐为公钥数据加密标准。这是一种非对称密钥密码体制，会将公共密钥和私有密钥分配给发送方和接收方来加密和解密消息。RSA公钥加密算法包含密钥生成，消息加密，消息解密三个步骤。

1.1.1 RSA密钥生成

（1）任意选取两个不相干的大素数p和q，并将其保密存储；

（2）计算n=pq和欧拉函数φ（n）=（p-1）（q-1）；

（3）随机选取一个正整数e，使其满足1

（4）计算解密密钥d，使其满足0

1.1.2 消息加密

消息发送方使用如下方式对明文M进行加密：

C=Memod（n）

1.1.3 消息解密

消息接收方使用如下方式对密文C进行解密：

C=Cdmod（n）

其中：M代表需要加密的明文，C代表加密后的密文，e代表加密时的密钥，d代表解密时的密钥，n代表模数。n和e公开，p，q，d和φ（n）需保密。

1.2 基于RSA的数字签名

基于RSA算法的数字签名[11]中，通信双方各拥有2个密钥。秘密密钥SK-A，SK-B及公开密钥PK-A，PK-B，分别对应加密算法EPK-A，EPK-B和解密算法DSK-A，DSK-B。若用户A传送需签名的消息m给用户B，则A可用自己的解密算法DSK-A对消息m进行加密，从而得到DSK-A（m），再用B的加密算法EPK-B对DSK-A（m）进行加密：

C=EPK-B（DSK-A（m））

当用户B获得密文C后，首先用自己的解密算法DSK-B对C进行解密：

DSK-B（C）=DSK-B（EPK-B（DSK-A（m）））=DSK-A（m）

接着再用A的加密算法EPK-A对DSK-A（m）进行解密：

EPK-A（DSK-A（m））=m'

若m'=m，则可确定消息来自于A，否则拒绝对方的签名。若A否认给B发送过消息m，则用户B只需向公证方提供A的签名DSK-A（m）和公钥e，公证方通过算法便能轻易证实签名的确属于A；同样，若用户B伪造了消息m'，因其不知道A的私钥，于是便无法提供正确的签名，因此消息通信双方都可有效防止一方抵赖的情况发生，从而保证数字签名的可靠性。

2 改进RSA算法数字签名

2.1 基于消息分组和密钥指数的RSA算法

RSA算法中使用单整数密钥，为了提高安全性，文中基于两个大素数使用多个整数（多重密钥）来提高密钥破译的难度。由于利用不同的公钥指数对不同的分组明文进行了加密，故改进算法不会遭受针对同一明文不同公钥指数的公共模数攻击。

2.1.1 密钥生成

解得：M=（Mpqp-1+Mqpq-1）mod n，即为原明文M。由上述过程可见，明文分组M1，M2，…，Mk皆可由算法计算得到，该定理的优势在于能把大整数对n的模幂运算转换成相对较小的数p，q的模幂运算，最后合并运算结果。在RSA算法中应用CRT能够降低签名过程的运算量和复杂度。

3 实验结果及分析

实验选用i5-2450M CPU，是含6 GB内存和Windows 64位系统的平台，实验工具采用Microsoft Visual Studio 2017。实验对50～200不同长度的字符进行测试，改进后的算法加解密效果如图1所示。加密后的密文无法被识别，证实了改进RSA算法能够取得良好的加解密效果。数字签名证书的实现结果如图2所示。

为了对传统RSA算法，ElGamal算法，MD5算法以及改进后的算法性能进行对比，使用这4种算法分别对1 MB，5 MB，10 MB，20 MB的字符串数据量进行签名，实验结果见表1所列。從表1中4种算法平均所耗时间的对比可知：改进后的RSA算法的平均签名速度分别是传统算法的1.60倍，ElGamal算法的2.58倍，MD5算法的1.49倍。而且随着数据量的增大，改进算法对签名效率的优化并未明显降低。为了更加直观地观察4种算法的签名效率，我们将算法平均所耗时间放在图3中进行对比。

4 结 语

数字签名作为信息安全领域的一项重要技术，其算法可靠性应放在首位。本文在介绍与分析传统RSA算法的基础上，提出了一种改进的RSA算法，通过使用多重密钥增强签名过程的安全性，并通过实验验证了提出的RSA算法的有效性。对于影响RSA算法运算效率的大量模幂运算，文中通过在改进算法中融入中国剩余定理，在确保算法安全性的基础上把模幂运算降到最低来优化运算效率。最后，将改进RSA算法和其他三种签名算法在不同数据量的情况下进行对比实验，记录算法平均所耗时间。实验结果显示，改进RSA算法的签名时间明显降低，算法签名的效率得到了提升。改进后的算法的不足之处是无法保证在数据量较大时签名效率的显著提升。因此，如何探索既保证签名系统的安全性，又提升大数据量下的签名效率的数字签名方案成为下一步研究的重点。

参考文献

[1] LAKSHMANAN T，MUTHUSAMY M. A novel secure hash algorithm for public key digital signature schemes[J]. International arab journal of information technology，2013， 9（3）：262-267.

[2] FU C，ZHU Z. An efficient implementation of RSA digital si-gnature algorithm[C] //Wireless Communications， Networking and Mobile Computing， 2008，WiCOM08. 4th International Conference on. IEEE， 2008： 1-4.

[3] SCHNORR C P. Efficient identification and signatures for smart cards[Z].In：Proceeding s of Advances in Cryptology-Crypto89， Berlin：Springer-Verlag，1990：239-251.

[4] ELGAMAL T. A public-key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE transactions on information theory ， 1985， 31（4）：469-472.

[5] SCHNEIER B.Applied Cryptography ：Protocols， Algorithms，and Source Code in C[M].2nd Edition，New York：Wiley ， 1995：521-522.

[6] KAMAL K G，GUPTA B，IQBAL Z， et al. Modified RSA digital signature scheme for data confidentiality[J]. International journal of computer applications，2014， 106（13）：13-16.

[7] ANSOUR A H. Analysis of RSA Digital Signature Key Generation using Strong Prime[J]. International journal of computer （IJC），2017， 24（1）： 28-36.

[8]周升力.RSA密码算法的研究与快速实现[D].南昌：南昌大学，2008： 38-39.

[9]何俊杰，焦淑云，祁传达.一个基于身份的签密方案的分析与改进[J].计算机应用研究， 2013， 30（3）： 913-916.

[10] RIVEST R， SHAMIR A， ALDEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM， 1978， 26（2）： 96-99.

[11] DOUGLAS R S密码学原理与实践（第3版）[M].北京： 电子工业出版社，2016： 222-234.