隨著計算機網(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ù)字長為w bit，字數(shù)為s=「n/w?骎，該算法描述如下：
        

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ù),降低運算速度。

    可以看出，采用這樣的流水線組織結構，兩級流水線之間的時鐘延遲已經(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得出，采用改進的流水線組織結構設計模乘單元，能夠達到與改進前流水線組織結構相近的時鐘頻率，并且由于減少了近一半的時鐘周期數(shù)，其模乘運算時間也大為縮短。

乘運算單元在運算速度方面略有劣勢，但在電路面積方面具有優(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 trialdivision[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.