劉金龍，張玉婷，王 堯

（海軍參謀部，北京 100841）

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由一種分布式、自組織的Ad hoc 網(wǎng)絡(luò)，但有別于傳統(tǒng)的Wireless Ad hoc 網(wǎng)絡(luò)。WSN 節(jié)點(diǎn)由能量有限、計(jì)算和存儲(chǔ)能力小、具有數(shù)據(jù)采集功能的傳感器節(jié)點(diǎn)組成。隨著傳感器節(jié)點(diǎn)資源的升級和某些傳感器網(wǎng)絡(luò)應(yīng)用的高強(qiáng)度安全需求，非對稱加密算法已被廣泛研究[1]。橢圓曲線密碼算法（Elliptic Curves Cryptography，ECC）因?yàn)樽陨淼陌踩珡?qiáng)度高、密鑰長度短、存儲(chǔ)和帶寬要求低等優(yōu)點(diǎn)[2]，特別適用于WSN 等資源受限的領(lǐng)域。而在ECC 密碼體制中，橢圓曲線的點(diǎn)乘運(yùn)算（Q=kP）是算法安全性的關(guān)鍵，占了整個(gè)運(yùn)算的很大比例，決定了算法的執(zhí)行效率[3]。因此，研究有限域內(nèi)點(diǎn)乘運(yùn)算的優(yōu)化實(shí)現(xiàn)具有重要的意義。

考慮到硬件實(shí)現(xiàn)的特點(diǎn)，本文以二進(jìn)制域的橢圓曲線密碼方案為研究重點(diǎn)，在權(quán)衡資源消耗與運(yùn)算速度的基礎(chǔ)上，設(shè)計(jì)了串并混合的點(diǎn)乘運(yùn)算整體結(jié)構(gòu)，并實(shí)現(xiàn)底層有限域的模加、模乘、模平方和模逆運(yùn)算的輕量化改進(jìn)和電路結(jié)構(gòu)設(shè)計(jì)，最后在FPGA 平臺(tái)上進(jìn)行仿真驗(yàn)證。結(jié)果表明，方案的點(diǎn)乘運(yùn)算效率得到了明顯提升。

1 橢圓曲線密碼基礎(chǔ)

1.1 橢圓曲線的定義

定義在二進(jìn)制域GF(2m)的橢圓曲線可表示如下：

其中a,b∈GF(2m)，且b≠0，除了式（1）所確定的所有點(diǎn)(X,Y)外，還包括一個(gè)特殊的點(diǎn)即無窮遠(yuǎn)點(diǎn)。在實(shí)際應(yīng)用中，為避免一些復(fù)雜的運(yùn)算，橢圓曲線上的點(diǎn)通常用其他坐標(biāo)系表示[4]。在標(biāo)準(zhǔn)射影坐標(biāo)下的點(diǎn)可表示為(X,Y,Z)，Z=0 表示無窮遠(yuǎn)點(diǎn)，Z≠0 時(shí)相互之間的轉(zhuǎn)化關(guān)系為x=X/Z、y=Y/Z。

1.2 橢圓曲線上點(diǎn)的運(yùn)算

橢圓曲線上所有的點(diǎn)的集合外加上無窮遠(yuǎn)點(diǎn)和橢圓曲線上的加法運(yùn)算構(gòu)成一個(gè)加法群[5]。在GF(2m)域內(nèi)，令E為式（1）所表示的曲線，P=(x1,y1)，Q=(x2,y2) ∈E，R=(x3,y3)=P+Q，則P、Q兩點(diǎn)相加的運(yùn)算規(guī)則如下。

（1）當(dāng)P≠Q(mào)時(shí)，點(diǎn)加運(yùn)算：

（2）當(dāng)P≠Q(mào)時(shí)，點(diǎn)加變?yōu)楸饵c(diǎn)運(yùn)算：

1.3 橢圓曲線密碼體制的運(yùn)算層次

點(diǎn)乘運(yùn)算在橢圓曲線加密體制中的作用如圖1 所示。最上層為協(xié)議層，通過調(diào)用點(diǎn)乘運(yùn)算實(shí)現(xiàn)ECC 加解密和數(shù)字簽名；之后為群運(yùn)算層，通過調(diào)用點(diǎn)加和倍點(diǎn)運(yùn)算實(shí)現(xiàn)點(diǎn)乘運(yùn)算；最底層為域運(yùn)算層，包括多種有限域模運(yùn)算，是實(shí)現(xiàn)點(diǎn)加和倍點(diǎn)運(yùn)算的基礎(chǔ)[6]。因此，實(shí)現(xiàn)橢圓曲線點(diǎn)乘運(yùn)算的高效設(shè)計(jì)需要針對不同運(yùn)算層次的特點(diǎn)進(jìn)行針對的優(yōu)化設(shè)計(jì)。

