加速有限域ＧＦ（２ｍ）上Ｍｏｎｔｇｏｍｅｒｙ乘法實現(xiàn)的指令集擴展研究

（西北工業(yè)大學(xué) 自動化學(xué)院， 西安 710072）

摘 要：通過擴展多項式乘法指令MULGF2和多項式乘加指令MAGF2來加速Montgomery算法的軟件實現(xiàn)。性能分析顯示，指令集擴展能夠顯著提高Montgomery算法的執(zhí)行效率，特別是同時擴展多項式乘法及乘加指令時效果更佳，且當處理器字長越大效果越明顯。

關(guān)鍵詞：指令集擴展；多項式乘法；多精度；有限域

中圖分類號：TP309；TP301.6 文獻標志碼：A

文章編號：10013695(2009)01035603

Instruction set extension for accelerating Montgomery multiplication in GF(2m)

LI Meifeng，DAI Guanzhong，LIU Hang，HU Wei

(College of Automation， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:This paper introduced instruction set extension to accelerate the software implementation of Montgomery multiplication in GF(2m).The performance estimate results show that instruction set extension can rapidly increase the implementation efficiency， especially when polynomials multiplication instruction MULGF2 and polynomials multiplyaccumulate instruction MAGF2 are both available， and the larger the word size of processor is， the better the performance is.

Key words:instruction set extension；polynomial multiplication；multiprecision；finite field

0 引言

有限域在密碼算法領(lǐng)域有著廣泛的應(yīng)用，如橢圓曲線密碼（elliptic curve cryptosystems，ECC）和DiffieHellman密鑰交換算法等。這些算法中，冪操作是其核心運算。采用二進制方法求冪時，冪運算轉(zhuǎn)換為乘法（包括平方）運算的多次迭代來實現(xiàn)，以GF(2m)上的ECC為例，乘法運算占據(jù)了最多99%的加解密時間[1]。因此，乘法運算的快速與否直接決定了冪運算的效率。

Montgomery算法是實現(xiàn)有限域乘法最有效的方法，它通過簡單的移位運算來代替復(fù)雜的除法運算，在一定程度上提高了有限域乘法的實現(xiàn)效率。GF(2m)上的Montgomery乘法中包含了大量的多項式乘法運算，而現(xiàn)今的處理器體系結(jié)構(gòu)大多數(shù)都是基于整數(shù)功能單元的，對于多項式乘法沒有相應(yīng)的指令支持。因此，這些處理器上的多項式乘法運算是通過移位和異或指令來仿效的[2]，效率很低。

指令集擴展是加速軟件實現(xiàn)速度的一種有效途徑，它面向特定的應(yīng)用對處理器指令進行擴展，采用硬件實現(xiàn)影響算法軟件性能的關(guān)鍵操作，并在指令集中添加相應(yīng)的指令。這種方法既保留了軟件實現(xiàn)的靈活性，又進一步提升了系統(tǒng)性能，因此，在最近幾年引起了廣泛關(guān)注。文獻[3]中增強了MIPS 4K處理器的體系結(jié)構(gòu)，并擴展了移位指令SHA和特殊乘加指令M2ADDU，從而加速RISC處理器上Montgomery乘法的速度，但是所基于的有限域為素數(shù)域GF(P)。文獻[4~6]中擴展了多項式乘法指令MULGF來加速二進制擴域GF(2m)上ECC算法的執(zhí)行速度。

本文通過分析有限域GF(2m)上Montgomery乘法的多精度算法，發(fā)現(xiàn)內(nèi)循環(huán)每個多項式乘法后都有兩個XOR運算，因此，提出了用于加速上Montgomery乘法的乘加指令MAGF2指令。通過引入MULGF2和MAGF2指令，Montgomery算法的計算性能得到顯著提高。

1 GF(2m)上的運算

11 域元素

有限域GF(2m)上的元素可以用不同的基來表示，本文中對于Montgomery乘法的描述都是基于多項式基。GF(2m)上任何一個元素均可表示成一個長度為m的多項式，如下所示：

a(x)=m-1i=0aixi=am-1xm-1+am-2xm-2+…+a1x+a0

其中：系數(shù)ai∈GF(2)。

GF(2m)上任何一個元素a可以表示長度為m的比特串(am-1am-2…a1a0)。當采用多精度算法時，將比特串劃分成s個等長字串，通常字串的長度等于處理器的字長w。因此，A可以表示成(As-1As-2…A1A0)。其中：Ai=(aiw+w-1aiw+w-2…aiw+1aiw)；s=[m/w]。

12 域運算

加法：如果a=(am-1am-2…a1a0)和b=(bm-1bm-2…b1b0)為GF(2m)中元素，則

a+b=c=(cm-1cm-2…c1c0)，ci=(ai+bi) mod 2=ai XOR bi

加法通過對應(yīng)比特位之間的異或運算來完成，這在處理器上非常容易實現(xiàn)。

乘法： 如果a=(am-1am-2…a1a0)和b=(bm-1bm-2…b1b0)為GF(2m)中元素，n=(nmnm-1…n1n0)為GF(2m)上度為m的既約多項式，則

a*b=c=(cm-1cm-2…c1c0），c(x)=a(x)b(x) mod n(x)

乘法運算需要先計算出兩個多項式的乘積，然后對既約多項式求模。其中a(x)與b(x)進行的乘法即位多項式乘法，與整數(shù)乘法不同的是，計算的過程中沒有進位。

2 GF(2m)上的Montgomery算法

Montgomery算法是加速有限域上乘法運算最有效的方法。它通過增加額外的乘法運算從而避免了計算余數(shù)所必需的除法運算，在一定程度上提高了有限域乘法的計算效率。GF(2m)上的Montgomery乘法如算法1所示。其中：a(x)、b(x)為GF（2m）上的元素；r(x)、n(x)為GF(2)上度為m的多項式，n（x）為既約多項式；r(x)與n(x)互素，存在多項式r-1(x)和n′(x)使得r(x)r-1(x)+n(x)n′(x)=1，且r-1(x)r(x)=1 mod n(x)。

算法1 GF(2m)上的Montgomery乘法

輸入：a(x)， b(x)， r(x)，n′(x)

輸出：c(x) = a(x)b(x)r-1(x)mod n(x)

S1.t(x):=a(x)b(x)

S2.u(x):=t(x)r-1mod r(x)

S3.c(x) := [t(x)+u(x)n(x)]/r(x)

當處理器上實現(xiàn)Montgomery算法時，由于處理器的字長遠遠小于操作數(shù)的位寬，通常將操作數(shù)劃分成等于處理器字長的多個字段，然后進行計算。GF(2m)上Montgomery乘法的多精度實現(xiàn)如算法2所示。其中n′0(x)為n′(x)的最低w位，取r(x)=xm。為了與整數(shù)乘法以示區(qū)別，下文中采用表示多項式乘法。

算法2 GF(2m)上Montgomery乘法的多精度實現(xiàn)

3 指令集擴展及性能評價

31 指令集擴展

Montgomery乘法的多精度實現(xiàn)中，有限域的乘法是通過多項式乘法和異或運算的多次迭代來完成的。異或運算在通用處理器中有對應(yīng)的指令，且在一個時鐘周期內(nèi)完成。當處理器中沒有多項式乘法指令時，多項式乘法是通過異或指令和移位指令來仿效的。一次w*w位的多項式乘法運算是通過2w條移位指令和w條異或指令來完成的[2]，共需要3w個時鐘周期，效率很低。

為了加速多項式乘法的執(zhí)行速度，通常用硬件來實現(xiàn)多項式乘法的工作邏輯，而相應(yīng)地在指令集中添加相應(yīng)的多項式乘法指令MULGF2 [4~6]。MULGF2的格式及功能如下所示：

MULGF2RdHi， RdLo， Rm，Rs

功能描述：（RdHi，RdLo）=RmRs

其中:Rm和Rs為兩個w位的源操作數(shù)；Rd為2w位的目的操作數(shù)，用于存放多項式乘法的結(jié)果。

算法2內(nèi)循環(huán)中，每個MULGF2運算之后均有兩個異或運算對乘法的輸出結(jié)果進行累加。如果能夠?qū)ULGF2和隨后的兩個異或運算用一條多項式乘加指令MAGF2來完成，且MAGF2指令與MULGF2指令周期數(shù)相同，則可以顯著降低內(nèi)循環(huán)所耗費的時鐘周期數(shù)。MAGF2的格式及功能定義如下：

MAGF2RdHi， RdLo， Rm，Rs

功能描述：（RdHi，RdLo）=（RdHi，RdLo）XOR （RmRs）

MAGF2指令中，將RmRs的結(jié)果與Rd相異或，然后將結(jié)果存儲在Rd中。由于RmRs的結(jié)果最多為2w位，而Rd也為2w位，且異或操作不產(chǎn)生進位，最終的計算結(jié)果仍然最多為2w位。

在處理器中實現(xiàn)新增指令的功能要求，共有三種途徑，即增加新的功能單元、擴展已有的功能單元和引入功能單元之間的接口[7]。現(xiàn)今的多數(shù)RISC處理器中均有對整數(shù)乘法和乘加指令的支持，而且多項式乘法能夠很容易地集成到整數(shù)乘法器的數(shù)據(jù)路徑中形成雙域乘法器。因此，多項式乘法和乘加指令的擴展僅需要將原來的整數(shù)乘法器修改為雙域乘法器即可，雙域乘法器的設(shè)計可以參看文獻[8，9]。

32 性能評價

本節(jié)對于擴展指令前后Montgomery乘法的計算性能進行了比較，這是通過統(tǒng)計算法所采用計算指令的個數(shù)以及所耗費的時鐘周期數(shù)來完成的，所涉及到的指令包括異或指令、移位指令、MULGF2和MAGF2指令。

通常認為異或和移位指令能夠在一個時鐘周期內(nèi)完成，而MULGF2指令則需要三個時鐘周期[4]；一次ww位MULGF2運算需要2w條移位指令和w條異或指令來仿效[2]。MULGF2運算顯然要比異或運算復(fù)雜得多。MAGF2指令的數(shù)據(jù)通路延時主要耗費在MULGF2運算上，因此，可以認為MAGF2和MULGF2指令耗費同樣多的時鐘周期數(shù)。實驗如表1、2所示。

在未進行指令擴展的通用處理器上執(zhí)行一次Montgomery乘法所需要的計算指令數(shù)目及耗費的時鐘周期數(shù)見表2，此時認為多項式乘法通過移位（SHIFT）和異或（XOR）指令來仿效。指令擴展后執(zhí)行一次Montgomery乘法所需要的計算指令數(shù)目及耗費的時鐘周期數(shù)如表3和4所示。

當前的通用處理器主要有32和64 bit，因此，僅考慮w=32和w=64時指令擴展對Montgomery乘法的性能提升。由表1可知指令擴展前執(zhí)行一次Montgomery算法需要的時鐘周期數(shù)為T0=(6w+4)s2+3ws；當w=32時，T0=196s2+96s，當w=64時，T0=388s2+192s。表4和5給出了m取不同數(shù)值時指令擴展前后的加速比σ的取值。其中：σ1為僅引入MULGF2指令后的加速比；σ2為同時引入MULGF2和MAGF2后的加速比。σ1=T0/T1，σ2=T0/T2，T1=10s2+3s， T2=6s2+5s。

表4 w=32時擴展指令后的加速比

4 結(jié)束語

Montgomery算法是實現(xiàn)有限域乘法最有效的方法。由于其中包含大量的多項式乘法運算而使其在通用處理器上效率很低。本文通過指令集擴展來加速GF(2m)上Montgomery算法的執(zhí)行效率。32位的處理器上，擴展多項式乘法指令MULGF2后，執(zhí)行效率提高將近二十倍，而同時擴展MULGF2和多項式乘加指令MAGF2后則加速比大于31。64 bit的處理器上，相應(yīng)的加速比可以達到40~60。顯然，指令集擴展能夠顯著提高Montgomery算法的執(zhí)行效率，特別是同時擴展多項式乘法及乘加指令時效果更佳，當處理器字長越大效果越明顯。

參考文獻：

［1］

GAUBATZ G.Versatile montgomery multiplier architectures[R].[S.l.]:Faculty of the Worcester Polytechnic Institute，2002.

[2]KOC C K，ACAR T.Montgomery multiplication in GF(2m)[J].Des Codes Cryptography，1998，14(1):5769.

[3]GROBSCHADL J，POSCH K C，TILLICH S.Architectural enhancements to support digital signal processing and publickey cryptography[C]//Proc of the 2nd Workshop on Intelligent Solutions in Embedded Systems (WISES2004).Graz:[s.n.]，2004:129143.

[4]BARTOLINI S，BRANOVIC I，GIORGI R，et al.A performance evaluation of ARM ISA extension for elliptic curve cryptography over binary finite fields[C]//Proc of the 16th Symposium on Computer Architecture and High Performance Computing.Washington DC:IEEE Computer Society Press，2004.

[5]GROBSCHADL J，KAMENDJE G A.Instruction set extension for fast elliptic curve cryptography over binary finite fields GF(2m)[C]//Proc of the 14th Conference on Applicationspecific Systems，Architectures and Processors.Washington DC:IEEE Computer Society Press，2003.

[6]BARTOLINI S，BENNATI P，GIORGI R，et al.Elliptic curve cryptography support for ARM based embedded systems[C]//Proc of ACACES’06.2006.

［7］GSCHWIND M.Instruction set selection for ASIP design[C]//Proc of the 7th International Symposium on Hardware/Software Codesign (CODES’99).New York:ACM Press，1999:711.

[8]SAVAS E，TENCA A F，KOC C K.A scalable and unified multiplier architecture for finite fields GF(p) and GF(2m)[C]//Proc ofCryptographic Hardware and Embedded Systems.London:SpringerVerlag，2000:277292.

[9]SUDHAKAR M，KAMALA R V，SRINIVAS M B.A unified’reconfigurable architecture for Montgomery multiplication in finite fields GF(p) and GF(2n)[C]//Proc of the 20th International Conference on VLSI Design (VLSID’07).Washington DC:IEEE Computer Society，2007：750755.