0 引言

公鑰密碼體制以其獨特的理論依據(jù)很好地填補了密碼領(lǐng)域的空缺。它在密鑰分發(fā)、身份認證等方面具有明顯優(yōu)勢。1985年Neal Koblitz和Victor Miller分別獨立提出了橢圓曲線在密碼學(xué)中的應(yīng)用。作為三大公鑰密碼體制之一，橢圓曲線密碼體制具有相同粒度更難破解、單位比特安全強度更大的特點。

橢圓曲線密碼運算在底層結(jié)構(gòu)設(shè)計時，主要包括模加減、模乘和模除、模逆。其中，模除和模逆運算最為復(fù)雜，通常通過轉(zhuǎn)換運算坐標來降低其實現(xiàn)復(fù)雜度，且使用頻率不是很高。而模乘和模加減運算使用更為頻繁。如何高效率、低成本地實現(xiàn)模乘模加減是當前的一個研究熱點。1985年Montmery提出了一種全新的模乘算法，他將普通模乘的運算轉(zhuǎn)換到Montgomery剩余類中進行，其所有大數(shù)均規(guī)約到了剩余類中，計算大幅度簡化。Montgomery模乘算法是目前最為常見的模乘實現(xiàn)方法，但傳統(tǒng)的算法具有算法粒度固定、關(guān)鍵運算路徑過長的缺陷，而且不支持雙有限域運算。文獻[2]提出了一種Montgomery模乘算法在高基陣列上的優(yōu)化算法。文獻[3]提出了一種基于CIOS模乘的可重構(gòu)可伸縮的雙域模乘加器，將模乘與模加減糅合，但面積不夠優(yōu)化。文獻[4]提出了一種改進的基于FIOS類型Montgomery雙域模乘器，流水線切割較為合理。本文在前人的研究基礎(chǔ)上，通過對雙域模乘和模加減單元進行分析，以FIOS算法為基礎(chǔ)，重新設(shè)計了一種MAS（multiplication- addition-subtraction）結(jié)構(gòu)，將模乘和模加減進行可重構(gòu)糅合，一定程度上降低了單元面積，又可以靈活地適配各種長度的模運算，從而適應(yīng)各種不同的應(yīng)用場景和任務(wù)。同時對模乘的關(guān)鍵運算路徑進行了流水線設(shè)計，相對于傳統(tǒng)的模乘算法，運算頻率有一定的提高。

1 模乘加算法分析

模乘、模加減和模逆運算構(gòu)成了ECC密碼算法中的主體運算。設(shè)計模乘模加減功能復(fù)用的模乘加單元結(jié)構(gòu)，可以提高結(jié)構(gòu)利用率，減少多余連線資源，進而降低總體面積。本文對雙域模加減算法及雙域模乘算法進行了分析。根據(jù)兩者運算的原理可知，模乘對模加減無論是在算法層次還是結(jié)構(gòu)層次上具有較為完整的兼容性。兼容關(guān)系如圖1所示。

本文針對現(xiàn)有模乘和模加算法進行改進，設(shè)計了如下所示的模乘加算法。

算法1 適于硬件實現(xiàn)的FIOS模乘加改進算法

算法將輸入的大整數(shù)A、B、N按照32 bit字長進行分解運算[4]，字數(shù)為s，算法具有內(nèi)外兩層循環(huán)，對操作數(shù)按32 bit字長進行循環(huán)掃描，其中內(nèi)循環(huán)完成32 bit數(shù)據(jù)的乘和64 bit的加法運算，外循環(huán)完成對被乘數(shù)的遍歷掃描。算法在GF(2n)域與GF(p)域上實現(xiàn)過程大致相同，區(qū)別在于GF(2n)域上的加法是異或操作，乘法則為多項式乘法，并且循環(huán)結(jié)束后直接輸出結(jié)果，而不需要與不可約多項式進行比較。

