車文潔，高獻(xiàn)偉

（北京電子科技學(xué)院 北京 100070）

基于FPGA的進(jìn)位保留Barrett模乘法器設(shè)計(jì)與實(shí)現(xiàn)

車文潔，高獻(xiàn)偉

（北京電子科技學(xué)院 北京 100070）

在有限域上的模算術(shù)運(yùn)算中，乘法運(yùn)算最基礎(chǔ)且最耗時(shí)，因此為提高公鑰密碼體質(zhì)的運(yùn)算速度，設(shè)計(jì)出運(yùn)算速度快、消耗時(shí)間少的模乘法器非常關(guān)鍵。該文設(shè)計(jì)出進(jìn)位保留Barrett模乘法器，乘法部分利用進(jìn)位保留乘法器，求模運(yùn)算部分利用Barrett約減運(yùn)算，用硬件描述語言進(jìn)行FPGA設(shè)計(jì)與實(shí)現(xiàn)，避免了除法運(yùn)算。對(duì)于192位的操作數(shù)，完成Barrett模乘需要約186個(gè)時(shí)鐘周期，計(jì)算速率可以達(dá)到269.17 Mb/s。

Barrett模約減；Barrett模乘法器；FPGA；硬件描述語言

作為目前最受歡迎的公鑰密碼算法，ECC具有傳輸帶寬少、處理速度快、存儲(chǔ)空間占用小、靈活性高及安全性好等優(yōu)點(diǎn)［1］，公鑰密碼算法均以模算術(shù)運(yùn)算為基本運(yùn)算，其操作數(shù)通常是大整數(shù)，運(yùn)算量較大、耗時(shí)多，模算術(shù)運(yùn)算的效率決定了公鑰密碼系統(tǒng)的運(yùn)行效率，設(shè)計(jì)出高效模乘法器一直是公鑰研究領(lǐng)域的關(guān)注焦點(diǎn)，本文設(shè)計(jì)出的模乘法器運(yùn)算速度高，耗時(shí)較少，在公鑰密碼系統(tǒng)有較高的實(shí)用性。

1 進(jìn)位保留并行乘法器

利用進(jìn)位保留并行乘法器原理，得出電路圖如圖1所示。

該結(jié)構(gòu)圖由1×1乘法器的n×m陣列組成，其耗時(shí)等于n·T（1，1）加上m位輸出加法器的延時(shí)。關(guān)鍵路徑如上圖陰影部分所示。其計(jì)算時(shí)間等于

2 Barrett模約減運(yùn)算

即使m不屬于非特殊形式的模數(shù)，xmodm的計(jì)算仍屬于模運(yùn)算，屬于模乘運(yùn)算中較耗時(shí)的部分。由于域乘法的速度是ECC算法的運(yùn)算速度快慢的關(guān)鍵，因此選擇模很重要。

圖1 進(jìn)位保留并行乘法器Fig.1 Carry-save combinational multiplier

Barrett方法［2-4］利用模約減運(yùn)算代替了高成本的除法。如果使用模約減方法直接代替一般的模運(yùn)算，則需要一種高成本的與模相關(guān)的的計(jì)算，因此本文中的設(shè)計(jì)方法適用于對(duì)一個(gè)模的多次約減運(yùn)算。

假設(shè)Bk-1＜m＜Bk，其中B是基（B通常是2或2的冪）。如果m是B的冪，計(jì)算很簡(jiǎn)單。z=xmodm的值是m整除x所得的余數(shù)，也就是

Barrett算法首先計(jì)算q=?x/m」的近似值q′，因此

首先計(jì)算（隨后計(jì)算q的近似值q′）

因?yàn)閦=x-qm，由式（2）和式（3）得

令t為使

的最小整數(shù)，則

故

又由式（3）得出

下面的算法用于計(jì)算（k+T）比特?cái)?shù)r=xmodm，其中包括計(jì)算q=?x/m」的近似值q′的approximation函數(shù)。

算法2.1 n-digit to（k+t）-digit約減

q:=approximation（x，m）；//q=?x/m」的近似值q′

r:=（（x mod Bk+t）-（q*m mod Bk+t））mod Bk+t；//計(jì)算 （k+T）比特?cái)?shù)r=xmodm

如果a=2且B≥3，則式（5）中Bt≥3且t=1時(shí)等式成立。因而，可用modBk+1來計(jì)算x-q′m，該情況與經(jīng)典的Barrett算法相對(duì)應(yīng)。

