程桂花 羅永龍 齊學梅 左開中

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

關鍵詞： 有限域； 模乘； 模2運算； 硬件設計

中圖分類號：TP309文獻標識碼：A文章編號：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 引言

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

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

1 模乘算法

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

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

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

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

2 模乘運算器電路設計與實現(xiàn)

2.1 電路設計

基于式⑸的模乘運算器的電路結構如圖1所示。加電后電路按如下時序工作：

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

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

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

圖1模乘運算器電路結構示意圖

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

2.2 快速低功耗設計

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

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

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

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

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

3 仿真波形與實例分析

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

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

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

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

表1中計算步驟1為初始化操作。計算步驟2中，首先因gxr(x)=x5+x4+x2+1=35H多項式系數(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)多項式系數(shù)的最高位為0，fxm(x)=fxl(x)=x7+x5+x4+x3+x2+x，這為下一步驟中模乘部分積的計算準備好數(shù)據(jù)；重復上述操作，直到多項式gxr(x)=0，通過finsh輸出正脈沖“ ”，表示完成一次模乘運算，運算結果通過fgx輸出。

表1 模乘運算過程（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)&時鐘

（圖2（a））&時鐘

（圖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，模乘運算完成，fgxm(x) = x7+x5+x3+ x1為模乘的乘積&]]

4 結束語

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

參考文獻：

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

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

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

[4] 劉強,佟冬,程旭.一款RSA模乘冪運算器的設計與實現(xiàn)[J].電子學報,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.密碼編碼學與網(wǎng)絡安全:原理與實踐(第四版)[M].孟慶樹,王麗娜,傅建明等譯.電子工業(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] 吳訓威,韋健,M.Pedram.低功耗雙邊沿觸發(fā)器的邏輯設計[J].電子學報,1999.27(5):129~131

[10] 吳訓威,盧仰堅.CMOS可預置雙邊沿觸發(fā)器的設計及其應用[J].電路與系統(tǒng)學報,2001.6(1):27~31