大數模乘硬件模塊的研究與實現*

段曉毅 黃 燁 曹佳樂

北京電子科技學院,北京市 100070

1 簡介

RSA、ECC(Elliptic Curve Cryptography)算法是常用的公鑰算法,而素數域上的模乘運算[1]是公鑰加密算法中的基礎算法。 但在密碼體系的運算中,其運算操作數一般是任意大整數,即位數為256 bit 或以上的數據結構,算法復雜度較大,已經成為影響當前公鑰加密體系發展的重要問題。 素數域中的模乘算法是最費時的計算,所以為了提升公鑰密碼系統的計算效率,選擇計算速度快、資源耗費少的高效硬件模塊非常重要[2]。

當前國內外對于大數模乘問題的研究方案大致可分為兩種:第一種即利用各類基本算法及其改進算法,通過算法結構構建對應的硬件電路,實現大數模乘功能,例如加法型算法[3]、估商型算法[4]、蒙哥馬利算法,其中又以蒙哥馬利型算法應用范圍最廣,相繼提出多種改進方式,實現效果良好。 另一種則從硬件結構出發,對于硬件架構進行重構,高效利用計算資源,提升模乘計算速度[5],以FPGA 細粒度映射技術為例[6],此在各類硬件載體上都有相關運用,例如通過加密智能卡實現[7]。

大數模乘在基礎研究以及密碼學等領域都有大量應用,特別是在公鑰密碼算法方面[8]。模乘通常情況下表示為:C =(A × B)mod N,其中A、B、N 都為k bit 二進制的大整數。 模乘運算由基本的乘法和計算余數的模運算簡化組成,目前主要的運算形式有先計算乘法后再進行模簡化運算,以及一邊進行乘法同時進行模簡化運算這兩大類基本實現方式[9]。

若以更細化、更精準的處理方式來劃分大數模乘的處理流程的話,大數模乘算法又可分為加法型算法、估商型算法、蒙哥馬利型算法這三大類。 蒙哥馬利型模乘算法是目前在硬件結構上用于快速實現模乘計算最適合的算法。 本文改進了蒙哥馬利算法并將其實現。

2 改進的蒙哥馬利模乘算法

蒙哥馬利模乘算法是蒙哥馬利在1986 年所提出的一種算法[10],主要是為了解決大整數模冪運算問題。 由于模冪與模乘運算可以互相轉換,蒙哥馬利模乘算法把部分積對任意的n 取模運算轉化為對與n 互素的數基R 進行取模,通常都選R=2k,k 是非負整數。 由于R 比n 小得多,對數基R 的取模運算要比對n 的取模運算簡單得多[11],所以蒙哥馬利模乘算法在RSA 密碼算法的研究中得到廣泛的應用。

定義模乘算法為MM(x,y),如果模數m 是素數,且滿足m>2,則存在一個元素2-1∈Fm,使得2 × 2-1mod m =1。 假設m 是一個k bit 位的素數,那么可以選擇一個數R,使得R = 2k且滿足x,y∈Fm其中x可表示為:

將式(2.1) 代入模乘計算表達式,得到下式:

由于基本的蒙哥馬利模乘算法中不但包含基本的乘法、加法運算,還包含了模逆運算,并不利于計算機的硬件實現。 改進的蒙哥馬利模乘算法通過對基本算式的重新表達,配合數論里的基本結論,巧妙避免了復雜運算,易于模乘計算[12]。

由數論知識可知用一個自然數去乘2-1有以下結論:

將式(2.2)中單次運算括號中的部分套用式(2.3),即可得到改進后的蒙哥馬利模乘算法[13]MM(x,y),其算法流程如下所示:

改進后的蒙哥馬利模乘算法結構簡單,易于硬件描述實現,本文就以改進的蒙哥馬利模乘算法MM(x,y) 為設計基礎,實現蒙哥馬利型大數模乘模塊功能。

3 蒙哥馬利型大數模乘模塊的總體設計

3.1 蒙哥馬利型大數模乘模塊外部總視圖

本方案中的大數模乘模塊的外部總視圖如圖3-1 所示:

圖3-1 蒙哥馬利型大數模乘模塊外部總視圖

輸入:x、y、m

輸出:C

x:參與模乘運算的乘數1,輸入范圍從1bit-4096bit。

