程桂花 羅永龍 齊學(xué)梅 左開(kāi)中

摘要： 有限域的運(yùn)算是密碼學(xué)的基礎(chǔ)，而在有限域的運(yùn)算中模乘運(yùn)算是核心運(yùn)算之一。為此，分析了模乘運(yùn)算的原理及特點(diǎn)，使用Verilog HDL設(shè)計(jì)模乘電路，通過(guò)FPGA實(shí)現(xiàn)了基于有限域的模乘運(yùn)算。電路應(yīng)用雙沿寄存器結(jié)構(gòu)，并且規(guī)模小、速度快、功耗低能實(shí)現(xiàn)有限域通用模乘運(yùn)算對(duì)加密算法的硬件實(shí)現(xiàn)具有實(shí)際價(jià)值。

關(guān)鍵詞： 有限域； 模乘； 模2運(yùn)算； 硬件設(shè)計(jì)

中圖分類(lèi)號(hào)：TP309文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1006-8228（2012）04-21-03

Design and implementation of a modular multiplication circuit of low power and high speed

Cheng Guihua1,2, Qi Xuemei1,2, Luo Yonglong1,2, Zuo Kaizhong1,2

（1. College of Mathematics and Computer Science， Anhui Normal University， Wuhu， Anhui 241000， China；

2. Research Center of Network and Information Security， Anhui Normal University， Anhui Normal University）

Abstract： The finite field arithmetic is the base of cryptography and modular multiplication is one of core operations. Based on analysis of finite field modular multiplication, the authors design a modular multiplication circuit in Verilog HDL, and its modular multiplication is realized by FPGA in finite fields. The circuit uses double-edge-triggered register, and realizes small-scale, low power consumption and high speed. It implements modular multiplication to reduce its scale and it has practical value for hardware implementation of encoding algorithm.

Key words： finite fields； modular multiplication； modular 2 arithmetic； hardware design

0 引言

加密是保證信息安全的主要途徑之一，被廣泛應(yīng)用于信息技術(shù)的各個(gè)方面，如智能卡、手機(jī)銀行、無(wú)線局域網(wǎng)和傳感網(wǎng)等便攜式設(shè)備中。因此設(shè)計(jì)快速、低功耗的硬件加密模塊至關(guān)重要。加密算法基于有限域的運(yùn)算，而模乘運(yùn)算是有限域運(yùn)算的核心運(yùn)算之一，其運(yùn)算速度對(duì)加密算法的實(shí)現(xiàn)起著重要作用，其功耗的高低會(huì)直接影響使用性能。

模乘運(yùn)算是基于有限域的多項(xiàng)式乘法的模運(yùn)算，一般通過(guò)移位和模2加運(yùn)算代替多項(xiàng)式乘法和除法運(yùn)算。文獻(xiàn)[1-5]從算法的角度對(duì)如何提高模乘運(yùn)算效率進(jìn)行了討論。本文分析了模乘運(yùn)算的原理與特點(diǎn)，綜合軟硬件知識(shí)設(shè)計(jì)了一種小規(guī)模、快速、低功耗的模乘運(yùn)算電路模乘電路使用Verilog HDL設(shè)計(jì)，在Quartus II開(kāi)發(fā)軟件中仿真，通過(guò)FPGA實(shí)現(xiàn)。電路引入雙沿工作的寄存器，在系統(tǒng)工作時(shí)鐘頻率不變的情況下，不僅使模乘運(yùn)算的速度加倍，還可使電路的功耗大大降低。

1 模乘算法

有限域GF(2n)上二進(jìn)制多項(xiàng)式系數(shù)運(yùn)算以2為模，運(yùn)算時(shí)不考慮進(jìn)位和借位。模2加減是按位執(zhí)行“異或”運(yùn)算，模2乘除則采用模2加減計(jì)算部分積和部分余數(shù)。若被乘數(shù)f(x)、乘數(shù)g(x)、模m(x)多項(xiàng)式定義如式⑴⑵⑶所示：

則有限域GF(2n)上模乘運(yùn)算如公式⑷[6]所示。

