段曉毅 黃 燁 曹佳樂

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

1 簡介

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

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

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

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

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

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

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

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

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

由數(shù)論知識可知用一個自然數(shù)去乘2-1有以下結(jié)論:

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

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

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

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

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

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

輸入:x、y、m

輸出:C

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

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

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

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

對于本文系統(tǒng)的輸入數(shù)據(jù)x、y、m 來說,最大可以滿足4096 bit,能滿足現(xiàn)在對公鑰算法強度的要求。

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

3.2 蒙哥馬利型大數(shù)模乘模塊內(nèi)部結(jié)構(gòu)設計

蒙哥馬利型大數(shù)模乘模塊的內(nèi)部結(jié)構(gòu)設計如圖3-2 所示:

圖3-2 蒙哥馬利型大數(shù)模乘模塊內(nèi)部結(jié)構(gòu)設計

本設計的運算處理步驟是通過四次調(diào)用改進的蒙哥馬利模乘算法,并且每次調(diào)用中輸入不同的數(shù)據(jù),最終得到?jīng)]有R-1影響的大數(shù)模乘。

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

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

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

3.3.1 蒙哥馬利模乘單元介紹

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

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

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

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

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

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

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

圖3-4 雙模塊數(shù)據(jù)處理流程

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

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

3.4 蒙哥馬利模乘模塊總設計實現(xiàn)

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

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

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

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

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

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

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

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

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

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

4 系統(tǒng)仿真

4.1 算法基本結(jié)構(gòu)的正確性驗證

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

圖4-1 x、y 值未互換仿真結(jié)果

4.2 算法運算結(jié)果的正確性驗證

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

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

圖4-2 x、y 值互換后仿真結(jié)果

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

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

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

4.3 Modelsim 功能仿真分析

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

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

圖4-4 256 位仿真測試結(jié)果

圖4-5 512 bit 仿真測試結(jié)果

圖4-6 1024 bit 仿真測試結(jié)果

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

5 總結(jié)

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

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

與已有的大數(shù)模乘研究方案相比,本文設計具有以下優(yōu)點:

1. 算法設計原理簡單,設計結(jié)構(gòu)簡介,易于硬件實現(xiàn);

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

3. 在功能仿真環(huán)節(jié),通過編寫測試文件的方式讀取輸入數(shù)據(jù),簡化了數(shù)據(jù)輸入形式;

4. 數(shù)據(jù)處理位數(shù)區(qū)間充沛,可完成1 至4096 bit 范圍內(nèi)的蒙哥馬利模乘計算,并將運算結(jié)果輸出反饋。

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