下面我們給出計(jì)算q的近似值q′的一種方法［5］。

把x和m用基B表示為

q=?x/m」的近似值q′是

可以看到

此外

又因x＜Bn且m≥Bk-1則

于是

由式（11）和式（12）得出

相當(dāng)于

根據(jù)式（5）和式（14），t的值要符合Bt≥3，因此

若B=2，則t=2（估算時(shí)運(yùn)算modBk+2），

若B＞2，則t=1（估算時(shí)運(yùn)算modBk+1）。

綜上總結(jié)，可得出計(jì)算z=xmodp的算法2.2，其中，常數(shù)c必需提前計(jì)算，如式（15）。

圖2 Barrett約減算法的數(shù)據(jù)路徑（B=2）Fig.2 Datapath of a Barrett reducer

B=2時(shí)Barrett約減的數(shù)據(jù)路徑對(duì)應(yīng)圖2所示。圖中乘法器的輸入值mul1與mul2的大小取決于n與k的相對(duì)值：y 和c是（n-k+1）-bit數(shù)，q是（k+2）-bit數(shù)，m是k-bit數(shù)，因此

所述時(shí)鐘信號(hào)的最小周期值是n1-bit×n2-bit乘法器的延遲，上述乘法器僅使用了（n+3）個(gè)輸出。若使用進(jìn)位保留乘法器，則相應(yīng)消耗時(shí)間約為（n+3）TMULT。由式（6）和式（14），且r′＜3m，則得出最終計(jì)算結(jié)果為r′，r′-m或r′-2m。因此，總的計(jì)算時(shí)間最多是5個(gè)周期，則

3 基于Stratix II器件的硬件實(shí)現(xiàn)

Stratix II器件是Altera在2004年初推出的采用1.2 V、90 nm、9層金屬走線、全銅SRAM工藝制造的高端FPGA［6］，它的內(nèi)部主要特性有內(nèi)嵌RAM模塊、DSP塊、鎖相環(huán)（PLL）和外部的存儲(chǔ)器接口等，同時(shí)采用了全新的邏輯結(jié)構(gòu)——自適應(yīng)邏輯模塊（Adaptive Logic Module，ALM），在降低了成本的基礎(chǔ)上顯著地提高了性能和邏輯利用率。

文中基于StratixII系列器件EP2S180F1508C3芯片，以Quartus II 9.0為開發(fā)環(huán)境，采用硬件描述語言VHDL進(jìn)行進(jìn)位保留Barrett模乘法器的FPGA設(shè)計(jì)與實(shí)現(xiàn)，并對(duì)實(shí)現(xiàn)結(jié)果分析驗(yàn)證。

4 進(jìn)位保留Barrett模乘法器的設(shè)計(jì)

進(jìn)位保留Barrett模乘法器，即乘法部分使用進(jìn)位保留乘法器，求模運(yùn)算部分使用 Barrett約減運(yùn)算。電路如圖 3所示。

圖3 Barrett模乘法器Fig.3 Carry-save Barrett modular multiplication

如圖3中的第一個(gè)模塊是進(jìn)位保留乘法器，第二個(gè)模塊是2節(jié)中的Barrett模約減電路，總的計(jì)算時(shí)間是計(jì)算兩個(gè)模塊所用時(shí)間的總和。

圖4 進(jìn)位保留Barrett模乘法器接口定義Fig.4 Carry-save Barrett modular multiplication's block symbol files

圖3的接口定義如圖4所示。實(shí)現(xiàn)結(jié)果基于模齒為p192。

本文取模數(shù)：

m=p192=2192-264-1=（FFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFEFFFFFFFFFFFFFFFF）16。仿真結(jié)果得出：共使用7 132個(gè)組合ALUTs，589個(gè)專用邏輯寄存器，仿真結(jié)果如圖5所示。

圖5 Barrett模乘法器仿真結(jié)果Fig.5 Carry-save Barrett modular multiplication’s simulation results

編譯和仿真后得到Barrett模乘法器的運(yùn)行最高頻率為260.76 MHz，運(yùn)行的總時(shí)鐘數(shù)為186，數(shù)據(jù)寬度為192 bit。根據(jù)公式：速度=最高頻率 （主頻）*數(shù)據(jù)寬度/運(yùn)行總時(shí)鐘數(shù)（bit/s），經(jīng)過計(jì)算得出運(yùn)行速度：

