GF(2m)域Montgomery模乘器的高效設(shè)計(jì)及FPGA實(shí)現(xiàn)

張 麗 董秀則 明嬌嬌 高獻(xiàn)偉,

1(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)2(北京電子科技學(xué)院 北京 100070)

0 引 言

隨著物聯(lián)網(wǎng)(IOT)的發(fā)展，通信安全的重要性日益增加，其安全問題引起了人們的廣泛關(guān)注。1949年，香農(nóng)發(fā)表了著名論文—《保密系統(tǒng)的通信理論》，密碼學(xué)作為一門獨(dú)立的科學(xué)從此形成。1976年，W.Diffie和M.E.Hellman提出了公鑰密碼的概念，從此密碼學(xué)的發(fā)展進(jìn)入了一個(gè)新的時(shí)代。公鑰密碼體制解決了傳統(tǒng)對(duì)稱密碼中密鑰分配的難題，不僅滿足計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用，而且易于實(shí)現(xiàn)數(shù)字簽名，所以迅速成為研究的焦點(diǎn)[1-2]。Neal Koblitz和Victor Miller于1985年提出橢圓曲線密碼體制(ECC)，其中，橢圓曲線離散對(duì)數(shù)問題(ECDLP)的困難性是保證ECC安全的基礎(chǔ)[3]，現(xiàn)在求解ECLDP的最佳算法仍然具有全指數(shù)時(shí)間復(fù)雜度。而應(yīng)用頗為廣泛的RSA公鑰密碼體制是基于整數(shù)因子分解的困難問題，目前該問題已出現(xiàn)亞指數(shù)時(shí)間算法。這說明在相同的安全水平下，橢圓曲線密碼使用的密鑰長(zhǎng)度要比RSA密碼短得多。例如普遍認(rèn)為，160位橢圓曲線密碼可以提供相當(dāng)于1 024位RSA密碼的安全強(qiáng)度[4]。由于密鑰短，帶寬占用少，所以工程實(shí)現(xiàn)的加解密速度較快，并且可以節(jié)省能源、存儲(chǔ)空間，使得ECC特別適合在航空、航天、衛(wèi)星及其智能卡等體系中應(yīng)用[5-6]。

橢圓曲線密碼體制自頂向下依次是算法協(xié)議層、ECC點(diǎn)運(yùn)算模塊層和底層有限域模運(yùn)算層。其中點(diǎn)乘運(yùn)算是整個(gè)密碼算法的核心模塊，其運(yùn)算速度更是決定著整個(gè)系統(tǒng)加解密的效率，而點(diǎn)乘的實(shí)現(xiàn)則是采取自下而上的調(diào)用結(jié)構(gòu)[7]，所以底層各有限域模運(yùn)算的效率就成為橢圓曲線加密的關(guān)鍵[8]。底層有限域運(yùn)算主要包括模加減、模乘和模逆等。其中，模逆運(yùn)算最為復(fù)雜耗時(shí)，在點(diǎn)運(yùn)算的調(diào)用過程中，通常通過轉(zhuǎn)換運(yùn)算坐標(biāo)系來降低模除法的出現(xiàn)頻次，或者將其轉(zhuǎn)換為相對(duì)易于進(jìn)行的模乘、模加/減和移位等操作，因此如何高效率、低成本快速地實(shí)現(xiàn)模乘是當(dāng)前的一個(gè)研究熱點(diǎn)。目前最為高效、研究較為廣泛的模乘算法是Montgomery模乘算法[9]。文獻(xiàn)[10]提出了一種Montgomery模乘算法在高基陣列上的優(yōu)化算法，顯著減少了時(shí)鐘周期數(shù)，但消耗資源較大，對(duì)于模乘基本處理單元的結(jié)構(gòu)還有待改進(jìn)。文獻(xiàn)[11]簡(jiǎn)化原始Montgomery算法的求商過程，設(shè)計(jì)模乘流水化陣列結(jié)構(gòu)，提高了Montgomery模乘的性能。文獻(xiàn)[12]結(jié)合Karatsuba算法提出一種基于全字的Montgomery模乘方案，降低了計(jì)算復(fù)雜度，但是硬件實(shí)現(xiàn)中占用了FPGA內(nèi)部大量DSP單元，使得該方案的可移植性與靈活性較差。

