基于余數系統蒙哥馬利模乘器的RSA密碼算法

程雨芊，李智超

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

1 引言

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

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

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

2 余數系統蒙哥馬利模乘器設計

因為余數系統(residue number system，簡稱RNS)具有高速、并行的模計算性能，通過一組互質的余數系統基[4]，便能夠將其分解為一個較大規模的數，從而利用一組小數完成并行計算，所以有效結合余數系統與蒙哥馬利模乘，可以進一步使模乘運算效率得到提升，實現并行挖掘。

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

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

(1)

式中，xi=Xmodmi。

若想將余數系統的表示形式轉變成常用的二進制數值表示形式，則需要通過下列公式達成

(2)

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

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

(3)

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

圖1 余數系統蒙哥馬利模乘器框架示意圖

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

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

基于余數系統的蒙哥馬利模乘器儲存空間如下表所示。

表1 余數系統蒙哥馬利模乘器儲存空間統計表

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

(4)

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

3 RSA密碼算法設計

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

(5)

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

(6)

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

(7)

利用該近似方法對移位操作進行除法運算，使硬件架構復雜度下降，并采用修整因子對產生的誤差進行修正。

通過二進制位掃描模冪算法對數據進行預處理，將數表示形式轉變為蒙哥馬利域的表示形式，按照冪指數有效位從高到低的順序進行掃描，迭代次數為n，該值同時也表示冪指數的二進制比特位數。因為RSA協處理器的匯編代碼控制整個循環階段，因此能夠實現不同密鑰長度循環，因此該階段為密碼協處理器優化的重要階段之一。

根據余數系統蒙哥馬利模乘器中的數據依賴關系，構建RSA密碼算法執行的預估時間公式

(8)

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

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

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

(9)

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

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

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

(10)

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

<0.75n2M+3A+5T

(11)

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

對大數Y進行分解后，m是二進制位寬[9]，那么n是基二進制位寬，劃分數量為p+1，那么得到

(12)

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

(13)

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

(14)

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

(15)

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

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

xi=Xmodmi

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

(16)

4 仿真研究

4.1 仿真環境

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

4.2 性能分析

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

表2 素數獲取速率統計表(單位：s)

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

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

在上述實驗的基礎上，對比三種算法的執行時間，結果如圖2所示。

圖2 三種算法執行時間比較

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

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

圖3 密碼分布情況比較

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

5 結論

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

利用雙模式乘法器與硬件實現平臺，設計余數系統蒙哥馬利模乘器，采用余數系統通道組成各個模乘器，并微調至偽梅森素數，實現數據預計算。通過二進制位掃描模冪算法的預處理，將數表示形式轉變為蒙哥馬利域的表示形式，并按照冪指數有效位從高到低的順序進行掃描，根據余數系統蒙哥馬利模乘器中的數據依賴關系，構建RSA密碼算法執行的預估時間公式，應用特殊基簡化整個取模操作復雜度，采取相同轉換形式實現RSA密碼算法構建。實驗結果表明，該算法素數獲取速率與RSA加密速率高，執行時間短，加密效果更好。該算法為各領域的加密計算奠定了相關的運算基礎，具有廣闊的應用前景。