y:參與模乘運算的乘數2,輸入范圍從1bit-4096bit。

m:參與模乘運算的模數,輸入范圍從1bit-4096bit。

C:模乘的輸出結果, 輸出范圍從1bit-4096bit。

對于本文系統的輸入數據x、y、m 來說,最大可以滿足4096 bit,能滿足現在對公鑰算法強度的要求。

當要進行計算時,輸入x、y、m,即可通過此模塊計算得到結果C,即:C=x*ymodm,此為所要研究的大數模乘。

3.2 蒙哥馬利型大數模乘模塊內部結構設計

蒙哥馬利型大數模乘模塊的內部結構設計如圖3-2 所示:

圖3-2 蒙哥馬利型大數模乘模塊內部結構設計

本設計的運算處理步驟是通過四次調用改進的蒙哥馬利模乘算法,并且每次調用中輸入不同的數據,最終得到沒有R-1影響的大數模乘。

在第一、二次調用中,將R2作為第二個乘數來進行代入計算(在相同模數m 的情況下,R2的數值不變,可以重復使用),這一步得到X′=X*Rmodm與Y′=Y*Rmodm;第三次調用中將得到的X′、Y′作為操作數再進行一次蒙哥馬利模乘計算,得到S′=X*Y*Rmodm; 第四次調用中,1 作為另一個操作數被代入計算,R 與R-1即可相互抵消,最終得到大數模乘運算結果C=x*ymodm。

3.3 蒙哥馬利模乘單元模塊設計

如上文介紹,蒙哥馬利型大數模乘模塊實際上就是在不斷重復計算蒙哥馬利模乘算法的過程[14],所以設計大數模乘的關鍵就在于對于蒙哥馬利模乘單元模塊進行設計實現,也就是說將章節2 中提到的改進后的蒙哥馬利模乘算法MM(x,y) 設計為一個基本算法單元,目的是方便后續不斷調用,最終整體實現圖3-2 所示的蒙哥馬利型大數模乘模塊。

3.3.1 蒙哥馬利模乘單元介紹

如章節2 所介紹的改進的蒙哥馬利模乘算法,計算兩個k bit 位數的蒙哥馬利模乘至少需要到k 個處理時鐘,通過觀察章節2 中MM(x,y) 算法流程里的步驟2,發現該算法的基本運算過程是從低位到高位,逐bit 地處理數據,即改進算法采取的是全串行處理流程,一個時鐘僅進行1 bit 的數據處理。

當處理的數據位數較小時,該算法是比較有效的,所耗時鐘周期也較少,然而對于現在的密碼算法來說,處理的都是位數較長的數據,例如RSA 應用中就需要1024 bit 以上的大整數相乘,因此該算法在處理位數較長的兩個數的模乘計算時,計算速度會較慢。 本文通過設計使得該算法能夠在一個時鐘周期內完成多位數的數據處理,即在同一個時鐘內完成多次的乘法、加法以及移位處理,能夠有效地提高算法的效率。

3.3.2 蒙哥馬利模乘單元模塊設計

本設計中,難點集中在蒙哥馬利模乘運算單元模塊中,完成對此部分的模塊化工作后,即完成了上文介紹的改進蒙哥馬利模乘算法中的a=p+x(i)*y部分,在模乘實現的主程序中通過不斷循環調用此單元模塊,實現對數據的逐位計算處理,提升運算處理效率。 圖3-3 展示了蒙哥馬利模乘算法單元的模塊化程序設計框圖。

圖3-3 mm_r2mm 模塊程序流程圖

本文將此程序記為“mm_r2mm”。 在模塊中,首先對于數據進行初始化處理,將結果S、位標志符i 賦0;再判斷乘數對應的位是否為1,為1 則將輸入的乘數y 與S 相加處理,結果賦值給新S,否則S 值保持不變;再判斷S 的最低位是否為0,也就是對S 值進行了一個奇偶判斷,若為0,則通過將S 值右移一位來實現除2 計算,不為0 則將S 值與模數m 值相加,所得值賦給新S 后再進行右移一位操作,完成單次的數據處理,最后將結果S 的值返回,此即完成整個數據處理流程。

單個模塊單元在一個時鐘周期內可以完成對于1 bit 數據的處理工作,圖3-4 展示了雙模塊設計方案,用以說明在運算過程中具體的調用方式,便于理解分析。

