楊曉輝 ，王雪瑞 ，秦 帆 ，張永福

(1.信息工程大學 電子技術學院，河南 鄭州450004;2.河南工程學院，河南 鄭州 451191)

隨著計算機網(wǎng)絡的發(fā)展和普及，信息安全問題越來越多地被人們所關注。公鑰密碼體制有效地解決了在公共信道上保護信息的抗抵賴性、身份認證、密鑰分發(fā)等問題。橢圓曲線密碼 ECC（Elliptic Curve Cryptography）是一種基于橢圓曲線離散對數(shù)問題的公鑰密碼，1985年分別由Miller[1]和Koblitz[2]獨立提出。相對于其他公鑰密碼系統(tǒng)，橢圓曲線密碼系統(tǒng)具有計算速度快、存儲空間小、帶寬要求低等優(yōu)點，特別適用于各種無線設備和智能卡等計算資源受限的設備，因而受到了人們的廣泛關注，成為新一代公鑰密碼標準。而模乘運算是橢圓曲線加密算法中的核心運算，如何高效地實現(xiàn)模乘運算是當前的一個研究熱點。

Montgomery模乘算法[3]是目前應用最為廣泛、同時也是最為高效的模乘算法。但Montgomery模乘算法存在的主要問題是模乘運算數(shù)據(jù)長度固定，不具備可配置性。另一個缺陷就是模乘運算的數(shù)據(jù)路徑延遲達到2級n位全加器的延遲，極大地限制了電路的時鐘頻率。Bajard將Montgomery模乘算法擴展到剩余數(shù)系統(tǒng)RNS(Residue Number System),并進一步提高了模乘的性能，但數(shù)系轉換硬件實現(xiàn)復雜，并且不支持雙域運算[4]。在對算法進行硬件實現(xiàn)時，一般是將運算數(shù)據(jù)分成若干個字，對運算數(shù)據(jù)按字進行處理，以提高算法并行度和電路時鐘頻率，參考文獻[5]提出了基于高基陣列的Montgomery模乘算法。

目前Montgomery模乘運算的擴展和優(yōu)化實現(xiàn)算法主要可以分為以下四種類型：比特級-完全長度BLFP(Bit-Level Full-Precision)算法；比特級-字級 BLWL(Bit-Level Word-Level)算法；字級-完全長度WLFP(Word-Level Full-Precision)算法，對另一個運算數(shù)據(jù)按完全長度進行處理；字級-字級WLWL(Word-Level Word-Level)算法。因為BLFP和WLFP類型的算法與原始Montgomery模乘算法存在相同的缺陷，所以考慮到設計高效的模乘運算單元，本文基于BLWL和WLWL這兩種類型的算法,結合FIOS(Finely Integrated Operand Scanning)Montgomery模乘擴展算法，提出了一種Montgomery雙域模乘器實現(xiàn)方案。結果表明,相比較于傳統(tǒng)的Montgomery模乘器，本文的設計減少了近一半的時鐘周期數(shù)，不僅大大提高了模乘運算速度，而且支持運算長度可配置的兩個有限域GF(p)和GF(2n)的模乘運算，提高了模乘處理的靈活性。

1 FIOS類型的Montgomery模乘算法

Montgomery模乘算法按求乘法部分積與約簡運算結合方式的不同，參考文獻[6]提出了SOS(Separated Operand Scanning)、CIOS (Coarsely Integrated Operand Scanning)、FIOS(Finely Integrated Operand Scanning)、FIPS(Finely Integrated Product Scanning)、CIHS(Coarsely Integrated Hybrid Scanning)這五種不同類型的Montgomery擴展算法，算法詳細內(nèi)容可參閱文獻。

五種算法中,在不考慮并行實現(xiàn)算法的前提下，F(xiàn)IOS算法的運算量最少。

1.1 BLWL類型的FIOS算法

為縮短電路數(shù)據(jù)路徑中的延遲，首先將BLWL類型的FIOS算法中的中間變量全部采用TS-TC這樣的冗余數(shù)表示,以進位保留加法運算完成算法中的加法運算。在算法中以這樣的形式表示進位保留加法 (TC,TS)=X+Y+Z。算法中Ai表示A的第i位，B(i)表示B的第i個字，運算數(shù)據(jù)字長為wbit，字數(shù)為s=「n/w，該算法描述如下：

GF(p)上BLWL類型FIOS模乘算法[7]

GF(p)的Montgomery模乘算法可以擴展到GF(2n)上來，算法中的加法運算為簡單的“異或”操作，沒有進位產(chǎn)生。

1.2 WLWL類型的FIOS算法

為進一步縮短運算周期，提高速度，可以將BLWL類型的FIOS模乘算法擴展為WLWL類型的算法。WLWL類型算法每次對兩個運算數(shù)據(jù)和模數(shù)的一個字進行掃描，所以相比較于BLWL類型算法，可以進一步縮短運算所需周期。該算法在縮短運算周期的同時，由于采用字乘字的乘法器增加了電路的面積和復雜度。算法中Ai表示A的第i個字，運算數(shù)據(jù)字長為wbit,字數(shù)為s=「n/w，W=2w，modW，該算法同樣可以擴展到GF(2n)上來，其中加法運算為簡單的“異或”操作。

