GF(2m)域上II型最優(yōu)正規(guī)基的字級(jí)乘法器

倪 樂，陳 韜，戴紫彬，李 淼

(信息工程大學(xué)，河南 鄭州 450004)

近些年來(lái)，隨著橢圓曲線密碼體制應(yīng)用的發(fā)展，有限域運(yùn)算的硬件實(shí)現(xiàn)方法成為了研究的熱點(diǎn)。由于有限域中正規(guī)基[1]上平方運(yùn)算的易于實(shí)現(xiàn)性，正規(guī)基被廣泛用于表達(dá)二進(jìn)制域上的元素。

本文主要研究正規(guī)基上的運(yùn)算，在正規(guī)基中有兩種最高效的表示方式，一種是I型最優(yōu)正規(guī)基，一種是II型最優(yōu)正規(guī)基。在 ANSI X9.62[2]和ANSI X9.63[3]中規(guī)定了有限域上的元素以正規(guī)基表示時(shí)的選取規(guī)則。但出于安全角度的考慮，I型最優(yōu)正規(guī)基已被許多安全標(biāo)準(zhǔn)排除在外，如 NIST ECDSA和 ANSI X9.62；而 II型正規(guī)基由于其更好的安全特性，被廣泛推薦及使用在密碼算法應(yīng)用設(shè)計(jì)中去。本文提出了一種新型基于字級(jí)結(jié)構(gòu)的II型正規(guī)基乘法器。其特點(diǎn)是關(guān)鍵路徑與分割字?jǐn)?shù)及字段大小無(wú)關(guān)，并可達(dá)到很高的時(shí)鐘頻率。

1 II型最優(yōu)正規(guī)基及重序正規(guī)基

在 m∈[2，1 000]內(nèi)，有 155個(gè) m值是存在 II型最優(yōu)正規(guī)基的。II型最優(yōu)正規(guī)基下的乘法矩陣M中1的個(gè)數(shù)最少，為2m-1個(gè)，除第一列外，其他每一列只有兩個(gè)1，這樣就大大降低了乘法運(yùn)算的空間復(fù)雜度和時(shí)間復(fù)雜度。因此設(shè)計(jì)針對(duì)II型最優(yōu)正規(guī)基的乘法器具有非常重要的意義。

假設(shè)β是GF(2)上次數(shù)為m的不可約多項(xiàng)式f(x)(正規(guī)多項(xiàng)式)的根。如果集合 N={β，β2，β22，…，β2m-1

}中的元素是互相線性無(wú)關(guān)的，則集合N是擴(kuò)域GF(2m)上的一組正規(guī)基。通過尋找正規(guī)多項(xiàng)式，可以建立GF(2)上的擴(kuò)域GF(2m)的正規(guī)基。

定理1[4]令GF(2m)是含2m個(gè)元素的有限域。如果2m+1是素?cái)?shù)，且下面兩個(gè)條件之一成立：

(1)2是模2m+1的原根；

(2)2m+1是模4為3的一個(gè)素?cái)?shù)，并且2模2m+1的次數(shù)為m。

則 β=γ+γ-1生成一個(gè) GF(2m)到 GF(2)上的一組最優(yōu)正規(guī)基，其中γ是(2m+1)次本原單位根。

記M為新生成的一組正規(guī)基：

則稱m為GF(2m)到GF(2)上的一組II型最優(yōu)正規(guī)基。

[5]可得 ，基 M={γ1，γ2，… ，γm-1，γm}為 正222m-1規(guī)基 N={β，β2，β ，…，β}的另一種排序形式，M與N之間a′j與 ai角標(biāo)的映射關(guān)系由參考文獻(xiàn)[6]中推導(dǎo)出，如下所示：

2 重序正規(guī)基字級(jí)乘法器設(shè)計(jì)

2.1 新型字級(jí)重序正規(guī)基乘法算法

