基于GF（2m）的橢圓曲線求逆算法的改進研究

郭高峰+崔強強

摘 要： 針對二進制域上現有求逆算法計算量大、并行度小、速度慢的缺點進行改進，基于二元Euclidean算法提出了改進，設計了相應的乘法器硬件結構，并且分析了其運算效能和資源占用情況。將此求逆計算器的并行改進算法使用Verilog語言編程實現，利用Xilinx ISE 12.4對整個求逆算法綜合仿真（行為級），在Xilinx Virtex?5 XC5VFX70T的硬件平臺上驗證求逆算法的運算效率，結果表明對求逆算法的改進有效地提高了求逆運算的速度。

關鍵詞： 橢圓加密； 二進制域； 求逆； 擴展歐幾里得算法

中圖分類號： TN918?34； TP309.7 文獻標識碼： A 文章編號： 1004?373X（2014）18?0019?04

Improvement and research of inversion algorithm of elliptic curve based on GF （2m）

GUO Gao?feng1， CUI Qiang?qiang2

（1. Purchasing Center of Navy Equipments， Lianyungang 222000， China； 2. Jiangsu Automation Research Institute， Lianyungang 222000， China）

Abstract： Since the existing inversion operation algorithm based on GF（2m） has the following disadvantages： large amount of calculation， poor degree of parallelism and slow speed， an improved algorithm is proposed in this paper based on Extended Euclidean Algorithm. A corresponding multiplier hardware structure was designed. Its operation performance and the status of resource occupancy are analyzed. This parallel improved algorithm of inversion operation calculator was realized with the program based Verilog. The comprehensive simulation of the whole inversion algorithm was conducted with Xilinx ISE 12.4. The operation efficiency of the inversion algorithm was verified on hardware platform of Xilinx Virtex?5 xc5vfx70t. The experimental result and performance comparison show that the modification of the inversion algorithm has improved its speed.

Keywords： ECC； GF（2m）； inverse operation； expend Euclidean algorithm

0 引 言

橢圓密碼算法ECC（Elliptic Curve Cryptography）[1]具有每bit 最高的安全性[2]，ECC算法的主要優點有[3]：安全性能高；計算量小且運算速度快；占用存儲空間小；對數據運算帶寬要求低。目前常用的定義橢圓曲線的有限域有兩種：素數域GF（p） 和二進制域GF（2m）。在二進制域上元素可以直接用二進制位向量表示，這樣元素的加、減、乘等操作在計算機中可以并行實現，所以二進制域的橢圓曲線加密通常被用于硬件實現的橢圓曲線加密系統中。GF（2m）上的非奇異橢圓曲線是Weierstrass 公式定義的：y2+xy=x3+ax2+b。其中a，b是GF（2m）中的元素，且b≠0。曲線E同時還包括一個無窮遠點，通常用O 表示， 為曲線上點的加法單位元。有限域上的模逆運算是橢圓曲線密碼系統中的關鍵性計算，但是其運算效率卻是最低的，據M.Brown， D.Hankerson等人粗略估計[4]，求逆運算與乘法運算（帶有快速取模運算）的資源占用比是80∶1，因此通過改進加速求逆運算減少其計算時間可以在很大程度上提高橢圓加密的運算效率和吞吐量。

GF（2m）上的求逆算法有兩類：基于費爾瑪小定理使用乘法的算法、擴展歐幾里德算法及其變體。Scliroeppel等人在文獻[5]中提出了Almost求逆算法。如果橢圓加密算法使用仿射坐標，那么求逆運算將是制約標量乘法性能提高的主要瓶頸。擴展歐幾里德算法及其變體適合加密算法的軟件實現；基于擴展歐幾里德算法求逆電路會對核心電路和控制器并行性要求較高，所以硬件實現的研究還較少。

本文基于二元Euclidean算法提出了改進，根據資源和需求的不同，通過修改算法執行結構，將原算法中制約效能的步驟進行改進，并引入并行執行方式，實現了求逆運算的加速。

1 求逆運算的原理

域元素的求逆運算無論在軟件和硬件實現上都有很大復雜度，相比于乘法運算其計算效率要低很多。單純的求逆算法有兩種：基于擴展Euclidean方法的算法、基于Fermat小定理的算法。基于Fermat小定理的算法是將求逆運算轉化為升冪運算，算法中的模乘和模平方運算決定其運算速度，算法的評估軟件得到結果是完成一次求逆運算需要「log2（m-l）」+w（m-1）-1次模乘和m+1次模平方，這種方法不但會增加軟硬件設計的復雜度，算法中的運算需要反復執行，性能受到很大影響[7]。而擴展Euclidean方法便于硬件實現，沒有大量的乘法，只涉及移位、判斷和加法，可以方便并行化設計，因此，本文通過研究三種基于擴展Euclidean方法的算法，得到新的算法：對二元Euclidean方法進行并行優化和改進。

