Montgomery模乘法器的實現與優化

車文潔 董秀則 高獻偉 張曉楠

(北京電子科技學院 北京 100070)

Montgomery模乘法器的實現與優化

車文潔 董秀則 高獻偉 張曉楠

(北京電子科技學院 北京 100070)

蒙哥馬利算法是公鑰密碼實現的基礎算法, 應用范圍廣泛。要想提高公鑰密碼體制的運算速度，設計運算速度快、消耗資源少、效率高的蒙哥馬利模乘法器非常關鍵。根據蒙哥馬利乘積算法實現了蒙哥馬利乘法器，通過硬件描述語言分別對其進行FPGA設計與實現，將其實現結構由串行結構優化為并行結構，在多占用資源約50%的基礎上，速度實現了6倍左右的提高。與現有的相關研究成果相比，在增加耗用較少的資源的基礎上速度實現大幅度的提升。

Montgomery算法 Montgomery模乘法器 FPGA 硬件描述語言協同

0 引 言

ECC是目前應用最廣泛的一種公鑰密碼算法，它具有密鑰量小、靈活性好及安全性高等優點。許多公鑰密碼的運算只能在素域上進行，所以素域上公鑰密碼的應用較廣泛[1,2,7]。 模算術運算為素數域上的公鑰密碼算法基本運算。其操作數通常為大整數，運算復雜度高，成為制約公鑰密碼系統性能的瓶頸[8-9]。素域上模算術運算中的乘法運算是最基礎、也是最耗時的運算，因此，要提高公鑰密碼體制的運算速度，設計運算速率高、資源消耗少的高效模乘法器很關鍵[10-11]。提到模乘法器，目前研究的熱點是Montgomery算法，該算法是1985年由Peter L.Montgomery于提出[12]。 其實用性強，不僅適合軟件實現，而且適合硬件實現。本文設計的蒙哥馬利乘法器，其實現代碼的通用性強，即通過修改相關的參數，可在384-bit內任意的素數域上實現。考慮到實用性與安全性，本文對操作數為384-bit的蒙哥馬利乘法器在實現的基礎上進行優化，其與現有的研究成果作比較，綜合性能較優。

1 Montgomery算法介紹

蒙哥馬利算法的主要思想是通過簡單的移位操作來代替除法，將原始操作數通過運算用蒙哥馬利域里面的數表示出來，提高了效率, 大大降低了計算復雜度。

定義Montgomery乘積：

MP(x,y)=xyR-1modm

(1)

其中x、y

定義Montgomery約減：

MR(x)=xR-1modm

(2)

因為gcd(m,R)=1，所以存在-m-1∈ZR即m(-m-1)modR=-1。如果(-m-1)已被算出，用a來表示。Montgomery約減用下面的算法1來計算：

算法1Montgomery約減

a=(x mod R)(-m-1) mod R(0≤x≤R)

b=(x+am)/R

if b≥m then return (b-m)

else return b;

從上面的算法求MR(x)，可以看出，因為am≡xm(-m-1)≡-xmodR，故b為整數；因bR≡xmodmbR，則b≡xR-1modm。由于0≤x+am

給定x,y∈Zm，乘積p=xy

MP(x,y)=MR(xy)

(3)

若m是奇數，那么有元素2-1∈Zm，即2·2-1modm=1。若m的長度為k-bit，定義R=2k。給出x=xk-1·2k-1+xk-2·2k-2+…+x0·20,y∈Zm，則：

MP(x,y) =xy(2k)-1modm

=(xk-1y2k-1+xk-1y2k-1+…+

x0y20)(2k)-1modm

=((…(((0+x0y)2-1+x1y)2-1+

x2y)2-1+…)2-1+xk-1y)2-1modm

(4)

執行a·2-1如下：

(5)

根據式(4)和式(5)推導出算法2：

算法2Montgomery乘積

p:= 0;

for i in 0 .. k-1 loop

qi:=( p0+ xi*y0)mod2;

p:=(p+xi*y+qi*m)/2;

end loop;

if p >= m then z <= p-m; else z <= p; end if;

證明：p的值恒定小于2m的。如果p<2m，則a=p+x，y<2m+y<3m，a/2<(3/2)m<2m，(a+m)/2<4m/2=2m，這樣，最后一步z就是p或p-m，均為小于m的數。

2 Montgomery乘法器的設計與實現

