基于FPGA的Edwards曲線標(biāo)量乘法實(shí)現(xiàn)方法*

韓煉冰,段俊紅,王 松,房利國(guó),劉 蘊(yùn)

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

基于FPGA的Edwards曲線標(biāo)量乘法實(shí)現(xiàn)方法*

韓煉冰,段俊紅,王 松,房利國(guó),劉 蘊(yùn)

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

點(diǎn)加和倍點(diǎn)是標(biāo)量乘法的基本運(yùn)算。首先對(duì)原始的Edwards曲線計(jì)算公式進(jìn)行了研究,再結(jié)合FPGA并行計(jì)算的特點(diǎn)，提出了一種適合FPGA快速實(shí)現(xiàn)的點(diǎn)加和倍點(diǎn)計(jì)算方法；其次給出了并行和串行兩種標(biāo)量乘法算法。最后在ALTERA的EP2AGX260 FPGA中分別對(duì)兩種標(biāo)量乘法進(jìn)行了實(shí)現(xiàn)和測(cè)試。結(jié)果表明，該實(shí)現(xiàn)方法能達(dá)到較理想的效果。

Edwards曲線；FPGA；標(biāo)量乘法；點(diǎn)加；倍點(diǎn)

0 引 言

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

Edwards[2]曲線是2007年提出的一種新形式的橢圓曲線，該曲線的主要優(yōu)勢(shì)是其上的群運(yùn)算規(guī)則較簡(jiǎn)單，且倍點(diǎn)和點(diǎn)加運(yùn)算具有相同的公式。文獻(xiàn)[3]的進(jìn)行一步研究表明Edwards群運(yùn)算的效率及安全性優(yōu)于Jacobian等其他形式的橢圓曲線[4]。

橢圓曲線標(biāo)量乘法np是ECC中最耗時(shí)的運(yùn)算，直接影響著ECC算法的運(yùn)算效率。本文首先介紹Edwards曲線及其運(yùn)算算法，再根據(jù)FPGA并行計(jì)算的特性，將原算法進(jìn)行分解，設(shè)計(jì)了一種采用兩個(gè)模乘法器和一個(gè)模加法器結(jié)構(gòu)的快速點(diǎn)加實(shí)現(xiàn)方法，并將其用在了標(biāo)量乘法的FPGA編程實(shí)現(xiàn)中。

1 Edwards曲線

Edwards給出的橢圓曲線表達(dá)形式為：

X2+Y2=C2(1+X2Y2)

(1)

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

X2+Y2=C2(1+dX2Y2)

(2)

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

X2+Y2=1+dX2Y2

(3)

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

(4)

對(duì)于倍點(diǎn)運(yùn)算，即當(dāng)P1=P2時(shí)，公式(4)仍然成立。Edwards曲線點(diǎn)加和倍點(diǎn)計(jì)算公式相同的這一特性對(duì)FPGA實(shí)現(xiàn)來(lái)說(shuō)可以節(jié)省不少的資源，尤其是在域的數(shù)據(jù)很大，如256比特或者更多時(shí)。

2 標(biāo)量乘法的FPGA實(shí)現(xiàn)

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

圖1 標(biāo)量乘法設(shè)計(jì)框圖

2.1 點(diǎn)加倍點(diǎn)的FPGA實(shí)現(xiàn)

假定P1=(X1,Y1,Z1),P2=(X2,Y2,Z2)為射影坐標(biāo)的兩點(diǎn)，P3=(X3,Y3,Z3)為P1,P2兩個(gè)點(diǎn)相加的結(jié)果，那么有:

FPGA實(shí)現(xiàn)時(shí)，采用2個(gè)模乘法器和1個(gè)模加減法器的并行結(jié)構(gòu)，并定義一些寄存器存放中間結(jié)果，約7次模乘后即可完成X3,Y3,Z3的計(jì)算，實(shí)現(xiàn)框圖如圖2所示。點(diǎn)加的FPGA實(shí)現(xiàn)算法如下：

算法1：點(diǎn)加運(yùn)算

輸入：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

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

圖2 點(diǎn)加實(shí)現(xiàn)框圖

2.2 模乘及模加減的FPGA實(shí)現(xiàn)

模乘法器采用文獻(xiàn)[6]的快速實(shí)現(xiàn)方法，并將流水線級(jí)數(shù)增加了原文的一倍，從而使模乘運(yùn)算的效率提高了42%。以384比特的數(shù)據(jù)為例，完成一次模乘運(yùn)算的時(shí)間，從原來(lái)的96個(gè)時(shí)鐘節(jié)拍減少到改進(jìn)后的56個(gè)時(shí)鐘節(jié)拍。

模加減法器完成兩個(gè)大數(shù)的相加或相減并對(duì)結(jié)果取模，實(shí)現(xiàn)方法為：將大數(shù)拆分成多個(gè)64 bit段，每段數(shù)據(jù)串行相加或者相減并進(jìn)行模運(yùn)算。以384比特?cái)?shù)據(jù)為例子，完成一次模加減運(yùn)算需要7個(gè)時(shí)鐘節(jié)拍。

2.3 坐標(biāo)轉(zhuǎn)換及求逆的實(shí)現(xiàn)

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

求逆運(yùn)算采用擴(kuò)展的歐幾里德算法。

2.4 標(biāo)量乘法的實(shí)現(xiàn)