針對(duì)以上問題，本文結(jié)合FPGA硬件結(jié)構(gòu)的特點(diǎn)，提出一種基于k步長(zhǎng)迭代的串并結(jié)合Montgomery模乘器，不僅顯著減少了執(zhí)行一次模乘所需的時(shí)鐘數(shù)，還在速度與資源上取得最佳的折衷。

1 GF(2m)Montgomery模乘運(yùn)算

應(yīng)用在密碼學(xué)中的橢圓曲線按其奇偶性質(zhì)可分為兩大類，它們分別對(duì)應(yīng)于GF(p)和GF(2m)多項(xiàng)式，其中GF(p)中的橢圓曲線由于更適合硬件實(shí)現(xiàn)而被選作常用曲線。在橢圓曲線加密過程中，標(biāo)量乘是整個(gè)系統(tǒng)的核心運(yùn)算，而模乘又是其中的關(guān)鍵運(yùn)算。Montgomery模乘是目前計(jì)算模乘較快的算法。為了提高模乘的計(jì)算效率，本設(shè)計(jì)選擇GF(2m)域?qū)ontgomery模乘器進(jìn)行FPGA設(shè)計(jì)與實(shí)現(xiàn)。

1.1 GF(2m)基本模乘運(yùn)算

h(x)=a(x)b(x)modf(x)

(1)

由式(1)可以看出，傳統(tǒng)的計(jì)算模乘方法可分多項(xiàng)式相乘和對(duì)不可約多項(xiàng)式取模約化兩步進(jìn)行。即首先計(jì)算得到階為2m-2的d(x)=a(x)·b(x)，然后計(jì)算d(x)modf(x)，如Karatsuba-Ofman多項(xiàng)式乘法方案、Matrix-Vector乘法等，但計(jì)算速度都有待提高。因此，邊乘邊約化的Montgomery模乘算法補(bǔ)足了傳統(tǒng)模乘方案的短板，能夠達(dá)到較高的實(shí)現(xiàn)速度。

1.2 基本的Montgomery模乘算法

Montgomery模乘算法利用完全剩余系的性質(zhì)，采用簡(jiǎn)單移位代替求模過程中耗時(shí)的除法運(yùn)算，提高了模乘的計(jì)算效率[13]。設(shè)f(x)是GF(2)上的不可約多項(xiàng)式，選定多項(xiàng)式r(x)使得gcd(r(x),f(x))=1，則Montgomery模乘乘積的計(jì)算如下：

c(x)=a(x)b(x)r-1(x)modf(x)

(2)

式中：r-1(x)是r(x)對(duì)f(x)取模得到的逆。即：

r(x)r-1(x)+f(x)f′(x)=1

(3)

具體的Montgomery模乘的計(jì)算過程如算法1所示。

算法1GF(2m)上Montgomery模乘結(jié)構(gòu)

輸入：a(x),b(x),r(x),f′(x)

輸出：c(x)=a(x)b(x)r-1(x)modf(x)

1.t(x)=a(x)b(x)

2.u(x)=t(x)f′(x)modr(x)

3.c(x)=[t(x)+u(x)f(x)]/r(x)

由以上算法可知，為了得到計(jì)算結(jié)果c(x)，需要經(jīng)歷步驟1中的多項(xiàng)式乘法、步驟2中的取模運(yùn)算、最后還需要一次加法、多項(xiàng)式乘法和除法的操作。但是當(dāng)選取r(x)為單項(xiàng)式r(x)=xm時(shí)，由于f(x)是GF(2)上的不可約多項(xiàng)式，所以gcd(r(x),f(x))=1依然成立。此時(shí)結(jié)合硬件實(shí)現(xiàn)的特點(diǎn)，步驟2、步驟3中的乘法和除法操作便可以快速實(shí)現(xiàn)，任意多項(xiàng)式除以r(x)=xm的除法操作可轉(zhuǎn)變?yōu)橛乙苖位的移位運(yùn)算。而且當(dāng)逐比特掃描因子a(x)的系數(shù)時(shí)，預(yù)計(jì)f′(x)計(jì)算也可以避免，大大減少運(yùn)算的時(shí)間。改進(jìn)后的快速M(fèi)ontgomery模乘如算法2所示。

算法2GF(2m)上Montgomery模乘快速實(shí)現(xiàn)

輸入：a(x),b(x)，f(x)

輸出：c(x)=a(x)b(x)x-mmodf(x)

1.c(x)←0

