GF(2m)域雙參數(shù)ECDSA算法優(yōu)化設(shè)計(jì)

方應(yīng)李,方玉明

(南京郵電大學(xué) 集成電路科學(xué)與工程學(xué)院,江蘇 南京 210023)

在數(shù)字簽名方法中,文獻(xiàn)[1～2]提出的基于離散對(duì)數(shù)的橢圓曲線密碼體制具有更高的安全性,該密碼體制得到了密碼學(xué)界的重視與推廣。文獻(xiàn)[3]提出了經(jīng)典的橢圓曲線數(shù)字簽名算法(Elliptic Curve Digital Signature Algorithm,ECDSA),用戶A使用私鑰進(jìn)行簽名,用戶B通過用戶A的公鑰對(duì)簽名進(jìn)行驗(yàn)簽。簽名算法中包括兩次模逆、3次點(diǎn)乘以及若干次模乘運(yùn)算。

文獻(xiàn)[4]表明模逆運(yùn)算的時(shí)耗是模乘運(yùn)算的80倍。由于點(diǎn)乘運(yùn)算中至少存在1次模逆運(yùn)算,所以點(diǎn)乘運(yùn)算是影響ECDSA安全性和效率的關(guān)鍵之處,因此業(yè)界學(xué)者集中研究點(diǎn)乘和模逆運(yùn)算。文獻(xiàn)[5]提出了無模逆運(yùn)算的數(shù)字簽名算法,簡化了運(yùn)算的復(fù)雜程度。文獻(xiàn)[6]改進(jìn)了模乘運(yùn)算,提出了一種新的簽名算法。雖然減少模逆運(yùn)算可以提升簽名效率,但也會(huì)引起偽造簽名等安全性問題。因此,業(yè)界學(xué)者在改進(jìn)簽名效率問題的同時(shí)還應(yīng)考慮到算法的安全問題。文獻(xiàn)[7]提出一種高效的串行乘法器。文獻(xiàn)[8]提出在二元愛德華曲線上進(jìn)行標(biāo)量乘。文獻(xiàn)[9]提出了一種新的Itoh-Tsujii算法模逆算法,不僅提高了簽名速度,且能更好地利用現(xiàn)場可編程門陣列硬件資源。

本文針對(duì)算法的時(shí)耗和安全性問題,提出了一種雙參數(shù)ECDSA的改進(jìn)方案,包括3次點(diǎn)乘和0次模逆運(yùn)算,提高了算法的簽名效率和安全性。權(quán)衡資源消耗與運(yùn)算速度之后,本文提出一種基于二進(jìn)制域的ECDSA的高性能實(shí)現(xiàn)方案。充分利用硬件并行優(yōu)勢[10],在模乘、模逆、點(diǎn)乘以及整體系統(tǒng)結(jié)構(gòu)上進(jìn)行了優(yōu)化,取得了良好的效果。

1 雙參數(shù)橢圓數(shù)字簽名方案

1.1 數(shù)字簽名算法描述

雙參數(shù)ECDSA算法流程如圖1所示。用戶A選取隨機(jī)數(shù)k、私鑰d和橢圓上一點(diǎn)G,計(jì)算出消息M的簽名信息(r,s,k1)。簽名加密結(jié)束后,將公鑰Q=dG、消息M以及簽名信息(r,s,k1)一同發(fā)送給用戶B。用戶B進(jìn)行簽名驗(yàn)證后,通過對(duì)比計(jì)算結(jié)果判斷簽名是否成功。簽名成功則說明消息M在傳輸過程未受到篡改;反之,消息M則被第三方攻擊。

圖1 雙參數(shù)數(shù)字簽名算法流程Figure 1. Flow of double parameters signature algorithm

式(1)可證明雙參數(shù)ECDSA算法邏輯的正確性。

(1)

式中,r、s為簽名信息;e為消息的離散值;d、Q為私鑰和公鑰;k、k1、k2均為隨機(jī)數(shù);G為橢圓上一點(diǎn)。

簽名運(yùn)算的耗時(shí)主要集中于模乘、模逆和點(diǎn)乘3種運(yùn)算。由表1可以看出,新簽名方案中沒有模逆運(yùn)算且僅使用了3次點(diǎn)乘運(yùn)算,提高了簽名效率。

表1 簽字方案效率對(duì)比Table 1.Efficiency comparison of signature schemes