算法初始有一個信號a，用于判斷運算模加減或者模乘。如果a=0進入step2運行模乘，否則進入step5運行模加減，而此時的加法不再是模乘中的64 bit加，而是3個64 bit加的級聯(lián)，即為192 bit加。此處即為本文提出的模乘模加糅合結(jié)構(gòu)的關(guān)鍵所在。運算過程有3個for循環(huán)，其中前兩個是嵌套在一起內(nèi)外循環(huán)。設(shè)計的流水運算單元也是主要用來完成這部分嵌套循環(huán)。在硬件設(shè)計過程中step2.2、2.3、2.4作為一部分結(jié)構(gòu)Y。step2.5.1、2.5.2、2.5.3、2.5.4作為重復(fù)的結(jié)構(gòu)X出現(xiàn)在硬件結(jié)構(gòu)中。

為了更加清晰描述算法中數(shù)據(jù)的傳遞與處理過程，列出了FIOS模乘器流水樹結(jié)構(gòu)，其中X與Y分別對應(yīng)上文提到的結(jié)構(gòu)X與結(jié)構(gòu)Y(Y結(jié)構(gòu)包括PreY與Y兩個操作)。每一橫行表示同一時鐘周期參與運算的單元，每一豎列表示下一時鐘周期數(shù)據(jù)傳遞方向。圖2描述的是前n個時鐘周期數(shù)據(jù)運算傳遞。

2 可編程FIOS模乘加器電路設(shè)計

2.1 模乘加器總體結(jié)構(gòu)設(shè)計

模乘運算電路是該設(shè)計的核心，本文設(shè)計的模乘單元數(shù)據(jù)路徑位寬為192 bit，通過迭代，可以完成576 bit以內(nèi)任意比特的雙有限域模乘運算。該模乘加數(shù)據(jù)路徑核心為處理單元Y、N個處理單元X和模加減單元，其中Y結(jié)構(gòu)由兩部分構(gòu)成，詳見流水線結(jié)構(gòu)設(shè)計。具體結(jié)構(gòu)如圖3所示。模加減單元中的兩個虛線ADDER192 bit，表示其由MA X#N和MA X#N-1的相關(guān)結(jié)構(gòu)替代。

雙域模乘加器主要由數(shù)據(jù)輸入、數(shù)據(jù)輸出、狀態(tài)機控制、模乘運算、模加減運算等單元構(gòu)成。

數(shù)據(jù)輸入輸出單元負責(zé)對數(shù)據(jù)進行整合以及與外界的數(shù)據(jù)對接。其中輸出單元需要根據(jù)運算域的不同改變輸出模式。

狀態(tài)機控制單元完成整個可重構(gòu)向量模乘加單元運算時對各個模塊的調(diào)度控制。根據(jù)輸入的運算選擇信號及數(shù)據(jù)的長度，判斷進行模乘還是模加減，二元域還是素數(shù)域，以及進行模乘的輪數(shù)和。

由于算法1在實現(xiàn)中存在較高的內(nèi)部并行性，因此模乘運算模塊可以采用多個并列處理單元來組成線性陣列流水線結(jié)構(gòu)實現(xiàn)算法提速，也就是上文提到的N個處理單元X的結(jié)構(gòu)。

2.2 雙域模乘加糅合部分設(shè)計

圖4是模加減器結(jié)構(gòu)示意圖。有兩個可重構(gòu)的向量加法運算單元。

向量模加減單元的核心是一個位寬為192 bit能夠進行雙有限域加減法運算的加法器。當數(shù)據(jù)長度不超過192 bit時，數(shù)據(jù)路徑?jīng)]有反饋情況；當大于192 bit時，則在控制電路的調(diào)度下循環(huán)反饋多次運算。該192 bit加法器由6個32 bit可重構(gòu)字加法器組成。其中，每個字加法器可以執(zhí)行兩個有限域上的加減法運算，且通過級聯(lián)方式完成192 bit數(shù)據(jù)的運算，如圖5所示。每個字加器無需等待上一級進位才進行運算，而是預(yù)先對兩種進位情況分別進行計算，得到兩種不同的結(jié)果。當前一級進位到達時，由進位信號進行結(jié)果選擇。若計算數(shù)據(jù)的長度超過192 bit，則需要將第六級字加法器的進位返回至第一級字加法器，進行下一循環(huán)的計算。圖6中DFA為雙有限域加法器。