圖1 橢圓曲線加密體制的運(yùn)算層次

2 有限域模運(yùn)算優(yōu)化設(shè)計(jì)

有限域內(nèi)的模運(yùn)算是點(diǎn)乘運(yùn)算實(shí)現(xiàn)的基礎(chǔ)，是影響點(diǎn)乘運(yùn)算效率的關(guān)鍵。下文分別對GF(2m)域上的模加運(yùn)算、模平方運(yùn)算、模乘運(yùn)算和模逆運(yùn)算進(jìn)行優(yōu)化設(shè)計(jì)。

2.1 模加運(yùn)算設(shè)計(jì)

有限域GF(2m)域內(nèi)的加法相對簡單，可以通過將表示模加元素的二進(jìn)制序列進(jìn)行逐位異或運(yùn)算來完成。

它對應(yīng)的硬件電路可用m個(gè)異或門實(shí)現(xiàn)，如圖2 所示。

圖2 模加單元電路結(jié)構(gòu)

2.2 模乘運(yùn)算設(shè)計(jì)

模乘運(yùn)算是影響點(diǎn)乘實(shí)現(xiàn)效率的關(guān)鍵，包括多項(xiàng)式相乘和取模兩步，而多項(xiàng)式相乘部分的計(jì)算周期較長，分為并行和串行兩種類型。有限域GF(2m)并行結(jié)構(gòu)乘法器的硬件復(fù)雜度為m2，它的面積和功耗隨m的增加而增加。在硬件實(shí)現(xiàn)時(shí)常用串行模乘算法，雖然該算法的計(jì)算周期較長，但是其實(shí)現(xiàn)面積和功耗最小[7]，比較適合無線傳感器網(wǎng)絡(luò)這種資源受限的環(huán)境。本文采用一種優(yōu)化的LSB 串行模乘算法，如下：

算法在每次循環(huán)中完成兩次異或和兩次移位操作，對于硬件實(shí)現(xiàn)來說很方便，而且不需要占用任何邏輯單元。通過對A的移位操作，通過A值是否為0 進(jìn)行判斷，確定算法是否結(jié)束。當(dāng)A的高位有多個(gè)0 時(shí)，算法的運(yùn)算效率會(huì)顯著提高。另外，算法中的移位和判斷操作對算法的運(yùn)算效率影響很小。

模乘單元的硬件電路結(jié)構(gòu)如圖3 所示。

圖3 模乘單元電路結(jié)構(gòu)

2.3 模平方運(yùn)算設(shè)計(jì)

在有限域GF(2m)內(nèi)，模平方運(yùn)算可以用模乘來實(shí)現(xiàn)。但是，由上文可知，模乘運(yùn)算的計(jì)算周期較長且硬件電路設(shè)計(jì)復(fù)雜。因此，本文利用有限域GF(2m)下模平方運(yùn)算的特殊性，采用一種基于多項(xiàng)式平方的快速模約減算法，通過預(yù)計(jì)算的方式，犧牲算法的靈活性，達(dá)到提高計(jì)算的效率并減少資源消耗的目的。

對約減多項(xiàng)式f(x)進(jìn)行取模時(shí)，根據(jù)xm=r(x)modf(x)，將A2(x)中次數(shù)高于m-1 的多項(xiàng)式元素轉(zhuǎn)化為低于m位，再把結(jié)果在同一位的所有值進(jìn)行異或。在固定的約減多項(xiàng)式下，通過預(yù)計(jì)算，模平方運(yùn)算可在一次異或運(yùn)算時(shí)間內(nèi)完成，且所用的資源不超過m個(gè)異或門。

針對特定的m≤233 與f(x)=x233+x47+1，對應(yīng)的組合邏輯電路設(shè)計(jì)如圖4 所示。

圖4 GF(2233)域下模平方單元結(jié)構(gòu)

2.4 模逆運(yùn)算設(shè)計(jì)