若直接根據(jù)公式⑷在GF(2n)上執(zhí)行多項(xiàng)模乘運(yùn)算，需要用到多項(xiàng)式乘法和除法運(yùn)算，時(shí)間開(kāi)銷(xiāo)較大，也難以用軟件硬件實(shí)現(xiàn)[7-8]，因此我們將式⑷變換為式⑸[6]：

式⑸表明：xi×g(x)多項(xiàng)式模乘運(yùn)算可以重復(fù)使用i次式⑸來(lái)實(shí)現(xiàn)。這樣一來(lái)，在有限域GF(2n)上，式（4）定義的多項(xiàng)式模乘運(yùn)算可以直接使用兩個(gè)n位的二進(jìn)制整數(shù)相乘，并通過(guò)多個(gè)中間結(jié)果作移位和模2加來(lái)實(shí)現(xiàn)。

2 模乘運(yùn)算器電路設(shè)計(jì)與實(shí)現(xiàn)

2.1 電路設(shè)計(jì)

基于式⑸的模乘運(yùn)算器的電路結(jié)構(gòu)如圖1所示。加電后電路按如下時(shí)序工作：

第一步，當(dāng)Clr端收到負(fù)脈沖“ ”時(shí)，fxl、gxr和fgxm寄存器異步裝入初值（如圖1所示）。

第二步，當(dāng)寄存器fxl的最高位為“1”，fxl mx →fxm，實(shí)現(xiàn)模乘運(yùn)算；否則fxl→fxm。當(dāng)寄存器gxr的最低位為1時(shí)，fgxm fxm→fxm1；否則fgxm→fxm1。

第三步，在時(shí)鐘信號(hào)的作用下，電路同時(shí)完成如下三項(xiàng)工作：一是將fxm1存入fgxm寄存器；二是將fxm左移一位（低位補(bǔ)“0”）存入fxl寄存器；三是將gxr寄存器內(nèi)容右移一位（高位補(bǔ)“0”）。重復(fù)第二、三步直到gxr寄存器為全“0”時(shí)，運(yùn)算結(jié)束。fgxm寄存器的內(nèi)容為所需的多項(xiàng)式模乘運(yùn)算的乘積，通過(guò)fgx輸出。

圖1模乘運(yùn)算器電路結(jié)構(gòu)示意圖

模乘運(yùn)算電路的規(guī)模取決于所采用的控制電路的規(guī)模。在圖1中，將模運(yùn)算（fxm）和左移操作合二為一，減少了電路的運(yùn)算步驟與工作延時(shí)；利用乘數(shù)寄存器gxr右移時(shí)空出的高位補(bǔ)“0”，當(dāng)gxr寄存器的值為全“0”時(shí)完成一次模乘運(yùn)算。這樣設(shè)計(jì)，一方面不需要額外增加控制電路，減少了模乘運(yùn)算器電路的規(guī)模；另一方面加速了運(yùn)算過(guò)程，完成一次模乘運(yùn)算平均只需n/2個(gè)時(shí)鐘邊沿信號(hào)。

2.2 快速低功耗設(shè)計(jì)

模乘運(yùn)算器的主要邏輯部件之一是寄存器，時(shí)鐘信號(hào)是寄存器必備的輸入信號(hào)之一。傳統(tǒng)的寄存器僅對(duì)時(shí)鐘的上升沿或下降沿敏感，十個(gè)單邊沿觸發(fā)器[9]，在另一方向上的時(shí)鐘跳變成為一種冗余跳變，所對(duì)應(yīng)的功耗也是多余的。如果能對(duì)時(shí)鐘信號(hào)的兩個(gè)邊沿都能敏感，不僅可以降低電路的功耗，還可以使模乘運(yùn)算器的運(yùn)算速度加倍，從而提高系統(tǒng)的效率。依據(jù)文獻(xiàn)[10]的設(shè)計(jì)思想和主從觸發(fā)器的工作原理，我們利用“與非“門(mén)”組成雙沿觸發(fā)器的寄存器并用于模乘運(yùn)算器器電路中（如圖1中的fxl、gxr和fgxm寄存器），使模乘運(yùn)算速度加倍、功耗減半。兩種模乘運(yùn)算器的工作波形如圖2所示。