圖3-4 雙模塊數據處理流程

其中:x[sel]和x[sel]+1 分別為輸入數據x的對應位。 雙模塊思想通過將模塊單元mm_r2mm_0 中的輸出數據So 作為模塊單元mm_r2mm_1 中的輸入數據Si,再將模塊單元mm_r2mm_1 中的輸出數據So 作為模塊單元mm_r2mm_0 的輸入數據Si。 這一操作實現了模塊單元間的數據連接傳遞,將運算結果傳遞到下一次計算中,保證運算處理的連續性,配合步進信號對數據位進行選擇控制,循環實現迭代運算,直至處理到數據的最后一位。 表3-1 說明了步進控制信號在數據選擇時的作用,展示了具體的數據位處理過程。

表3-1 步進信號Sel 與各處理位數的關系

3.4 蒙哥馬利模乘模塊總設計實現

本部分介紹改進后的蒙哥馬利模乘算法,即MM(x,y) 的設計實現過程,以此實現蒙哥馬利模乘計算功能,具體流程如圖3-5 所示。

圖3-5 蒙哥馬利模乘模塊總程序框圖

表3-2 說明了在程序框圖中出現各定義值及其在程序中的作用,方便對程序流程進行解釋說明。

表3-2 框圖中各信號定義及作用

配合表3-2 的說明,對程序流程的介紹如下:

第一步對于程序的啟動條件進行判斷,當req 啟動信號值為1 且步進選擇信號為0 時(數據可從最低位開始處理),滿足啟動條件,此時進行3.3.2 章節中模塊程序的處理(mm_r2mm_0/1),進行數據的迭代處理,同時將sel 步進選擇信號進行sel=sel+2 的處理,同時再將第1 個模塊單元mm_r2mm_0 的輸出值作為第2 個模塊單元mm_r2mm_1 的輸入數據,實現單次數據處理的傳遞,再將mm_r2mm_1 的模塊輸出值sid_w 賦給mm_r2mm_0 的模塊輸入值sid_r,完成一次步進中兩位數據處理結果的傳遞,傳遞進行下一次步進處理;

第二步進行位數判斷處理,如果運算到數據的最后兩位,即滿足這一判斷條件,就說明了運算處理已接近完成,此時再進行最后一次模塊單元處理,完成后的迭代運算結果也就是模塊單元mm_r2mm_1 的輸出值sid_w,若不滿足則返回到模塊程序,繼續進行數據處理;

第三步進行一次條件減法處理,如果模塊輸出值sid_w 大于等于模數m 的值,則將sid_w-m的值作為最終的運算結果賦值給res,否則直接將作為運算結果賦給res;最后將輸出結果標志位val 置1,步進選擇信號sel 置0,結束本次程序運算。

本程序設計的主要運算處理集中在對數據逐bit 位進行迭代運算的處理過程,也就是上文提到的“mm_r2mm_0/1”模塊程序,如果對于算法運算處理效率不滿意,理論上是可以通過增加模塊單元的個數,改變步進,使得在一個時鐘周期內進行多次數據處理,進而減少總的迭代次數,減少總的時鐘周期,進而提升運算效率。 從理論上分析,模塊的單元數量與運算處理效率是成正比的,模塊單元數量越多,運算處理效率越高,4 單元、8 單元、甚至16 單元都是可行的,但是過多引入模塊單元會引入更多的中間變量,在定義與調用時不利于整體程序的實現,同時在實際應用時會占用更多的存儲資源。 綜合考慮資源消耗與處理效率,本文設計將模塊的單元數量設置為2。

需要說明的一點是,為了便于在功能仿真階段中通過時序圖來準確對比出時鐘消耗數,在本設計中引入的啟動信號req 與輸出結果標志信號val 也發揮了一定作用,通過觀察輸出波形中的指定返回信號,即可快速統計出在功能仿真環節運算消耗的總時鐘數,關于這一內容以及功能仿真所需要的相關文件的編寫設計將在下一章節作具體介紹說明。

4 系統仿真

4.1 算法基本結構的正確性驗證

