改進的RSA算法在數(shù)字簽名中的應用

肖振久，胡馳，陳虹

1.遼寧工程技術(shù)大學軟件學院，遼寧葫蘆島 125105

2.中國傳媒大學計算機學院，北京 100024

改進的RSA算法在數(shù)字簽名中的應用

肖振久1，2，胡馳1，陳虹1

1.遼寧工程技術(shù)大學軟件學院，遼寧葫蘆島 125105

2.中國傳媒大學計算機學院，北京 100024

針對傳統(tǒng)RSA密碼算法運算效率較低的問題，在標準RSA密碼算法的自身結(jié)構(gòu)和具體運算操作兩方面做出了相應的改進，提出了一種新的RSA密碼優(yōu)化算法，并將該算法運用到數(shù)字簽名技術(shù)中。然后通過仿真實驗，將其與傳統(tǒng)RSA算法以及基于乘同余對稱特性的SMM算法和指數(shù)2k進制化相結(jié)合的組合優(yōu)化算法相比較，實驗結(jié)果表明新的RSA密碼優(yōu)化算法在提升運算速度方面達到了較高的水平。

RSA算法；數(shù)字簽名；乘同余對稱；模重復平方

1 引言

隨著網(wǎng)絡(luò)和通信技術(shù)的發(fā)展，在給人們帶來益處的同時，也給人們帶來了安全隱患。由于傳輸過程中存在數(shù)據(jù)被通信雙方之外的第三方偽造或篡改的可能，通信雙方無法驗證數(shù)據(jù)來源，就很有可能出現(xiàn)一方抵賴的情況，此時就要求保證傳輸信息的不可否認性。數(shù)字簽名就是通信雙方在網(wǎng)上交換信息時，基于公鑰密碼體制來防止偽造和欺騙的一種身份認證技術(shù)，通信雙方不需要實現(xiàn)交換密鑰，保密性好。數(shù)字簽名的算法很多，較為常見的有RSA簽名[1]、DSA簽名和橢圓曲線簽名，其中RSA簽名安全性高、易于實現(xiàn)，既可以用來加密數(shù)據(jù)又可以用于身份認證，因此得到了最為廣泛的應用。但是它涉及到大數(shù)運算，其運算速度一直是RSA的瓶頸，目前雖然提出了許多的改進算法[2]，其中比較有代表性的就是將SMM算法和指數(shù)2k進制化算法相結(jié)合的組合優(yōu)化算法，此算法相對于傳統(tǒng)算法在運算速度上的確有一定提高，但效果仍不明顯，本文提出一種在算法自身結(jié)構(gòu)和運算操作上都加以改進的優(yōu)化算法，實驗證明，此算法相對于傳統(tǒng)算法在運算效率上有較大幅度提高。

2 相關(guān)研究工作

2.1 數(shù)字簽名技術(shù)原理

數(shù)字簽名[3]過程如圖1所示，分為簽名和驗證兩個環(huán)節(jié)。假設(shè)用戶A要發(fā)送消息X給用戶B，首先A用自己的私鑰d對X進行簽名得Y=Sigd(X)，然后將X與Y一同發(fā)送給B，B接收以后需要用A的公鑰e驗證簽名，計算X'=Vere(Y)，若X'=X，則說明消息確實來自于A，否則拒絕該簽名。采用以上通信協(xié)議，若A否認曾發(fā)送消息X給B，用戶B只需出示A的簽名Y和公鑰e給公證方，公證方采用正確的算法很容易證實簽名確實屬于A；若用戶B偽造了消息X'，由于他不知道A的私鑰，也就無法出示正確的簽名，這樣一來，通信雙方都必須真實地反映通信情況，有效防止了一方抵賴的情形發(fā)生。

圖1 數(shù)字簽名過程

2.2 經(jīng)典RSA數(shù)字簽名方案

RSA數(shù)字簽名方案[4]使用了RSA公開密鑰密碼算法進行數(shù)字簽名，基本算法表述如下：

（1）選擇大素數(shù)p、q，生成n、d、fn。其中，n=p×q、fn=(p-1)×(q-1)，選一整數(shù)e，滿足1＜e＜fn，計算d，滿足d×e≡1(mod fn)。公開模數(shù)n和公鑰e，對于p、q、私鑰d和fn嚴格保密。

（2）簽名過程

假設(shè)用戶A對數(shù)據(jù)M∈Zn進行簽名，則計算：

并將S作為用戶A對數(shù)據(jù)M的數(shù)字簽名附在數(shù)據(jù)M后。

（3）驗證算法

假設(shè)用戶B需要驗證用戶A對M的數(shù)字簽名S，則用戶B計算：

并判定M*是否等于M，若M*=M，則說明簽名S確實是用戶A所產(chǎn)生的，否則，簽名S可能是偽造的。