2.i從0增加到m-1循環(huán)執(zhí)行：

3.c(x)←c(x)+aib(x)

4.c(x)←c(x)+c0f

按照硬件實(shí)現(xiàn)的結(jié)構(gòu)分，多項(xiàng)式乘法運(yùn)算可以分為全串行結(jié)構(gòu)、全并行結(jié)構(gòu)和串并混合結(jié)構(gòu)。觀察算法2中的步驟2可知，該方案是逐比特的處理數(shù)據(jù)，至少需要m個(gè)時(shí)鐘才可以完成。對(duì)應(yīng)到硬件實(shí)現(xiàn)時(shí)，即為全串行結(jié)構(gòu)。全串行結(jié)構(gòu)比較簡(jiǎn)潔，對(duì)于處理較小的數(shù)據(jù)速度很快，但是隨著密鑰長(zhǎng)度的增加，對(duì)于超長(zhǎng)位操作數(shù)，必然消耗大量的時(shí)鐘數(shù)。若采用串并混合結(jié)構(gòu)，算法2的效率將會(huì)得到有效提高。

2 Montgomery模乘器的優(yōu)化設(shè)計(jì)

為了達(dá)到較高的安全性要求，目前的密碼算法所使用的密鑰長(zhǎng)度越來越大，對(duì)硬件實(shí)現(xiàn)方式的要求也越來越高[14]。串行結(jié)構(gòu)簡(jiǎn)潔直觀，適合于小操作數(shù)運(yùn)算，而對(duì)于超長(zhǎng)位大數(shù)運(yùn)算，必然耗費(fèi)大量的時(shí)鐘數(shù)，無法滿足速度的要求。全并行結(jié)構(gòu)可以在一個(gè)時(shí)鐘內(nèi)完成全部的運(yùn)算，但是資源開銷巨大，對(duì)于資源受限的網(wǎng)絡(luò)設(shè)備，并沒有實(shí)際的使用價(jià)值。所以，為了提高M(jìn)ontgomery模乘的計(jì)算效率，找到基于全串行結(jié)構(gòu)與全并行結(jié)構(gòu)模乘器性能的平衡點(diǎn)，設(shè)計(jì)在一個(gè)時(shí)鐘內(nèi)進(jìn)行多步運(yùn)算的模乘算法，即可以在資源沒有增加太多的情況下大大減少時(shí)鐘的個(gè)數(shù)，從而提高M(jìn)ontgomery模乘器的性能。

為了詳細(xì)說明改進(jìn)后的Montgomery模乘結(jié)構(gòu)，首先引入k、t、r三個(gè)參數(shù)。其中，k表示一個(gè)時(shí)鐘內(nèi)執(zhí)行模乘核心運(yùn)算的步數(shù)，為了增加改進(jìn)后模乘器的靈活性，k可以選取大于0小于m的任意值。t表示執(zhí)行完一次模乘所需要的迭代次數(shù)，r表示m位操作數(shù)在執(zhí)行t個(gè)周期后剩余步數(shù)。顯然三個(gè)參數(shù)之間的關(guān)系可以表示如下:

m=k·t+r

(4)

算法3根據(jù)式(3)中的關(guān)系，對(duì)改進(jìn)后的GF(2m)域Montgomery模乘算法進(jìn)行具體描述：

所謂西學(xué)之用，實(shí)為清廷應(yīng)對(duì)日趨嚴(yán)峻的外交局面，有限度地變更舊制勢(shì)在必行，被壓抑的入侵文化的聲音也因此得以顯現(xiàn)于譯文，現(xiàn)代法律意識(shí)的雛形伴隨著殖民權(quán)力的擴(kuò)張悄然扎根。盡管如此，中學(xué)為體的理念根深蒂固。洋務(wù)運(yùn)動(dòng)的中堅(jiān)兩江總督張之洞在《勸學(xué)篇》中甚至將三綱五常提升到國(guó)家民族生死存亡的高度：“保種必先保教，保教必先保國(guó)”(2002：1)。即便到了十九世紀(jì)末，維新變法的代表康有為依然鼓吹：“必有宋學(xué)義理之體，而講西學(xué)政藝之用，然后收其用也?！?/p>

算法3改進(jìn)后的域Montgomery模乘運(yùn)算

輸入：a(x),b(x)，f(x),k,t,r,m

輸出：c(x)=a(x)b(x)x-mmodf(x)

