GF(2m)域ECC 點乘算法優(yōu)化設(shè)計*

劉金龍，張玉婷，王 堯

（海軍參謀部，北京 100841）

0 引言

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

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

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

1.1 橢圓曲線的定義

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

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

1.2 橢圓曲線上點的運算

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

（1）當P≠Q(mào)時，點加運算：

（2）當P≠Q(mào)時，點加變?yōu)楸饵c運算：

1.3 橢圓曲線密碼體制的運算層次

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

圖1 橢圓曲線加密體制的運算層次

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

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

2.1 模加運算設(shè)計

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

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

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

2.2 模乘運算設(shè)計

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

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

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

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

2.3 模平方運算設(shè)計

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

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

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

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

2.4 模逆運算設(shè)計

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

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

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

表1 Itoh-Tsujii 模逆計算過程

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

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

3 點乘運算總體方案設(shè)計

3.1 點乘算法分析與設(shè)計

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果分析

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

圖8 仿真波形

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

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

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

5 結(jié)語

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