2.3 SMM算法和指數(shù)2k次方化算法

由于RSA算法[5]在實際操作過程中存在運算效率低的瓶頸，許多的學者提出了不同的改進算法，這里重點介紹基于乘同余對稱特性的SMM算法和指數(shù)2k次方化算法相結(jié)合的優(yōu)化算法。

SMM算法[6]是利用乘同余對稱特性來減少RSA算法中乘法和求模運算量的一種快速算法。傳統(tǒng)的RSA算法是將指數(shù)x表示成t位二進制形式，并將冪剩余變成一系列的乘同余迭代，以a=gx(mod n)為例，每一步迭代必有運算a=a2(mod n)和可能有運算a=(a×g)(mod n)，此算法是在每步迭代計算中對乘數(shù)和被乘數(shù)進行進行有條件的代換：如果用ai-1表示第i-1步的迭代結(jié)果，則在進行第i步迭代時，若g≤(n-1)/2或ai-1≤(n-1)/2，則保持原數(shù)不變，否則用n-g或n-ai-1來代替g或 ai-1。

指數(shù)2k進制化算法[7]是通過縮短指數(shù)的長度來減少迭代次數(shù)的一種優(yōu)化算法。該算法分兩步進行：首先計算gXi(mod n)，其中Xi={0，1，2，…，2k-1}，需要計算從g0(mod n)到g2k-1mod n的每一個值，并將其存放在數(shù)組R中，然后進行冪剩余和同余計算：置變量c=1，對于i=m-1，…，1，0（m為指數(shù)2k進制化后的位數(shù)）重復執(zhí)行c=c2k(mod n)和(c×R[xi])(mod n)，最后得到c即為所求。

把以上兩種算法組合起來可得到一種新的組合優(yōu)化算法，它的基本思路是：根據(jù)2k進制化算法將指數(shù)2k進制化，減短指數(shù)長度，通過迭代法把乘方后求模的計算改為在求乘方的過程中求模的計算，減少中間結(jié)果的數(shù)值，如果中間結(jié)果值大于模數(shù)的一半，則根據(jù)SMM算法用模數(shù)減去該值得到的差來代替中間結(jié)果值，并繼續(xù)計算。通過實驗，此優(yōu)化算法在運算速度上有一定的提高，但效果仍不明顯。

3 RSA算法的改進與優(yōu)化

3.1 算法結(jié)構(gòu)改進

RSA算法有著大量制約著執(zhí)行效率的冪剩余運算，它的安全性又依賴著大整數(shù)n的因數(shù)分解，那么在不改變n的情況下把冪剩余運算減到最少就可以在保證安全性的情況下大幅度提高運算效率。于是，可以先把算法做一些改動：設(shè)明文分組m=(m1，m2，…，mk)，相應的密文分組為c=(c1，c2，…，ck)，按照RSA算法有：

（1）加密運算

（2）解密運算

可見，加密和解密都要執(zhí)行k次冪剩余運算。那么改進的思路是盡可能減少冪剩余運算的次數(shù)，最好的辦法就是把冪剩余運算改為加法剩余運算[8]，算法如下：

（1）加密運算

（2）解密運算

這樣改動之后，加密和解密都只需進行1次冪剩余運算和k-1次加法剩余運算。而一次加法剩余運算比一次冪剩余運算至少快mimin(e，d)倍，因此，改進之后的算法比傳統(tǒng)RSA算法運算速度至少快(k-1)mimin(e，d)倍。改進后的算法安全性取決于第一個明文分組m1的抗破譯性，只要第一個明文分組不被破譯，攻擊者便無法恢復出明文m。而第一個明文分組的安全性與傳統(tǒng)RSA算法一樣，都依賴于分解模數(shù)n的困難性，數(shù)學上，至今還沒有人提出有效的大數(shù)分解方法。因此，改進后的算法抗破譯能力并沒有降低。

3.2 運算操作改進

由于在實際操作中，為了保證安全，p和q都是1 024位二進制數(shù)，那么n就是2 048位的二進制數(shù)，換算成十進制600多位，它的冪剩余運算仍然值得去做優(yōu)化，這里，采用的是一種模重復平方算法的rho改進算法。

首先介紹一下模重復平方算法[9]，若要計算bn(mod m)，先將指數(shù)n寫成二進制：n=n0+n1×2+…+ nk-1×2k-1，則bn≡bn0(b2)n1…(b2k-2)nk-2(b2k-1)nk-1(mod m)，再按下列步驟計算：

（1）令a=1，b0=b。

（2）如果n0=1，則計算a0≡a×b0(mod m)否則取a0=a，再計算b1≡b02(mod m)。

（3）如果n1=1，則計算a1≡a0×b1(mod m)否則取a1=a0，再計算b2≡b12(mod m)。

……

