基于多重密鑰與CRT的數(shù)字簽名研究

高磊 周金治

摘 要：數(shù)字簽名是網(wǎng)絡(luò)信息安全的有力保障，對實現(xiàn)身份驗證、數(shù)據(jù)完整性、不可抵賴性等功能以及解決偽造、抵賴、冒充和篡改等問題都有重要應(yīng)用。文中分析了RSA算法和數(shù)字簽名的實現(xiàn)原理，提出了基于多重密鑰的改進(jìn)RSA數(shù)字簽名方案，提高了數(shù)字簽名的安全性，該方案包括數(shù)字簽名的生成和驗證。為了提升數(shù)字簽名的效率，文中采用中國剩余定理來優(yōu)化大數(shù)的模冪運算。最后通過仿真實驗，將傳統(tǒng)RSA算法，ElGamal算法，MD5算法與改進(jìn)算法的數(shù)字簽名時間進(jìn)行對比，實驗結(jié)果表明，改進(jìn)后的算法對簽名效率有一定程度的提升。

關(guān)鍵詞：數(shù)字簽名；身份驗證；RSA算法；多重密鑰；中國剩余定理；簽名效率

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2018）04-00-03

0 引 言

隨著互聯(lián)網(wǎng)與信息化社會的不斷發(fā)展，計算機網(wǎng)絡(luò)通信技術(shù)的應(yīng)用領(lǐng)域和應(yīng)用深度也不斷擴(kuò)大，這在給人們帶來益處的同時，也帶來了諸多信息安全方面的挑戰(zhàn)，譬如網(wǎng)絡(luò)通信中敏感數(shù)據(jù)和機密信息的安全問題。因此許多針對解決這類問題的技術(shù)與方案應(yīng)運而生，其中用來保證信息完整性且能夠解決消息傳輸過程中的否認(rèn)、偽造、篡改及冒充等問題的安全技術(shù)——數(shù)字簽名技術(shù)就成為人們研究的課題之一。由于數(shù)據(jù)在傳輸過程中存在被通信雙方之外的第三方偽造或篡改的可能性，通信雙方無法驗證數(shù)據(jù)的真實來源，導(dǎo)致某一方否認(rèn)或抵賴的情況出現(xiàn)，因此保證傳輸信息的不可抵賴性尤為重要。數(shù)字簽名是基于公鑰密碼體制，防止通信雙方在網(wǎng)上進(jìn)行信息交換時偽造和欺騙的一種身份認(rèn)證技術(shù)。在通信過程中，雙方無需進(jìn)行密鑰交換，有著良好的保密性。數(shù)字簽名可以用來驗證消息來源的唯一性和不可否認(rèn)性，同時，數(shù)字簽名也可用來驗證存儲的消息或程序的完整性。雖然傳統(tǒng)的使用散列函數(shù)產(chǎn)生數(shù)字摘要的算法[1]可以避免某些攻擊，但如果系統(tǒng)參數(shù)不合適，亦存在安全風(fēng)險。

目前，常見的數(shù)字簽名算法包括RSA簽名算法[2]，Schnorr算法[3]，ElGamal算法[4]以及DSA算法[5]。文獻(xiàn)[6][7]提出了基于改進(jìn)RSA算法的數(shù)字簽名方案，旨在增強簽名的安全性，并未對簽名效率作出優(yōu)化。RSA算法中的大數(shù)模冪運算一直是影響其運算速度的重要因素，目前提出了譬如SMM算法[8]和指數(shù)2k次方組合優(yōu)化算法[9]等改進(jìn)算法，雖然相對于傳統(tǒng)RSA算法在簽名效率上有所提升，但效果甚微。

本文提出了一種基于多密鑰指數(shù)的RSA簽名方案，為了優(yōu)化簽名效率，采用中國剩余定理（Chinese Remainder Theorem， CRT）對RSA算法簽名過程加以改進(jìn)，實驗結(jié)果表明，該算法相比傳統(tǒng)算法，簽名效率得到了一定程度的提升。

1 相關(guān)技術(shù)研究

1.1 RSA算法

非對稱加密算法中最著名的是由美國MIT的Rivest，Shamir和Adleman于1978年發(fā)表的RSA算法[10]，它是目前應(yīng)用最為廣泛的公鑰加密算法，現(xiàn)被國際標(biāo)準(zhǔn)化組織（International Organization for Standardization，ISO）推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。這是一種非對稱密鑰密碼體制，會將公共密鑰和私有密鑰分配給發(fā)送方和接收方來加密和解密消息。RSA公鑰加密算法包含密鑰生成，消息加密，消息解密三個步驟。

1.1.1 RSA密鑰生成

（1）任意選取兩個不相干的大素數(shù)p和q，并將其保密存儲；

（2）計算n=pq和歐拉函數(shù)φ（n）=（p-1）（q-1）；

（3）隨機選取一個正整數(shù)e，使其滿足1

（4）計算解密密鑰d，使其滿足0

1.1.2 消息加密

消息發(fā)送方使用如下方式對明文M進(jìn)行加密：

C=Memod（n）

1.1.3 消息解密

消息接收方使用如下方式對密文C進(jìn)行解密：

C=Cdmod（n）

其中：M代表需要加密的明文，C代表加密后的密文，e代表加密時的密鑰，d代表解密時的密鑰，n代表模數(shù)。n和e公開，p，q，d和φ（n）需保密。