Euclidean算法本質是計算多項式的最大公因式。在多項式a1（x）和a2（x）的最大公因式gcd（（a1（x），a2（x））時，用a1（x）除a2（x）得到商p（x）和余數q（x），滿足a2（x）=a1（x）p（x）+q（x），其中q（x）的次數低于a1（x）的次數，由Euclidean算法得gcd（a1（x），a2（x））=gcd（a1（x），q（x））。

定理1 設a1（x），a2（x）和a3（x）是GF（2m）上的任意多項式，求a1（x）和a2（x）的最大公因式有：gcd（a1（x），a2（x））=gcd（a1（x），a2（x）-a3（x）a1（x））。對于二元擴域上的逆元也可以使用該算法。二元擴域GF（2m）上的元素a，其多項式表示為a（x），那么a的逆元a-1可用a（x）的擴展Eucl idean算法求出。

使用傳統的Euclidean算法計算正整數a，b的gcd原理就是當b≥a時，用a去除b得到商q和余數r，滿足：b=qa+r，且0≤r

算法1 求二進制多項式的Euclidean算法

INPUT： 非零多項式a和b同時deg（a）≤deg（b）。

OUTPUT：d=gcd（a，b） 以及二進制多項式g，y滿足 ag+bh=d。

1. u←a，v←b.

2. g1←1，g2←0，h1←0，h2←1.

3. While u≠0 do

3.1 j←deg（u）-deg（v）.

3.2 If j<0 then：u?v，g1?g2，h1?g2，j←-j.

3.3 u←u+zjv.

3.4 g1←g1 z j g2，h1←h1+zjh2.

4. d←v，g←g2，h←h2.

5.Return（d，g，h）.

假定f為一個m次二進制不可約多項式，非零多項式a的次數不超過m-1，這時gcd（a，f）=1，在算法中，如果輸入是a和f，則在步驟3中，最后的非零的輸入u=1，那么在步驟4中有ag1+fh1=1。所以ag1≡1（mod f）and so a-1=g1。說明：在求取g1的過程中，不需要求出h1和h2，基于此導出如下的求GF（2m）上的求逆的擴展Euclidean算法。

算法2 擴展Euclidean算法求逆[6]

INPUT： a∈GF（2m），a≠0，域的約減多項式f（x）

OUTPUT： a-1 mod f

1.B=1，C=0，U=A，V=F；

2.while deg（U）≠0 do

j=deg（U）-deg（V）；

if j<0 then U=V，B=C，j=-j；

U=U+xjV，B=B+xjC；

3.return B。

算法3 二元Euclidean算法[3]

INPUT： a∈GF（2m），a≠0，域的約減多項式f（x）

OUTPUT： a-1 mod f

1. u←a，v←f，g1←1，g1←0.

2. While（u≠1 and v≠1） do

2.1 While x divides u do

2.1.1 u←u/x.

2.1.2 If x divides g1 then g1←g1/x；else g1←（g1+f）/x.

2.2 While x divides v do

2.2.1 v←v/x.

2.2.2 If x divides g2 then g2←g2/x；else g2←（g2+f）/x.

2.3 If deg（u）>deg（v）then：u←u+v，g1←g1+g2；

Else：v←v+u，g2←g2+g1.

3. If u=1 then return（g1）； else return（g2）.

另外還有一種改進的二進制算法求逆方法叫殆逆算法，運算過程是先計算一個多項式h（x）以及一個正整數k，滿足a（x）h（x）≡xk mod f（x），然后得到a-1（x） = h（x）x-k mod f（x）。如果多項式是某些特定的結構，其約減速度殆逆算法會比二元Euclidean算法快，如果多項式為任意結構，其約減速度比較的話二元Euclidean算法適應性更強。

2 求逆算法的改進及其硬件實現

2.1 改進求逆算法