1c(x)←0

2 for(i=0tot-1) loopi從0增加到t-1循環(huán)執(zhí)行：

for(j=0 tok-1) loop

2.1c(x)←c(x)+aib(x)

2.2c(x)←c(x)+c0f(x)

2.3c(x)←c(x)/x

3 如果r>0,則

3.1c(x)←c(x)+aib(x)

3.2c(x)←c(x)+c0f(x)

3.3c(x)←c(x)/x

否則，跳轉(zhuǎn)

3 高效Montgomery乘法器的硬件實(shí)現(xiàn)

為了進(jìn)一步詳細(xì)說明基于可變步長(zhǎng)的串并混合硬件結(jié)構(gòu)設(shè)計(jì)原理，給出基本結(jié)構(gòu)說明如圖1所示。其中Core是該Montgomery模乘器的核心運(yùn)算模塊，步驟1-步驟k表示一個(gè)時(shí)鐘周期內(nèi)進(jìn)行的k次迭代，PE表示單次迭代的數(shù)據(jù)通路結(jié)構(gòu)，其詳細(xì)電路設(shè)計(jì)如圖2所示[15]。將GF(2m)域中不可約多項(xiàng)式f(x)和乘因子b(x)對(duì)應(yīng)的二進(jìn)制串分別存入兩個(gè)循環(huán)移位寄存器中，然后控制中心在時(shí)鐘信號(hào)的作用下，周期性的存取數(shù)據(jù)以驅(qū)動(dòng)Core電路周期性執(zhí)行模乘運(yùn)算。由式(3)不難得出，該Montgomery模乘器計(jì)算一次模乘的周期數(shù)即為└m/k┘，與上面的討論一致，之所以對(duì)m/k向上取整，是因?yàn)閞>0時(shí)，需要再執(zhí)行一次剩余的迭代運(yùn)算。此處k>1,所以時(shí)鐘周期數(shù)定然小于m,進(jìn)而大大減少了計(jì)算Montgomery模乘的時(shí)間。

圖1 改進(jìn)后的Montgomery模乘結(jié)構(gòu)圖

圖2 Montgomery模乘單次迭代的關(guān)鍵路徑圖

由圖2可知，Montgomery模乘電路圖僅僅使用了簡(jiǎn)單的與門、異或門以及寄存器資源，并沒有使用任何的芯片內(nèi)部的DSP單元，便于移植，所以本方案不僅僅追求速度的提高，也注重靈活性和資源功耗的問題。

4 結(jié)果分析

為了公平合理的與文獻(xiàn)[1]、文獻(xiàn)[16-18]比較該模乘器的性能，本設(shè)計(jì)選擇NIST推薦的5個(gè)二進(jìn)制有限域F2163,F2233,F2283,F2409,F2571中的GF(2233)和GF(2163)分別進(jìn)行功能仿真驗(yàn)證,選取的GF(2)域上的不可約多項(xiàng)式分別是f(x)=x233+x74+1和f(x)=x163+x7+x6+x3+1。改進(jìn)后的Montgomery模乘器采用Verilog HDL硬件描述語言進(jìn)行代碼描述，并使用Modelsime 10.2a進(jìn)行功能仿真，有限域F2233上的一組數(shù)據(jù)仿真結(jié)果如圖3所示。其中一組測(cè)試矢量如下(十六進(jìn)制)：

a=233′H0FA C9DFCBAC 8313BB21 39F1BB75

5FEF65BC 391F8B36 F8F8EB73 71FD558B

b=233′H100 6A08A419 03350678 E58528BE

BF8A0BEF F876A7CA 36716F7E 01F81052

c=233′H169 4FAF37D6 04D3F2F5 6727F419

356344CB 90C4BC1C 51BCBE66 2A18E0E6

圖3 modelsime測(cè)試仿真圖

在功能仿真驗(yàn)證正確后，又使用Synopsys公司的Synplify Pro編譯器進(jìn)行綜合，綜合實(shí)現(xiàn)是基于FPGA硬件實(shí)現(xiàn)平臺(tái)，選用Xilinx Virtex2系列的xc2v3000芯片。當(dāng)單次迭代步數(shù)為k=14時(shí)，該模乘器的速度與資源取得最佳折衷，如圖4所示，此時(shí)僅僅用了17個(gè)時(shí)鐘周期。表1依據(jù)計(jì)算一次模乘所需要的時(shí)鐘周期數(shù)、最高時(shí)鐘頻率、時(shí)間作為比較要素和相關(guān)文獻(xiàn)進(jìn)行對(duì)比。

