基于余數(shù)系統(tǒng)蒙哥馬利模乘器的RSA密碼算法

程雨芊，李智超

(山東大學(xué)(威海)，山東 威海 264209)

1 引言

隨著計算機網(wǎng)絡(luò)技術(shù)的高速發(fā)展，社會信息化程度日益提升，使得網(wǎng)絡(luò)信息的開放性與共享性更容易受到不安全因素的威脅，從而導(dǎo)致國家與社會領(lǐng)域中的動態(tài)信息和個人信息被泄露、竊取，所以信息安全問題引起了相關(guān)領(lǐng)域的廣泛關(guān)注。作為信息安全領(lǐng)域的有力工具，密碼技術(shù)不僅能夠確保信息的安全性與完整性，還可以實現(xiàn)身份驗證，提高系統(tǒng)安全性能[1]。密碼技術(shù)憑借其安全保密功能與普遍應(yīng)用性，具有更寬廣的應(yīng)用空間。二十世紀(jì)末期的三位著名密碼學(xué)者創(chuàng)建了一種基于大數(shù)因子分解困難性的公開密鑰密碼，即RSA密碼，作為當(dāng)今最具影響力的公鑰加密算法，RSA除了加密功能之外，還可以用來完成數(shù)字簽名，所以該算法已經(jīng)成為應(yīng)用最為廣泛的公開密鑰密碼之一。

文獻(xiàn)[2]為了更好地觀測到RSA的加密過程，將旁路電磁軌跡特征作為加密對象，對模板進(jìn)行創(chuàng)建，通過識別未知測試軌跡中的加密操作，再與密鑰相結(jié)合，得到密鑰序列，經(jīng)過分析移動設(shè)備PCM-9589F凌動主板的電磁旁路，構(gòu)建一種旁路信號采集平臺，利用提取到的RSA加密算法二進(jìn)制密鑰序列，完成密鑰破解與算法設(shè)計。文獻(xiàn)[3]針對海洋信息觀測與無線組網(wǎng)安全通信需求，設(shè)計一種融合了AES算法、RSA算法以及消息認(rèn)證碼的一次性雙向口令認(rèn)證協(xié)議，通過評估RSA算法，改進(jìn)算法流程，使資源消耗得到減少，從而提高通信安全。

由于上述文獻(xiàn)中的RSA算法無法通過大位寬乘法實現(xiàn)模乘運算，因此本文設(shè)計出一種基于余數(shù)系統(tǒng)蒙哥馬利模乘器的RSA密碼算法。采用一組兩兩互素的整數(shù)對余數(shù)系統(tǒng)進(jìn)行界定，并將余數(shù)系統(tǒng)的表示形式轉(zhuǎn)變成常用的二進(jìn)制數(shù)值表示形式，根據(jù)雙模式乘法器與硬件平臺創(chuàng)建模乘器，其輸入端的初始操作是由系統(tǒng)總線傳輸，在主路選器上連接所有模乘器的輸出端，確保下一周期的正常運轉(zhuǎn)，經(jīng)過嵌入ROM以便儲存預(yù)計算數(shù)據(jù)。利用引入的蒙哥馬利模乘來去除取模階段的除法運算形式，從而改寫余數(shù)系統(tǒng)轉(zhuǎn)二進(jìn)制數(shù)值的運算方式，以取模階段中的參數(shù)為基礎(chǔ)，運用一種近似方法的移位操作替換除法運算，并采用修整因子對產(chǎn)生的誤差進(jìn)行修正，使用barret約減算法完成模乘與模乘累加的取模操作，最后經(jīng)過將大數(shù)分解成小數(shù)部分，令RSA密碼算法得以實現(xiàn)。

2 余數(shù)系統(tǒng)蒙哥馬利模乘器設(shè)計