根據式(4)、式(5)以及算法2，借鑒串行進位加法器的實現結構，實現Montgomery乘法器，實現結構如圖1所示。

圖1 Montgomery乘法器的電路圖

從該結構圖可知，p是進位，y與xi相乘后與進位相加，對其和進行奇偶判斷，若為奇數，則加m除以2，若為偶數，則直接除以2，將所得到的結果依次與后面的xi與y的乘積相加，直至x的最后一位，最后計算p_minus_m，若p_minus_m(k)為1，z為p_minus_m(k-1…0)，否則z為p(k-1…0)。

該結構圖的最小時鐘周期約等于2kTFA，若不算最后的操作，則時鐘總數為k，相應總的時間消耗為2k2TFA。最后操作包括計算p與p_minus_m，其中p為k-bit數，p_minus_m是(k+1)-bit數。使用串行進位加法器，計算時間大約是kTFA。因此，總的計算時間為：

T≈2k2TFA+kTFA

(6)

式(6)中的第二項kTFA對應于最后的操作，該操作不能在一個時鐘周期內完成。

接下來我們來觀察操作數為192-bit時，其操作仿真結果圖。

取模數：

m=p192=2192-264-1=(FFFFFFFFFFFFFFFFFF

FFFFFFFFFFFFFEFFFFFFFFFFFFFFFF)16。資源消耗情況：共使用405個Registers，1 157個LUTs，仿真結果如圖2所示。

圖2 Montgomery模乘法器仿真結果(mod p192)

編譯和仿真后得到Montgomery模乘法器的運行最高頻率為199.898MHz，運行的總時鐘數為304。根據公式：速度=最高頻率(主頻)/運行總時鐘數，經過計算得出運行速度：

199.898MHz/304=657 559次/秒

圖2中，x=(8055AA55AA55AA55AA55AA55AA55

AA55AA55AA55AA55AA55)16，y=(96AA55AA55AA55AA

55AA55AA55AA55AA55AA55AA55AA55AA)16時，z=(37 1441BE41BE41BE7ABE092F97A126128FF7CF695DDAEC4C)16。計算結果與仿真結果一致，驗證了仿真結果的正確性。

接下來我們來觀察操作數為384-bit時，其操作仿真結果圖。取模數：

m=p384=2384-2128-296+232-1=″fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff000000000000 0000ffffffff″。資源消耗情況：共使用791個Registers，2 362個LUTs，仿真結果如圖3所示。

圖3 Montgomery模乘法器仿真結果(mod p384)

編譯和仿真后得到Montgomery模乘法器的運行最高頻率為131.673MHz，運行的總時鐘數為602。根據公式：速度=最高頻率(主頻)/運行總時鐘數，經過計算得出運行速度：

131.673MHz/602bit=218 725次/秒

圖3中，X=′9807A0C5177CEF9817F58EA8BD4A8 D66503E9E22EAEA46EACF5BFCB0C6E683DDF80D5CF 2B3FB0D8B023E20CEE0475BD′，Y=′6EECFBD48A0 A4216F418049462C70894786708BB0D96F9B4C58240E 3AFF5E7E8F53DBCAAC99A62DF0BD6CF41BCE315F′， Z=′8AA51A52D7EE968848AED51E7941F9C22DC5F2F 5DEBDE5424A977C3A6F08EBBB863A1AE97FBC511328 6BC2E98F5DFAB2′，經過計算后得出結果與仿真結果一致，驗證其仿真結果的正確性。

3 Montgomery乘法器的優化

上小節雖然實現的Montgomery乘積，但整體實現結構為串行結構，總的計算時間約等于T≈2k2TFA+kTFA，時間消耗較多，速度也較慢。因此 使用進位保留加法器，將實現結構優化為并行結構，相應的實現結構如圖4所示。

圖4 優化后Montgomery模乘法器的電路圖

在圖4中，變量p根據存儲-進位的形式表示，這樣就能夠使用進位保留加法器。

最后的操作包括計算p=pc+ps與p-m，其中pc和ps是(k+1)-bit數，m是k-bit數。假如不包括最后的操作，結構圖4時鐘周期的最小值約為2TFA，時鐘總數為k，則總的計算時間近似為2kTFA。在計算pc和ps的結果后，最后的步驟分為兩步：分別使用串行進位加法器計算pc與ps的和以及使用進位保留加法器、串行進位加法器計算pc、ps和minus_m的和，而進位保留加法器計算時間為TFA，相應的計算時間分別為kTFA和(k+1)TFA，則最后步驟的計算時間的最大值為(k+1)TFA，因此，總的時間消耗近似為：