（4）如果nk-2=1，則計算ak-2≡ak-3×bk-2(mod m)，否則取ak-2=ak-3，再計算bk-1≡bk-22(mod m)。

（5）如果nk-1=1，則計算ak-1≡ak-2×bk-1(mod m)，否則取ak-1=ak-2，最后，ak-1就是所得結(jié)果。

在以上算法中，由于b0=b，bi+1≡bi+2(mod m)(i=0，1，…)，但Zm是有限的，所以序列bi有一個周期。即存在j，w，使得bj=bj+w，那么，序列b0，b1，…，bj-1可以畫成一個rho(ρ)的“尾”，而回路bj，bj+1，…，bj+w-1，可以看成rho的“體”。bk叫做bk+1的前導，bk+1叫做bk的后繼。把滿足bj=bj+w最小的j叫做序列bi的索引，記為λ，把滿足bj=bj+w的最小w叫做序列bi的周期，記為μ，rho結(jié)構(gòu)如圖2[10]所示。

圖2 rho結(jié)構(gòu)圖

使用Floyd循環(huán)查找算法，從數(shù)對(b1，b2)開始，由前一數(shù)對(bi-1，b2i-2)來迭代計算(bi，b2i)直到某個w處，bw=b2w。用“/”表示除以，所得結(jié)果向下取整，第一次bw=b2w時，w=μ(1+λ/μ)。注意，這里λ＜w≤λ+μ。令θ=w，如果bw=bw+θ/2，則θ除以2，循環(huán)這一過程，最終的θ就是所求周期μ。令α=-1，β=w，如果bα+(β-α)/2= bα+(β-α)/2+μ，令β=α+(β-α)/2，否則，令α=α+(β-α)/2，循環(huán)這一過程，直到β-α=1，β就是所求的索引λ。

下面研究rho“體”上元素的性質(zhì)。

性質(zhì)1令M=bjbj+1bj+2…bj+w-1，則對任意整數(shù)n＞0，X有：XM≡XMn(mod m)。

在引出下面一條性質(zhì)之前，先說明“循環(huán)二進位”的概念。向量(t0，t1，…，tn)（其中ti∈N）的循環(huán)二進位是把t0，t1，…，tn看成二進制的低位到高位，從低位到高位滿2進1，到最高位時滿2再向最低位進1，循環(huán)這一過程直到t0，t1，…，tn只有0或1。例如向量（3，4，4，6）的循環(huán)二進位過程為：（3，4，4，6）→（1，4+1，4，6）→（1，1，6+ 2，4）→（1，1，0，4+4）→（1+4，1，0，0）→（1，1+2，0，0）→（1，1，1，0），則向量（1，1，1，0）即為向量（3，4，4，6）的循環(huán)二進位結(jié)果。

利用這兩條性質(zhì)，可得模重復平方算法的rho改進算法：

（1）令a=1，b0=b，并將n寫成二進制。

（2）計算并存儲bi，同時使用Floyd循環(huán)查找算法查找w。如果找到w則停止計算bi，并根據(jù)前面的算法計算出周期μ和索引λ；如果w不存在則令μ=0。

（3）如果μ為0，按照模重復平方算法的計算步驟從a0計算到ak-1，則bn≡ak-1(mod m)。

（4）如果μ為1，則M=bλ。由性質(zhì)1，如果bλ=0，則bn≡0(mod m)，否則，令nλ=1，按照模重復平方算法的計算步驟從a0計算到aλ，則bn≡aλ(mod m)。

（5）如果λ＞1，nλ，nλ+1，…，nλ+μ-1及其后面的ni每隔μ為一個單位（不足μ位后面補0）平移疊加到一組初始值為0的零時變量tλ，tλ+1，…，tλ+μ-1。由性質(zhì)2，對疊加后的tλ，tλ+1，…，tλ+μ-1進行循環(huán)二進位，并把tλ，tλ+1，…，tλ+μ-1的值分別賦值給nλ，nλ+1，…，nλ+μ-1。按照模重復平方算法的計算步驟從a0計算到aλ+μ-1，則bn≡aλ+μ-1(mod m)。

這種算法的實質(zhì)是一種指數(shù)約減算法，可以有效減少模重復平方算法中的模乘運算。由此可見，新的改進算法，先從結(jié)構(gòu)上把冪剩余運算的次數(shù)減到最低，再從算法操作上把一次冪剩余運算中的模乘減到最低，這樣大幅度地減少了計算機中最耗時的運算，它的運算速度將會有極大地提高。下面將通過實驗來對比三種算法在數(shù)字簽名中的耗時情況。

4 實驗結(jié)果及比較分析