1.2 基于RSA的數(shù)字簽名

基于RSA算法的數(shù)字簽名[11]中，通信雙方各擁有2個密鑰。秘密密鑰SK-A，SK-B及公開密鑰PK-A，PK-B，分別對應(yīng)加密算法EPK-A，EPK-B和解密算法DSK-A，DSK-B。若用戶A傳送需簽名的消息m給用戶B，則A可用自己的解密算法DSK-A對消息m進(jìn)行加密，從而得到DSK-A（m），再用B的加密算法EPK-B對DSK-A（m）進(jìn)行加密：

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

當(dāng)用戶B獲得密文C后，首先用自己的解密算法DSK-B對C進(jìn)行解密：

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

接著再用A的加密算法EPK-A對DSK-A（m）進(jìn)行解密：

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

若m'=m，則可確定消息來自于A，否則拒絕對方的簽名。若A否認(rèn)給B發(fā)送過消息m，則用戶B只需向公證方提供A的簽名DSK-A（m）和公鑰e，公證方通過算法便能輕易證實簽名的確屬于A；同樣，若用戶B偽造了消息m'，因其不知道A的私鑰，于是便無法提供正確的簽名，因此消息通信雙方都可有效防止一方抵賴的情況發(fā)生，從而保證數(shù)字簽名的可靠性。

2 改進(jìn)RSA算法數(shù)字簽名

2.1 基于消息分組和密鑰指數(shù)的RSA算法

RSA算法中使用單整數(shù)密鑰，為了提高安全性，文中基于兩個大素數(shù)使用多個整數(shù)（多重密鑰）來提高密鑰破譯的難度。由于利用不同的公鑰指數(shù)對不同的分組明文進(jìn)行了加密，故改進(jìn)算法不會遭受針對同一明文不同公鑰指數(shù)的公共模數(shù)攻擊。

2.1.1 密鑰生成

解得：M=（Mpqp-1+Mqpq-1）mod n，即為原明文M。由上述過程可見，明文分組M1，M2，…，Mk皆可由算法計算得到，該定理的優(yōu)勢在于能把大整數(shù)對n的模冪運算轉(zhuǎn)換成相對較小的數(shù)p，q的模冪運算，最后合并運算結(jié)果。在RSA算法中應(yīng)用CRT能夠降低簽名過程的運算量和復(fù)雜度。

3 實驗結(jié)果及分析

實驗選用i5-2450M CPU，是含6 GB內(nèi)存和Windows 64位系統(tǒng)的平臺，實驗工具采用Microsoft Visual Studio 2017。實驗對50～200不同長度的字符進(jìn)行測試，改進(jìn)后的算法加解密效果如圖1所示。加密后的密文無法被識別，證實了改進(jìn)RSA算法能夠取得良好的加解密效果。數(shù)字簽名證書的實現(xiàn)結(jié)果如圖2所示。

為了對傳統(tǒng)RSA算法，ElGamal算法，MD5算法以及改進(jìn)后的算法性能進(jìn)行對比，使用這4種算法分別對1 MB，5 MB，10 MB，20 MB的字符串?dāng)?shù)據(jù)量進(jìn)行簽名，實驗結(jié)果見表1所列。從表1中4種算法平均所耗時間的對比可知：改進(jìn)后的RSA算法的平均簽名速度分別是傳統(tǒng)算法的1.60倍，ElGamal算法的2.58倍，MD5算法的1.49倍。而且隨著數(shù)據(jù)量的增大，改進(jìn)算法對簽名效率的優(yōu)化并未明顯降低。為了更加直觀地觀察4種算法的簽名效率，我們將算法平均所耗時間放在圖3中進(jìn)行對比。

4 結(jié) 語

數(shù)字簽名作為信息安全領(lǐng)域的一項重要技術(shù)，其算法可靠性應(yīng)放在首位。本文在介紹與分析傳統(tǒng)RSA算法的基礎(chǔ)上，提出了一種改進(jìn)的RSA算法，通過使用多重密鑰增強簽名過程的安全性，并通過實驗驗證了提出的RSA算法的有效性。對于影響RSA算法運算效率的大量模冪運算，文中通過在改進(jìn)算法中融入中國剩余定理，在確保算法安全性的基礎(chǔ)上把模冪運算降到最低來優(yōu)化運算效率。最后，將改進(jìn)RSA算法和其他三種簽名算法在不同數(shù)據(jù)量的情況下進(jìn)行對比實驗，記錄算法平均所耗時間。實驗結(jié)果顯示，改進(jìn)RSA算法的簽名時間明顯降低，算法簽名的效率得到了提升。改進(jìn)后的算法的不足之處是無法保證在數(shù)據(jù)量較大時簽名效率的顯著提升。因此，如何探索既保證簽名系統(tǒng)的安全性，又提升大數(shù)據(jù)量下的簽名效率的數(shù)字簽名方案成為下一步研究的重點。

參考文獻(xiàn)

[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密碼算法的研究與快速實現(xiàn)[D].南昌：南昌大學(xué)，2008： 38-39.

[9]何俊杰，焦淑云，祁傳達(dá).一個基于身份的簽密方案的分析與改進(jìn)[J].計算機應(yīng)用研究， 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密碼學(xué)原理與實踐（第3版）[M].北京： 電子工業(yè)出版社，2016： 222-234.