T≈2kTFA+(k+1)TFA

(7)

式(7)中的第二項(k+1)TFA對應于最后的操作，該操作不能在一個時鐘周期內完成。

資源消耗情況：共使用609個Registers，1 738個LUTs，仿真結果如圖5所示。

圖5 Montgomery模乘法器仿真結果(mod p192)

編譯和仿真后得到Montgomery模乘法器的運行最高頻率為725.018MHz，運行的總時鐘數為213。根據公式：速度=最高頻率(主頻)/運行總時鐘數，經過計算得出運行速度：

725.018MHz/213=3 403 755次/秒

圖5中，x=(8055AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55)16，y=(96AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA55AA)16時，z=(371441BE41BE41BE7ABE092F97A126128FF7CF695DDAEC4C)16。經驗證，仿真結果正確。

接下來我們來觀察操作數為384-bit時，其操作仿真結果圖。

取模數：

m=p384=2384-2128-296+232-1=″fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000 000000ffffffff″。資源消耗情況：共使用1 208個Registers，3 467個LUTs，仿真結果如圖6所示。

圖6 Montgomery模乘法器仿真結果(mod p384)

編譯和仿真后得到Montgomery模乘法器的運行最高頻率為708.723MHz，運行的總時鐘數為380。根據公式：速度=最高頻率(主頻)/運行總時鐘數，經過計算得出運行速度：

708.723MHz/380=1 865 060次/秒

圖6中，X=′9807A0C5177CEF9817F58EA8BD4A8 D66503E9E22EAEA46EACF5BFCB0C6E683DDF80D5CF 2B3FB0D8B023E20CEE0475BD′，Y=′6EECFBD48A0A 4216F418049462C70894786708BB0D96F9B4C58240E3 AFF5E7E8F53DBCAAC99A62DF0BD6CF41BCE315F′， Z=′8AA51A52D7EE968848AED51E7941F 9C22DC5F2 F5DEBDE5424A977C3A6F08EBBB863A1AE97FBC5113 286BC2E98F5DFAB2′，經過計算后得出結果與仿真結果一致，驗證仿真結果的正確性。

優化前的結構圖，使用的是串行進位加法器，操作數長度為k位串行進位加法器的總資源為一個全加器單元面積的k倍，每一個全加器單元計算時都要等待其低位全加器單元的進位輸出。因此，總的時間消耗是一個全加器單元時間消耗的k倍，而整個實現結構是串行進行的，即每一步運算操作都要等待上一步運算操作完成后才能進行，因此實現速度較慢。

優化后的結構圖，所使用的加法器為進位保留加法器，運算時，將進位保留，開始輸入操作數并行運算，最后將運算的結果與進位的結果相加，只需兩步則得出最后的結果。因為整個結構是并行進行的，最終結果的時間消耗等于兩個FA(全加器)單元的時間消耗之和。因此大幅度地縮短了消耗時間，提升了速度。但因為需要寄存器保留進位，增加了其資源消耗。

現在，將優化前后Montgomery模乘法器做一個全面、系統的比較(本文所用的元器件為7vx980tffg1926-2)，如表1所示。

表1 Montgomery模乘法器優化前后比較

通過優化前后Montgomery模乘法器的運算速度、資源占用情況的對比，我們可以看出：操作數為192-bit時，雖然優化后的Montgomery模乘法器較優化前相比，寄存器、查找表LUTs分別多出50.3%、50.2%，但是運算速度卻比優化前的多出5.17倍。

操作數為384-bit時，優化后的Montgomery模乘法器較優化前相比，寄存器、查找表LUTs分別多出52.7%、46.7%，但是運算速度卻比優化前的多出8.53倍。

此外，我們增加了一個比較量，即速度(萬次/秒)/面積(LUT)，通過比較速度/面積，分析算法的效率。可以看出優化后的Montgomery模乘算法比優化之前的Montgomery模乘算法效率平均高出4倍以上。如表2所示。

表2 性能對比分析

通過上述對比分析，可以看出優化后的Montgomery模乘法器與優化前的相比，在資源占用方面平均約高出50%，但是速度卻平均高出6倍左右。當操作數較少(192-bit)時，速度高出5.17倍，但隨著操作數增大，資源占用高出50%左右，而速度卻高出8倍以上，優化效果明顯。可以看出，通過多消耗少量的資源達到了明顯提高速度的目的，這與設計原理一致。

