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

郭高峰+崔強(qiáng)強(qiáng)

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

關(guān)鍵詞： 橢圓加密； 二進(jìn)制域； 求逆； 擴(kuò)展歐幾里得算法

中圖分類號(hào)： TN918?34； TP309.7 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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算法的主要優(yōu)點(diǎn)有[3]：安全性能高；計(jì)算量小且運(yùn)算速度快；占用存儲(chǔ)空間??；對(duì)數(shù)據(jù)運(yùn)算帶寬要求低。目前常用的定義橢圓曲線的有限域有兩種：素?cái)?shù)域GF（p） 和二進(jìn)制域GF（2m）。在二進(jìn)制域上元素可以直接用二進(jìn)制位向量表示，這樣元素的加、減、乘等操作在計(jì)算機(jī)中可以并行實(shí)現(xiàn)，所以二進(jìn)制域的橢圓曲線加密通常被用于硬件實(shí)現(xiàn)的橢圓曲線加密系統(tǒng)中。GF（2m）上的非奇異橢圓曲線是Weierstrass 公式定義的：y2+xy=x3+ax2+b。其中a，b是GF（2m）中的元素，且b≠0。曲線E同時(shí)還包括一個(gè)無窮遠(yuǎn)點(diǎn)，通常用O 表示， 為曲線上點(diǎn)的加法單位元。有限域上的模逆運(yùn)算是橢圓曲線密碼系統(tǒng)中的關(guān)鍵性計(jì)算，但是其運(yùn)算效率卻是最低的，據(jù)M.Brown， D.Hankerson等人粗略估計(jì)[4]，求逆運(yùn)算與乘法運(yùn)算（帶有快速取模運(yùn)算）的資源占用比是80∶1，因此通過改進(jìn)加速求逆運(yùn)算減少其計(jì)算時(shí)間可以在很大程度上提高橢圓加密的運(yùn)算效率和吞吐量。

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

本文基于二元Euclidean算法提出了改進(jìn)，根據(jù)資源和需求的不同，通過修改算法執(zhí)行結(jié)構(gòu)，將原算法中制約效能的步驟進(jìn)行改進(jìn)，并引入并行執(zhí)行方式，實(shí)現(xiàn)了求逆運(yùn)算的加速。

1 求逆運(yùn)算的原理

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

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

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

使用傳統(tǒng)的Euclidean算法計(jì)算正整數(shù)a，b的gcd原理就是當(dāng)b≥a時(shí)，用a去除b得到商q和余數(shù)r，滿足：b=qa+r，且0≤r

算法1 求二進(jìn)制多項(xiàng)式的Euclidean算法

INPUT： 非零多項(xiàng)式a和b同時(shí)deg（a）≤deg（b）。

OUTPUT：d=gcd（a，b） 以及二進(jìn)制多項(xiàng)式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為一個(gè)m次二進(jìn)制不可約多項(xiàng)式，非零多項(xiàng)式a的次數(shù)不超過m-1，這時(shí)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，基于此導(dǎo)出如下的求GF（2m）上的求逆的擴(kuò)展Euclidean算法。

算法2 擴(kuò)展Euclidean算法求逆[6]

INPUT： a∈GF（2m），a≠0，域的約減多項(xiàng)式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，域的約減多項(xiàng)式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）.

另外還有一種改進(jìn)的二進(jìn)制算法求逆方法叫殆逆算法，運(yùn)算過程是先計(jì)算一個(gè)多項(xiàng)式h（x）以及一個(gè)正整數(shù)k，滿足a（x）h（x）≡xk mod f（x），然后得到a-1（x） = h（x）x-k mod f（x）。如果多項(xiàng)式是某些特定的結(jié)構(gòu)，其約減速度殆逆算法會(huì)比二元Euclidean算法快，如果多項(xiàng)式為任意結(jié)構(gòu)，其約減速度比較的話二元Euclidean算法適應(yīng)性更強(qiáng)。

2 求逆算法的改進(jìn)及其硬件實(shí)現(xiàn)

2.1 改進(jìn)求逆算法

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

算法4 改進(jìn)的二元Euclidean算法

INPUT： a∈GF（2m），a≠0，域的約減多項(xiàng)式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

利用設(shè)計(jì)的獨(dú)立判斷和移位元件并行執(zhí)行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

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

圖1 程序運(yùn)行狀態(tài)圖

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

2.2 改進(jìn)求逆算法的結(jié)構(gòu)圖

根據(jù)2.1節(jié)的改進(jìn)算法，運(yùn)算流程圖如圖2所示。

圖2 改進(jìn)算法的運(yùn)算流程圖

參數(shù)初始化之后進(jìn)入并行執(zhí)行模塊，在并行執(zhí)行模塊內(nèi)部，首先判斷執(zhí)行條件， 當(dāng)條件滿足時(shí)，在兩個(gè)運(yùn)算部件中分別判斷Count_u和Count_v以及u或者v次數(shù)大于1的條件滿足時(shí)，分別單獨(dú)執(zhí)行。在并行執(zhí)行的同時(shí)，并行判斷部件也在運(yùn)行，當(dāng)Count_u或Count_v的跳轉(zhuǎn)條件滿足時(shí)，Count_u>Count_v或者Count_u

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

圖3 改進(jìn)算法的運(yùn)算結(jié)構(gòu)圖

2.3 硬件仿真與實(shí)現(xiàn)

根據(jù)2.2節(jié)改進(jìn)原理以及實(shí)現(xiàn)結(jié)構(gòu)圖，本文選取有限域GF（2192），編寫相應(yīng)的Verilog代碼，Xilinx Virtex?5 XC5VFX70T的硬件開發(fā)板上對(duì)改進(jìn)算法進(jìn)行板級(jí)驗(yàn)證。本文設(shè)計(jì)的求逆代碼仿真結(jié)果如圖4所示。

圖4 改進(jìn)求逆算法一次仿真圖

針對(duì)一次求逆所需的時(shí)間，與現(xiàn)有的實(shí)現(xiàn)效果進(jìn)行了對(duì)比，比較如表1所示，數(shù)據(jù)表明：在使用資源規(guī)模相當(dāng)?shù)那闆r下，本文提出的改進(jìn)算法運(yùn)算效率提高約20.9%。

3 結(jié) 語

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

表1 求逆運(yùn)算實(shí)現(xiàn)對(duì)比

參考文獻(xiàn)

[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實(shí)現(xiàn)[D].廣州：廣州大學(xué)，2006.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].張煥國，譯.北京：電子工業(yè)出版社，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] 高獻(xiàn)偉，歐海文，董秀則，等.基于FPGA的GF（2）域求逆算法的設(shè)計(jì)研究[J].計(jì)算機(jī)工程與應(yīng)用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上橢圓曲線模逆運(yùn)算的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（23）：117?119.

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

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].張煥國，譯.北京：電子工業(yè)出版社，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] 高獻(xiàn)偉，歐海文，董秀則，等.基于FPGA的GF（2）域求逆算法的設(shè)計(jì)研究[J].計(jì)算機(jī)工程與應(yīng)用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上橢圓曲線模逆運(yùn)算的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（23）：117?119.

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

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].張煥國，譯.北京：電子工業(yè)出版社，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] 高獻(xiàn)偉，歐海文，董秀則，等.基于FPGA的GF（2）域求逆算法的設(shè)計(jì)研究[J].計(jì)算機(jī)工程與應(yīng)用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上橢圓曲線模逆運(yùn)算的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（23）：117?119.

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