基于FIOS類型的Montgomery雙域模乘器設(shè)計(jì)*

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

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

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

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

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

1 FIOS類型的Montgomery模乘算法

Montgomery模乘算法按求乘法部分積與約簡運(yùn)算結(jié)合方式的不同，參考文獻(xiàn)[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擴(kuò)展算法，算法詳細(xì)內(nèi)容可參閱文獻(xiàn)。

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

1.1 BLWL類型的FIOS算法

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

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

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

1.2 WLWL類型的FIOS算法

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

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

2 兩種算法的流水線組織結(jié)構(gòu)分析

2.1 BLWL類型算法的流水線組織結(jié)構(gòu)

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

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

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

2.2 WLWL類型算法的流水線組織結(jié)構(gòu)

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

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

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

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

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

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

4 性能分析和比較

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

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

表1 BLWL算法改進(jìn)流水線組織結(jié)構(gòu)實(shí)現(xiàn)結(jié)果

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

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

表2 WLWL算法流水線組織結(jié)構(gòu)實(shí)現(xiàn)結(jié)果

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

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

[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]胡進(jìn)，何德彪，陳建華.基于高基陣列乘法器的高速模乘單元設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(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é)處理器設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī),2005,22(5):8-12.