算法描述如下：GF(p)上WLWL類型FIOS模乘算法[8]

2 兩種算法的流水線組織結構分析

2.1 BLWL類型算法的流水線組織結構

通過對算法1的分析研究，可以采用多處理單元的流水線結構來實現(xiàn)算法。流水線運算流程如圖1所示，每一豎列表示一級流水線，每一橫行表示一個運算周期，其中X和Y為運算處理單元。從圖1可以看出，在外部循環(huán)i=0和內(nèi)部j=1這兩個過程經(jīng)兩個時鐘周期完成后，才能夠得到下一級流水線處理單元PU所需的(C(0)，S(0))，即此時才開始對A的第 2個 bit進行掃描。也就是說在第i個外部循環(huán)的第1個內(nèi)部循環(huán)經(jīng)兩個時鐘周期完成后才可以開始第i+1個外部循環(huán)的運算，所以采用這種流水線組織形式，每級流水線之間的延遲為兩個時鐘周期。因為流水線每級間存在兩個時鐘周期的延遲，所以需要兩級寄存器用來存儲中間結果，而且這種流水線組織形式會增加時鐘周期數(shù),降低運算速度。

采用以上的流水線組織結構，每級流水線之間存在兩個時鐘的周期延遲，這是因為必須在上一級流水線的第2個運算單元計算出S(1)之后，才能得到下一級流水線的第1個運算單元要進行計算所需要的S(0)，此時下一級的流水線才能夠開始。實際上在上一級流水線的第1個運算單元計算完成后，已經(jīng)產(chǎn)生新的S(0)的低w-1 bit，第2個運算單元運算完成后才產(chǎn)生S(0)的最高一個bit。所以每一級流水線的第一個運算單元可以采用由上級流水線運算單元產(chǎn)生的S(0)，即采用(0,)和(1,)分別進行計算，得到兩個結果，由上級流水線的第2個運算單元產(chǎn)生的這一bit數(shù)對這兩個數(shù)據(jù)計算得到的結果進行選擇。經(jīng)過改進的流水線組織如圖2所示。

可以看出，采用這樣的流水線組織結構，兩級流水線之間的時鐘延遲已經(jīng)由2個時鐘縮短為1個時鐘。所以在存在足夠的運算單元的條件下，完成兩個位數(shù)據(jù)的模乘運算需要n+e-1個時鐘周期，而采用改進前的流水線組織結構則時需要2n+e-1個時鐘周期[4]。

2.2 WLWL類型算法的流水線組織結構

通過對算法2的分析研究，模乘運算的多處理單元流水線運算流程中，在i=0及j=1這兩步運算完成后，得到下一級流水線處理單元X進行運算所需的T0，這時開始進行由A的第2個字對B的逐字掃描。也就是說在第i個外部循環(huán)的第1個內(nèi)部循環(huán)完成后可以開始進行第i+1個外部循環(huán)。所以說對于WLWL類型算法，在不同的i循環(huán)之間存在并行性，采用多處理單元流水線的設計方式可以提高運算效率，相鄰兩級流水線之間的延遲為兩個處理單元的運算時間。

若流水線中有不少于k=「s/2個處理單元，流水線運算將連續(xù)地進行下去，不會因為沒有空閑的處理單元而停頓部分時鐘周期，所以完成兩個n位數(shù)據(jù)的模乘運算需要3s-1個時鐘周期。當電路中的處理單元少于k=「s/2個，流水線運算將會因為沒有空閑的處理單元而停頓部分時鐘周期，此時完成模乘運算需要(「n/2k-1)(「s/2+1-k)+3s-1 個時鐘周期。

3 算法的硬件實現(xiàn)

根據(jù)算法1和算法2以及前面對于BLWL算法和WLWL算法流水線結構的分析，基于FIOS類型Montgomery雙域模乘器的整體硬件實現(xiàn)結構如圖3所示。

圖中，雙域模乘器整體結構主要由數(shù)據(jù)輸入和輸出、狀態(tài)機控制、模乘運算等單元構成。數(shù)據(jù)的輸入和輸出單元與外部的數(shù)據(jù)接口寬度可以根據(jù)具體的應用環(huán)境進行靈活設計，外部數(shù)據(jù)的寫操作和輸出結果數(shù)據(jù)的讀操作均在狀態(tài)機控制模塊的控制下完成，數(shù)據(jù)輸入單元中各個操作數(shù)寄存器的數(shù)據(jù)輸出同樣也在狀態(tài)機控制模塊的控制下完成，所有控制信號由輸入的數(shù)據(jù)長度值產(chǎn)生。

