可重構(gòu)雙基雙域模乘器設(shè)計與實現(xiàn)

倪 樂，戴紫彬，楊同杰，李 淼，陳 韜

(信息工程大學 電子技術(shù)學院，河南 鄭州450004)

基于橢圓曲線離散對數(shù)問題 （ECDLP）的橢圓曲線密碼 ECC（Elliptic Curve Cryptography）[1-2]已經(jīng)被證明是一種比RSA更安全、計算上更高效的公鑰密碼體制，因此正逐步取代RSA成為下一代公鑰密碼標準[3]。作為橢圓曲線密碼算法的核心運算，模乘運算的性能至關(guān)重要，如何靈活、高效地實現(xiàn)模乘運算是當前的一個研究熱點。

ECC的基域有素數(shù)域和二進制域兩種，在實際應(yīng)用中，常常需要能夠支持兩個域上的模乘運算，為此設(shè)計了一種雙域模乘器是一種有效的解決方案。Montgomery模乘算法[4]是目前應(yīng)用最為廣泛且最為高效的模乘算法，它將傳統(tǒng)模乘運算中的除法運算以移位操作代替，大大加快了模乘運算的速度和效率，非常適合硬件實現(xiàn)。由于兩個域上的傳統(tǒng)模乘器設(shè)計的延遲不同，因此本文選取適合雙域運算的Montgomery算法進行分析，采用選取不同字長的設(shè)計方法，提出了可重構(gòu)的雙基雙域模乘器設(shè)計方案。結(jié)果表明，本設(shè)計有效提高了二進制域上模乘運算的速度，使得兩個有限域上模乘運算的時鐘頻率更加匹配。

1 雙域Montgomery模乘算法

素數(shù)域和二進制域上基于字的Montgomery模乘算法如算法1所示。其中，A、B表示被乘數(shù)和乘數(shù)，N表示模數(shù)，C表示Montgomery模乘運算的乘積。字長為w，基r為 2w，s=「m/w（m是模數(shù)N的位長）。A(i)代表A的第i個字，B(j)、C(j)、N(j)分別代表B、C、N的第j個字。

算法1基于字的Montgomery模乘算法

算法1是一種對原始Montgomery模乘算法的改進，它對操作數(shù)按字進行了分割，把大整數(shù)的乘法運算分割成小整數(shù)的乘法，避免了硬件實現(xiàn)中大整數(shù)運算帶來的時鐘延遲較大的問題。算法中運算+Field、-Field和×Field的具體定義是某一個有限域上的運算：對于素數(shù)域，為普通整數(shù)的加、減法和乘法運算；對于二進制域，元素在運算中都采用多項式表示形式，加、減法運算就是“異或”運算，乘法運算比較特殊，部分積的累加采用對應(yīng)位“異或”的方式。算法最后(第10步)的比較和減法運算只針對素數(shù)域，二進制域不需要這一步。

2 可重構(gòu)雙基雙域模乘器設(shè)計

2.1 傳統(tǒng)雙域模乘器分析

傳統(tǒng)的雙域模乘器大都采用單一基的設(shè)計，即素數(shù)域和二進制域采用相同的字長進行運算，最有代表性的就是Akashi Satoh設(shè)計的雙域模乘器[5],其中的邏輯運算單元完成算法1的第2～第9步，是整個電路的關(guān)鍵路徑。然而關(guān)鍵路徑的延遲又和運算選取的基域密切相關(guān)，二進制域上的加法運算是“異或”運算，而素數(shù)域上的加法是帶進位的普通整數(shù)加法運算，縮短延遲最有效的辦法是采用進位保留加法器(CSA)。一級CSA的最大延遲為 2TXOR(“異或”門的傳輸延遲)是“異或”運算的兩倍，因此在采用相同運算字長的情況下，這種雙域結(jié)構(gòu)的模乘器在時鐘頻率上必然取決于延遲較大的素數(shù)域運算，一定程度上影響了二進制域上模乘運算的速度。

為了解決上述問題，本文采用雙基的設(shè)計思想，即素數(shù)域和二進制域上的運算采用不同的字長，通過增大二進制域上模乘運算單次掃描的字長，達到減少模乘運算消耗的總時鐘周期數(shù)的目的，解決了由于時鐘頻率降低所帶來的運算時間增大的問題。

2.2 運算字長的選擇