圖7是模乘單元的MA X#1到MA X#N-2的結(jié)構(gòu)。對應(yīng)于算法的step2.6。不過，它將Tj+Ai×Bj與C+mNj并行計算，而且還有Tj-1+Ai×Bj-1與C+mNj-1進行相加的單元。

圖7結(jié)構(gòu)包含3個64 bit的加法器，如果進行級聯(lián)，并加入進位判斷電路，即可完成模加模塊所需的192 bit加法運算。如圖8所示，即為加入級聯(lián)結(jié)構(gòu)的MA X#N-1和MA X#N的結(jié)構(gòu)?？梢酝瑫r滿足模乘與模加的運算需求。其中的ADDER64是由進位為0或1的兩個32 bit加法器級聯(lián)構(gòu)成的，即運用了上文中可重構(gòu)字加器的設(shè)計方法。

2.3 流水線單元設(shè)計

該模乘加器的流水加速設(shè)計主要體現(xiàn)在模乘器的嵌套循環(huán)結(jié)構(gòu)上。如圖9所示。該流水線單元主要由3部分構(gòu)成，分別是：移存器、處理單元Y（由preY、Y構(gòu)成）、處理單元X。其中，移存器完成A、B、N的字輸入；Y單元完成算法中的step2.2、2.3、2.4；X單元用于完成step2.5.1、2.5.2、2.5.3、2.5.4的循環(huán)。N個X單元可以滿足576 bit以內(nèi)的任意比特模乘運算，以下是針對7個X的結(jié)構(gòu)分析。其合理性將在后文進行分析。

狀態(tài)機產(chǎn)生控制信號，驅(qū)動移存期，為每個單元提供相應(yīng)的數(shù)據(jù)字，數(shù)據(jù)A首先通過Y結(jié)構(gòu)進行6個時鐘周期的運算完成前兩個字Ai與B0的乘法，而后傳輸?shù)絏單元中，并根據(jù)參加模乘數(shù)據(jù)的長度，進行對應(yīng)輪數(shù)的X單元運算，而后以字為單位輸出運算結(jié)果。下面對長度分別為192 bit、384 bit、576 bit的數(shù)據(jù)運算過程進行分析。

(1)參加模乘運算數(shù)據(jù)為192 bit時，即6個字。根據(jù)結(jié)構(gòu)設(shè)計，Ai與B0在外循環(huán)中進行，X單元本級運算的數(shù)據(jù)Tj+Ai×Bj與C+mNj傳到下一級使用(詳見硬件結(jié)構(gòu)設(shè)計)，因此需要經(jīng)過6個X單元的運算才能完成數(shù)據(jù)的輸出。最終最低字T0在X2中輸出，最高位T5在X7中輸出。數(shù)據(jù)進入X單元后，需要經(jīng)過兩個周期才能輸出。因此從第一個有效數(shù)據(jù)A1進入X1開始，第3個周期產(chǎn)生T0；第6個周期，第二個有效數(shù)據(jù)A2進入X1。即此時A1和B的乘法與A0和B的乘法并行運行。第12個周期，第一輪的中間T1生成，之后以此類推。