將本文所設計優化的Montgomery乘法器與已有的Montgomery乘法器作比較，可以看出，本文優化后的蒙哥馬利乘法器相比于文獻[13]、文獻[6]在時間、最高時鐘頻率上都有所優化。文獻[13] 所用的元器件為2vp100ff1696-5，消耗LUTs的數目為5 188，最高時鐘頻率為100.0038MHz。文獻[6]的工藝為FPGA，面積為2135LUT。本文優化后的蒙哥馬利乘法器保持合理的可接受資源消耗的基礎上，提高運算速度，較好發揮性能潛力。

4 結 語

本文應用VHDL語言，利用Montgomery模乘算法，設計出Montgomery模乘法器，并用ISE開發工具和Modelsim仿真軟件對算法進行了仿真與測試，結果與理論一致，驗證其正確性。其次，根據開始實現Montgomery模乘法器的結構圖，將其串行運算的結構改進為并行運算結構，在多消耗少量資源的基礎上，實現了速度的快速提升，成功實現了Montgomery模乘法器的優化。

[1] 高獻偉,靳濟方,方勇,等.GF(2m)域乘法器的快速設計及FPGA實現[J].計算機工程與應用,2004,40(25):111-112,123.

[2] 葛亞明,彭永豐,薛冰,等.零基礎學FPGA[M].機械工業出版社,2010:17-29.

[3] 陳光化,朱景明,劉名,等.雙有限域模乘和模逆算法及其硬件實現[J].電子與信息學報,2010,32(9):2095-2010.

[4] 鄔貴明,謝向輝,吳東,等.高基模Montgomery模乘陣列結構設計與實現[J].計算機工程與科學,2014,36(2):201-205.

[5] 郭曉,蔣安平,宗宇.SM2高速雙域Montgomery模乘的硬件設計[J].微電子學與計算機,2013,30(9):17-21.

[6] 韓煉冰,黃銳,段俊紅,等.基于FPGA的素域模乘快速實現方法[J].信息安全與通信保密,2013(9):76-78.

[7] 周德金.32位高速浮點乘法器設計技術研究[D].江南大學,2008.

[8] 周軼男,李曦,朱兆國.橢圓曲線密碼算法的硬件設計與實現[J].計算機系統應用,2006(3):43-45,48.

[9] 孔凡玉.公鑰密碼體制中的若干算法研究[D].山東大學,2006.

[10] ?etinKayaKo?,TolgaAcar.AnalyzingandComparingMontgomeryMultiplicationAlgorithms[J].IEEEMicro,1996,16(3):26-33.

[11]RivcstR,ShamirA,AdlemanL.Amethodforobtainingdigitalsigna-turesandpublic-keycryptosystem[J].CommunicationsoftheACM,1978,21:120-126.

[12]FranciscoR.NewAlgorithmsandArchitecturesforArithmeticinGF(2(m))SuitableforEllipticCurveCryptography[D].Corvallis,OR,USA:OregonStateUniversity,2000.

[13] 梁鵬飛.基于流水線的Montgomery模乘算法硬件實現[D].華南理工大學,2011.

IMPLEMENTATION AND OPTIMISATION OF MONTGOMERY MULTIPLIER

Che Wenjie Dong Xiuze Gao Xianwei Zhang Xiaonan

(BeijingElectronicScienceandTechnologyInstitute,Beijing100070,China)

Montgomery algorithm is the basic algorithm of public key cryptography, which has a wide range of applications. Therefore, to improve the calculating speed of public-key cryptosystem, it is very important to design the Montgomery Multiplier with faster calculating speed, less resource consumption and high efficiency. This paper implements the Montgomery multiplier according to the Montgomery multiplication algorithm. It is designed and implemented respectively on FPGA by hardware description language and the implementation results are verified. Meanwhile, the implementation structure has been optimised(parallel one from serial one), which takes up 50% more resources but speed increases about 6 times. Compared with the existing relevant research results, the proposed multiplier achieves a substantial increase in speed on the basis of increasing consumption of fewer resources.

Montgomery algorithm Montgomery multiplier FPGA Hardware description language

2015-12-30。車文潔，碩士生，主研領域：密碼算法的硬件實現。董秀則，講師。高獻偉，教授。張曉楠，碩士生。

TP333.2

A

10.3969/j.issn.1000-386x.2017.03.056