對(duì)于任意 A、B∈GF(2m)及其乘積 C∈GF(2m)，均為重序正規(guī)基M上表示的數(shù)。

則C的單比特ci由以下公式得出：

可推出：

綜合式(3)、式(4)和式(5)，可得：

由式(6)可推出一種新型字級(jí)重序正規(guī)基模乘最優(yōu)算法。

算法1新型字級(jí)重序正規(guī)基乘法算法

輸 入 ：A=(a1，… ，am)、B=(b1，… ，bm)∈GF(2m)，d 為 分割字?jǐn)?shù)，1≤d≤m

輸出：C=A×B=(c1，…，cm)∈GF(2m)

②for i=1，2，…，m

④ for l=1，2，…，w，

⑦ end

⑨ end

⑩ end

由以上可得出重序正規(guī)基字級(jí)乘法器的結(jié)構(gòu)，算法1中的運(yùn)算均為單比特。在算法第⑤步中，加法用一個(gè)XOR門來(lái)實(shí)現(xiàn)，乘法用一個(gè)AND門來(lái)實(shí)現(xiàn)，而需要一個(gè)觸發(fā)器來(lái)保持上一個(gè)狀態(tài)的臨時(shí)變量。操作數(shù)A由外部存儲(chǔ)輸入，操作數(shù)B則需要存入一個(gè)(2m+1)bit循環(huán)移位寄存器。其中，在l個(gè)時(shí)鐘狀態(tài)中，函數(shù)s(.)的變化規(guī)律由bs(i+kw+l)和bs(i-kw-l)決定，如式(7)所示 ：

由上式可推出算法中bs(i+kw+l)和bs(i-kw-l)的下標(biāo)，并由兩個(gè)寄存器組成，一個(gè)為R1：

另一個(gè)為R2：

由公式可知，R1與R2其實(shí)為一個(gè)寄存器，設(shè)計(jì)乘法器時(shí)將其作為一個(gè)(2m+1)bit的寄存器來(lái)使用。

2.2 GF(2m)域上重序正規(guī)基字級(jí)乘法器設(shè)計(jì)

根據(jù)算法1，可以設(shè)計(jì)出一種 GF(2m)域上新型基于字級(jí)結(jié)構(gòu)的重序基乘法器，如圖1所示。

圖1 GF(2m)域上重序正規(guī)基字級(jí)乘法器

從圖1中可以看出，該乘法器結(jié)構(gòu)由一個(gè)(2m+1)bit的循環(huán)移位寄存器、連線擴(kuò)散網(wǎng)絡(luò)、一層與門、一層累加單元（該單元由一個(gè)“異或”門和一個(gè)觸發(fā)器組成）以及一層“異或”陣列組成。其中每一路的核心單元為操作數(shù)B的 2 bit相加(“異或”運(yùn)算)后生成 1 bit，然后再與 1 bit操作數(shù)A進(jìn)行相乘（與運(yùn)算）得出1 bit部分積，最后部分積反饋到累加單元從而完成一個(gè)時(shí)鐘周期的運(yùn)算。在經(jīng)過w+d(d=「m/w-1)個(gè)時(shí)鐘周期后累加單元里的值通過“異或”網(wǎng)絡(luò)生成最終1 bit的ci值。根據(jù)以上分析及圖1中的結(jié)構(gòu)，表1中列出了新型字級(jí)重序正規(guī)基乘法器的空間復(fù)雜度。

由于乘積C在經(jīng)過w個(gè)時(shí)鐘周期后還需要經(jīng)過“異或”陣列的延遲之后輸出有效。這額外的延遲Tex=「log2dTX。 綜上所述，總的時(shí)鐘周期數(shù)為

表1 新型字級(jí)重序正規(guī)基乘法器空間復(fù)雜度

3 性能分析與比較

3.1 性能分析