算法1中最核心的運算是內(nèi)循環(huán)中第6步的2次乘法和3次加法運算，而乘法運算又是GF(p)和GF(2m)上延遲時間差距最大的運算。因此下面將針對雙域模乘器進行分析，通過對兩個域上不同字長下模乘器延遲時間的比較，選擇出能夠使兩個域上模乘器延遲時間相當?shù)淖珠L。

根據(jù)分析，在字長相同時，素數(shù)域上的整數(shù)乘法運算延遲要大于二進制域上的乘法運算延遲，因此二進制域上的字長應(yīng)該大于素數(shù)域上的字長，才能使得兩個域上模乘器的延遲大體相當。

假設(shè)X、Y∈GF(2m),并且X和Y二進制形式表示的字長都是k=2w。

若用一般方法，X和Y相乘先通過k2個“與”門生成k個k-bit位寬的部分積，再通過(「k/27+「k/22+「k/23+…+「k/2「log2k)(k-1)個“異或”門對這些部分積進行求和。

Karatsuba-Ofman算法[6]是一種利用w-bit乘法運算來實現(xiàn)2w-bit乘法運算的方法。X和Y可以表示為：X=2wXH+XL，Y=2wYH+YL， 其中XH和XL分別表示被乘數(shù)X的高半部分和低半部分，YH和YL分別表示乘數(shù)Y的高半部分和低半部分。

X和Y的乘法表示為：

共需要4次乘法和3次加法運算。通過對XHYL+XLYH的進一步簡化，X和Y的乘法還可表示為：

簡化后需要3次乘法和6次加法運算。這種方法稱為一級Karatsuba-Ofman方法。

Karatsuba-Ofman算法不僅可以單獨實現(xiàn)模乘器，還可以嵌套完成更大字長的模乘器。一重Karatsuba-Ofman嵌套的設(shè)計方法稱為二級Karatsuba-Ofman方法。

在0.18 μm CMOS工藝下對上述模乘器設(shè)計進行綜合，表1比較了整數(shù)模乘器與不同方法實現(xiàn)的二進制域模乘器的延遲。從表1發(fā)現(xiàn)，16 bit整數(shù)模乘器的延遲與64 bit二級Karatsuba-Ofman模乘器的延遲最為接近，符合兩個域上模乘運算延遲更加相近的要求。因此，本文選擇素數(shù)域整數(shù)模乘器和二級Karatsuba-Ofman方法實現(xiàn)的二進制域模乘器，運算字長分別為16 bit和64 bit。

表1 兩個域上模乘器延遲比較

2.3 可重構(gòu)模乘器設(shè)計

結(jié)合上述分析，本文設(shè)計的可重構(gòu)雙基雙域模乘器整體架構(gòu)如圖1所示，主要由存儲單元、雙基雙域運算單元、控制單元以及運算數(shù)據(jù)選擇單元構(gòu)成。其中，存儲單元用來存儲運算參數(shù)A、B、N、Q以及中間變量T、C、Z；雙基雙域運算單元完成算法1的第2～第9步運算，運算數(shù)據(jù)位寬為64 bit，執(zhí)行二進制域上的運算時為單路運算，執(zhí)行素數(shù)域上的運算時變?yōu)?路并行運算；控制單元為存儲單元生成讀寫控制信號，對運算數(shù)據(jù)選擇單元的輸出進行選擇，并對雙基雙域運算單元的進位信號進行寄存。

雙基雙域運算單元結(jié)構(gòu)如圖2所示，主要由2個并行的64 bit雙基雙域模乘器、1個64 bit雙基雙域加法器和兩個128 bit雙基雙域加法器組成。該單元能夠用一次操作完成算法1中最核心的第6步運算：二進制域運算時，運算字長 64 bit，在一個時鐘內(nèi)單路完成一輪內(nèi)循環(huán)運算；素數(shù)域運算時，每路運算字長 16 bit，4路并行完成相鄰4個外循環(huán)運算。

圖2中的兩個64 bit雙基雙域模乘器采用二級Karatsuba-Ofman方法實現(xiàn)，電路結(jié)構(gòu)如圖3所示，主要包含3個Karatsuba-Ofman模乘器，#0和 #1為16 bit位寬，#2為64-bit位寬。該模乘器完成的功能根據(jù)有限域選擇信號field的不同分為兩種情況：二進制域時，完成64 bit輸入數(shù)據(jù)A和B的乘積A×B；素數(shù)域時，輸入數(shù)據(jù) A和B自高到低分割成 4個16 bit，并行完成 A3×B3、A2×B2、A1×B1、A0×B0 4 路整數(shù)乘法運算。

3 功能仿真與性能分析

3.1 功能仿真