模逆運(yùn)算是有限域運(yùn)算中最復(fù)雜也是最耗時(shí)的。GF(2m)域上的求模逆算法有兩種——基于擴(kuò)展Euclideam 算法和基于Fermat 小定理的算法[8]。前者通過判斷、移位和異或來實(shí)現(xiàn)模逆運(yùn)算，實(shí)現(xiàn)比較簡單，但是需要增加單獨(dú)的模逆運(yùn)算模塊，大大增加了整體面積；而基于Fermat 小定理的模逆算法是將有限域的逆運(yùn)算轉(zhuǎn)換為模冪運(yùn)算，可以通過調(diào)用模乘和模平方來實(shí)現(xiàn)，算法如下。

可以看出，一次模逆運(yùn)算需要m-2 次模乘和m-1 次模平方。盡管這樣，一次模逆運(yùn)算的計(jì)算效率還是較低。而由前文可知，模乘運(yùn)算的計(jì)算復(fù)雜度比模平方復(fù)雜得多，本文采用Itoh-Tsujii 算法[9]改進(jìn)運(yùn)算，以減少模逆運(yùn)算中的模乘運(yùn)算次數(shù)。

所以，當(dāng)a∈GF(2233)時(shí)，可以得到加法鏈U=(1,2,3,6,7,14,28,29,58,116,232)?？梢钥吹剑笠淮文Ｄ孢\(yùn)算僅需要10 次模乘和232 次模平方運(yùn)算，具體的計(jì)算過程如表1 所示。由計(jì)算過程可知，每一步都具有相關(guān)性，只能串行執(zhí)行。

表1 Itoh-Tsujii 模逆計(jì)算過程

在ECC算法中，模逆與乘法運(yùn)算是分步進(jìn)行的，因此可以將乘法器集成在模逆運(yùn)算單元中，加上一個(gè)模冪運(yùn)算單元組成乘/逆運(yùn)算單元。其中，模冪運(yùn)算可以利用一個(gè)計(jì)數(shù)器和一個(gè)模平方單元實(shí)現(xiàn)。具體的硬件結(jié)構(gòu)如圖5 所示。

圖5 GF(2233)域模乘/逆單元結(jié)構(gòu)

3 點(diǎn)乘運(yùn)算總體方案設(shè)計(jì)

3.1 點(diǎn)乘算法分析與設(shè)計(jì)

ECC 點(diǎn)乘算法包括模加、模平方、模乘和模逆運(yùn)算，其中模逆運(yùn)算的運(yùn)算復(fù)雜度是其他運(yùn)算的數(shù)十倍[10]。在仿射坐標(biāo)下計(jì)算點(diǎn)乘需要多次模逆運(yùn)算，而在投影坐標(biāo)下只需要一次模逆運(yùn)算。為避免進(jìn)行多次模逆運(yùn)算，本文采用投影坐標(biāo)下的Montgomery點(diǎn)乘算法[11]。Montgomery 算法是現(xiàn)階段最安全高效的點(diǎn)乘算法，相較于其他算法不需要進(jìn)行預(yù)處理，且在計(jì)算過程中只用到點(diǎn)的橫坐標(biāo)，特別適合在硬件上實(shí)現(xiàn)。投影坐標(biāo)下的Montgomery 算法包括初始化、主循環(huán)和坐標(biāo)轉(zhuǎn)換3 部分。

初始化部分主要實(shí)現(xiàn)對循環(huán)部分的輸入數(shù)據(jù)初始化處理，輸入投影坐標(biāo)下點(diǎn)P(x0,y0)，輸出投影坐標(biāo)下點(diǎn)P1、P2，可以用兩個(gè)模平方模塊在1 個(gè)時(shí)鐘周期內(nèi)完成。P(x0,1)為點(diǎn)P 在射影坐標(biāo)下的對應(yīng)點(diǎn)，P2為P1的2 倍點(diǎn)，可以利用一個(gè)倍點(diǎn)運(yùn)算在3 個(gè)時(shí)鐘周期內(nèi)實(shí)現(xiàn)。點(diǎn)加和倍點(diǎn)數(shù)據(jù)流分析，如圖6所示。

主循環(huán)部分由m-1 次點(diǎn)加和倍點(diǎn)運(yùn)算組成。由于兩者之間沒有數(shù)據(jù)依賴關(guān)系，可以同時(shí)計(jì)算。通過對循環(huán)部分的數(shù)據(jù)流進(jìn)行分析，可以看出每次循環(huán)中共執(zhí)行6 次模乘、5 次模平方及3 次模加運(yùn)算。本文采用整體串行部分并行的結(jié)構(gòu)，利用兩個(gè)乘法器，將第i次循環(huán)中的點(diǎn)加和倍點(diǎn)運(yùn)算（Montgomery算法中的①②（③④）步）劃分為3 個(gè)階段串行完成，每個(gè)階段中的運(yùn)算并行執(zhí)行。

