基于多重密鑰與CRT的數字簽名研究

高磊 周金治

摘 要：數字簽名是網絡信息安全的有力保障，對實現身份驗證、數據完整性、不可抵賴性等功能以及解決偽造、抵賴、冒充和篡改等問題都有重要應用。文中分析了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.