因為余數(shù)系統(tǒng)(residue number system，簡稱RNS)具有高速、并行的模計算性能，通過一組互質(zhì)的余數(shù)系統(tǒng)基[4]，便能夠?qū)⑵浞纸鉃橐粋€較大規(guī)模的數(shù)，從而利用一組小數(shù)完成并行計算，所以有效結(jié)合余數(shù)系統(tǒng)與蒙哥馬利模乘，可以進(jìn)一步使模乘運算效率得到提升，實現(xiàn)并行挖掘。

作為并行數(shù)值表征系統(tǒng)的余數(shù)系統(tǒng)，與一般系統(tǒng)相比，所有分量間均相對獨立、并行，且沒有進(jìn)位。余數(shù)系統(tǒng)的界定方式為一組兩兩互素的整數(shù)，而余數(shù)系統(tǒng)的基則是該組互素整數(shù)集合[5]。假設(shè)B=(m1，m2，…，mk)為一個余數(shù)系統(tǒng)的基，故采用下列表達(dá)式來描述任意整數(shù)X

[X]RNS=(x1，x2，…xk)

(1)

式中，xi=Xmodmi。

若想將余數(shù)系統(tǒng)的表示形式轉(zhuǎn)變成常用的二進(jìn)制數(shù)值表示形式，則需要通過下列公式達(dá)成

(2)

設(shè)定余數(shù)系統(tǒng)的a、b表示是a=(a1，a2，…，ak)與b=(b1，b2，…，bk)，則利用下列表達(dá)式對其加、減以及乘運算法則進(jìn)行描述

a?b=(|a1?b1|m1，|a2?b2|m2，…，|ak?bk|mk)

(3)

式中，?=(+，-，×)。

圖1 余數(shù)系統(tǒng)蒙哥馬利模乘器框架示意圖

通過四狀態(tài)下有限狀態(tài)機的調(diào)度控制器對模乘器進(jìn)行控制[6]，系統(tǒng)總線將原始操作數(shù)據(jù)輸送至模乘器的輸入端，并在主路選器上連接全部模乘器的輸出端，為總線入口挑選合適數(shù)據(jù)，確保下一周期硬件能夠正常運轉(zhuǎn)，而各模乘器間的數(shù)據(jù)通路則是為了基擴(kuò)展的中間數(shù)據(jù)共享。

模乘器的核心模塊是算術(shù)邏輯單元[7]，用于完成乘法與乘累加運算，該模乘器的輸入源分為三種：系統(tǒng)總線輸入、存儲于片內(nèi)ROM的預(yù)計算數(shù)據(jù)以及算術(shù)邏輯單元的輸出端數(shù)據(jù)。

基于余數(shù)系統(tǒng)的蒙哥馬利模乘器儲存空間如下表所示。

表1 余數(shù)系統(tǒng)蒙哥馬利模乘器儲存空間統(tǒng)計表

算術(shù)邏輯單元的構(gòu)成部分為異或門與選通器，部分積累加器為其主要部分，用于計算多項式乘法，基本原理如下式所示

(4)

積累加器的加法器主要用于實現(xiàn)累加運算，維持其正常工作的前提條件是乘累加模式為啟動狀態(tài)。

3 RSA密碼算法設(shè)計

由于余數(shù)系統(tǒng)中的運算式(3)無法完成并行化的除法運算[8]，故引入蒙哥馬利模乘來去除取模階段的除法運算形式，進(jìn)而對算法流程進(jìn)行調(diào)整。

(5)

把M取模時所需的參數(shù)β引入上式，能夠得到下列表達(dá)式

(6)

為了使硬件部分設(shè)計順利完成，采取一種近似方法，將εi近似為高g位，mi近似為2r，從而推導(dǎo)出下列表達(dá)式

(7)

利用該近似方法對移位操作進(jìn)行除法運算，使硬件架構(gòu)復(fù)雜度下降，并采用修整因子對產(chǎn)生的誤差進(jìn)行修正。

