關(guān)于可編程可伸縮的雙域模乘加器研究與設(shè)計(jì)

0 引言

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

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

1 模乘加算法分析

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

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

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

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

算法初始有一個(gè)信號(hào)a，用于判斷運(yùn)算模加減或者模乘。如果a=0進(jìn)入step2運(yùn)行模乘，否則進(jìn)入step5運(yùn)行模加減，而此時(shí)的加法不再是模乘中的64 bit加，而是3個(gè)64 bit加的級(jí)聯(lián)，即為192 bit加。此處即為本文提出的模乘模加糅合結(jié)構(gòu)的關(guān)鍵所在。運(yùn)算過(guò)程有3個(gè)for循環(huán)，其中前兩個(gè)是嵌套在一起內(nèi)外循環(huán)。設(shè)計(jì)的流水運(yùn)算單元也是主要用來(lái)完成這部分嵌套循環(huán)。在硬件設(shè)計(jì)過(guò)程中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ù)的傳遞與處理過(guò)程，列出了FIOS模乘器流水樹(shù)結(jié)構(gòu)，其中X與Y分別對(duì)應(yīng)上文提到的結(jié)構(gòu)X與結(jié)構(gòu)Y(Y結(jié)構(gòu)包括PreY與Y兩個(gè)操作)。每一橫行表示同一時(shí)鐘周期參與運(yùn)算的單元，每一豎列表示下一時(shí)鐘周期數(shù)據(jù)傳遞方向。圖2描述的是前n個(gè)時(shí)鐘周期數(shù)據(jù)運(yùn)算傳遞。

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

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

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

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

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

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

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

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

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

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

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

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

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

該模乘加器的流水加速設(shè)計(jì)主要體現(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個(gè)X單元可以滿足576 bit以內(nèi)的任意比特模乘運(yùn)算，以下是針對(duì)7個(gè)X的結(jié)構(gòu)分析。其合理性將在后文進(jìn)行分析。

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

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

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

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

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

3 性能分析

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

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

4 結(jié)論

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