模乘運算應用最基本的形式為X*Ymodm,通過模乘算法的基本定理易知:如果將計算X 與Y 的值互換后,計算結果是不會改變的。借鑒這一想法,通過互換x、y 的值,觀察最終的運算結果是否保持不變,在一定程度上也能夠說明算法運算結構的正確性。 故本文在功能仿真環節將x 與y 值互換后進行運算仿真,仿真結果如下圖4-1、4-2 所示,結果未發生改變,說明了算法結構的正確性。

圖4-1 x、y 值未互換仿真結果

4.2 算法運算結果的正確性驗證

本文設計的蒙哥馬利型模乘法器能夠完成形如x*y*R-1modm的算法運算,其中R 為常數,取值為:R= 2k,與數據位數的選擇有關。

通過觀察其算法形式可以得出一個驗證方法:如果將y 的取值確定為2k,那么算法的運算形式就轉換為x*2k*2-kmodm,由于x 值小于模數m,則可知最終計算值為x。 在這一想法的基礎上,通過設定一組低位數據來進行驗證運算,如果系統仿真運算結果與理論分析一致,則系統運算結果的正確性就得到了保障。

圖4-2 x、y 值互換后仿真結果

在這一步的驗證中,設定x=10000000,m=11110001,對應十六進制數x=80,m=F1,本應設置y=28=256,但由于本文設計中x、y、m應滿足位數相同這一條件,故只能設置y=27=128,最終的運算結果為:

通過Modelsim 軟件進行測試,仿真測試結果如下圖4-3 所示,實際測試結果與理論分析值吻合,進一步說明了系統運算的正確性。

圖4-3 運算正確性驗證仿真測試圖

4.3 Modelsim 功能仿真分析

在上一部分中該算法模塊運算正確性得以驗證,確保該系統的計算功能在算法結構上的正確無誤,但僅僅停留在對于小位數的計算處理中,因此在本部分中對于本文所設計的蒙哥馬利模乘器,在Modelsim SE 10.4 軟件中輸入測試多組數據,展示計算處理功能的完備性。 首次輸入的測試數據類型為256bit 位二進制數,具體數值如下:

同時為了本系統的測試數據的完備性,以及展現系統在處理不同位數的大數模乘時運算時間上的差異性,本文又在原來256 bit 位的基礎上,另行測試了以下三組數據,分別從512 bit、1024 bit、4096 bit 不同位數展現本系統的仿真效果,配合啟動信號req 以及輸出結果標志信號val,即可得出具體的仿真運算處理時間,此內容由于在之前的部分中已經進行過展示,因此在本部分就不再贅述。 本部分主要展示所得的具體仿真結果,分別如圖4-5、圖4-6、圖4-7 所示。

圖4-4 256 位仿真測試結果

圖4-5 512 bit 仿真測試結果

圖4-6 1024 bit 仿真測試結果

經過設計測試,蒙哥馬利大數模乘計算系統理論上能夠計算的最大位數為4096 bit 二進制數,通過修改相關位寬K 參數,即可完成限定位數內任意位數的大數模乘運算,在文本文件中修改輸入測試數據x、y 以及m 的具體數值,即可通過仿真任務窗口進行相關計算數值的輸出展示。

5 總結

當前各主流公鑰密碼算法如RSA,以及各類橢圓曲線加密算法都主要涉及到大數之間的運算,尤其是模乘、模冪計算,而此類計算資源消耗大、運算處理時間長,成為制約系統處理速度的瓶頸。

本文則以蒙哥馬利模乘算法為理論依據,研究設計了大數模乘模塊,以Verilog 硬件描述語言編寫算法程序,并利用Modelsim 軟件進行仿真功能測試,最后利用Altera 對此設計進行綜合,完成研究。

與已有的大數模乘研究方案相比,本文設計具有以下優點:

1. 算法設計原理簡單,設計結構簡介,易于硬件實現;

2. 將串行改進為并行運算,利用模塊化思想使得數據處理效率得到較大提升,理論提升了二倍的處理速度;

3. 在功能仿真環節,通過編寫測試文件的方式讀取輸入數據,簡化了數據輸入形式;

4. 數據處理位數區間充沛,可完成1 至4096 bit 范圍內的蒙哥馬利模乘計算,并將運算結果輸出反饋。

通過總結與比較,現階段本模塊還存在一些不足需要改進完善,需要完成模冪運算,以進一步滿足RSA 等密碼算法的大數運算要求。