123,123,123

基为64的可扩展模乘法器设计

来源：电子技术应用2011年第7期

刘建国1, 管文强2, 杨同杰1, 杨晓辉1

1. 解放军信息工程大学电子技术学院，河南郑州450004； 2. 72850部队，山东济南 250031

摘要： 针对Tenca提出的基为8的Montgomery模乘器，采用基为64的改进设计，使其在不同运算长度下，运算速度比Tenca的设计平均提高了48%。同时对硬件设计进行了优化，缩短了关键路径的延迟。该设计具有良好的可扩展性，能够支持任意位数的模乘运算，可广泛应用于不同性能和面积需求的公钥密码协处理器设计。

關鍵詞： Montgomery乘法器高基可扩展

中圖分類號： TP332
文獻標識碼： A
文章編號： 0258-7998(2011)07-153-03

Design of a scalable radix-64 montgomery multiplier

Liu Jianguo1, Guan Wenqiang2, Yang Tongjie1, Yang Xiaohui1

1. Institute of Electronic Technology, the PLA Information Engineering University, Zhengzhou 450004, China； 2. Unit 92850 of the PLA , Jinan 250031, China

Abstract： An improved version of Montgomery multiplier was proposed basing the Tenca’s word based radix-8 Montgomery multiplier. Radix-64 was used for our design. The performance was improved up to 48% comparing to the Tenca’s design. Furthermore, the critical path was shortened by adjusting the data-path. The proposed multiplier is also able to work with any precision of the input operands and can suitable to various public key cryptosystem.

Key words : montgomery multiplier; high-radix; scalable

    模乘運算在公鑰密碼系統(tǒng)中(例如RSA算法、橢圓曲線密碼算法（ECC）以及ElGamal算法等)有著廣泛的應用。Montgomery模乘算法利用易于硬件實現(xiàn)的加法和移位操作來實現(xiàn)大整數(shù)的模乘運算，避免了復雜的除法運算，從而大大提高了模乘運算的效率[1]。
    本文提出一種高速可擴展的Montgomery乘法器設計方案，該方案是在Tenca提出的Booth-8 Montgomery模乘法器的基礎上，采用Booth-64編碼進行改進，使速度平均提高了48%。同時對數(shù)據(jù)通路進行了優(yōu)化，使得流水線數(shù)據(jù)通路的平均延遲大大降低。


其中，k表示基，X為模乘運算的乘數(shù)，Y是被乘數(shù)，M是模數(shù)。其中，操作數(shù)長度為N，部分積用為S表示，Y、M和S分成NW個BPW bit的字進行運算，xj表示X的第j bit，Sk(i)表示第i個字的第k位，Ca、Cb表示進位，q_yj、q_Mj分別是在計算部分積過程中Y和M的系數(shù)。
   核心數(shù)據(jù)路徑采用流水線組織結構，每一級之間用寄存器隔開。每個MMcell單元完成一輪外循環(huán)，每個時鐘輸入Y、M、SS、SC的一個字參與運算，并把Y、M和計算出來的SS、SC傳遞該下一級。為了能使數(shù)據(jù)路徑可伸縮，加入了兩個FIFO分別用來存儲SS和SC。如圖1所示，NS是流水線級數(shù)，由面積和時間需求來決定。

2 基為64的高速Montgomery乘法器設計
    Tenca提出的模乘器設計中Booth編碼采用的基為8，并且能夠支持操作數(shù)長度可變的模乘運算，對操作數(shù)按字進行運算,縮短了關鍵路徑的延遲，并且使用CSA(Carry Save Adder)提高了整體的系統(tǒng)性能。
    通過分析,采用基為8的Booth編碼可以將部分積數(shù)量減少為原來的1/3，而采用基為64的Booth編碼則可以將部分積數(shù)量減少為原來的1/6。據(jù)此本文對Tenca提出的設計方案進行改進，因此提出基為64的高速Montgomery乘法器。
    對于基為64的設計，乘數(shù)X每次掃描6 bit，經(jīng)Booth編碼后得到7 bit的輸入數(shù)據(jù)，同時Y和M每次輸入一個字。乘數(shù)X的Booth編碼為：

3 性能分析與比較
對于基為64的Montgomery乘法器,計算一次模乘運算的總時鐘周期數(shù)時，需要考慮NW≤2NS和NW>2NS兩種情況，NW代表操作數(shù)所含的字數(shù)。一個MMcell需要兩個時鐘周期的執(zhí)行時間，因此一個字經(jīng)過流水線的總時鐘周期數(shù)是2NS+1。由于每次可處理6 bit，所以需

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

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

本文對Tenca提出的基為8的可擴展Montgomery模乘器進行改進，采用了更高的基為64的設計，進一步減少了部分積的個數(shù)，縮短了運算時間。與Tenca在參考文獻[2]中的設計相比，時鐘周期數(shù)平均減少了48%，并且縮短了關鍵路徑的延遲相比，綜合性能具有明顯地提高。
參考文獻
[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ù)乘法器設計[J].清華大學學報（自然科學版），2007，47(10)：1681-1684．
[4] 顧葉華，曾曉洋，趙佳，等. 一種新型操作數(shù)長度可伸縮的模乘器VLSI設計[J]. 計算機工程, 2007，33(19)：227-229．

原創(chuàng)聲明：此內容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權禁止轉載。

相關內容