??? 摘? 要：?采用雙Booth 2編碼技術(shù)，對(duì)高基radix-16 Montgomery模乘法器進(jìn)行了優(yōu)化設(shè)計(jì)，減小了電路面積，提高了模乘運(yùn)算速度。使用SMIC0.18μm標(biāo)準(zhǔn)單元工藝庫綜合后，計(jì)算256bit有限域GF(p)上的模乘只需要0.51μs。?

??? 關(guān)鍵詞： 布斯編碼； Montgomery； 有限域； 模乘法器

?

??? RSA算法、數(shù)字簽名標(biāo)準(zhǔn)、橢圓曲線密碼系統(tǒng)都要涉及到模乘或模冪運(yùn)算。Montgomery模乘算法^[1]把模乘運(yùn)算時(shí)的除法運(yùn)算轉(zhuǎn)換成了簡(jiǎn)單的移位操作，大大提高了模乘運(yùn)算的速度，從而得到了廣泛的應(yīng)用^[2-4]。公鑰密碼體制中模乘運(yùn)算的操作數(shù)位寬很大，ECC需要160～512bit，RSA等甚至達(dá)到1 024～2 048bit。直接利用原始的Montgomery模乘算法只能處理固定位寬的操作數(shù)，而且速度和面積均不理想。為此,一種基于字的Montgomery模乘算法被提了出來^[2]，該算法不僅大大縮短了關(guān)鍵路徑，而且可將操作數(shù)擴(kuò)展到任意位寬。目前已有多種基于這種算法的模乘法器設(shè)計(jì)方案^[3-4]。本文基于雙Booth 2編碼提出了另一種改進(jìn)方案并進(jìn)行了優(yōu)化設(shè)計(jì)，使得模乘運(yùn)算的速度得到了進(jìn)一步的提高。?

1 基于字的雙有限域Montgomery模乘算法?

??? Tenca^[2]提出了基于字的雙有限域Montgomery模乘算法。基于這種算法設(shè)計(jì)的模乘法器采用基于字的操作數(shù)代替固定長度操作數(shù)，不但解決了大數(shù)加法進(jìn)位鏈過長使電路關(guān)鍵路徑延遲太大的問題，而且使得模乘法器具有了可擴(kuò)展性，能支持任意位長的模乘。把素?cái)?shù)域GF(p)與二進(jìn)制域GF(2^m)上的模乘統(tǒng)一起來則能在一個(gè)硬件上支持兩種域上的運(yùn)算，從而節(jié)省了成本。基于字的雙有限域Montgomery模乘算法如下：?

??? Input: A,B,p,w,k,field?

??? Output: C∈[1,p-1]?

??? 1a: C=0?

??? 1b: spill=0?

??? 2: for i=0 to u-1?

??? 3: (spill|c0)=(a_ib₀)φc0?

??? 4: q=f(c₀,p₀,field)?

??? 5a: (spill|c0)=(q·p₀)φ(spill|c₀)?

??? 5b: for j=0 to e-1?

??? 5c: (spill|c_j)=(a_i·b_j)φc_jφspillφ(q·p_j)?

??? 6a: c_j-1=(c_j|c_j-1)/r mod w?

??? 6b: c_e-1=(spill|c_e-1)/r mod w?

??? 6c: c_e=0?

??? 7: if C>p, then C=C-p?

??? 算法把m bit模乘操作數(shù)擴(kuò)展后看作基于字的向量，然后對(duì)操作數(shù)逐字掃描進(jìn)行運(yùn)算。其中,p=(0,p_e-1,…,p₁,p₀),B=0(0,b_e-1,…,b₁,b₀),C=(0,c_e-1,…,c₁,c₀),A=(a_u-1,…,a₁,a₀),p_i、b_i、c_i是基為2^w的字，a_i是基為2^k的字,u=二進(jìn)制域上多項(xiàng)式A(x)可以簡(jiǎn)單地看成素?cái)?shù)域上的A，只是在部分積累加時(shí)有區(qū)別，素?cái)?shù)域上有進(jìn)位的傳播，二進(jìn)制域上為“異或”運(yùn)算無進(jìn)位，算法中統(tǒng)一用φ表示。函數(shù)f(c₀,p₀,field)只用到了c₀、p₀的最低k bit，有限域GF(p)上q=(c₀·（2^k-p₀^-1))mod r，有限域GF(2^m)上q=(c₀·p₀^-1)mod r。?