在實現二元Euclidean算法時，總共需要四個m+1位的寄存器u，v，g1，g2，其中deg（u）和deg（v）分別表示u和v中域元素的多項式次數，在第2步中判斷u和v是否能整除x，只要判斷u和v的最低比特位是否為0，在整除時只要對應的寄存器進行邏輯右移，第3步是域元素的加法，因此制約二元Euclidean算法的執行效率的因素是對循環的判斷，以及比較deg（u）和deg（v）。文獻[8]給出了一種方案，這種算法能在一個時鐘周期內比較deg（u）和deg（v）的函數，其硬件實現結構為優先級譯碼器，這種設計利用硬件資源換取了速度的提高，但是當選取域GF（2m）的m值較大的時候，其延遲也很大。因此，提出一種改進算法有效加速deg（u）和deg（v）的比較，能在很大程度上提高求逆速度。本文就是基于這一思想，增加了兩個寄存器Count_u和Count_v，用于存儲并檢測u和v中元素次數的變化，設計了一種并行的硬件結構，同時執行循環中的判斷和移位、加法操作。本文提出的改進的算法二元Euclidean算法描述如下：

算法4 改進的二元Euclidean算法

INPUT： a∈GF（2m），a≠0，域的約減多項式f（x）

OUTPUT： a-1 mod f

1.u←a，v←f，g1←1，g2←0. Count_u←m，Count_v←m+1

2. While（u≠1 and v≠1） do

利用設計的獨立判斷和移位元件并行執行2.1和2.2

2.1 While Count_u>1 and x divides u do

2.1.1 u←u/x.

2.1.2 Count_u←Count_u-1

2.1.3 If x divides g1 then g1←g1/x；else g1←（g1+f）/x.

2.2 While Count_v >1 and x divides v do

2.2.1 v←v/x.

2.2.2 Count_v←Count_v-1.

2.2.3 If x divides g2 then g2←g2/x；else g2←（g2+f）/x.

3. 并行判斷部件

3.1 If Count_u=1 then return g1.

3.2 Elsif Count_v=1 then return g2.

3.3 Elsif Count_u >Count_v then

3.3.1 u←u+v，g1←g1+g2；

3.3.2 Goto step 2.1

Else：

3.3.1 v←v+u，g2←g2+g1.

3.3.2 Goto step 2.2

本文增加的兩個寄存器Count_u和Count_v只需在初始化的時候賦予二進制項的系數，然后隨著移位的進行檢測u和v的次數的變化，也就是在步驟2.1和2.2中根據相應的跳轉條件減1計數，在硬件中比較兩個（log2（m+1））位的寄存器Count_u和Count_v是容易實現的。程序狀態圖如圖1所示。

圖1 程序運行狀態圖

在循環的判斷、移位、域加法的操作執行時增加的兩個并行部件，這兩個部件同時執行，而且他們的出口都是連接到并行判斷元件上去，一旦跳出條件滿足，兩個部件同時終止，這就避免了串行循環帶來的大延遲，以增加了很小的硬件資源的代價換來了求逆速度的極大的提升。

2.2 改進求逆算法的結構圖

根據2.1節的改進算法，運算流程圖如圖2所示。

圖2 改進算法的運算流程圖

參數初始化之后進入并行執行模塊，在并行執行模塊內部，首先判斷執行條件， 當條件滿足時，在兩個運算部件中分別判斷Count_u和Count_v以及u或者v次數大于1的條件滿足時，分別單獨執行。在并行執行的同時，并行判斷部件也在運行，當Count_u或Count_v的跳轉條件滿足時，Count_u>Count_v或者Count_u

由于改進的求逆算法在計算沒有太多的I/O限制，而且計算密集，判決條件具有并行性，運算步驟可以流水處理和并行處理，根據上述的運算流程，本文基于FPGA設計了高效的執行結構，利用FPGA內部豐富的邏輯布線資源和算法功能塊實現結構圖如圖3所示。

圖3 改進算法的運算結構圖

2.3 硬件仿真與實現

根據2.2節改進原理以及實現結構圖，本文選取有限域GF（2192），編寫相應的Verilog代碼，Xilinx Virtex?5 XC5VFX70T的硬件開發板上對改進算法進行板級驗證。本文設計的求逆代碼仿真結果如圖4所示。

圖4 改進求逆算法一次仿真圖

針對一次求逆所需的時間，與現有的實現效果進行了對比，比較如表1所示，數據表明：在使用資源規模相當的情況下，本文提出的改進算法運算效率提高約20.9%。

3 結 語

橢圓曲線密碼進行實現時，有限域上的求逆運算占有很大比例。由于求逆運算是標量乘法的重要組成部分，提高求逆算法效率可以在很大程度上提高點乘的運算速度，進而提高整個橢圓加密的吞吐率，本文提出的改進二元Euclidean算法，簡化了其中的耗時運算，并且引入了并行化操作機制，在此基礎上設計了一套適合FPGA實現的求逆運算器結構。采用Verilog語言，將此求逆算法進行并行優化，并且編程實現，使用Xilinx ISE 12.4對整個算法仿真、綜合，在Xilinx Virtex?5 XC5VFX70T的開發板上實現了域內標量乘法的驗證，比較結果表明該改進算法有效地提高了橢圓曲線加密算法的硬件運算速度。