由圖2可知，相對(duì)于單邊沿寄存器組成的模乘運(yùn)算器而言，在相同頻率時(shí)鐘的作用下，雙邊沿寄存器組成的模乘運(yùn)算器運(yùn)算速度加倍，同時(shí)避免了時(shí)鐘冗余跳變，從而大幅降低了模乘運(yùn)算器電路的功耗。

(a) 單邊沿模乘運(yùn)算器波形圖

(b) 雙邊沿模乘運(yùn)算器波形圖

圖2單、雙邊沿乘法器時(shí)序?qū)Ρ葓D

3 仿真波形與實(shí)例分析

我們應(yīng)用Verilog HDL語(yǔ)言設(shè)計(jì)基于有限域高速、低功耗的模乘運(yùn)算器電路模型，并用Visual FoxPro語(yǔ)言進(jìn)行了軟件驗(yàn)證，證明所有運(yùn)算結(jié)果完全正確。選擇EP2C5Q208CN芯片，在Quartus II開(kāi)發(fā)工具中配置、綜合和優(yōu)化后通過(guò)Quartus II中的Programmer工具下載到芯片中，可以快速穩(wěn)定地實(shí)現(xiàn)模乘運(yùn)算操作且占用面積小，達(dá)到預(yù)期設(shè)計(jì)目標(biāo)。

圖2是f(x) =x6+x4+x3+x2+x+1，g(x) =x5+x4+x2+1在有限域GF(28)中以m(x)=x8+x4+x3+x+1為模的多項(xiàng)式模乘運(yùn)算仿真波形；模乘運(yùn)算過(guò)程如表1所示。

在有限域中,每個(gè)多項(xiàng)式都可以表示為二進(jìn)制整數(shù)，反之亦然，也就是說(shuō)m(x)=x8+x4+x3+x+1等價(jià)于二進(jìn)制數(shù)100011011B或十六進(jìn)制數(shù)11BH，f(x)=x6+x4+x3+x2+x+1=5FH、g(x)=x5+x4+x2+1=35H。圖2中的各數(shù)值為相應(yīng)多項(xiàng)式系數(shù)的十六進(jìn)制表示。

由表1可知，計(jì)算步驟1、2在單邊沿模乘運(yùn)算器中需要使用T1和T2兩個(gè)時(shí)鐘的上升沿，而在雙邊沿模乘運(yùn)算器中只需要使用一個(gè)時(shí)鐘T1的上升沿和下降沿完成，這不僅加速了運(yùn)算過(guò)程，同時(shí)也減少了時(shí)鐘的冗余跳變，降低了功耗。

表1中計(jì)算步驟1為初始化操作。計(jì)算步驟2中，首先因gxr(x)=x5+x4+x2+1=35H多項(xiàng)式系數(shù)的第0位為1，模乘部分積fgxm(x)=fgxm(x)+fxm(x)=0+x6+x4+x3+x2+x+1=x6+x4+x3+x2+x+1=5FH；其次fxm(x)、gxr(x)分別左移和右移一位得到fxl(x)=x7+x5+x4+x3+x2+x=0BEH、gxr(x)=x4+x3+x1=1AH、并因移位前fxm(x)多項(xiàng)式系數(shù)的最高位為0，fxm(x)=fxl(x)=x7+x5+x4+x3+x2+x，這為下一步驟中模乘部分積的計(jì)算準(zhǔn)備好數(shù)據(jù)；重復(fù)上述操作，直到多項(xiàng)式gxr(x)=0，通過(guò)finsh輸出正脈沖“ ”，表示完成一次模乘運(yùn)算，運(yùn)算結(jié)果通過(guò)fgx輸出。

表1 模乘運(yùn)算過(guò)程（f(x)=x6+x4+x3+x2+x+1、g(x)=x5+x4+x2+1、m(x)=x8+x4+x3+x+1）

