基于FPGA的Edwards曲線標量乘法實現方法*

2015-03-25 05:29:36韓煉冰段俊紅房利國

通信技術 2015年10期

韓煉冰,段俊紅,王松,房利國,劉蘊

(中國電子科技集團公司第三十研究所，四川成都 610041)

韓煉冰,段俊紅,王松,房利國,劉蘊

(中國電子科技集團公司第三十研究所，四川成都 610041)

點加和倍點是標量乘法的基本運算。首先對原始的Edwards曲線計算公式進行了研究,再結合FPGA并行計算的特點，提出了一種適合FPGA快速實現的點加和倍點計算方法；其次給出了并行和串行兩種標量乘法算法。最后在ALTERA的EP2AGX260 FPGA中分別對兩種標量乘法進行了實現和測試。結果表明，該實現方法能達到較理想的效果。

Edwards曲線；FPGA；標量乘法；點加；倍點

0 引言

橢圓曲線密碼體制(ECC)是1985提出的。同RSA密碼體制比，要達到相同安全強度，它可以使用較RSA密碼更短的密鑰。由于密鑰短，所以工程實現的加密速度較快，并節省資源、帶寬和存儲空間，適于在移動通信、智能卡等系統中運用[1]，并已成為信息安全領域研究的熱點。

Edwards[2]曲線是2007年提出的一種新形式的橢圓曲線，該曲線的主要優勢是其上的群運算規則較簡單，且倍點和點加運算具有相同的公式。文獻[3]的進行一步研究表明Edwards群運算的效率及安全性優于Jacobian等其他形式的橢圓曲線[4]。

橢圓曲線標量乘法np是ECC中最耗時的運算，直接影響著ECC算法的運算效率。本文首先介紹Edwards曲線及其運算算法，再根據FPGA并行計算的特性，將原算法進行分解，設計了一種采用兩個模乘法器和一個模加法器結構的快速點加實現方法，并將其用在了標量乘法的FPGA編程實現中。

1 Edwards曲線

Edwards給出的橢圓曲線表達形式為：

X2+Y2=C2(1+X2Y2)

(1)

(0,C)為曲線式(1)的零元，該形式下的曲線加法較簡單，且加法法則具有完備性。Bernstein和Lange將Edwards曲線進行擴展，表達形式為[5]：

X2+Y2=C2(1+dX2Y2)

(2)

其中c,d∈k,c,d≠0，且cd4≠1,(0,1)為其零元。進一步的研究表明，任何特征值不為2的域上的橢圓曲線均可轉換為該域上C=1的曲線，即式(2)簡化為:

X2+Y2=1+dX2Y2

(3)

曲線式(3)的零元為(0,1)。令P1=(X1,Y1),P2=(X2,Y2)為曲線式(3)上的兩個點，P3=(X3,Y3)為P1,P2兩點相加的結果，則有:

(4)

對于倍點運算，即當P1=P2時，公式(4)仍然成立。Edwards曲線點加和倍點計算公式相同的這一特性對FPGA實現來說可以節省不少的資源，尤其是在域的數據很大，如256比特或者更多時。

2 標量乘法的FPGA實現

標量乘法nP的運算最終都會轉化成多次點加和倍點運算來完成。通過公式(4)知道，完成一次點加或者倍點需要進行2次求逆運算，8次乘法運算，4次加法運算。通常求逆運算非常耗時，為了盡可能的減少求逆運算，采用標準射影坐標代替原來的仿射坐標，即仿射坐標下的點(x,y)在射影坐標下表示成(X,Y,Z)，兩種坐標下點的對應關系為x=X/Z,y=Y/Z,Z≠0。在射影坐標系下，不需要對每次點加或者倍點后的結果求逆，只需要在運算完成后從射影坐標轉換到仿射坐標時進行一次求逆運算，因而大大提高了算法實現效率。標量乘法的設計框圖如圖1所示：

圖1 標量乘法設計框圖

2.1 點加倍點的FPGA實現

假定P1=(X1,Y1,Z1),P2=(X2,Y2,Z2)為射影坐標的兩點，P3=(X3,Y3,Z3)為P1,P2兩個點相加的結果，那么有:

