劉建國,管文強(qiáng),楊同杰,楊曉輝

(1.解放軍信息工程大學(xué) 電子技術(shù)學(xué)院，河南 鄭州 450004；2.72850部隊(duì)，山東 濟(jì)南 250031)

模乘運(yùn)算在公鑰密碼系統(tǒng)中(例如RSA算法、橢圓曲線密碼算法（ECC）以及 ElGamal算法等)有著廣泛的應(yīng)用。Montgomery模乘算法利用易于硬件實(shí)現(xiàn)的加法和移位操作來實(shí)現(xiàn)大整數(shù)的模乘運(yùn)算，避免了復(fù)雜的除法運(yùn)算，從而大大提高了模乘運(yùn)算的效率[1]。

本文提出一種高速可擴(kuò)展的Montgomery乘法器設(shè)計方案，該方案是在Tenca提出的Booth-8 Montgomery模乘法器的基礎(chǔ)上，采用Booth-64編碼進(jìn)行改進(jìn)，使速度平均提高了48%。同時對數(shù)據(jù)通路進(jìn)行了優(yōu)化，使得流水線數(shù)據(jù)通路的平均延遲大大降低。

1 MWR2kMM算法分析

Tenca等人在參考文獻(xiàn)[2]中提出一種MWR2kMM算法，MWR2kMM算法如下：

其中，k表示基，X為模乘運(yùn)算的乘數(shù)，Y是被乘數(shù)，M是模數(shù)。其中，操作數(shù)長度為N，部分積用為S表示，Y、M和S分成NW個BPW bit的字進(jìn)行運(yùn)算，xj表示 X的第 j bit，Sk(i)表示第 i個字的第 k 位，Ca、Cb表示進(jìn)位，qYj、qMj分別是在計算部分積過程中Y和M的系數(shù)。

核心數(shù)據(jù)路徑采用流水線組織結(jié)構(gòu)，每一級之間用寄存器隔開。每個MMcell單元完成一輪外循環(huán)，每個時鐘輸入 Y、M、SS、SC的一個字參與運(yùn)算，并把 Y、M和計算出來的SS、SC傳遞該下一級。為了能使數(shù)據(jù)路徑可伸縮，加入了兩個FIFO分別用來存儲SS和SC。如圖1所示，NS是流水線級數(shù)，由面積和時間需求來決定。

圖1 數(shù)據(jù)路徑結(jié)構(gòu)

2 基為64的高速M(fèi)ontgomery乘法器設(shè)計

Tenca提出的模乘器設(shè)計中Booth編碼采用的基為8，并且能夠支持操作數(shù)長度可變的模乘運(yùn)算，對操作數(shù)按字進(jìn)行運(yùn)算,縮短了關(guān)鍵路徑的延遲，并且使用CSA(Carry Save Adder)提高了整體的系統(tǒng)性能。

通過分析,采用基為8的Booth編碼可以將部分積數(shù)量減少為原來的1/3，而采用基為64的Booth編碼則可以將部分積數(shù)量減少為原來的1/6。據(jù)此本文對Tenca提出的設(shè)計方案進(jìn)行改進(jìn)，因此提出基為64的高速M(fèi)ontgomery乘法器。

對于基為64的設(shè)計，乘數(shù)X每次掃描6 bit，經(jīng)Booth編碼后得到7 bit的輸入數(shù)據(jù)，同時Y和M每次輸入一個字。乘數(shù)X的Booth編碼為：

xi-1是前一組掃描數(shù)據(jù)的最高位，qY的值表示為：

通過計算可知，qy的取值范圍為[-32,32]，這樣需要預(yù)先計算3Y、5Y、…、31Y的Y奇數(shù)倍的值，從而占用大量的存儲空間，且電路復(fù)雜，顯然難以直接應(yīng)用到模乘器的硬件設(shè)計中。為了解決這個問題，可以將qy用一個線性表達(dá)式 qY=ha+b來表示，其中h為系數(shù)，a、b為變量。

為了確定系數(shù)h和變量a、b的取值范圍，便于硬件實(shí)現(xiàn)，將 a、b 的取值范圍限定在集合{±0,±1,±2,±3,±4}中。通過觀察，要使qY=32，由于 a、b的值最大為 4，則要求 h≥7;同時，要使 qY=5， a取 1、b最小為-4，要求 h≤9?？紤]到硬件的快速實(shí)現(xiàn)，系數(shù)h取8。則有：