260.76 MHz/186*192bit=269.17 Mb/s

表1為與已設(shè)計(jì)出的模乘法器的性能比較。

表1 性能比較Tab.1 Performance comparison

經(jīng)過對(duì)比，可以看出本文設(shè)計(jì)出的模乘法器各方面綜合性能較佳。

圖 3中，x=（13579BDF）16，y=（2468ACE）16，計(jì)算出 z= （2C03A9277FA372）16，與仿真結(jié)果一致，則結(jié)果正確。改變模數(shù)m及被求模的數(shù)x，仍可驗(yàn)證仿真結(jié)果的正確性。

5 結(jié)束語

本文應(yīng)用 VHDL語言，利用進(jìn)位保留乘法器及Barrett約減運(yùn)算，設(shè)計(jì)出Barrett模乘法器，并在QuartusⅡ9.0環(huán)境下進(jìn)行了綜合仿真驗(yàn)證，結(jié)果與理論一致，驗(yàn)證其正確性。這種方法能夠充分發(fā)揮硬件的速度和并行性，計(jì)算速率可以達(dá)到269.17 Mb/s，相比于Barrett算法［8］中的預(yù)計(jì)算部分使用的除法算法，在Barrett模乘法器只用到乘法算法及模約減運(yùn)算，大大降低了設(shè)計(jì)復(fù)雜度以及硬件成本，運(yùn)算效率提高，在公鑰密碼體制領(lǐng)域應(yīng)用前景廣闊。

［1］張遠(yuǎn)洋.素?cái)?shù)域上公鑰密碼加速器庫的研究與實(shí)現(xiàn)［D］.鄭州：解放軍信息工程大學(xué)，2007.

［2］Jean-Pierre Deschamps，José Luis Ima？a，Gustavo D.Sutter，et al.Hardware Implementation of Finite-Field Arithmetic ［M］.3rd ed.［S.l.］:The McGraw-Hill Companies，2009.

［3］Parhami B.Computer Arithmetic［M］.New York:Oxford University Press，2000.

［4］Ercegovac M D，Lang T.Digital Arithmetic［M］.San Francisco: Morgan Kaufmann，2004.

［5］J.-P.Deschamps，G.Bioul，G.Sutter，et al.Synthesis of Arithmetic Circuits［M］.Wiley，Hoboken，New Jersey:Wiley，Hoboken，2006.

［6］葛亞明，彭永豐，薛冰，等.零基礎(chǔ)學(xué)FPGA［M］.北京：機(jī)械工業(yè)出版社，2010.

［7］TENCA A F，TODOROV GKOC C K.High-radix Design of a Scalable Modular Multiplier［A］.Cryptography Hardware and Embedded System-CHES 2001.Springer Verlag，Berlin，Gcrmanv，2001：189-205.

［8］Barrett P.Implementing the Rivest，Shamir and Adleman Public-key Encryption Algorithm on Standard Digital Signal Processor［C］.In:Cryptology-CRYPTO’86 Proceedings，vol.263 of Lecture Notes in Computer Science，Springer-Verlag，1987:311-323.

FPGA design and implementation of the carry-save Barrett modular multiplication

CHE Wen-jie，GAO Xian-wei
（Beijing Electronic Science and Technology Institute，Beijing 100070，China）

modulo arithmetic operation of multiplication on prime field is the most basic and most time-consuming operation，therefore，It is very important to design the faster operation speed，less resource efficient multiplier，This paper design a carry-save Barrett modular multiplier，multiplication part use carry-save multiplier，the modulo operation part use Barrett subtraction operation，It's designed and implemented on FPGA by hardware description language and the implementation results are verified.The Barrett modular multiplication operation requires approximately 186 clock cycles and the calculated rate can reach 269.17Mb/s for 192 bit operand.

Barrett modulo subtraction algorithm；Barrett modular multiplication；Field Programmable Gate Array；hardware description language

TN918.2

A

1674－6236（2016）04-0007-03

2015-03-03 稿件編號(hào)：201503048

北京市教育教學(xué)改革項(xiàng)目（121）；北京電子科技學(xué)院教研基金項(xiàng)目（jy201218）

車文潔（1991—），女，甘肅天水人，碩士研究生。研究方向：密碼算法的硬件實(shí)現(xiàn)等。