1.2 橢圓曲線算法理論基礎(chǔ)

通常在有限域上定義橢圓曲線,常用的有限域包括素?cái)?shù)域GF(p)和二進(jìn)制域GF(2m)。由于GF(2m)域中的運(yùn)算無法進(jìn)位,故更適合硬件實(shí)現(xiàn)。因此,本文選用GF(2m)域?qū)崿F(xiàn)ECDSA算法,GF(2m)域上多項(xiàng)式基表示方法如式(2)所示

(2)

其中,ai∈{0,1}。

橢圓曲線加密體制的運(yùn)算層次如圖2所示。最上層的算法協(xié)議通過調(diào)用群運(yùn)算層中的點(diǎn)乘(Point Multiplication,PM)、點(diǎn)加(Point Addition,PA)和倍點(diǎn)(Double Point,DP)實(shí)現(xiàn)。最底層為4種有限域模運(yùn)算,是實(shí)現(xiàn)群運(yùn)算層的基礎(chǔ)。因此,實(shí)現(xiàn)橢圓曲線加密的高效設(shè)計(jì)需針對(duì)不同運(yùn)算層次進(jìn)行優(yōu)化設(shè)計(jì)。

圖2 橢圓曲線加密體制的運(yùn)算層次Figure 2.Operation level of elliptic curve encryption system

2 運(yùn)算模塊的優(yōu)化設(shè)計(jì)

2.1 域運(yùn)算優(yōu)化設(shè)計(jì)

本文選用233位域?qū)挼腉F(2m),對(duì)應(yīng)的不可約多項(xiàng)式F(x)如式(3)所示。GF(2233)域上的模加運(yùn)算通常使用異或運(yùn)算來完成,對(duì)應(yīng)的硬件電路可以利用233個(gè)異或門進(jìn)行實(shí)現(xiàn)。

F(x)=x233+x74+1

(3)

2.1.1 模乘運(yùn)算設(shè)計(jì)

模乘運(yùn)算是影響點(diǎn)乘運(yùn)算效率的關(guān)鍵之處,包括多項(xiàng)式乘法和模約減運(yùn)算兩個(gè)步驟。本文提出基于移位相加和異或運(yùn)算的串并混合快速模乘運(yùn)算,主要步驟如下所示:

步驟1輸入A(x),B(x),C(x)∈GF(2233);

步驟2模乘值的初始化,C(x)=0;

步驟3將233位寬的數(shù)據(jù)A(x)分段,如

A(x)={a7,a6,a5,a4,a3,a2,a1,a0}

(4)

步驟4進(jìn)行8輪乘法和取模運(yùn)算,具體為

C(x)=aiB(x)+C(x),i∈[0,7]

(5)

如果C232=0,則C(x)保持不變;反之,C232=1時(shí),C(x)執(zhí)行式(6)取模運(yùn)算;

C(x)=C(x)⊕F(x)

(6)

步驟5輸出A(x)和B(x)的模乘值C(x)。

本文提出的串并混合快速模乘運(yùn)算流程如圖3所示。將輸入多項(xiàng)式數(shù)據(jù)A(x)分為8段32位的子數(shù)據(jù),最后一段32位子數(shù)據(jù)通過補(bǔ)零實(shí)現(xiàn)。每個(gè)時(shí)鐘進(jìn)行一次32位的移位相加和取模運(yùn)算?？梢钥闯?需要(232/32)+1個(gè)時(shí)鐘便可完成一次模乘操作。

圖3 串并混合快速模乘運(yùn)算Figure 3. Serial parallel hybrid fast modular multiplication

2.1.2 模平方運(yùn)算設(shè)計(jì)

模平方運(yùn)算是兩個(gè)相同數(shù)的模乘運(yùn)算。由于模乘運(yùn)算耗時(shí)大且硬件電路復(fù)雜,因此本文提出基于GF(2233)域的快速模平方運(yùn)算,從而提高了簽名算法的效率。具體步驟如下所示:

步驟1輸入多項(xiàng)式A(x)∈GF(2233)。

步驟2遍歷i從0到73。若i為偶數(shù),則執(zhí)行式(7);若i為奇數(shù),則執(zhí)行式(8)。

C(i)=A[i/2]⊕A[196+i/2]

(7)

C(i)=A[117+(i-1)/2]

(8)

步驟3遍歷i從74到147。若i為偶數(shù),則執(zhí)行式(9);若i為奇數(shù),則執(zhí)行式(10)。