FPGA實現時，采用2個模乘法器和1個模加減法器的并行結構，并定義一些寄存器存放中間結果，約7次模乘后即可完成X3,Y3,Z3的計算，實現框圖如圖2所示。點加的FPGA實現算法如下：

算法1：點加運算

輸入：P1=(X1,Y1,Z1),P2=(X2,Y2,Z2)

輸出：P3=(X3,Y3,Z3)

(1)t1=X1Y2t2=X2Y1NULL

(2)t3=Z1Z2t2=t1t2t1=t1+t2

(3)t5=X1X2t4=Y2Y1NULL

(4)t6=t3t3t2=dt2t4=t4-t5

(5)t4=t4t3t5=t1t3t1=t6-t2

(6)NULLNULLt3=t6+t2

(7)Y3=t4t3Z3=t1t3NULLt2←t5

(8)NULLX3=t1t2NULL

其中，每個步驟中的三列分別對應于圖2中的模乘法器1、模乘法器2和模加減法器。t1,t2,t3,t4,t5,t6為寄存器中間結果，NULL表示當前步驟不做運算。值得注意的是：橢圓曲線運算的數據通常都是一個大數，在某些FPGA上實現時往往出現FPGA的邏輯資源使用不多，但編譯卻失敗的情況。這種情況多因為FPGA內部數據位寬很寬，導致了局部布線資源不足。算法1的步驟7)中t2←t5表示在模乘法器運算完成后將t5的值賦給t2，不屬于加法器或者乘法器的運算。這樣可以減少模乘法器2的一個輸入變量，對FPGA設計起到一定的優化作用。

圖2 點加實現框圖

2.2 模乘及模加減的FPGA實現

模乘法器采用文獻[6]的快速實現方法，并將流水線級數增加了原文的一倍，從而使模乘運算的效率提高了42%。以384比特的數據為例，完成一次模乘運算的時間，從原來的96個時鐘節拍減少到改進后的56個時鐘節拍。

模加減法器完成兩個大數的相加或相減并對結果取模，實現方法為：將大數拆分成多個64 bit段，每段數據串行相加或者相減并進行模運算。以384比特數據為例子，完成一次模加減運算需要7個時鐘節拍。

2.3 坐標轉換及求逆的實現

標量乘法完成后需要將射影坐標系的點(X,Y,Z)轉換仿射坐標的點(x,y)，其中x=X/Z,y=Y/Z。計算x,y時，與點加倍點共用模乘法器1和模乘法器2。

求逆運算采用擴展的歐幾里德算法。

2.4 標量乘法的實現

標量乘法中的通常是一個大整數。FPGA實現時將n轉換成二進制形式，再逐位計算。計算時有兩種方法：一是由低位向高位開始計算，稱為并行計算；二是由高位向低位計算，稱為串行計算。兩種計算算法如下：

算法2：標量乘法并行計算

輸出：Q=nP

(1)Q←0

(2)Forifrom0tok-1do

(3)Ifni=1,Q←Q+P

(4)P←2P

(5)endfor

(6)returnQ

算法3：標量乘法串行計算

輸出：Q=nP

(1)Q←0

(2)Forifromk-1to0do

(3)Q=2Q

(4)Ifni=1,Q←Q+P

(5)endfor

(6)returnQ

算法2和算法3中的Q+P為點加運算，2P和2Q為倍點計算。從算法2的計算公式可以看出，該算法的優點有：一是在FPGA實現時，點加運算和倍點運算可以并行執行，能大大提高算法效率；二是算法的運算時間不依賴于n的具體比特位值，因此可以抵御SPA(簡單能量攻擊)等。算法2的缺點是多占用FPGA的硬件資源。算法3的優缺點恰與算法2相反，點加運算需用到倍點的運算結果，使算法只能串行計算，從而降低算法性能。同時，點加是否執行依賴于當前循環的比特位ni是否為1，因此計算時間與具體的n值有關。但算法3的優點是點加倍點共用一個模塊，可以大大減少硬件資源。

2.5 實現結果

選用ALTERA公司的EP2AGX45C6FPGA平臺對算法2和算法3進行了實現。表1和表2分別給出了并行和串行兩種實現方式的性能和資源比較，其中，實現1對應算法2，實現2對應算法3。