本文采用Verilog語言對可重構(gòu)雙基雙域模乘器進行RTL級描述，選用Mentor公司的ModelSim 6.1f進行硬件功能仿真,以驗證設(shè)計的正確性。以下給出了GF(p)上 384 bit和 GF(2m)上 234 bit Montgomery模乘運算的仿真結(jié)果（數(shù)據(jù)按照低32 bit在前，高 32 bit在后的順序輸入和輸出）。

素數(shù)域上的運算數(shù)據(jù)：

乘積AB2-384mod N:

二進制域上的運算數(shù)據(jù)：

乘積A(x)B(x)x-256mod N:

表2 不同長度下模乘運算時鐘周期數(shù)比較

3.2 性能分析

素數(shù)域上模乘運算采用4路并行運算，每一路運算消耗s+1個時鐘周期，一共循環(huán)「(s+1)/4次。同時相鄰兩路運算之間相差3個時鐘周期,最后一路運算結(jié)束需要額外3×「(s+1)%4-1個時鐘周期,因此運算時間為：

二進制域上模乘運算采用單路循環(huán)完成，每一路運算消耗s+1個時鐘周期，一共循環(huán)s+1次，因此運算時間為：

表2列出了本設(shè)計與其他設(shè)計在GF(p)和GF(2m)上不同長度下模乘運算時鐘周期數(shù)的比較結(jié)果。

從表中可以看出，在GF(p)上，本設(shè)計選用的基比參考文獻[5]小，所以時鐘周期數(shù)平均是參考文獻[5]的1.5倍；與參考文獻[7]相比，雖然選用的基相同并且都是4路并行，但是本文采用二級Karatsuba-Ofman方法實現(xiàn)，使得算法1中的1輪內(nèi)循環(huán)只需要1個時鐘周期，比參考文獻[7]平均縮短了48%。在GF(2m)上，在選用相同基的情況下，本設(shè)計的時鐘周期數(shù)平均比參考文獻 [5]和參考[7]縮短了46%。

不同類型模乘器的電路面積和運算速度有著較大的差別，而單一地從某一方面進行性能衡量都是不全面的，所以通常以面積與速度的乘積作為比較全面的衡量性能優(yōu)劣的重要指標。圖4、圖5分別給出了本文設(shè)計的可重構(gòu)雙基雙域模乘器與參考文獻[5]、[7]設(shè)計的模乘器的性能比較?？梢钥闯觯瑹o論是在GF(p)還是在GF(2m)上，本文設(shè)計的模乘器都具有最小的面積×速度，電路延遲較小，電路規(guī)模適中，綜合性能更好。

本文基于字級的Montgomery模乘算法，針對雙域模乘器設(shè)計中存在的二進制域上模乘運算效率不高的問題，設(shè)計了一種新的可重構(gòu)雙基雙域模乘器。根據(jù)以上的分析和比較，本文設(shè)計的可重構(gòu)雙基雙域模乘器在靈活性、運算速度以及面積等方面具有優(yōu)勢，與雙域上采用單一基的模乘器相比，在GF(2m)上的模乘運算效率得到顯著提高，滿足現(xiàn)代通信網(wǎng)絡(luò)對公鑰密碼處理高速性和靈活性的要求。

[1]MILLER V.Use of elliptic curves in cryptography[A].In:H.C.Williams.Advances in Cryptography-CRYPTO′85[C].Heidelberg:Springer-Verlag,1986:417-426.

[2]KOBLITZ N.Elliptic Curve Cryptosystems[J].Mathematics of Computation,1987(48):203-209.

[3]陳華鋒.橢圓曲線密碼算法及芯片實現(xiàn)方法研究[D].杭州：浙江大學,2008:56-60.

[4]MONTGOMERY P L.Modular multiplication without trial division[J].Mathematics of Computation,1985,44:519-521.

[5]SATOH A,TAKANO K.A scalable dual-field elliptic curve cryptographic processor[J].IEEE Transactions on Computers,2003,4(52):449-460.

[6]Zhou Gang,MICHALIK H,HINSENKAMP L.Complexity analysis and efficient implementations of bits parallel finite field multiplier based on karatsuba-ofman algorithm on FPGAs[J].IEEE Transcations on Very Large Scale Integration(VLSI)Systems,2010,18(7):1057-1066.

[7]TANIMURA K,NARA R,KOHARA S.Scalable unified dual-radix architecture for montgomery multiplication in GF(p)and GF(2n)[C].Design Automation Conference,Seoul,March 2008:697-702.