表1 求逆運算實現對比

參考文獻

[1] W.DIFFIE H M. New direction in cryptography [J]. IEEE Tran?

sactions on information Theory， 1976， 22（6）： 644?654.

[2] 王峰.GF（2163）上橢圓曲線密碼體制的FPGA實現[D].廣州：廣州大學，2006.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].張煥國，譯.北京：電子工業出版社，2005.

[4] BROWN M， HANKERSON D， LOPEZ J， et al. Software implementation of the NIST elliptic curves over prime fields [C]// Topics in Cryptology?CT?RSA. [S.l.]： Springer， 2002： 250?265.

[5] SEHROEPPEL R， ORMAN H， O′MALLEY S， et al. Fast key exchange with elliptic curve systems [C]// Advances in Cryptology?CRYPTO. [S.l.]： [s.n.]， 1995： 43?56.

[6] IEEE. IEEEP1363?2000 IEEE standard specifications for public?key cryptography [S]. USA： IEEE， 2000.

[7] ZHANG Yu， CHEN Dong?dong， CHOI Younhee， et al. A high performance ECC hardware implementation with instruction?level parallelism over GF（2163） [J]. Microprocessors and Microsystems， 2010， 34： 228?236.

[8] 高獻偉，歐海文，董秀則，等.基于FPGA的GF（2）域求逆算法的設計研究[J].計算機工程與應用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上橢圓曲線模逆運算的設計與實現[J].計算機工程與應用，2008，44（23）：117?119.

[10] 蔡振國，陳韜，郁濱.基于GF（2n）的ECC乘法逆元的快速實現[J].微處理機，2006（3）：59?62.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].張煥國，譯.北京：電子工業出版社，2005.

[4] BROWN M， HANKERSON D， LOPEZ J， et al. Software implementation of the NIST elliptic curves over prime fields [C]// Topics in Cryptology?CT?RSA. [S.l.]： Springer， 2002： 250?265.

[5] SEHROEPPEL R， ORMAN H， O′MALLEY S， et al. Fast key exchange with elliptic curve systems [C]// Advances in Cryptology?CRYPTO. [S.l.]： [s.n.]， 1995： 43?56.

[6] IEEE. IEEEP1363?2000 IEEE standard specifications for public?key cryptography [S]. USA： IEEE， 2000.

[7] ZHANG Yu， CHEN Dong?dong， CHOI Younhee， et al. A high performance ECC hardware implementation with instruction?level parallelism over GF（2163） [J]. Microprocessors and Microsystems， 2010， 34： 228?236.

[8] 高獻偉，歐海文，董秀則，等.基于FPGA的GF（2）域求逆算法的設計研究[J].計算機工程與應用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上橢圓曲線模逆運算的設計與實現[J].計算機工程與應用，2008，44（23）：117?119.

[10] 蔡振國，陳韜，郁濱.基于GF（2n）的ECC乘法逆元的快速實現[J].微處理機，2006（3）：59?62.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].張煥國，譯.北京：電子工業出版社，2005.

[4] BROWN M， HANKERSON D， LOPEZ J， et al. Software implementation of the NIST elliptic curves over prime fields [C]// Topics in Cryptology?CT?RSA. [S.l.]： Springer， 2002： 250?265.

[5] SEHROEPPEL R， ORMAN H， O′MALLEY S， et al. Fast key exchange with elliptic curve systems [C]// Advances in Cryptology?CRYPTO. [S.l.]： [s.n.]， 1995： 43?56.

[6] IEEE. IEEEP1363?2000 IEEE standard specifications for public?key cryptography [S]. USA： IEEE， 2000.

[7] ZHANG Yu， CHEN Dong?dong， CHOI Younhee， et al. A high performance ECC hardware implementation with instruction?level parallelism over GF（2163） [J]. Microprocessors and Microsystems， 2010， 34： 228?236.

[8] 高獻偉，歐海文，董秀則，等.基于FPGA的GF（2）域求逆算法的設計研究[J].計算機工程與應用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上橢圓曲線模逆運算的設計與實現[J].計算機工程與應用，2008，44（23）：117?119.

[10] 蔡振國，陳韜，郁濱.基于GF（2n）的ECC乘法逆元的快速實現[J].微處理機，2006（3）：59?62.