[[步驟&fxl(x)&gxr(x)&fxm(x)&fgxm(x)&時(shí)鐘

（圖2（a））&時(shí)鐘

（圖2（b））&1&=x6+x4+x3+x2+x+1&=x5+x4+x2+1&=x6+x4+x3+x2+x+1&=0&T1↑&T1↑&2&=21fxm(x)

=x7+x5+x4+x3+ x2+x&=2-1gxr(x)

=x4+x3+x1&=fxl(x)

=x7+x5+x4+x3+ x2+x&=fgxm(x)+ fxm(x)

=x6+x4+x3+x2+x+1&T2↑&T1↓&3&=21fxm(x)

=x8+x6+x5+x4+ x3+ x2&=2-1gxr(x)

=x3+x2+1&=fxl(x) mod m(x)

=x6+x5+x2+x1+1&=fgxm(x)

=x6+x4+x3+x2+x+1&T31↑&T2↑&4&=21fxm(x)

=x7+x6+x3+x2+x1&=2-1gxr(x)

=x2+x1&=fxl(x)

=x7+x6+x3+x2+x1&=fgxm(x)+ fxm(x)

=x5+x4+x3&T4↑&T2↓&5&=21fxm(x)

=x8+x7+x4+x3+x2&=2-1gxr(x)

=x1+1&=fxl(x) mod m(x)

=x7+x2+x1+1&=fgxm(x)

=x5+x4+x3&T5↑&T3↑&6&=21fxm(x)

=x8 +x3+x2+x1&=2-1gxr(x)

=1&=fxl(x) mod m(x)

=x4+x2+1&=fgxm(x)+ fxm(x)

=x7+x5+x4+x3+ x2+x&T6↑&T3↓&7&=21fxm(x)

=x5+x3+ x1&=2-1gxr(x)

=0&=fxl(x)

=x5+x3+ x1&=fgxm(x)+ fxm(x)

=x7+x5+x3+ x1&T7↑&T4↑&8&因gxr(x)=0，模乘運(yùn)算完成，fgxm(x) = x7+x5+x3+ x1為模乘的乘積&]]

4 結(jié)束語(yǔ)

通過(guò)“移位”和“異或”基本邏輯實(shí)現(xiàn)有限域模乘運(yùn)算，電路規(guī)模小、運(yùn)算效率高；電路引入雙沿工作的寄存器，在系統(tǒng)工作時(shí)鐘頻率不變的情況下，不僅使模乘運(yùn)算的速度加倍，還可避免時(shí)鐘信號(hào)的冗余跳變，使電路的功耗大大降低。

參考文獻(xiàn)：

[1] 丁宏,郭艷華.快速大數(shù)模乘算法及其應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng),2003.24(7):1367~1370

[2] 雷明,葉新,張煥國(guó).Montgomery算法及其快速實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程,2003.29(14):44~46

[3] 孔凡玉,于佳,李大興.一種改進(jìn)的Montgomery模乘快速算法[J].計(jì)算機(jī)工程,2005.31(8):1~3

[4] 劉強(qiáng),佟冬,程旭.一款RSA模乘冪運(yùn)算器的設(shè)計(jì)與實(shí)現(xiàn)[J].電子學(xué)報(bào),2005.33(5):923~927

[5] P L Montgomery.Modular multiplication without trial division[J].Mathematics of Computation.1985.44(170):519~521

[6] Stallings,W.密碼編碼學(xué)與網(wǎng)絡(luò)安全:原理與實(shí)踐(第四版)[M].孟慶樹(shù),王麗娜,傅建明等譯.電子工業(yè)出版社,2006.

[7]GUO J H,WANG C L.Systolic array implementation of Euclid's algorithm for inversion and division in GF(2m)[J].IEEE Trans Computers.1998,47(10):1161~1167

[8]Lu C C,Tseng S Y.Integrated Design of AES Encrypter and Decrypter[J].IEEE Transactions on Information Theory.1991.37(5):1241~1260

[9] 吳訓(xùn)威,韋健,M.Pedram.低功耗雙邊沿觸發(fā)器的邏輯設(shè)計(jì)[J].電子學(xué)報(bào),1999.27(5):129~131

[10] 吳訓(xùn)威,盧仰堅(jiān).CMOS可預(yù)置雙邊沿觸發(fā)器的設(shè)計(jì)及其應(yīng)用[J].電路與系統(tǒng)學(xué)報(bào),2001.6(1):27~31