表1 性能比較

表2 資源消耗比較

3 結語

本文將原始的點加公式進行了坐標轉換，將轉換后的公式進行了分解，給出了適合FPGA并行計算的點加計算公式。最后給出了兩個標量乘法計算公式，分別對應于FPGA的資源優先和性能優先兩種實現方式，并對兩種實現方式的資源和性能做了比較，有很好的實用意義。

標量乘法中的倍點運算是必不可少的，當前有關標量乘法的優化都是減少點加運算的次數(如非相鄰表示(NAF)法[7],窗口法[8]等)，但由此會帶來額外的資源轉換開銷或者存儲資源開銷，對于資源寶貴的FPGA而言不一定適合。目前，針對Edwards曲線FPGA實現的研究較少，如何提高標量乘法的性能且又適合FPGA實現還需更深入的研究。

[1] 金曉剛.素數域上橢圓曲線密碼體制的軟件實現[J].通信技術，2010,43(09):136-138. JIN Xiao-gang. Software Implementation of Elliptic Curve Cryptosystem over Prime Field[J].Communications Technology，2010,43(09): 136-138.

[2] Edwards H M.A Normal Form for Elliptic Curves[J].Bulletin of the American Mathematical Society, 2007, 44(3): 393-422.

[3] Bernstein D J，Lange T. Faster Addition and Doubling on Elliptic Curves[J].Asiacrypt,2007(10):29-50.

[4] 張寶華,殷新春,張海靈.Edwards曲線安全快速標量乘法運算算法—EDSM[J].通信學報，2008,29(10):76-81. ZHANG Bao-hua, YIN Xin-chun，ZHANG Hai-ling. EDSM: Secure and Efficient Scalar Multiplication Algorithm on Edwards Curves[J].Journal on Communications，2008,29(10):76-81.

[5] 蘇賀鵬，張盛兵.基于二進制Edwards曲線的橢圓曲線加密多標量乘法結構設計與實現[J].微電子學與計算機, 2011,28(2):98-102. SU He-peng, ZHANG Shen-bing. Design and Implementation of an Architecture Multi-Scalar Multiplication for ECC based on Binary Edwards Curves[J].Microelectronics & Computer, 2011,28(2):98-102.

[6] 韓煉冰，黃銳，段俊紅.基于FPGA的素域模乘快速實現方法[J].信息安全與通信保密,2013(09):76-78. HAN Lian-bing，HUANG Rui，DUAN Jun-hong. Fast Implementation Method of Prime Fields Modular Multiplication based on FPGA[J].Information Security and Communications Privacy,2013(09):76-78.

[7] 龔亮.基于GF(P)橢圓曲線加密的點乘實現方案[J].大眾科技，2011(12):4-6. GONG Liang. Implementation of Point Multiplication for ECC over GF(P)[J].Popular Science,2011(12):4-6.

[8] 劉彬彬，聶意新，嚴燁.橢圓曲線倍點算法的比較研究[J].信息網絡安全,2013(06):22-25. LIU Bin-bin, NIE Yi-xin, YAN Ye. Comparisons of Point Multiplication in Elliptic Curve Cryptography[J].Net Info Security,2013(06):22-25.

FPGA-based Implementation of Scalar Multiplication on Edwards Curve

HAN Lian-bing, DUAN Jun-hong, WANG Song, FANG Li-guo, LIU Yun

(No.30 Institute of CETC, Chengdu Sichuan 610041, China)

Point-plus and double-point operation is the basic operation of scalar multiplication. Firstly, the original formula of Edwards curve is studied, and in combination with the characteristics of FPGA parallel computing,a point-plus and double-point computing method suitable for fast implementation of FPGA is proposed,and then both parallel and serial scalar multiplication algorithms are presented, and finally, both two scalar multiplications are implemented and tested on EP2AGX260 FPGA of ALTERA. Results show that this implementation method could achieve a fairly ideal effect.

Edwards curve; FPGA; scalar multiplication; point plus; double point

10.3969/j.issn.1002-0802.2015.10.016

2015-06-01；

2015-09-14 Received date:2015-06-01；Revised date：2015-09-14

TN918.4

1002-0802(2015)10-1179-04