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

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

隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展和普及，信息安全問題越來越多地被人們所關(guān)注。公鑰密碼體制有效地解決了在公共信道上保護(hù)信息的抗抵賴性、身份認(rèn)證、密鑰分發(fā)等問題。橢圓曲線密碼ECC（Elliptic Curve Cryptography）是一種基于橢圓曲線離散對(duì)數(shù)問題的公鑰密碼，1985年分別由Miller [1]和Koblitz[2]獨(dú)立提出。相對(duì)于其他公鑰密碼系統(tǒng)，橢圓曲線密碼系統(tǒng)具有計(jì)算速度快、存儲(chǔ)空間小、帶寬要求低等優(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級(jí)n位全加器的延遲，極大地限制了電路的時(shí)鐘頻率。Bajard將Montgomery模乘算法擴(kuò)展到剩余數(shù)系統(tǒng)RNS(Residue Number System),并進(jìn)一步提高了模乘的性能，但數(shù)系轉(zhuǎn)換硬件實(shí)現(xiàn)復(fù)雜，并且不支持雙域運(yùn)算[4]。在對(duì)算法進(jìn)行硬件實(shí)現(xiàn)時(shí)，一般是將運(yùn)算數(shù)據(jù)分成若干個(gè)字，對(duì)運(yùn)算數(shù)據(jù)按字進(jìn)行處理，以提高算法并行度和電路時(shí)鐘頻率，參考文獻(xiàn)[5]提出了基于高基陣列的Montgomery模乘算法。
目前Montgomery模乘運(yùn)算的擴(kuò)展和優(yōu)化實(shí)現(xiàn)算法主要可以分為以下四種類型：比特級(jí)-完全長度BLFP(Bit-Level Full-Precision)算法；比特級(jí)-字級(jí)BLWL(Bit-Level Word-Level)算法；字級(jí)-完全長度WLFP(Word-Level Full-Precision)算法，對(duì)另一個(gè)運(yùn)算數(shù)據(jù)按完全長度進(jìn)行處理；字級(jí)-字級(jí)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ù)字長為w bit，字?jǐn)?shù)為s=「n/w?骎，該算法描述如下：


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