文獻(xiàn)標(biāo)識(shí)碼： A
文章編號(hào)： 0258-7998(2011)07-153-03
模乘運(yùn)算在公鑰密碼系統(tǒng)中(例如RSA算法、橢圓曲線密碼算法（ECC）以及ElGamal算法等)有著廣泛的應(yīng)用。Montgomery模乘算法利用易于硬件實(shí)現(xiàn)的加法和移位操作來(lái)實(shí)現(xiàn)大整數(shù)的模乘運(yùn)算，避免了復(fù)雜的除法運(yùn)算，從而大大提高了模乘運(yùn)算的效率[1]。
本文提出一種高速可擴(kuò)展的Montgomery乘法器設(shè)計(jì)方案，該方案是在Tenca提出的Booth-8 Montgomery模乘法器的基礎(chǔ)上，采用Booth-64編碼進(jìn)行改進(jìn)，使速度平均提高了48%。同時(shí)對(duì)數(shù)據(jù)通路進(jìn)行了優(yōu)化，使得流水線數(shù)據(jù)通路的平均延遲大大降低。
其中，k表示基，X為模乘運(yùn)算的乘數(shù)，Y是被乘數(shù)，M是模數(shù)。其中，操作數(shù)長(zhǎng)度為N，部分積用為S表示，Y、M和S分成NW個(gè)BPW bit的字進(jìn)行運(yùn)算，xj表示X的第j bit，Sk(i)表示第i個(gè)字的第k位，Ca、Cb表示進(jìn)位，qyj、qMj分別是在計(jì)算部分積過(guò)程中Y和M的系數(shù)。
核心數(shù)據(jù)路徑采用流水線組織結(jié)構(gòu)，每一級(jí)之間用寄存器隔開(kāi)。每個(gè)MMcell單元完成一輪外循環(huán)，每個(gè)時(shí)鐘輸入Y、M、SS、SC的一個(gè)字參與運(yùn)算，并把Y、M和計(jì)算出來(lái)的SS、SC傳遞該下一級(jí)。為了能使數(shù)據(jù)路徑可伸縮，加入了兩個(gè)FIFO分別用來(lái)存儲(chǔ)SS和SC。如圖1所示，NS是流水線級(jí)數(shù)，由面積和時(shí)間需求來(lái)決定。
2 基為64的高速M(fèi)ontgomery乘法器設(shè)計(jì)
Tenca提出的模乘器設(shè)計(jì)中Booth編碼采用的基為8，并且能夠支持操作數(shù)長(zhǎng)度可變的模乘運(yùn)算，對(duì)操作數(shù)按字進(jìn)行運(yùn)算,縮短了關(guān)鍵路徑的延遲，并且使用CSA(Carry Save Adder)提高了整體的系統(tǒng)性能。
通過(guò)分析,采用基為8的Booth編碼可以將部分積數(shù)量減少為原來(lái)的1/3，而采用基為64的Booth編碼則可以將部分積數(shù)量減少為原來(lái)的1/6。據(jù)此本文對(duì)Tenca提出的設(shè)計(jì)方案進(jìn)行改進(jìn)，因此提出基為64的高速M(fèi)ontgomery乘法器。
對(duì)于基為64的設(shè)計(jì)，乘數(shù)X每次掃描6 bit，經(jīng)Booth編碼后得到7 bit的輸入數(shù)據(jù)，同時(shí)Y和M每次輸入一個(gè)字。乘數(shù)X的Booth編碼為：
3 性能分析與比較
對(duì)于基為64的Montgomery乘法器,計(jì)算一次模乘運(yùn)算的總時(shí)鐘周期數(shù)時(shí)，需要考慮NW≤2NS和NW>2NS兩種情況，NW代表操作數(shù)所含的字?jǐn)?shù)。一個(gè)MMcell需要兩個(gè)時(shí)鐘周期的執(zhí)行時(shí)間，因此一個(gè)字經(jīng)過(guò)流水線的總時(shí)鐘周期數(shù)是2NS+1。由于每次可處理6 bit，所以需
從表1可以看出，在不同條件下，本文的設(shè)計(jì)在性能上平均比Tenca的設(shè)計(jì)提高了48%。本文采用字長(zhǎng)32 bit，級(jí)數(shù)NS=8實(shí)現(xiàn)基為64的Montgomery乘法器，且使用Verilog HDL語(yǔ)言實(shí)現(xiàn)上述設(shè)計(jì)，并使用ModelSim 對(duì)設(shè)計(jì)進(jìn)行了仿真驗(yàn)證；基于SMIC 0.18 μm CMOS標(biāo)準(zhǔn)數(shù)字邏輯工藝，利用Design Compiler 進(jìn)行了綜合設(shè)計(jì)，結(jié)果顯示頻率達(dá)到251 MHz，面積為37 381門(mén)。
顧葉華在參考文獻(xiàn)[4]中對(duì)Tenca提出的流水線結(jié)構(gòu)進(jìn)行了優(yōu)化，提出了一種基為4的Montgomery乘法器方案。面積和速度的比較如表2所示。從表中可以看出，本設(shè)計(jì)在512 bit和1 024 bit下具有最小的時(shí)間×面積的值，綜合性能最優(yōu)。
本文對(duì)Tenca提出的基為8的可擴(kuò)展Montgomery模乘器進(jìn)行改進(jìn)，采用了更高的基為64的設(shè)計(jì)，進(jìn)一步減少了部分積的個(gè)數(shù)，縮短了運(yùn)算時(shí)間。與Tenca在參考文獻(xiàn)[2]中的設(shè)計(jì)相比，時(shí)鐘周期數(shù)平均減少了48%，并且縮短了關(guān)鍵路徑的延遲相比，綜合性能具有明顯地提高。
參考文獻(xiàn)
[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] 顏曉東，李樹(shù)國(guó). 二次Booth編碼的大數(shù)乘法器設(shè)計(jì)[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，47(10)：1681-1684．
[4] 顧葉華，曾曉洋，趙佳，等. 一種新型操作數(shù)長(zhǎng)度可伸縮的模乘器VLSI設(shè)計(jì)[J]. 計(jì)算機(jī)工程, 2007，33(19)：227-229．