通過對qY進(jìn)行線性表示，可以將qYY運(yùn)算轉(zhuǎn)化為計算8(aY)+bY的值。為了進(jìn)一步簡化電路設(shè)計，a=3時，可以把3Y拆分成4Y與-Y的和；a=-3時，可以把-3Y拆分成Y與-4Y的和，這種方法同樣適用于b。因此對a和b進(jìn)行再編碼，即a=qYa1+qYa2,b=qYb1+qYb2。qY可以分解為a和b，a和b又分解為 qYa1、qYa2、qYb1、qYb2，這樣可以避免對3Y進(jìn)行預(yù)計算，大大簡化了電路的設(shè)計[3]。

對于qM,它取決于 S和 M的最低 6 bit的值，即 qM:=在 k=6時，qM的取值范圍為[0,63]。為了進(jìn)一步簡化電路，對qM進(jìn)行研究發(fā)現(xiàn)，當(dāng)qM在[-32，32]范圍取值時,同樣可以使S的低 6 bit變?yōu)?0。系數(shù) qM從[0,63]轉(zhuǎn)換到 qM′[-32,32]的方法為：

本設(shè)計對于 qM′的解碼采取與qy相同的辦法,首先對 qM′采用線性表示，然后進(jìn)行二次編碼，輸出 qMa1、qMa2和qMb1qMb2。處理單元MMcell的結(jié)構(gòu)如圖2所示，其中qY解碼器用來根據(jù)Xj信號進(jìn)行解碼，產(chǎn)生部分積選擇信號 qya1、qya2和 qyb1、qyb2,而 qM解碼器根據(jù) S和 M 的最低6 bit的值，產(chǎn)生部分積選擇信號 qMa1、qMa2和 qMb1、qMb2。 對于部分積的求和運(yùn)算，本文采用4～2的進(jìn)位保留加法器，以減少關(guān)鍵路徑的延遲，這樣輸出結(jié)果由SS和SC兩部分組成。

圖2 處理單元MMcell結(jié)構(gòu)

3 性能分析與比較

對于基為64的Montgomery乘法器,計算一次模乘運(yùn)算的總時鐘周期數(shù)時，需要考慮NW≤2NS和NW＞2NS兩種情況，NW代表操作數(shù)所含的字?jǐn)?shù)。一個MMcell需要兩個時鐘周期的執(zhí)行時間，因此一個字經(jīng)過流水線的總時鐘周期數(shù)是2NS+1。由于每次可處理6 bit，所以需要輪循環(huán)。完成一次模乘運(yùn)算的時鐘周期數(shù)為：

從表1可以看出，在不同條件下，本文的設(shè)計在性能上平均比Tenca的設(shè)計提高了48%。本文采用字長32 bit，級數(shù) NS=8實(shí)現(xiàn)基為 64的 Montgomery乘法器，且使用Verilog HDL語言實(shí)現(xiàn)上述設(shè)計，并使用ModelSim對設(shè)計進(jìn)行了仿真驗(yàn)證；基于SMIC 0.18 μm CMOS標(biāo)準(zhǔn)數(shù)字邏輯工藝，利用Design Compiler進(jìn)行了綜合設(shè)計，結(jié)果顯示頻率達(dá)到251 MHz，面積為37 381門。

表1 基為8和基為64的Montgomery乘法器在不同的NS和NW下的性能比較

顧葉華在參考文獻(xiàn)[4]中對Tenca提出的流水線結(jié)構(gòu)進(jìn)行了優(yōu)化，提出了一種基為4的Montgomery乘法器方案。面積和速度的比較如表2所示。從表中可以看出，本設(shè)計在512 bit和1 024 bit下具有最小的時間×面積的值，綜合性能最優(yōu)。

本文對Tenca提出的基為8的可擴(kuò)展Montgomery模乘器進(jìn)行改進(jìn)，采用了更高的基為64的設(shè)計，進(jìn)一步減少了部分積的個數(shù)，縮短了運(yùn)算時間。與Tenca在參考文獻(xiàn)[2]中的設(shè)計相比，時鐘周期數(shù)平均減少了48%，并且縮短了關(guān)鍵路徑的延遲相比，綜合性能具有明顯地提高。

表2 面積和速度性能比較

[1]KOC C K,ACAR T,KALISKI B.Analyzing and comparing Montgomery multiplication algorithms[C].IEEE Micro,1996:26-33.

[2]TENCA A F,TODOROV G,KOC C K.High-radix design of a scalable modular multiplier[A].Cryptography Hardware and Embedded System-CHES 2001.Springer Verlag,Berlin,Germany,2001:189-205.

[3]顏曉東，李樹國.二次Booth編碼的大數(shù)乘法器設(shè)計[J].清華大學(xué)學(xué)報（自然科學(xué)版），2007，47(10)：1681-1684.

[4]顧葉華，曾曉洋，趙佳，等.一種新型操作數(shù)長度可伸縮的模乘器 VLSI設(shè)計[J].計算機(jī)工程,2007，33(19)：227-229.