C(i)=A[i/2]⊕A[196+(i-74)/2]

(9)

C(i)=A[117+(i-1)/2]⊕A[117+(i-75)/2]

(10)

步驟4遍歷i從148到233。若i為偶數(shù),則執(zhí)行式(11);若i為奇數(shù),則執(zhí)行式(12)。

C(i)=A[i/2]

(11)

C(i)=A[117+(i-1)/2]⊕A[117+(i-75)/2]

(12)

步驟5輸出A(x)的模平方值C(x)。

2.1.3 模逆運(yùn)算設(shè)計(jì)

4種有限域模運(yùn)算中最復(fù)雜和最耗時(shí)的是模逆運(yùn)算,常用的模逆運(yùn)算有基于歐幾里德算法和費(fèi)馬小定理兩種[11-12]。如式(13)所示,本文采用費(fèi)馬小定理將模逆運(yùn)算轉(zhuǎn)換為模乘和模平方運(yùn)算,使用Itoh-Tsujii計(jì)算式減少模乘的次數(shù)。模逆運(yùn)算的計(jì)算過程如表2所示。

表2 模逆運(yùn)算過程Table 2. Modular inverse operation process

A(x)-1=A(x)2m-2

(13)

2.2 群運(yùn)算優(yōu)化設(shè)計(jì)

群運(yùn)算是在橢圓曲線上使用兩個(gè)點(diǎn)計(jì)算第3個(gè)點(diǎn)的過程,若兩個(gè)點(diǎn)相同為PD運(yùn)算,反之則為PA運(yùn)算。群運(yùn)算的計(jì)算過程只涉及點(diǎn)的橫坐標(biāo),適合在硬件上實(shí)現(xiàn)。本文選擇如式(14)所示的仿射坐標(biāo)下的橢圓方程,為避免群運(yùn)算中使用模逆運(yùn)算,當(dāng)Z≠0時(shí),令x=X/Z且y=Y/Z,將式(14)轉(zhuǎn)換為Lopez-Dahab(LD)投影坐標(biāo)系下的方程,如式(15)所示[13]。

y2+xy=x3+1

(14)

Y2+XYZ=X3+Z4

(15)

ECDSA采用目前最流行的抗側(cè)通道攻擊的蒙哥馬利點(diǎn)乘運(yùn)算,包括初始化、主循環(huán)和坐標(biāo)轉(zhuǎn)換3部分[14]。主要步驟如下所示:

步驟1輸入多項(xiàng)式k∈GF(2233)及橢圓上一點(diǎn)P(x,y)。

步驟2初始化坐標(biāo),將仿射坐標(biāo)轉(zhuǎn)化為LD投影坐標(biāo)。遍歷i從m-1到0,如果ki=1,則P1=(X1,Z1)=(x,1),P2=(X2,Z2)=(x4,x2)。

步驟3在主循環(huán)過程中一直調(diào)用PA、PD兩個(gè)運(yùn)算模塊。遍歷j從i-1到0,若kj=1,則P1=P1+P2,P2=2P2;反之kj=0,則P1=2P1,P2=P1+P2。

步驟4在坐標(biāo)轉(zhuǎn)換運(yùn)算中存在唯一的模逆運(yùn)算,將LD坐標(biāo)轉(zhuǎn)換仿射坐標(biāo)。

X3=X1/Z1

(16)

(17)

步驟5輸出仿射坐標(biāo)系下的點(diǎn)乘坐標(biāo)(X3,Y3)。

在主循環(huán)過程中,PA與PD之間的運(yùn)算數(shù)值沒有互相依賴。因此,本文采用部分并行PA和PD兩種運(yùn)算來提高PM運(yùn)算的效率。根據(jù)如圖4所示的并行運(yùn)算流程,計(jì)算PA和PD的輸入輸出數(shù)據(jù),如表3所示。

表3 PA、PD并行模型的輸入輸出Table 3.Input and output of PA and PD parallel models

圖4 PA和PD并行運(yùn)算Figure 4. Parallel operation between PA and PD

3 雙參數(shù)ECDSA方案仿真

3.1 加解密模型設(shè)計(jì)