通過前文分析，對(duì)于GF(2m)上的模乘運(yùn)算，該乘法器需要個(gè)時(shí)鐘周期。電路中“與門”個(gè)數(shù)為dm，“異或”門個(gè)數(shù)為2dm，空間復(fù)雜度為dm#AND+2dm#XOR，時(shí)間復(fù)雜度為TA+2TX。將本設(shè)計(jì)與參考文獻(xiàn)[7]中的設(shè)計(jì)進(jìn)行比較，電路面積對(duì)比如表2所示。可以看出，參考文獻(xiàn)[7]的設(shè)計(jì)所占用的電路面積要大于本文中的設(shè)計(jì)。

表2 不同字級(jí)模乘器之間的下復(fù)雜度比較

在表2中，與參考文獻(xiàn)[8]中的Massey-Omura型乘法器設(shè)計(jì)相比，本設(shè)計(jì)采用字級(jí)并行結(jié)構(gòu)以后，空間復(fù)雜度和時(shí)間復(fù)雜度均明顯降低，這表明電路的時(shí)鐘頻率更高，在花費(fèi)相同運(yùn)算時(shí)鐘周期數(shù)的條件下，運(yùn)算速度更快。

3.2 綜合結(jié)果

在對(duì)GF(2233)上的該型正規(guī)基乘法器進(jìn)行仿真驗(yàn)證后，利用Synopsys公司的Design Compiler工具在0.18μm CMOS工藝標(biāo)準(zhǔn)單元庫(kù)下對(duì)設(shè)計(jì)進(jìn)行綜合，表3給出了d=8時(shí)，4.0 ns約束下的綜合報(bào)告。

表3 在0.18μm CMOS工藝標(biāo)準(zhǔn)單元庫(kù)下的綜合結(jié)果

本文設(shè)計(jì)了一種支持II型最優(yōu)正規(guī)基的字級(jí)乘法算法，針對(duì)II型最優(yōu)正規(guī)基與重序正規(guī)基之間的特點(diǎn)，給出了基轉(zhuǎn)換方法，設(shè)計(jì)了一種新的支持II型最優(yōu)正規(guī)基的字級(jí)乘法器。根據(jù)以上的分析和比較，本文設(shè)計(jì)的II型最優(yōu)正規(guī)基乘法器在運(yùn)算速度以及面積等方面具有優(yōu)勢(shì)，與串行結(jié)構(gòu)的傳統(tǒng)正規(guī)基乘法器相比，在GF(2m)上的乘法運(yùn)算效率得到顯著的提高；與全并行結(jié)構(gòu)的傳統(tǒng)正規(guī)基乘法器相比，大大減少了電路面積；其關(guān)鍵路徑延遲與域元素字長(zhǎng)無(wú)關(guān)，能夠滿足公鑰密碼中處理高速性和靈活性的要求。

參考文獻(xiàn)

[1]WILSON R M．Optimal normal bases in GF(pn)[J]．Discrete Applied Mathematics，1988，89(22)：149-161．

[2]ANSI X9-62.Public key cryptography for the financial service industry-the elliptic curve digital signature algorithm(ECDSA)[S].1999.

[3]ANSI X9-63.Public key cryptography for the financial service industry-the elliptic curve key agreement and apparatus for finite field arithmetic[S].2000.

[4]MULLIN R C，WILSON R M.Optimal normal bases in GF(pn)[J].Discrete Applied Math，1989(22)149-161.

[5]GAO S，VANSTONE S.On orders of optimal normal basis generators[J].Math.Computation，1995，64(2)：1227-1233.

[6]WU H，HASAN M A，BLAKE I F，et al.Finite field multiplier using redundant representation[J].IEEE Trans.Computers，2002，51(11)：1306-1316.

[7]NAMIN A H，Wu Huapeng，AHMADI M.A high speed word level finite field multiplier using reordered normal basis[C].IEEE International Symposium on Circuits and Systems，Seattle，2008.

[8]MASOLEH A R，HASAN A.Low complexity word-level sequential normal basis multipliers[J].IEEE Transactions on Computers，2005，54(2)：98-109.