一次循環(huán)可以用2 個(gè)模乘模塊、2 個(gè)模加模塊和2 個(gè)模平方模塊在3 個(gè)時(shí)鐘周期內(nèi)完成，因此整個(gè)主循環(huán)部分共需要3（m-1）個(gè)時(shí)鐘周期。

坐標(biāo)轉(zhuǎn)換部分主要實(shí)現(xiàn)將投影坐標(biāo)變換成仿射坐標(biāo)，輸入投影坐標(biāo)下點(diǎn)P1、P2，輸出仿射坐標(biāo)下點(diǎn)Q(Qx,Qy)。主要計(jì)算過程為：

可見，它包括1 次模逆、10 次模乘、1 次模平方和7 次模加運(yùn)算，可以用1 個(gè)乘法單元、1 個(gè)乘/逆單元、2 個(gè)加法單元和1 個(gè)平方單元在6+t個(gè)時(shí)鐘周期內(nèi)實(shí)現(xiàn)，其中t為一次模逆運(yùn)算的時(shí)間。

3.2 總體電路結(jié)構(gòu)設(shè)計(jì)

點(diǎn)乘運(yùn)算3 個(gè)部分的結(jié)構(gòu)可以共用，整體的硬件電路實(shí)現(xiàn)如圖7 所示，共需要1 個(gè)模乘單元、1個(gè)模乘/逆單元、2 個(gè)模加單元和2 個(gè)模平方單元，共使用7 個(gè)寄存器X1、Z1、X2、Z2、T1、T2、R。其中，用來存儲(chǔ)曲線的參數(shù)值x0、y0、b，寄存器X1、Z1、X2、Z2用來存儲(chǔ)點(diǎn)乘算法中的坐標(biāo)值，T1和T2寄存計(jì)算過程的中間值。

圖7 點(diǎn)乘總體電路結(jié)構(gòu)

4 實(shí)驗(yàn)結(jié)果分析

本文選用GF(2233)域上的Koblitz 曲線，y2+xy=x3+x2+1，對本文的點(diǎn)乘運(yùn)算方案進(jìn)行驗(yàn)證。以Artix7 器件中的XC7A100T 為硬件平臺(tái)，利用Verilog 語言在FPGA 平臺(tái)上進(jìn)行結(jié)果仿真驗(yàn)證，并選用Modelsim 軟件進(jìn)行波形分析。圖8 是本方案執(zhí)行一次點(diǎn)乘運(yùn)算的仿真結(jié)果。

圖8 仿真波形

根據(jù)本文設(shè)計(jì)的方案，在GF(2233)域內(nèi)完成一次點(diǎn)乘運(yùn)算共需要3+233×3+6+t個(gè)時(shí)鐘周期，其中t為一次逆運(yùn)算的時(shí)間。在FPGA 上的仿真結(jié)果及與其他方案的對比如表2 所示，算法執(zhí)行過程中占用10 682 個(gè)Slices 資源，共用時(shí)1.644 4 ms。

表2 測試結(jié)果及對比

通過與其他相關(guān)文獻(xiàn)的對比可以看出，本文設(shè)計(jì)的點(diǎn)乘計(jì)算方案在占用面積和計(jì)算時(shí)間上都有所提升。

5 結(jié)語

本文通過對ECC 密碼算法進(jìn)行研究，針對不同運(yùn)算層次的特點(diǎn)作了針對的優(yōu)化改進(jìn)，設(shè)計(jì)并實(shí)現(xiàn)了輕量化ECC 點(diǎn)乘計(jì)算方案。首，先通過對有限域的模運(yùn)算單元進(jìn)行研究，重點(diǎn)對模乘和模逆計(jì)算單元進(jìn)行了改進(jìn)；其次，根據(jù)Montgomery 點(diǎn)乘算法設(shè)計(jì)整體的計(jì)算流程，并以此為基礎(chǔ)實(shí)現(xiàn)了有限域運(yùn)算單元和整體點(diǎn)乘方案的電路結(jié)構(gòu)設(shè)計(jì)。本文方案采用整體串行部分并行，經(jīng)過在FPGA 平臺(tái)上測試并與其他方案進(jìn)行對比，達(dá)到了計(jì)算速度與占用面積的優(yōu)化平衡，可以很好地適應(yīng)于無線傳感器網(wǎng)絡(luò)等資源受限的場合。