本次實驗的硬件環(huán)境為：Pentium?4 CPU 3.06 GHz、512 MB內(nèi)存、80 GB硬盤；操作系統(tǒng)為：window s XP；開發(fā)工具：Visual C++6.0。本程序旨在比較相同環(huán)境下3種算法的性能，所以選取小素數(shù)進行多次測試。為了防止溢出，取p=157、q=223、n=35 011、fn=34 632，e取4 097，算得d=25 097。由于C++標準中時間只能精確到毫秒，如果數(shù)據(jù)量太小將無法產(chǎn)生實驗結(jié)果，因此采用一個隨機生成特定長度字符串的函數(shù)分別對1 MB、10 MB、30 MB、50 MB的數(shù)據(jù)量用經(jīng)典RSA數(shù)字簽名方案進行簽名，考慮到機器對算法效率的影響，對每種長度的數(shù)據(jù)量做5次簽名再取平均時間，實驗結(jié)果如表1所示。

表1 算法平均耗時s

從以上的實驗數(shù)據(jù)可以看出，組合優(yōu)化算法相對于傳統(tǒng)算法平均可以提速4%，而新優(yōu)化算法相對于傳統(tǒng)算法和組合優(yōu)化算法均可提速98%，這無疑是一個質(zhì)的飛躍，特別是當數(shù)據(jù)量越大，分組越多時，簽名速度提高得越明顯。

5 結(jié)束語

由于傳統(tǒng)的RSA加密算法存在大量的模冪運算，這一直是制約其運算速度的瓶頸。本文提出一種新的優(yōu)化算法，先從結(jié)構(gòu)上把模冪運算的次數(shù)降到最低，再從運算上把一次模冪運算中的模乘運算次數(shù)降低，最后通過理論分析和仿真實驗，得出新的優(yōu)化算法在保證安全性的前提下，其運算速度較傳統(tǒng)RSA算法有較大幅度提高這一結(jié)論。新算法的不足之處是其中的模重復平方算法的rho改進算法實現(xiàn)起來比較復雜，如何進一步簡化該算法，這是下一階段重點研究的方向。

[1]Fu C.An efficient implementation of RSA digital signature algorithm[C]//4th International Conference on Wireless Communications，Networking and Mobile Computing，2008：1-4.

[2]Liu Qing.Two efficient variants of the RSA cryptosystem[C]//2010 International Conference on Computer Design and Applications（ICCDA），2010：550-553.

[3]楊波.現(xiàn)代密碼學[M].北京：清華大學出版社，2007.

[4]胡方.改進的RSA算法及其在數(shù)字簽名中的應用[D].沈陽：東北大學，2008.

[5]Stalling W.密碼編碼學與網(wǎng)絡(luò)安全—原理與實踐[M].5版.北京：電子工業(yè)出版社，2011.

[6]周升力.RSA密碼算法的研究與快速實現(xiàn)[D].南昌：南昌大學，2008.

[7]賀令亞.RSA加密算法的研究與實現(xiàn)[D].長沙：中南大學，2009.

[8]蘇開元.DES_RSA混合加密以及傳輸實現(xiàn)[D].南京：南京郵電大學，2012.

[9]陳恭亮.信息安全數(shù)學基礎(chǔ)[M].北京：清華大學出版社，2004.

[10]石小平，姜浩.模重復平方算法的rho改進算法[J].計算機應用與軟件，2011，28（12）：48-50.

XIAO Zhenjiu1，2,HU Chi1,CHEN Hong1

1.College of Software, Liaoning Technical University, Huludao, Liaoning 125105, China
2.School of Computer, Communication University of China, Beijing 100024, China

In order to enhance the operation efficiency of RSA algorithm, a new improved algorithm is suggested in this paper which makes some improvements in structure and operation, and it is applied to digital signature. The experiment makes comparison between a combinatorial optimization algorithm which combines SMM with index of 2k hexadecimal algorithm and the new algorithm. It shows that the new algorithm reaches a high level in operation speed.

RSA algorithm;digital signature; Symmetry of Modulo Multiplication（SMM）; modular repeated squaring algorithm

XIAO Zhenjiu, HU Chi, CHEN Hong. Improved RSA algorithm and application in digital signature. Computer Engineering and Applications, 2014, 50（17）：106-109.

A

TP309.7

10.3778/j.issn.1002-8331.1210-0044

國家自然科學基金（No.61103199）；北京市自然科學基金（No.4112052）。

肖振久（1968—），男，副教授，研究領(lǐng)域為網(wǎng)絡(luò)與信息安全、數(shù)字版權(quán)管理；胡馳（1988—），男，碩士研究生，研究領(lǐng)域為數(shù)據(jù)加密、數(shù)字簽名；陳虹（1967—），女，副教授，研究領(lǐng)域為網(wǎng)絡(luò)安全。E-mail：hcshrhh001@163.com

2012-10-08

2012-12-27

1002-8331（2014）17-0106-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130118.1024.006.htm l