改進(jìn)的RSA算法在數(shù)字簽名中的應(yīng)用

肖振久，胡馳，陳虹

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

2.中國(guó)傳媒大學(xué)計(jì)算機(jī)學(xué)院，北京 100024

改進(jìn)的RSA算法在數(shù)字簽名中的應(yīng)用

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

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

2.中國(guó)傳媒大學(xué)計(jì)算機(jī)學(xué)院，北京 100024

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

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

1 引言

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

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

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

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

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

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

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

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

（2）簽名過(guò)程

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

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

（3）驗(yàn)證算法

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

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

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

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

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

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

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

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

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

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

（1）加密運(yùn)算

（2）解密運(yùn)算

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

（1）加密運(yùn)算

（2）解密運(yùn)算

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

3.2 運(yùn)算操作改進(jìn)

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

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

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

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

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

……

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

（5）如果nk-1=1，則計(jì)算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有一個(gè)周期。即存在j，w，使得bj=bj+w，那么，序列b0，b1，…，bj-1可以畫成一個(gè)rho(ρ)的“尾”，而回路bj，bj+1，…，bj+w-1，可以看成rho的“體”。bk叫做bk+1的前導(dǎo)，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ù)對(duì)(b1，b2)開(kāi)始，由前一數(shù)對(duì)(bi-1，b2i-2)來(lái)迭代計(jì)算(bi，b2i)直到某個(gè)w處，bw=b2w。用“/”表示除以，所得結(jié)果向下取整，第一次bw=b2w時(shí)，w=μ(1+λ/μ)。注意，這里λ＜w≤λ+μ。令θ=w，如果bw=bw+θ/2，則θ除以2，循環(huán)這一過(guò)程，最終的θ就是所求周期μ。令α=-1，β=w，如果bα+(β-α)/2= bα+(β-α)/2+μ，令β=α+(β-α)/2，否則，令α=α+(β-α)/2，循環(huán)這一過(guò)程，直到β-α=1，β就是所求的索引λ。

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

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

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

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

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

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

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

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

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

這種算法的實(shí)質(zhì)是一種指數(shù)約減算法，可以有效減少模重復(fù)平方算法中的模乘運(yùn)算。由此可見(jiàn)，新的改進(jìn)算法，先從結(jié)構(gòu)上把冪剩余運(yùn)算的次數(shù)減到最低，再?gòu)乃惴ú僮魃习岩淮蝺缡Ｓ噙\(yùn)算中的模乘減到最低，這樣大幅度地減少了計(jì)算機(jī)中最耗時(shí)的運(yùn)算，它的運(yùn)算速度將會(huì)有極大地提高。下面將通過(guò)實(shí)驗(yàn)來(lái)對(duì)比三種算法在數(shù)字簽名中的耗時(shí)情況。

4 實(shí)驗(yàn)結(jié)果及比較分析

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

表1 算法平均耗時(shí)s

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

5 結(jié)束語(yǔ)

由于傳統(tǒng)的RSA加密算法存在大量的模冪運(yùn)算，這一直是制約其運(yùn)算速度的瓶頸。本文提出一種新的優(yōu)化算法，先從結(jié)構(gòu)上把模冪運(yùn)算的次數(shù)降到最低，再?gòu)倪\(yùn)算上把一次模冪運(yùn)算中的模乘運(yùn)算次數(shù)降低，最后通過(guò)理論分析和仿真實(shí)驗(yàn)，得出新的優(yōu)化算法在保證安全性的前提下，其運(yùn)算速度較傳統(tǒng)RSA算法有較大幅度提高這一結(jié)論。新算法的不足之處是其中的模重復(fù)平方算法的rho改進(jìn)算法實(shí)現(xiàn)起來(lái)比較復(fù)雜，如何進(jìn)一步簡(jiǎn)化該算法，這是下一階段重點(diǎ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)代密碼學(xué)[M].北京：清華大學(xué)出版社，2007.

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

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

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

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

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

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

[10]石小平，姜浩.模重復(fù)平方算法的rho改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用與軟件，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

國(guó)家自然科學(xué)基金（No.61103199）；北京市自然科學(xué)基金（No.4112052）。

肖振久（1968—），男，副教授，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)與信息安全、數(shù)字版權(quán)管理；胡馳（1988—），男，碩士研究生，研究領(lǐng)域?yàn)閿?shù)據(jù)加密、數(shù)字簽名；陳虹（1967—），女，副教授，研究領(lǐng)域?yàn)榫W(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