通過二進(jìn)制位掃描模冪算法對數(shù)據(jù)進(jìn)行預(yù)處理，將數(shù)表示形式轉(zhuǎn)變?yōu)槊筛珩R利域的表示形式，按照冪指數(shù)有效位從高到低的順序進(jìn)行掃描，迭代次數(shù)為n，該值同時也表示冪指數(shù)的二進(jìn)制比特位數(shù)。因為RSA協(xié)處理器的匯編代碼控制整個循環(huán)階段，因此能夠?qū)崿F(xiàn)不同密鑰長度循環(huán)，因此該階段為密碼協(xié)處理器優(yōu)化的重要階段之一。

根據(jù)余數(shù)系統(tǒng)蒙哥馬利模乘器中的數(shù)據(jù)依賴關(guān)系，構(gòu)建RSA密碼算法執(zhí)行的預(yù)估時間公式

(8)

采用上列公式設(shè)定各單元數(shù)量，進(jìn)而分析算法性能與芯片面積的關(guān)系，令不同的使用需求得到滿足。

作為RSA密碼算法的關(guān)鍵運算形式，模乘與模乘累加的取模操作可以通過barret約減算法的加法、乘法與移位實現(xiàn)。假設(shè)操作數(shù)的長度為z，下列公式即為barret約減算法操作復(fù)雜度的表示形式：

COMPLEXITY(barret)=2z2M+S+eA+kS+4T

(9)

其中，e取值為0或1，k≥0。兩個n比特的數(shù)相乘為n2M，減法、加法以及移位操作分別是S、A和T。由于乘法的次數(shù)與乘數(shù)位數(shù)決定了其復(fù)雜程度，因此，硬件實現(xiàn)復(fù)雜度的最具代表項為2n2M。

設(shè)定基為一種特殊形式2n-ci，其中ci為一個較小的數(shù)，n則表示基的二進(jìn)制比特位數(shù)，該形式的基不僅能夠降低模乘復(fù)雜度，而且可以實現(xiàn)基的高效選取，究其原因是該形式基的模加運算只需執(zhí)行兩次加法運算即可完成，采取移位操作就可以實現(xiàn)其除法與取模操作。因此，采用下列公式對該形式基的整個取模操作復(fù)雜度進(jìn)行描述：

COMPLEXITY(base)=ntM+ttM+3A+5T

(10)

COMPLEXITY(base)=(δ2+δ)n2M+3A+5T

<0.75n2M+3A+5T

(11)

通過上式可知，該形式基的取模操作復(fù)雜度遠(yuǎn)比一般形式的小，從而令RSA密碼算法的資源開銷大幅度下降。

對大數(shù)Y進(jìn)行分解后，m是二進(jìn)制位寬[9]，那么n是基二進(jìn)制位寬，劃分?jǐn)?shù)量為p+1，那么得到

(12)

若大數(shù)Y被分解為P個部分，則表示形式如下所示

(13)

基于特殊形式的基，對式(2)進(jìn)行改寫，得到

(14)

如果εi與mi符合下列各條件式，則β為σk或者σk-1

(15)

按照位數(shù)從高到低的次序，采取相同轉(zhuǎn)換方法，將Mi劃分為p-1個部分，分解M為p個部分，且各部分均與硬件資源數(shù)據(jù)位寬相一致。

結(jié)合式(1)，得出下列RSA密碼算法的轉(zhuǎn)換公式

xi=Xmodmi

=(Xp2pn+Xp-12(p-1)n+…+X12n+X0)modmi

(16)

4 仿真研究

4.1 仿真環(huán)境

為了驗證本文提出的基于余數(shù)系統(tǒng)蒙哥馬利模乘器的RSA密碼算法的有效性，進(jìn)行仿真。仿真環(huán)境的計算機配置是英特爾賽揚2.4G處理器，運行內(nèi)存為512M，操作系統(tǒng)為Windows 10，程序編寫軟件為VC++6.0版本。

4.2 性能分析

為了驗證研究算法的可行性，對文獻(xiàn)[2]算法、文獻(xiàn)[3]算法以及研究算法分別進(jìn)行仿真，所得的素數(shù)獲取速率與RSA加密速率實驗數(shù)據(jù)分別如下表所示。