(2)參加模乘運算數(shù)據(jù)為384 bit時，即12個字。同192 bit運算，需要經(jīng)過12個X單元才能完成一輪內(nèi)循環(huán)。不過在X7完成運算時需要數(shù)據(jù)再次傳送回X1繼續(xù)進行循環(huán)，且此時恰巧Y單元沒有數(shù)據(jù)輸入到X1單元（Y單元每6個時鐘周期更新一次Bi值。并不是每個周期都為X單元提供數(shù)據(jù)）。X單元運算需要2個時鐘周期，7次運算則需要14個時鐘周期。而Y單元需要6個時鐘周期才會往X1中輸入數(shù)據(jù)，14個時鐘正介于12到18時鐘周期之間，因此不會出現(xiàn)數(shù)據(jù)輸入沖突。該結(jié)構(gòu)包含7個X處理單元，可以避免576 bit以內(nèi)乘法運算均不出現(xiàn)數(shù)據(jù)沖突。

(3)參加模乘運算數(shù)據(jù)為576 bit時，即18個字。同理，需要經(jīng)過18個X單元才能完成一輪內(nèi)循環(huán)，要在第三輪的X4處完成第一次循環(huán)運算。而此時，7個X單元里面進行的是不同的內(nèi)循環(huán)，比如第40個時鐘周期（從有效數(shù)據(jù)輸入Y開始計算時鐘），X1到X7分別在進行A1×B14、A3×B8、A5×B2、A0×B17、A2×B11、空（X7此時無有效運算）的內(nèi)循環(huán)。其中，Ai×Bj表示A的第i個字與B的第j個字相乘。對應(yīng)算法step2.5.1 Hj=Tj+AiBj，Ij=mNj+C，及本輪內(nèi)循環(huán)。表1是具體的運算數(shù)據(jù)表格。

下面對不同級流水結(jié)構(gòu)進行分析。圖10是不同的流水線結(jié)構(gòu)下完成不同長度運算用時折線圖。由折線圖可知，到10級流水線結(jié)構(gòu)之后，再次增加X單元的數(shù)量運算周期不再降低，反而會使面積增大，降低單元的整體利用率。因此在綜合了面積、運算效率及單元利用率方面因素后，最終決定采用10級流水結(jié)構(gòu)，其中Y內(nèi)部有三級流水，7個X對應(yīng)7級。

3 性能分析

本文采用了Verilog HDL對設(shè)計進行了RTL級描述，對設(shè)計進行功能仿真驗證，并在0.18 μm CMOS工藝標準單元庫下對可重構(gòu)模乘單元進行邏輯綜合，綜合工具使用Synopsys公司的Design Complier。綜合結(jié)果表明，可重構(gòu)模乘加單元占用面積927 312 μm2，最大延遲4.3 ns，最高時鐘可達到230 MHz。由于沒有同類別的可重構(gòu)的模乘加單元可供比較且電路的綜合環(huán)境和仿真平臺不同，因此只與其他一些國內(nèi)外先進設(shè)計文獻中模乘器的性能進行比較。表2列出了本文與其他文獻的模乘運算單元的性能比較。

由于模乘加結(jié)構(gòu)的關(guān)鍵路徑存在于模乘模塊中，性能指標里面主要進行模乘方面的性能比較。與文獻[3]比較，雖然速度略有差距，但是面積具有很大優(yōu)勢。與文獻[4]比較，雖然面積略有劣勢，但是支持雙域運算且運算位寬范圍更廣。與文獻[5]、文獻[7]的設(shè)計相比，本文提出的結(jié)構(gòu)單元在運算速度和面積方面均有優(yōu)勢。綜合比較，本設(shè)計在功能及性能上具有較強的綜合優(yōu)勢，并且可以適應(yīng)于各種不同的場合和任務(wù)。

4 結(jié)論

本文提出了基于FIOS算法和可重構(gòu)模加減算法的雙域可伸縮模乘加算法。并運用了10級流水線結(jié)構(gòu)，設(shè)計了支持576 bit以內(nèi)的任意長度雙域可重構(gòu)模乘加減運算單元。在結(jié)構(gòu)上很好地完成了模乘與模加減的單元公用，提高了單元的利用率。為模乘加單元的設(shè)計提供了一定的參考。