??? Tenca^[2]把上述Montgomery模乘算法組織成了流水線結(jié)構(gòu)。它包括s級(jí)處理單元（PE），每個(gè)PE運(yùn)算單元做兩次一個(gè)字長的加法，加法器采用帶域選擇信號(hào)field的進(jìn)位保留加法器（CSA），運(yùn)算結(jié)果經(jīng)過一級(jí)流水線寄存器后傳給下一級(jí)PE運(yùn)算單元。PE經(jīng)重定時(shí)優(yōu)化后采用兩級(jí)寄存器結(jié)構(gòu)，第一級(jí)計(jì)算q，第二級(jí)完成第5步的累加。PE每次處理3bit的A，即對(duì)A的編碼采用基為8的Booth 3編碼。為面向RSA應(yīng)用，Yibo Fan^[3]在素?cái)?shù)域GF(p)上對(duì)Tenca^[2]提出的結(jié)構(gòu)進(jìn)行了優(yōu)化，采用基為16的Booth 4編碼，提高了近26%的性能。?

2 雙Booth 2雙有限域模乘法器的設(shè)計(jì)?

??? Yibo Fan^[3]采用的處理單元PE采用分裂基的方法簡(jiǎn)化對(duì)a_i的Booth編碼，有效避免了不規(guī)則b_i、p_i的倍數(shù)(如出現(xiàn)3b_i、7p_i)，但其需要六選一的數(shù)據(jù)選擇器，而且左右兩個(gè)數(shù)據(jù)選擇器不一樣，造成布局布線的不規(guī)則。本文經(jīng)研究發(fā)現(xiàn)可以把基為16的a_i分成兩個(gè)基為4的操作數(shù)同時(shí)操作，仍然可采用類似分裂基的硬件結(jié)構(gòu)，而且左右數(shù)據(jù)選擇器相同，使得VLSI實(shí)現(xiàn)時(shí)布線更容易；對(duì)基為4的操作數(shù)采用Booth 2編碼后，編碼器結(jié)構(gòu)也更簡(jiǎn)單，數(shù)據(jù)選擇器的輸入只有0、b_i、-b_i、2b_i、-2b_i，它們只需要經(jīng)過簡(jiǎn)單的移位與取反操作就能夠?qū)崿F(xiàn)，從而減小了電路面積。編碼電路和數(shù)據(jù)選擇器電路更加簡(jiǎn)單還可以縮短關(guān)鍵路徑的延遲，從而提高了模乘法器的速度。?

2.1 總體結(jié)構(gòu)設(shè)計(jì)與優(yōu)化?

??? 雙Booth 2雙有限域模乘法器的核心仍然是基于字的Montgomery模乘算法，因此也可以組織成流水線結(jié)構(gòu)，如圖1所示。它由s個(gè)處理單元（PE）、一個(gè)移位寄存器、兩個(gè)同步讀寫RAM、一個(gè)異步FIFO以及控制模塊組成。移位寄存器根據(jù)算法外層循環(huán)依次移位輸出a_i，兩個(gè)同步讀寫RAM則根據(jù)算法內(nèi)層循環(huán)輸出b_i、p_i。如果在模乘運(yùn)算中出現(xiàn)流水線溢出，則把中間結(jié)果暫存到FIFO中，等待流水線空閑；如果不出現(xiàn)流水線溢出，則旁路掉FIFO直接使中間結(jié)果進(jìn)入新的流水線。PE處理后的數(shù)據(jù)是以carry-save的冗余形式表示的，中間數(shù)據(jù)位寬增大了一倍，造成FIFO需要增大一倍。由于FIFO一路的中間結(jié)果不處在關(guān)鍵路徑上，可以用一個(gè)并行前綴加法器PPA把carry-save冗余形式轉(zhuǎn)化為整數(shù)形式，這樣可以節(jié)省一半的FIFO。Tenca^[2]實(shí)現(xiàn)的模乘法器中使用循環(huán)寄存器存儲(chǔ)b_i、p_i需要占用大量的面積,而本文使用RAM代替可以充分利用標(biāo)準(zhǔn)單元庫的資源，減小了電路面積。?

?

?

2.2 模乘處理單元結(jié)構(gòu)?