通過上文介紹的雙參數(shù)數(shù)字簽名流程,設(shè)計(jì)有限狀態(tài)機(jī)來調(diào)用群運(yùn)算層和GF(2233)域運(yùn)算層以此實(shí)現(xiàn)數(shù)字簽名驗(yàn)證系統(tǒng)。簽名狀態(tài)轉(zhuǎn)移如圖5(a)所示,具體步驟如下所示:

(a)

(b)圖5 狀態(tài)轉(zhuǎn)移圖(a)簽名加密 (b)簽名驗(yàn)證Figure 5. State transition diagram(a)Signature encryption (b)Signature verification

步驟1S0為初始狀態(tài),用戶A配置簽名參數(shù),包括消息M、橢圓曲線上的一點(diǎn)G,再選擇一個(gè)私鑰d和產(chǎn)生公鑰P=dG發(fā)送給用戶B。

步驟2S1狀態(tài)隨機(jī)選取k,若k∈[1,n-1],則進(jìn)入S2狀態(tài)計(jì)算點(diǎn)乘kG=(x1,y1)。

步驟3S3狀態(tài)將橫坐標(biāo)x1賦值給簽名信息r。若r=0,返回S1狀態(tài),反之進(jìn)入S4狀態(tài)。

步驟4S4狀態(tài)計(jì)算消息M的離散值e。

步驟5S5狀態(tài)中隨機(jī)選取k1、k2。S6狀態(tài)計(jì)算簽名信息s=(k2r-er+d)modn,若s≠0,進(jìn)入S7狀態(tài),將簽名信息(r,s,k1)傳遞給B用戶。

簽名驗(yàn)證狀態(tài)轉(zhuǎn)移如圖5(b)所示。用戶B對(duì)用戶A的簽名信息(r,s,k1)進(jìn)行的具體步驟如下所示:

步驟1在S0狀態(tài)中用戶B收到簽名信息,進(jìn)入S1狀態(tài)驗(yàn)證r,s,k1∈[1,n-1]。若驗(yàn)證失敗,則進(jìn)入S8狀態(tài)拒絕簽名。

步驟2S2狀態(tài)計(jì)算消息M的離散值e;S3狀態(tài)計(jì)算出參數(shù)u=(s+k1m+er)。

步驟3S4狀態(tài)計(jì)算點(diǎn)乘uG,S5狀態(tài)進(jìn)行點(diǎn)加運(yùn)算計(jì)算uG+Q=(x,y)。

步驟4若S5狀態(tài)中x≠0,則S6狀態(tài)將x賦值給參數(shù)v。若r=v,進(jìn)入S7狀態(tài)簽名成功,反之進(jìn)入S8狀態(tài)拒絕簽名。

3.2 仿真波形分析

圖6是通過軟件布局布線后生成的ECDSA加密和解密的頂層模塊。其中端口M_i、s_o、r_o、k1_o、success_o分別為輸入的待處理消息、加密后輸出的3種簽名信息以及簽名驗(yàn)證成功信號(hào)。

(a)

(b)圖6 ECDSA加解密頂層模塊(a)簽名加密 (b)簽名驗(yàn)證Figure 6. ECDSA encryption and decryption top-level module(a)Signature encryption (b)Signature verification

本文通過Vivado軟件利用Verilog語言對(duì)雙參數(shù)ECDSA架構(gòu)進(jìn)行完整的功能仿真,數(shù)字簽名運(yùn)算結(jié)果如圖7所示。待簽名消息M=233’h0f1571c947d9e8590cb7add6af7f6798,私鑰d=233’h15,隨機(jī)數(shù)k=233’h6a,輸出簽名消息k1=233’h129、r=233’h0e15ae1d3e035c8d4653ce24cb569e01a62c9cda208cc698c4eb3f3c87a、s=233’h12506c8a4f9be86b284c118269d774e926d19d03ee49250e1f1da7df3db。

圖7 數(shù)字簽名運(yùn)算的仿真結(jié)果Figure 7. Simulation results of digital signature operation

用戶A完成數(shù)字簽名后,將簽名信息(r,s,k1)、消息M與公鑰Q發(fā)送給用戶B進(jìn)行驗(yàn)證簽名。簽名驗(yàn)證仿真結(jié)果如圖8所示。輸出結(jié)果X_x為233’h0e15ae1d3e035c8d4653ce24cb569e01a62c9cda208cc698c4eb3f3c87a。從結(jié)果可以看出X_x=r,此時(shí)success_o信號(hào)出現(xiàn)高電平,表示數(shù)字簽名方案成功,消息M未受到第三方篡改。