表2 素數(shù)獲取速率統(tǒng)計表(單位：s)

表3 RSA加密速率統(tǒng)計表(單位：ms)

通過上表中的各項數(shù)據(jù)可以看出，各算法的素數(shù)獲取速度與RSA加密速度，均隨著進(jìn)制長度的增加而變慢。對于素數(shù)獲取速率，相對于文獻(xiàn)[2]算法，研究算法的速率分別提升了80%、44%、29.06%、36.48%，與文獻(xiàn)[3]算法進(jìn)行對比后，研究算法的素數(shù)獲取速率則分別增加了41.67%、77.93%、56.54%、70.62%；對RSA的加密速率來說，相比文獻(xiàn)[2]算法，研究算法的RSA加密速率分別上漲了19.01%、26.28%、20.01%、31.98%、27.52%、35.75%、30.68%、27.16%，而相對文獻(xiàn)[3]算法，研究算法的加密速率上升幅度分別是9.93%、43.13%、13.76%、14.4%、12.88%、16.55%、15.91%、11.85%。通過以上兩個結(jié)果驗證了本文提出的基于余數(shù)系統(tǒng)蒙哥馬利模乘器的RSA密碼算法的有效性與可靠性。

在上述實驗的基礎(chǔ)上，對比三種算法的執(zhí)行時間，結(jié)果如圖2所示。

圖2 三種算法執(zhí)行時間比較

分析圖2可知，文獻(xiàn)[2]算法的執(zhí)行時間在0-4.7s之間變化，文獻(xiàn)[3]算法的執(zhí)行時間在0-2.8s之間變化，而研究算法的執(zhí)行時間始終低于1.0s，說明該算法的執(zhí)行時間短、效率高。

比較三種算法的密碼分布情況，結(jié)果如圖3所示。

圖3 密碼分布情況比較

綜合比較三種算法的密碼分布情況可知，與其它兩種算法相比，研究算法的密碼分布更為均勻，說明該算法的加密性能更優(yōu)。

5 結(jié)論

隨著信息技術(shù)的快速發(fā)展，信息安全問題日益突出，為了保證信息能夠安全傳輸，因此RSA公鑰加密算法被廣泛應(yīng)用于各個領(lǐng)域中。由于當(dāng)前算法不符合大位寬的處理需求，執(zhí)行時間長，所以本文設(shè)計了一種基于余數(shù)系統(tǒng)蒙哥馬利模乘器的RSA密碼算法。根據(jù)余數(shù)系統(tǒng)獨特的無權(quán)屬性，用一般二進(jìn)制數(shù)值表示形式代替余數(shù)系統(tǒng)的表示形式。

利用雙模式乘法器與硬件實現(xiàn)平臺，設(shè)計余數(shù)系統(tǒng)蒙哥馬利模乘器，采用余數(shù)系統(tǒng)通道組成各個模乘器，并微調(diào)至偽梅森素數(shù)，實現(xiàn)數(shù)據(jù)預(yù)計算。通過二進(jìn)制位掃描模冪算法的預(yù)處理，將數(shù)表示形式轉(zhuǎn)變?yōu)槊筛珩R利域的表示形式，并按照冪指數(shù)有效位從高到低的順序進(jìn)行掃描，根據(jù)余數(shù)系統(tǒng)蒙哥馬利模乘器中的數(shù)據(jù)依賴關(guān)系，構(gòu)建RSA密碼算法執(zhí)行的預(yù)估時間公式，應(yīng)用特殊基簡化整個取模操作復(fù)雜度，采取相同轉(zhuǎn)換形式實現(xiàn)RSA密碼算法構(gòu)建。實驗結(jié)果表明，該算法素數(shù)獲取速率與RSA加密速率高，執(zhí)行時間短，加密效果更好。該算法為各領(lǐng)域的加密計算奠定了相關(guān)的運算基礎(chǔ)，具有廣闊的應(yīng)用前景。