??? 模乘處理單元PE是模乘法器的核心部件，若干級(jí)PE通過流水線寄存器串聯(lián)起來執(zhí)行大數(shù)模乘運(yùn)算，其電路結(jié)構(gòu)如圖2所示。它包含4個(gè)五選一的數(shù)據(jù)選擇器、2個(gè)雙有限域進(jìn)位加法器CSA、1個(gè)4位超前進(jìn)位加法器CLA、2個(gè)Booth 2編碼器、2個(gè)修改的Booth 2編碼器及若干寄存器。為了提高電路工作頻率，用寄存器把PE電路分成兩個(gè)部分，使其用兩個(gè)時(shí)鐘完成部分積的累加。為平衡路徑延遲，把兩個(gè)CSA放在寄存器的兩邊。由于第二個(gè)時(shí)鐘周期內(nèi)的編碼電路比第一個(gè)時(shí)鐘周期內(nèi)的編碼電路要復(fù)雜，延時(shí)更大，如果把4位CLA放在第一個(gè)時(shí)鐘內(nèi)計(jì)算則剛好能達(dá)到大致平衡。?

?

?

??? 乘數(shù)A每次掃描4位，分成兩組，每組2位，經(jīng)Booth 2編碼后得到3位的輸入數(shù)據(jù)控制數(shù)據(jù)選擇器的輸出。函數(shù)f通過編碼器實(shí)現(xiàn)，有限域GF(p)與GF(2^m)上的q值計(jì)算不一樣，因此需要同時(shí)編碼并通過域選擇信號(hào)field選擇輸出。編碼輸出的四位q值再次經(jīng)過雙Booth 2編碼控制數(shù)據(jù)選擇器的輸出。上述分兩步的編碼方式其中間值q是可以省略的，直接修改Booth 2編碼的輸入信號(hào)，一次編碼完成，部分編碼如表1所示。?

?

?

3 實(shí)現(xiàn)結(jié)果?

??? 基于雙Booth 2編碼的雙有限域模乘法器作為核心部件應(yīng)用在雙有限域ECC協(xié)處理器中，根據(jù)協(xié)處理器的實(shí)際需要，處理的最長操作數(shù)為384位，因此模乘法器采用4級(jí)流水；b_i、p_i的字寬為32位，便于與常用總線連接。這種設(shè)計(jì)既考慮了處理速度，又兼顧了電路占用的面積。模乘法器用Verilog語言描述，采用Synopsys公司的Design Complier 在SIMC 0.18μm-typcal工藝庫下綜合，等效“與非門”為4.5萬門，最高工作頻率可達(dá)280MHz，完成一次GF(p)上的256bit模乘運(yùn)算只需要0.51μs。表2是本文設(shè)計(jì)的模乘法器與已發(fā)表文獻(xiàn)中同類設(shè)計(jì)的比較結(jié)果。表中結(jié)果顯示,本文設(shè)計(jì)的速度比最好的已發(fā)表的設(shè)計(jì)^[3]提高了16%。?

?

?

??? 雙有限域模乘法器使用同一套硬件電路實(shí)現(xiàn)有限域GP(p)與GF(2^m)上的ECC模乘運(yùn)算，節(jié)約了硬件成本，擴(kuò)展了運(yùn)用空間。本文基于雙Booth 2編碼對(duì)基為16的Booth 4編碼的模乘法器進(jìn)行了優(yōu)化，使得電路更加規(guī)范、簡(jiǎn)單。從實(shí)現(xiàn)結(jié)果可以看出，本文的設(shè)計(jì)有效地減小了關(guān)鍵路徑延遲，提高了模乘法器的運(yùn)算速度。?

參考文獻(xiàn)?

[1] MONTGOMERY P L. Mondular multiplication without trial?division. Mathematics of Computation, 1985,44(7):519-521.?

[2] TENCA A F, SAVAS E, KOC C K. A design framework?for scalable and unified multipliers in GF(p) and GF(2m).?International Journal of Computer Research, 2004,13(1):68-83.?

[3] FAN Yi Bo, ZENG Xiao Yang, GANG Yi Yu,et al. A?modified high-radix scalable montgomery multiplier. IEEE??International Symposium on Circuit and System(ISCAS),?Island of ? Kos, Greece, May. 2006.?

[4] 史焱,吳行軍.高速雙有限域加密協(xié)處理器設(shè)計(jì).微電子學(xué)與計(jì)算機(jī)，2005,22(5):8-12.