圖8 簽名驗(yàn)證的仿真結(jié)果Figure 8. Simulation results of signature verification

3.3 改進(jìn)簽名算法分析

在本文提出的雙參數(shù)ECDSA算法中,非法用戶竊取到私鑰d或者公鑰Q其中一個(gè),無法通過Q=dG來求解另一個(gè),此方案具有前向安全性。非法用戶將簽名消息(r,s,k1)替換為(r′,s,k′1),接收方不能通過簽名驗(yàn)證,此方案可以抵御簽名消息偽造攻擊。無論是偽造私鑰d或者偽造消息M來進(jìn)行數(shù)字簽名時(shí),得到的都是偽簽名信息,簽名驗(yàn)證過程無法得到有效的輸出,此方案可以保證消息和私鑰的完整性和真實(shí)性,可以防止數(shù)據(jù)篡改。非法用戶偽造隨機(jī)數(shù)k'發(fā)起偽造攻擊,進(jìn)而得到偽造的簽名信息,此方案可以抵御替換隨機(jī)數(shù)的偽造攻擊。

該方案通過數(shù)字簽名技術(shù)實(shí)現(xiàn)了雙向認(rèn)證,非法用戶不能冒充任何一方,有效地防止了中間人攻擊[15]。接收方基于發(fā)送方發(fā)送的(r,s,k1)進(jìn)行驗(yàn)證工作,以保證發(fā)送方事后不可抵賴。將改進(jìn)后的方案與現(xiàn)有的方案進(jìn)行了安全性對(duì)比,3種方案的性能差距如表4所示。

表4 簽字方案安全性對(duì)比Table 4.Security comparison of signature scheme

本文對(duì)基于并行PA和PD運(yùn)算模塊的蒙哥馬利點(diǎn)乘法進(jìn)行仿真實(shí)驗(yàn),表5中列出本文與其他文獻(xiàn)方案之間的比較。本文的點(diǎn)乘算法運(yùn)算過程占用了23 087個(gè)邏輯單元,在時(shí)鐘頻率100 MHz下運(yùn)行4.77 μs完成一次點(diǎn)乘運(yùn)算。在本文與文獻(xiàn)[18]的邏輯單元基本相同的情況下,完成一次點(diǎn)乘運(yùn)算需要的時(shí)鐘數(shù)減少75%。本文的邏輯單元數(shù)略高于文獻(xiàn)[17],但完成一次點(diǎn)乘運(yùn)算時(shí)的鐘數(shù)減少90%。綜上,本文提出的點(diǎn)乘運(yùn)算在面積和速度上均取得較好的折中效果。

表5 二進(jìn)制域上PM性能比較Table 5.Performance comparison of PM on binary field

4 結(jié)束語

本文針對(duì)數(shù)字簽名的安全性低和運(yùn)算效率低等問題提出了可證明安全性的雙參數(shù)ECDSA,并通過GF(2m)上的模運(yùn)算來實(shí)現(xiàn)。本文優(yōu)化設(shè)計(jì)串并混合快速模乘運(yùn)算和Itoh-Tsujii模逆運(yùn)算,使用并行PA和PD運(yùn)算提高點(diǎn)乘的運(yùn)算效率。此外,本文使用LD射影坐標(biāo)系減少曲線運(yùn)算中的模逆運(yùn)算次數(shù)。安全性分析結(jié)果表明,改進(jìn)后的簽名算法不僅能抵抗偽造攻擊,還能有效地抵抗隨機(jī)數(shù)替換。簽名算法在Vivado軟件上仿真測試結(jié)果表明,該算法有效地實(shí)現(xiàn)了數(shù)字簽名驗(yàn)證,確保消息傳遞過程中的安全性。點(diǎn)乘運(yùn)算過程占用23 087個(gè)邏輯單元,在時(shí)鐘頻率100 MHz下僅需要4.77 μs便完成一次點(diǎn)乘運(yùn)算。點(diǎn)乘性能對(duì)比分析結(jié)果表明,利用優(yōu)化后的模乘、模逆運(yùn)算和并行運(yùn)算的思想能提高點(diǎn)乘運(yùn)算的效率。接下來的研究工作是將ECDSA算法與其他對(duì)稱加密算法混合使用,實(shí)現(xiàn)更加安全有效的密碼系統(tǒng)設(shè)計(jì)。