GF(2m)域Montgomery模乘器的高效設計及FPGA實現

張 麗 董秀則 明嬌嬌 高獻偉,

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

0 引 言

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

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

針對以上問題，本文結合FPGA硬件結構的特點，提出一種基于k步長迭代的串并結合Montgomery模乘器，不僅顯著減少了執行一次模乘所需的時鐘數，還在速度與資源上取得最佳的折衷。

1 GF(2m)Montgomery模乘運算

應用在密碼學中的橢圓曲線按其奇偶性質可分為兩大類，它們分別對應于GF(p)和GF(2m)多項式，其中GF(p)中的橢圓曲線由于更適合硬件實現而被選作常用曲線。在橢圓曲線加密過程中，標量乘是整個系統的核心運算，而模乘又是其中的關鍵運算。Montgomery模乘是目前計算模乘較快的算法。為了提高模乘的計算效率，本設計選擇GF(2m)域對Montgomery模乘器進行FPGA設計與實現。

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

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

(1)

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

1.2 基本的Montgomery模乘算法

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

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

(2)

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

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

(3)

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

算法1GF(2m)上Montgomery模乘結構

輸入：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)

由以上算法可知，為了得到計算結果c(x)，需要經歷步驟1中的多項式乘法、步驟2中的取模運算、最后還需要一次加法、多項式乘法和除法的操作。但是當選取r(x)為單項式r(x)=xm時，由于f(x)是GF(2)上的不可約多項式，所以gcd(r(x),f(x))=1依然成立。此時結合硬件實現的特點，步驟2、步驟3中的乘法和除法操作便可以快速實現，任意多項式除以r(x)=xm的除法操作可轉變為右移m位的移位運算。而且當逐比特掃描因子a(x)的系數時，預計f′(x)計算也可以避免，大大減少運算的時間。改進后的快速Montgomery模乘如算法2所示。

算法2GF(2m)上Montgomery模乘快速實現

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

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

1.c(x)←0

2.i從0增加到m-1循環執行：

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

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

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

2 Montgomery模乘器的優化設計

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

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

m=k·t+r

(4)

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

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

算法3改進后的域Montgomery模乘運算

輸入：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循環執行：

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

否則，跳轉

3 高效Montgomery乘法器的硬件實現

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

圖1 改進后的Montgomery模乘結構圖

圖2 Montgomery模乘單次迭代的關鍵路徑圖

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

4 結果分析

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

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測試仿真圖

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

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

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

(5)

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

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

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

5 結 語

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