摘 要： 針對FIOS類型的Montgomery模乘擴展算法的比特級-字級和字級-字級的兩種實現(xiàn)形式進行研究，設計多處理單元的流水線組織結構實現(xiàn)算法，并對模乘器進行雙有限域統(tǒng)一結構設計，使之能夠同時支持兩個有限域GF(p)和GF(2n)上的運算。最后對設計的兩種模乘器用Verilog硬件描述語言進行代碼描述,采用Synopsys公司的Design Compiler 在Artisan SIMC 0.18 μm typical工藝庫下綜合。實驗結果表明，該模乘器不僅在運算速度和電路面積方面各具有優(yōu)勢，而且具有運算長度可變的靈活性。
關鍵詞： 橢圓曲線加密算法； Montgomery模乘器； 比特級-字級算法； 字級-字級算法

隨著計算機網(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擴展算法，算法詳細內容可參閱文獻。
五種算法中,在不考慮并行實現(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和內部j=1這兩個過程經(jīng)兩個時鐘周期完成后，才能夠得到下一級流水線處理單元PU所需的(C(0)，S(0))，即此時才開始對A的第2個bit進行掃描。也就是說在第i個外部循環(huán)的第1個內部循環(huán)經(jīng)兩個時鐘周期完成后才可以開始第i+1個外部循環(huán)的運算，所以采用這種流水線組織形式，每級流水線之間的延遲為兩個時鐘周期。因為流水線每級間存在兩個時鐘周期的延遲，所以需要兩級寄存器用來存儲中間結果，而且這種流水線組織形式會增加時鐘周期數(shù),降低運算速度。