模乘運算電路的主要功能單元有流水線處理單元X和Y，對于BLWL算法的模乘器需要每級流水線最后一步移位運算的移位單元Z；而對于WLWL算法的模乘器則不需要。對于BLWL算法的模乘器，模乘運算電路每個時鐘輸出w bit的TS和TC值，若進行的是二進制域上的運算，那么TS直接就是最終運算結果，進行素數(shù)域上運算時，需要將TS和TC值相加得到最終運算結果。模乘單元每個時鐘周期輸出w bit的TS和TC，所以只需要一個w bit的加法器與模乘單元按流水線方式進行計算。對于WLWL算法的模乘器，模乘運算單元的整體電路中不需要位加法器對冗余表示數(shù)進行數(shù)據(jù)轉換。

4 性能分析和比較

在設計可配置模乘電路時，考慮到NIST推薦的有限域長度，并根據(jù)以上對模乘運算流水線組織結構的分析，本文在BLWL類型模乘運算單元電路中設計1個處理單元X和17個處理單元Y，在WLWL類型運算單元電路中設計1個處理單元X和8個處理單元Y。這樣兩種模乘運算單元均支持長度在163～571 bit之間任意數(shù)據(jù)的運算，并保證流水線運算連續(xù)進行?；谶\算部件的關鍵路徑延遲與運算速度折衷的考慮，選擇32作為運算數(shù)據(jù)字長和電路接口寬度。將以上設計的模乘器用VerilogHDL硬件語言進行代碼描述，并使用ModelSim SE 6.0c進行功能仿真。在功能仿真正確后，使用Synopsys公司的 Design Complier在 SIMC 0.18 μm工藝庫下進行綜合。

對于BLWL算法，采用改進的流水線組織結構模乘單元實現(xiàn)結果如表1所示。表格中的周期數(shù)為模乘運算和最終進行字加法運算以及減法運算共需的周期數(shù)。

表1 BLWL算法改進流水線組織結構實現(xiàn)結果

由表1得出，采用改進的流水線組織結構設計模乘單元，能夠達到與改進前流水線組織結構相近的時鐘頻率，并且由于減少了近一半的時鐘周期數(shù)，其模乘運算時間也大為縮短。

對于WLWL算法，由于字與字的乘法運算和加法運算的延遲較大，并且不能將這幾級的乘法和加法運算做并行化處理，所以為提高模乘電路的時鐘頻率和匹配流水線運算時序，本文對處理單元X和Y均采用五時鐘設計，即處理單元完成一次運算需要5個時鐘周期。實現(xiàn)結果如表2所示。

表2 WLWL算法流水線組織結構實現(xiàn)結果

由于電路的綜合環(huán)境和仿真平臺不同，只能將本文設計與其他一些國內(nèi)外先進設計作大致的比較。表3列出了本文設計的模乘器與其他文獻中的模乘運算單元的性能比較。因為這些參考文獻中的模乘運算單元最高支持256 bit數(shù)據(jù)的運算，為進行比較，對本文設計同樣考慮可以最高支持256 bit數(shù)據(jù)運算時的情況。如表3所示，與參考文獻[8]中采用乘法器的設計相比，WLWL類型模乘運算單元在運算速度方面略有劣勢，但在電路面積方面具有優(yōu)勢，若采用相同的工藝，WLWL類型模乘運算單元電路時鐘頻率會更高，因而運算速度會更優(yōu)。與參考文獻[8]中采用乘法器的設計相比，BLWL類型模乘運算單元雖然電路面積較大,但在運算速度方面具有優(yōu)勢。

本文基于FIOS的Montgomery模乘算法,設計了BLWL和WLWL類型的雙域模乘運算單元。根據(jù)以上的分析和比較，本文設計的兩種模乘運算單元在電路面積和運算速度方面各有優(yōu)勢，而且具有運算長度可配置功能,支持目前橢圓曲線密碼576 bit長度以內(nèi)的有限域模乘運算具備了很大的靈活性，滿足現(xiàn)代通信網(wǎng)絡對公鑰密碼處理高速性和靈活性的要求。

[1]MILLER V S.Use of elliptic curves in cryptography[C].Proc.of CRYPTO’85.Berlin:Springer-Verlag,1986:417-426.

[2]KOBLITZ N,Elleptic curve cryptosystems[J].Mathematics of computation,1987,48(4):203-209.

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

[4]BAJARD J C,KAIHARA M,PLANTARD T.Selected RNS bases for modular multiplication[J].IEEE computer society,2009,20:25-32.

[5]胡進，何德彪，陳建華.基于高基陣列乘法器的高速模乘單元設計與實現(xiàn)[J].計算機工程與設計，2010，31(6):1202-1204.

[6]KOC C K,ACAR T.Analyzing and comparing montgomery multiplication algorithms[J].IEEE.Micro,1996,16(3):26-33.

[7]SAVAS E,TENCA A F,KOC C K.A scalable and unified multiplier architecture for fields GF(p)and GF(2m)[C].Cryptographic Hardware and Embedded Systems(CHES 2000).New York:Springer-Verlag,2000:1-20.

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

[9]史焱,吳行軍.高速雙有限域加密協(xié)處理器設計[J].微電子學與計算機,2005,22(5):8-12.