標(biāo)量乘法中的通常是一個(gè)大整數(shù)。FPGA實(shí)現(xiàn)時(shí)將n轉(zhuǎn)換成二進(jìn)制形式，再逐位計(jì)算。計(jì)算時(shí)有兩種方法：一是由低位向高位開(kāi)始計(jì)算，稱為并行計(jì)算；二是由高位向低位計(jì)算，稱為串行計(jì)算。兩種計(jì)算算法如下：

算法2：標(biāo)量乘法并行計(jì)算

輸出：Q=nP

(1)Q←0

(2)Forifrom0tok-1do

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

(4)P←2P

(5)endfor

(6)returnQ

算法3：標(biāo)量乘法串行計(jì)算

輸出：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為點(diǎn)加運(yùn)算，2P和2Q為倍點(diǎn)計(jì)算。從算法2的計(jì)算公式可以看出，該算法的優(yōu)點(diǎn)有：一是在FPGA實(shí)現(xiàn)時(shí)，點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算可以并行執(zhí)行，能大大提高算法效率；二是算法的運(yùn)算時(shí)間不依賴于n的具體比特位值，因此可以抵御SPA(簡(jiǎn)單能量攻擊)等。算法2的缺點(diǎn)是多占用FPGA的硬件資源。算法3的優(yōu)缺點(diǎn)恰與算法2相反，點(diǎn)加運(yùn)算需用到倍點(diǎn)的運(yùn)算結(jié)果，使算法只能串行計(jì)算，從而降低算法性能。同時(shí)，點(diǎn)加是否執(zhí)行依賴于當(dāng)前循環(huán)的比特位ni是否為1，因此計(jì)算時(shí)間與具體的n值有關(guān)。但算法3的優(yōu)點(diǎn)是點(diǎn)加倍點(diǎn)共用一個(gè)模塊，可以大大減少硬件資源。

2.5 實(shí)現(xiàn)結(jié)果

選用ALTERA公司的EP2AGX45C6FPGA平臺(tái)對(duì)算法2和算法3進(jìn)行了實(shí)現(xiàn)。表1和表2分別給出了并行和串行兩種實(shí)現(xiàn)方式的性能和資源比較，其中，實(shí)現(xiàn)1對(duì)應(yīng)算法2，實(shí)現(xiàn)2對(duì)應(yīng)算法3。

表1 性能比較

表2 資源消耗比較

3 結(jié) 語(yǔ)

本文將原始的點(diǎn)加公式進(jìn)行了坐標(biāo)轉(zhuǎn)換，將轉(zhuǎn)換后的公式進(jìn)行了分解，給出了適合FPGA并行計(jì)算的點(diǎn)加計(jì)算公式。最后給出了兩個(gè)標(biāo)量乘法計(jì)算公式，分別對(duì)應(yīng)于FPGA的資源優(yōu)先和性能優(yōu)先兩種實(shí)現(xiàn)方式，并對(duì)兩種實(shí)現(xiàn)方式的資源和性能做了比較，有很好的實(shí)用意義。

標(biāo)量乘法中的倍點(diǎn)運(yùn)算是必不可少的，當(dāng)前有關(guān)標(biāo)量乘法的優(yōu)化都是減少點(diǎn)加運(yùn)算的次數(shù)(如非相鄰表示(NAF)法[7],窗口法[8]等)，但由此會(huì)帶來(lái)額外的資源轉(zhuǎn)換開(kāi)銷或者存儲(chǔ)資源開(kāi)銷，對(duì)于資源寶貴的FPGA而言不一定適合。目前，針對(duì)Edwards曲線FPGA實(shí)現(xiàn)的研究較少，如何提高標(biāo)量乘法的性能且又適合FPGA實(shí)現(xiàn)還需更深入的研究。

[1] 金曉剛.素?cái)?shù)域上橢圓曲線密碼體制的軟件實(shí)現(xiàn)[J].通信技術(shù)，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曲線安全快速標(biāo)量乘法運(yùn)算算法—EDSM[J].通信學(xué)報(bào)，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] 蘇賀鵬，張盛兵.基于二進(jìn)制Edwards曲線的橢圓曲線加密多標(biāo)量乘法結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(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的素域模乘快速實(shí)現(xiàn)方法[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)橢圓曲線加密的點(diǎn)乘實(shí)現(xiàn)方案[J].大眾科技，2011(12):4-6. GONG Liang. Implementation of Point Multiplication for ECC over GF(P)[J].Popular Science,2011(12):4-6.

[8] 劉彬彬，聶意新，嚴(yán)燁.橢圓曲線倍點(diǎn)算法的比較研究[J].信息網(wǎng)絡(luò)安全,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

A

1002-0802(2015)10-1179-04

韓煉冰(1984—)，男，學(xué)士,工程師，主要研究方向?yàn)樾畔踩?、通信安全技術(shù);

段俊紅(1984—)，男，工程師，主要研究方向?yàn)榍度胧较到y(tǒng)、通信安全技術(shù);

王 松(1985—),男，學(xué)士,工程師，主要研究方向?yàn)樾畔踩⑼ㄐ虐踩夹g(shù);

房利國(guó)(1977—)，男，碩士，高級(jí)工程師，主要主要研究方向?yàn)樾畔踩?、通信安全技術(shù)、計(jì)算機(jī)應(yīng)用;

劉 蘊(yùn)(1981—)，女，碩士，工程師，主要研究方向?yàn)樾畔踩?/p>