表1 GF(2m)域不同Montgomery模乘器的性能比較

表1給出文獻(xiàn)[1]、文獻(xiàn)[16]、文獻(xiàn)[17]、文獻(xiàn)[18]中各模乘器性能與本文優(yōu)化后的Montgomery模乘器性能的比較結(jié)果。由表中不難看出，文獻(xiàn)[16]中的模乘器頻率在各設(shè)計(jì)中是最高的，文獻(xiàn)[18]的資源占用在各模乘器中是最少的。但速度與資源的矛盾問題使得只考慮追求速度快或者資源占用少的方案是不可取的。所以，為了取得最佳的模乘器性能，所設(shè)計(jì)方案需平衡速度與資源，以取得兩者的最佳折衷。鑒于相關(guān)設(shè)計(jì)的實(shí)現(xiàn)平臺(tái)不同，比如文獻(xiàn)[16]使用Synopsys公司的Design Complier在SMIC 0.18 μm工藝庫(kù)下進(jìn)行的綜合，而文獻(xiàn)[17]選用了Xilinx Virtex2系列的xc2v3000芯片，文獻(xiàn)[18]選用Altera Stratix EP1S25F1020C5器件，本設(shè)計(jì)則是用Xilinx Virtex2系列的xc2v3000芯片，所以綜合工藝庫(kù)的不同使得直接比較并不合理。為了解決這一問題，引入?yún)?shù)C=A×T,其中A表示面積，T表示計(jì)算一次模乘的所需的時(shí)間。之所以選擇該參數(shù)，是因?yàn)樗軌蚓C合考慮執(zhí)行一次模乘時(shí)所需要的時(shí)鐘數(shù)、最大頻率以及占用面積這三個(gè)關(guān)鍵因素。參數(shù)C的具體含義如下所示：

(5)

式中：t為時(shí)鐘數(shù)目，f為最高頻率。由式(3)不難看出，當(dāng)C的值越大，也就標(biāo)志著消耗資源越多或者執(zhí)行模乘所需要的時(shí)鐘越多，而頻率f越小，即該模乘器的性能越低。反之，則表示模乘器的性能較高。據(jù)此得出各模乘器的C參數(shù)對(duì)比結(jié)果如圖4所示。

圖4 各Montgomery模乘器性能比較圖

由圖4不難看出，雖然文獻(xiàn)[16]的頻率最大，但是C參數(shù)的取值卻并不理想。文獻(xiàn)[18]中根據(jù)芯片的資源情況采用全局串行局部并行的結(jié)構(gòu)設(shè)計(jì)乘法器，可以看出該模乘器的效率是相對(duì)不錯(cuò)的。而本文的Montgomery模乘方案綜合考慮芯片資源與延時(shí)問題，依據(jù)算法設(shè)計(jì)中在單位時(shí)鐘周期內(nèi)所進(jìn)行的不定次循環(huán)迭代，對(duì)應(yīng)到硬件實(shí)現(xiàn)中的串并混合結(jié)構(gòu)，最終取得速度與面積的最佳折衷。所以本設(shè)計(jì)的Montgomery模乘器的效率在GF(2233)域和GF(2163)域都有很大提升。

5 結(jié) 語

為了提高橢圓曲線密碼體制中模乘運(yùn)算的效率，改進(jìn)后的Montgomery模乘算法將原算法中的逐位掃描運(yùn)算改為在單位時(shí)鐘內(nèi)進(jìn)行k步移位來計(jì)算模乘，大大減少了時(shí)鐘周期數(shù)。同時(shí)考慮資源占用情況，針對(duì)不同的操作數(shù)長(zhǎng)度選取特定步數(shù)k，以取得速度與資源的最佳折衷。然后根據(jù)硬件實(shí)現(xiàn)的特點(diǎn)，設(shè)計(jì)一種基于FPGA的串并混合結(jié)構(gòu)的Montgomery模乘器。通過與相關(guān)文獻(xiàn)的對(duì)比分析，本方案的模乘器不僅在速度與資源上有平衡的優(yōu)勢(shì)，而且更適合硬件實(shí)現(xiàn)，具有較高的靈活性與可移植性。