郭高峰+崔強強
摘 要: 針對二進制域上現(xiàn)有求逆算法計算量大、并行度小、速度慢的缺點進行改進,基于二元Euclidean算法提出了改進,設(shè)計了相應(yīng)的乘法器硬件結(jié)構(gòu),并且分析了其運算效能和資源占用情況。將此求逆計算器的并行改進算法使用Verilog語言編程實現(xiàn),利用Xilinx ISE 12.4對整個求逆算法綜合仿真(行為級),在Xilinx Virtex?5 XC5VFX70T的硬件平臺上驗證求逆算法的運算效率,結(jié)果表明對求逆算法的改進有效地提高了求逆運算的速度。
關(guān)鍵詞: 橢圓加密; 二進制域; 求逆; 擴展歐幾里得算法
中圖分類號: 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算法的主要優(yōu)點有[3]:安全性能高;計算量小且運算速度快;占用存儲空間??;對數(shù)據(jù)運算帶寬要求低。目前常用的定義橢圓曲線的有限域有兩種:素數(shù)域GF(p) 和二進制域GF(2m)。在二進制域上元素可以直接用二進制位向量表示,這樣元素的加、減、乘等操作在計算機中可以并行實現(xiàn),所以二進制域的橢圓曲線加密通常被用于硬件實現(xiàn)的橢圓曲線加密系統(tǒng)中。GF(2m)上的非奇異橢圓曲線是Weierstrass 公式定義的:y2+xy=x3+ax2+b。其中a,b是GF(2m)中的元素,且b≠0。曲線E同時還包括一個無窮遠點,通常用O 表示, 為曲線上點的加法單位元。有限域上的模逆運算是橢圓曲線密碼系統(tǒng)中的關(guān)鍵性計算,但是其運算效率卻是最低的,據(jù)M.Brown, D.Hankerson等人粗略估計[4],求逆運算與乘法運算(帶有快速取模運算)的資源占用比是80∶1,因此通過改進加速求逆運算減少其計算時間可以在很大程度上提高橢圓加密的運算效率和吞吐量。
GF(2m)上的求逆算法有兩類:基于費爾瑪小定理使用乘法的算法、擴展歐幾里德算法及其變體。Scliroeppel等人在文獻[5]中提出了Almost求逆算法。如果橢圓加密算法使用仿射坐標,那么求逆運算將是制約標量乘法性能提高的主要瓶頸。擴展歐幾里德算法及其變體適合加密算法的軟件實現(xiàn);基于擴展歐幾里德算法求逆電路會對核心電路和控制器并行性要求較高,所以硬件實現(xiàn)的研究還較少。
本文基于二元Euclidean算法提出了改進,根據(jù)資源和需求的不同,通過修改算法執(zhí)行結(jié)構(gòu),將原算法中制約效能的步驟進行改進,并引入并行執(zhí)行方式,實現(xiàn)了求逆運算的加速。
1 求逆運算的原理
域元素的求逆運算無論在軟件和硬件實現(xiàn)上都有很大復(fù)雜度,相比于乘法運算其計算效率要低很多。單純的求逆算法有兩種:基于擴展Euclidean方法的算法、基于Fermat小定理的算法?;贔ermat小定理的算法是將求逆運算轉(zhuǎn)化為升冪運算,算法中的模乘和模平方運算決定其運算速度,算法的評估軟件得到結(jié)果是完成一次求逆運算需要「log2(m-l)」+w(m-1)-1次模乘和m+1次模平方,這種方法不但會增加軟硬件設(shè)計的復(fù)雜度,算法中的運算需要反復(fù)執(zhí)行,性能受到很大影響[7]。而擴展Euclidean方法便于硬件實現(xiàn),沒有大量的乘法,只涉及移位、判斷和加法,可以方便并行化設(shè)計,因此,本文通過研究三種基于擴展Euclidean方法的算法,得到新的算法:對二元Euclidean方法進行并行優(yōu)化和改進。
Euclidean算法本質(zhì)是計算多項式的最大公因式。在多項式a1(x)和a2(x)的最大公因式gcd((a1(x),a2(x))時,用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)上的任意多項式,求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算法求出。
算法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
利用設(shè)計的獨立判斷和移位元件并行執(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
本文增加的兩個寄存器Count_u和Count_v只需在初始化的時候賦予二進制項的系數(shù),然后隨著移位的進行檢測u和v的次數(shù)的變化,也就是在步驟2.1和2.2中根據(jù)相應(yīng)的跳轉(zhuǎn)條件減1計數(shù),在硬件中比較兩個(log2(m+1))位的寄存器Count_u和Count_v是容易實現(xiàn)的。程序狀態(tài)圖如圖1所示。
圖1 程序運行狀態(tài)圖
在循環(huán)的判斷、移位、域加法的操作執(zhí)行時增加的兩個并行部件,這兩個部件同時執(zhí)行,而且他們的出口都是連接到并行判斷元件上去,一旦跳出條件滿足,兩個部件同時終止,這就避免了串行循環(huán)帶來的大延遲,以增加了很小的硬件資源的代價換來了求逆速度的極大的提升。
2.2 改進求逆算法的結(jié)構(gòu)圖
根據(jù)2.1節(jié)的改進算法,運算流程圖如圖2所示。
圖2 改進算法的運算流程圖
參數(shù)初始化之后進入并行執(zhí)行模塊,在并行執(zhí)行模塊內(nèi)部,首先判斷執(zhí)行條件, 當(dāng)條件滿足時,在兩個運算部件中分別判斷Count_u和Count_v以及u或者v次數(shù)大于1的條件滿足時,分別單獨執(zhí)行。在并行執(zhí)行的同時,并行判斷部件也在運行,當(dāng)Count_u或Count_v的跳轉(zhuǎn)條件滿足時,Count_u>Count_v或者Count_u 由于改進的求逆算法在計算沒有太多的I/O限制,而且計算密集,判決條件具有并行性,運算步驟可以流水處理和并行處理,根據(jù)上述的運算流程,本文基于FPGA設(shè)計了高效的執(zhí)行結(jié)構(gòu),利用FPGA內(nèi)部豐富的邏輯布線資源和算法功能塊實現(xiàn)結(jié)構(gòu)圖如圖3所示。 圖3 改進算法的運算結(jié)構(gòu)圖 2.3 硬件仿真與實現(xiàn) 根據(jù)2.2節(jié)改進原理以及實現(xiàn)結(jié)構(gòu)圖,本文選取有限域GF(2192),編寫相應(yīng)的Verilog代碼,Xilinx Virtex?5 XC5VFX70T的硬件開發(fā)板上對改進算法進行板級驗證。本文設(shè)計的求逆代碼仿真結(jié)果如圖4所示。 圖4 改進求逆算法一次仿真圖 針對一次求逆所需的時間,與現(xiàn)有的實現(xiàn)效果進行了對比,比較如表1所示,數(shù)據(jù)表明:在使用資源規(guī)模相當(dāng)?shù)那闆r下,本文提出的改進算法運算效率提高約20.9%。 3 結(jié) 語 橢圓曲線密碼進行實現(xiàn)時,有限域上的求逆運算占有很大比例。由于求逆運算是標量乘法的重要組成部分,提高求逆算法效率可以在很大程度上提高點乘的運算速度,進而提高整個橢圓加密的吞吐率,本文提出的改進二元Euclidean算法,簡化了其中的耗時運算,并且引入了并行化操作機制,在此基礎(chǔ)上設(shè)計了一套適合FPGA實現(xiàn)的求逆運算器結(jié)構(gòu)。采用Verilog語言,將此求逆算法進行并行優(yōu)化,并且編程實現(xiàn),使用Xilinx ISE 12.4對整個算法仿真、綜合,在Xilinx Virtex?5 XC5VFX70T的開發(fā)板上實現(xiàn)了域內(nèi)標量乘法的驗證,比較結(jié)果表明該改進算法有效地提高了橢圓曲線加密算法的硬件運算速度。 表1 求逆運算實現(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實現(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] 高獻偉,歐海文,董秀則,等.基于FPGA的GF(2)域求逆算法的設(shè)計研究[J].計算機工程與應(yīng)用,2005(9):135?137.
[9] 秦帆,戴紫衫.有限素域上橢圓曲線模逆運算的設(shè)計與實現(xiàn)[J].計算機工程與應(yīng)用,2008,44(23):117?119.
[10] 蔡振國,陳韜,郁濱.基于GF(2n)的ECC乘法逆元的快速實現(xiàn)[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] 高獻偉,歐海文,董秀則,等.基于FPGA的GF(2)域求逆算法的設(shè)計研究[J].計算機工程與應(yīng)用,2005(9):135?137.
[9] 秦帆,戴紫衫.有限素域上橢圓曲線模逆運算的設(shè)計與實現(xiàn)[J].計算機工程與應(yīng)用,2008,44(23):117?119.
[10] 蔡振國,陳韜,郁濱.基于GF(2n)的ECC乘法逆元的快速實現(xiàn)[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] 高獻偉,歐海文,董秀則,等.基于FPGA的GF(2)域求逆算法的設(shè)計研究[J].計算機工程與應(yīng)用,2005(9):135?137.
[9] 秦帆,戴紫衫.有限素域上橢圓曲線模逆運算的設(shè)計與實現(xiàn)[J].計算機工程與應(yīng)用,2008,44(23):117?119.
[10] 蔡振國,陳韜,郁濱.基于GF(2n)的ECC乘法逆元的快速實現(xiàn)[J].微處理機,2006(3):59?62.