ECDSA協(xié)同簽名方案設(shè)計(jì)與實(shí)現(xiàn)

彭金輝 雷宗華 張志鴻

1(鄭州信大捷安移動(dòng)信息安全關(guān)鍵技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室 鄭州 450004)

2(鄭州大學(xué)計(jì)算機(jī)與人工智能學(xué)院 鄭州 450001)

(pjh@xdja.com)

橢圓曲線數(shù)字簽名算法(elliptic curve digital signature algorithm,ECDSA)[1]和RSA/DSA相比,具有處理速度快、帶寬和存儲(chǔ)占用小的特點(diǎn)[2],廣泛應(yīng)用于電子商務(wù)、移動(dòng)安全接入等領(lǐng)域,可提供身份認(rèn)證、密鑰協(xié)商、簽名驗(yàn)證等服務(wù).在密碼應(yīng)用安全技術(shù)體系[3]中,簽名方案的安全性依賴于私鑰存儲(chǔ)環(huán)境和運(yùn)算環(huán)境的安全[4],私鑰安全通常由安全芯片、智能密碼鑰匙、PCI-E密碼卡、服務(wù)器密碼機(jī)等硬件密碼模塊提供保障.隨著公鑰密碼算法的普及,特別是在工業(yè)互聯(lián)網(wǎng)[5]、物聯(lián)網(wǎng)[6]、車(chē)聯(lián)網(wǎng)[7]、加密貨幣[8]、區(qū)塊鏈[9]等領(lǐng)域的廣泛應(yīng)用,智能終端設(shè)備可通過(guò)安裝加密TF卡、加密NM卡和加密SIM卡等外設(shè),或者通過(guò)在主板硬貼片TPM/TCM/TPCM等模塊,實(shí)現(xiàn)配置硬件密碼模塊,但更多的智能終端設(shè)備不具備上述條件.針對(duì)這種場(chǎng)景的軟件密碼模塊應(yīng)運(yùn)而生,并得到快速發(fā)展.對(duì)于軟件密碼模塊,其私鑰需要在終端設(shè)備上存儲(chǔ)和運(yùn)行,可采用口令派生密鑰、本地多份存儲(chǔ)或者其他方式加密保護(hù),但由于互聯(lián)網(wǎng)中這些智能終端設(shè)備大多屬于個(gè)人用戶,缺乏有效的私鑰保護(hù)環(huán)境,敏感信息非常容易被敵手攻擊甚至竊取,造成經(jīng)濟(jì)損失.基于安全多方計(jì)算[10]和門(mén)限簽名[11]的思想,一個(gè)可行的方案是將私鑰分拆成2個(gè)或多個(gè)分量,各分量獨(dú)立產(chǎn)生、存儲(chǔ)和運(yùn)算,私鑰簽名操作通過(guò)多方協(xié)同運(yùn)算完成,不重構(gòu)完整私鑰也可得到合法的簽名結(jié)果.

針對(duì)ECDSA雙方協(xié)同運(yùn)算,一些方案被提出：Lindell等人[12-13]提出了基于Paillier同態(tài)加密算法的兩方協(xié)同ECDSA簽名方案,但是計(jì)算開(kāi)銷(xiāo)和存儲(chǔ)開(kāi)銷(xiāo)比較大,簽名運(yùn)算效率受限;Doerner等人[14-15]提出了基于秘密共享和不經(jīng)意傳輸技術(shù)的(2,n)門(mén)限簽名方案,無(wú)需引入計(jì)算開(kāi)銷(xiāo)較高的同態(tài)加密及相關(guān)零知識(shí)證明,提高了協(xié)同簽名的計(jì)算性能,但不經(jīng)意傳輸協(xié)議增加了大量的通信帶寬開(kāi)銷(xiāo);王婧等人[16]通過(guò)預(yù)計(jì)算一次一密的Beaver三元組,利用其安全兩方乘法技術(shù),避免計(jì)算量大的同態(tài)運(yùn)算和通信開(kāi)銷(xiāo)大的不經(jīng)意傳輸?shù)炔僮?實(shí)現(xiàn)相對(duì)高效的兩方協(xié)同簽名,但該方案需要大量的預(yù)計(jì)算;嚴(yán)瑩子[17]提出了基于多方(t,n)門(mén)限的拆分方案,但該方案使用了加法同態(tài)加密、不經(jīng)意傳輸、承諾機(jī)制、零知識(shí)證明、秘密共享等,運(yùn)算量和傳輸量均較大.

除ECDSA之外,針對(duì)商用密碼算法：龍毅宏[18]和馮琦等人[19]通過(guò)數(shù)學(xué)公式巧妙構(gòu)造安全高效的SM2雙方協(xié)同簽名的方案;尚銘等人[20]基于秘密乘積的分享、秘密逆的分享、點(diǎn)乘的分享等設(shè)計(jì)了SM2門(mén)限簽名方案;Mu等人[21]設(shè)計(jì)了基于Paillier的兩方協(xié)同SM9算法簽名方案.

針對(duì)現(xiàn)有ECDSA雙方協(xié)同簽名方案的不足,本文設(shè)計(jì)了一個(gè)協(xié)同簽名方案C-ECDSA(collaborative ECDSA),通過(guò)數(shù)學(xué)公式構(gòu)造了雙方協(xié)同產(chǎn)生密鑰對(duì)、協(xié)同簽名的過(guò)程,在惡意模型下增加零知識(shí)證明.避免了使用計(jì)算開(kāi)銷(xiāo)大的同態(tài)運(yùn)算和通信量開(kāi)銷(xiāo)大的不經(jīng)意傳輸;避免了使用一次一密的各種預(yù)計(jì)算、預(yù)存儲(chǔ);避免了秘密的分享;在通信雙方其中一方可能被攻擊腐化的情況下,能夠有效保護(hù)簽名私鑰安全.

本文首先介紹標(biāo)準(zhǔn)ECDSA簽名算法,然后給出C-ECDSA方案設(shè)計(jì),包括協(xié)同產(chǎn)生密鑰對(duì)運(yùn)算過(guò)程、協(xié)同簽名運(yùn)算過(guò)程,并給出簽名結(jié)果的正確性證明.通過(guò)零知識(shí)證明和模擬協(xié)議給出了方案的安全性分析,最后給出了在智能終端上的驗(yàn)證以及性能分析.

1 ECDSA簽名算法

本節(jié)概要介紹ECDSA算法產(chǎn)生密鑰對(duì)和私鑰簽名算法的標(biāo)準(zhǔn)流程[22].

1.1 符號(hào)定義

定義橢圓曲線E的參數(shù)為params=(p,a,b,G,n),其中a,b為橢圓曲線方程的參數(shù),p為大素?cái)?shù),橢圓曲線上坐標(biāo)x,y的運(yùn)算均模p,G為橢圓曲線基點(diǎn)(Gx,Gy),n為橢圓曲線上G的階,[k]P表示橢圓曲線上P的k倍點(diǎn).

1.2 產(chǎn)生密鑰對(duì)

1) 使用隨機(jī)數(shù)發(fā)生器產(chǎn)生整數(shù)d∈[1,n-2];

2) 計(jì)算橢圓曲線點(diǎn)P=(x,y)=[d]G;

3) 輸出密鑰對(duì)(d,P),其中d為私鑰,P為公鑰.

1.3 簽名算法

1) 對(duì)待簽名消息M使用預(yù)定的雜湊算法(如SHA256),得到消息摘要e;

2) 產(chǎn)生隨機(jī)數(shù)k∈[1,n-1],根據(jù)k生成橢圓曲線點(diǎn)(x1,y1)=[k]G;

3) 計(jì)算簽名結(jié)果第1部分r=x1modn,如果r=0,返回步驟2);

4) 計(jì)算簽名結(jié)果第2部分s=k-1(e+rd) modn,如果s=0,返回步驟2);

5) (r,s)為最終簽名結(jié)果.

2 安全模型

2.1 安全模型和設(shè)計(jì)目標(biāo)

本節(jié)描述安全性證明所依賴的安全模型,通過(guò)構(gòu)造模擬協(xié)議,利用和被攻擊方的交互,將安全性規(guī)約到ECDSA原始簽名方案的安全假設(shè).

安全模型參照了文獻(xiàn)[19]的方法：

首先是通信模型,假設(shè)2個(gè)通信方共享ECDSA系統(tǒng)參數(shù)和曲線參數(shù),且存在一個(gè)點(diǎn)對(duì)點(diǎn)通道用于雙方協(xié)議通信.

其次是敵手能力,假設(shè)概率多項(xiàng)式時(shí)間(P.P.T)敵手E是惡意的,它可以在協(xié)議執(zhí)行過(guò)程中任意地偏離協(xié)議過(guò)程.如果通信雙方都被E控制,分析沒(méi)有意義.有以下4條假設(shè)：假設(shè)E可以控制其中一方,且知道被控制方的所有秘密值;假設(shè)在協(xié)議執(zhí)行之前就確定E攻擊哪一方,在協(xié)議執(zhí)行過(guò)程中不發(fā)生角色改變;在安全證明過(guò)程中,假設(shè)通信的每一輪都由誠(chéng)實(shí)方首先發(fā)給被控制方;假設(shè)E的視圖包括被攻擊方所有的輸入、隨機(jī)數(shù)和協(xié)議需要傳輸?shù)乃袛?shù)據(jù).

第三是安全目標(biāo),傳統(tǒng)的私鑰簽名方案安全性證明模型是選擇明文攻擊下的存在性不可偽造的安全模型EU-CMA(existential unforgeability against chosen-message attack).該模型假定敵手E已知公鑰且可以選擇任何消息進(jìn)行簽名驗(yàn)證.

在EU-CMA模型中,假定簽名方案為π,如果敵手E在多項(xiàng)式次簽名驗(yàn)證后,仍無(wú)法以一個(gè)不可忽略的概率偽造一個(gè)新消息的簽名,那么簽名方案π是可證明安全的,即

Pr[Expπ,E(1λ)=1]≤ε,

(1)

其中Expπ,E(1λ)是對(duì)ECDSA原始簽名方案的偽造,ε為一個(gè)可忽略概率閾值,λ是安全參數(shù).

協(xié)同簽名方案本質(zhì)是一種分布式簽名生成方案,簽名值在傳統(tǒng)驗(yàn)證算法下是有效的,本文把協(xié)同簽名方案的存在性不可偽造稱為C-EU-CMA(collaborative EU-CMA).

在C-EU-CMA模型中,假定簽名方案為Π,如果P.P.T敵手E控制了2個(gè)通信方的其中一方μ(μ取值為通信方A或者通信方B),同時(shí)允許E取得協(xié)同簽名的協(xié)議實(shí)例,E仍然無(wú)法以一個(gè)不可忽略的概率偽造出一個(gè)新消息的簽名,那么該協(xié)同簽名協(xié)議滿足存在性不可偽造的安全性,即

(2)

2.2 安全兩方計(jì)算

安全兩方計(jì)算最早由姚期智提出,要求通信雙方不泄露各自敏感數(shù)據(jù)的情況下,執(zhí)行各自計(jì)算邏輯并最終獲得計(jì)算結(jié)果,雙方除了各自輸入數(shù)據(jù)、有關(guān)中間計(jì)算數(shù)據(jù)以外無(wú)法獲得任何額外有效信息[10].針對(duì)ECDSA雙方協(xié)同產(chǎn)生密鑰對(duì)和協(xié)同簽名運(yùn)算,可描述為：通信雙方分別產(chǎn)生各自子私鑰d1和d2,協(xié)同產(chǎn)生公鑰P,根據(jù)待簽名消息摘要e和隨機(jī)數(shù)R(包括各自隨機(jī)數(shù)R1,R2),執(zhí)行簽名運(yùn)算過(guò)程S(R,e,d1,d2)得到可被公鑰P驗(yàn)證通過(guò)的簽名值(r,s).

要求協(xié)同簽名滿足以下條件：1)私密性,協(xié)同運(yùn)算執(zhí)行過(guò)程中雙方傳遞的數(shù)據(jù)不會(huì)泄露各自子私鑰的相關(guān)信息;2)正確性,簽名結(jié)果使用對(duì)應(yīng)公鑰能夠驗(yàn)證;3)安全性,和原始簽名算法具有相同的安全性.

安全多方計(jì)算根據(jù)參與方誠(chéng)實(shí)度分為半誠(chéng)實(shí)模型和惡意模型.半誠(chéng)實(shí)模型能夠正確地遵循協(xié)議的指令,但會(huì)記錄執(zhí)行期間的中間數(shù)據(jù),并企圖得到額外信息,只要通信雙方不泄露自己的輸入,該模型就是安全的;惡意模型指敵手可能任意違背協(xié)議的指令,一般包括誠(chéng)實(shí)方、惡意方和可信方.

2.3 零知識(shí)證明理想函數(shù)

在通用可組合安全框架下,理想函數(shù)是重要的組成部分,代表一個(gè)不可被攻擊的可信方,用來(lái)完成協(xié)議所需的理想功能與執(zhí)行過(guò)程.敵手E與任一通信方的交互用于模擬協(xié)議的現(xiàn)實(shí)執(zhí)行過(guò)程.任一通信方(包括可視為理想敵手的模擬器)與理想函數(shù)的交互用于模擬協(xié)議的理想執(zhí)行過(guò)程[16].

根據(jù)Lindell等人[13]的定義,標(biāo)準(zhǔn)零知識(shí)證明理想函數(shù)可以形式化表示為

Fzk：((x,w),λ)→(λ,(x,R(x,w))),

其中λ為公共參數(shù),R定義了聲明x和證據(jù)w的關(guān)系.在本文方案中,R特指關(guān)于循環(huán)群上橢圓曲線離散對(duì)數(shù)關(guān)系的零知識(shí)證明：Q=[k]P,即點(diǎn)Q關(guān)于點(diǎn)P的離散對(duì)數(shù)為k.Fzk函數(shù)收到通信方A的消息,且R驗(yàn)證有效,向通信方B發(fā)送證明;收到通信方B的消息,且R驗(yàn)證有效,向通信方A發(fā)送證明.

3 方案設(shè)計(jì)

本文方案中涉及2個(gè)參與方：通信方A和通信方B,方案內(nèi)容包括協(xié)同產(chǎn)生密鑰對(duì)和協(xié)同簽名2部分.

3.1 協(xié)同產(chǎn)生密鑰對(duì)設(shè)計(jì)

C-ECDSA方案協(xié)同產(chǎn)生密鑰對(duì)設(shè)計(jì)流程共包含8步,具體如下：

1) 通信方A執(zhí)行以下3步.

A1.通過(guò)隨機(jī)數(shù)模塊產(chǎn)生隨機(jī)數(shù)d1∈[1,n-1],作為A的子私鑰持久存儲(chǔ);

A2.根據(jù)d1和G計(jì)算得到橢圓曲線點(diǎn)P1=[d1]G;

A3.向理想函數(shù)Fzk發(fā)送P1關(guān)于G的離散對(duì)數(shù)是d1的零知識(shí)證明,并將客戶端身份標(biāo)識(shí)IDA和P1通過(guò)網(wǎng)絡(luò)模塊發(fā)送給B(如果通信異?；蛘邤?shù)據(jù)丟失,重新從A1開(kāi)始執(zhí)行).

2) 通信方B在收到P1后,執(zhí)行以下4步.

B1.判斷理想函數(shù)Fzk返回的零知識(shí)證明有效性,若無(wú)效則終止協(xié)議;否則通過(guò)隨機(jī)數(shù)模塊產(chǎn)生隨機(jī)數(shù)d2,d3∈[1,n-1],作為B端IDA對(duì)應(yīng)的子私鑰持久存儲(chǔ);

B3.計(jì)算P=P2-P3,P作為公鑰持久存儲(chǔ);

3) 通信方A在收到P2和P3后,執(zhí)行以下步驟：

A4.判斷理想函數(shù)Fzk返回的P2零知識(shí)證明有效性,若無(wú)效則終止協(xié)議;否則計(jì)算P=P2-P3,P作為公鑰持久存儲(chǔ).

至此,協(xié)同產(chǎn)生密鑰對(duì)完成,雙方擁有了各自的子私鑰和公鑰.

上述完整步驟流程如圖1所示：

圖1 C-ECDSA方案協(xié)同產(chǎn)生密鑰對(duì)流程

公鑰P的計(jì)算公式在數(shù)學(xué)上展開(kāi)：

令

(3)

則P=[d]G,此時(shí)d相當(dāng)于完整私鑰.

3.2 協(xié)同簽名設(shè)計(jì)

C-ECDSA方案協(xié)同簽名設(shè)計(jì)流程共包含11步,具體實(shí)現(xiàn)如下：

1) 通信方A執(zhí)行以下3步.

A1.對(duì)待簽名消息M使用預(yù)定的雜湊函數(shù),得到消息摘要e;

A2.通過(guò)隨機(jī)數(shù)模塊產(chǎn)生隨機(jī)數(shù)k1∈[1,n-1],根據(jù)k1和G生成第1部分簽名Q=[k1]G;

A3.向理想函數(shù)Fzk發(fā)送Q關(guān)于G的離散對(duì)數(shù)是k1的零知識(shí)證明,并將客戶端身份標(biāo)識(shí)IDA和e,Q通過(guò)網(wǎng)絡(luò)模塊發(fā)送給B(如果通信異常或者數(shù)據(jù)丟失,將重新從A1開(kāi)始執(zhí)行).

2) 通信方B在收到IDA,e,Q后,通過(guò)IDA查找該客戶端對(duì)應(yīng)私鑰d2和d3,并執(zhí)行以下6步.

B1.判斷理想函數(shù)Fzk返回的Q零知識(shí)證明有效性,若無(wú)效則終止協(xié)議;否則通過(guò)隨機(jī)數(shù)模塊產(chǎn)生隨機(jī)數(shù)k2,k3∈[1,n-1];

B3.根據(jù)x1和e計(jì)算得到第2部分簽名r=x1modn,若r=0,返回步驟B1;

B4.根據(jù)k2,k3,d2,e,r計(jì)算得到第3部分簽名s1=k3(k2+d3) (e+rd2) modn;

B6.將第2,3,4部分簽名r,s1,s2通過(guò)網(wǎng)絡(luò)模塊發(fā)送給A,如果通信異?；蛘邤?shù)據(jù)丟失,將重新從A1開(kāi)始執(zhí)行.

3) 通信方A在收到r,s1,s2后,執(zhí)行以下2步.

A5.將(r,s)作為最終簽名結(jié)果.

上述完整步驟流程如圖2所示：

圖2 C-ECDSA方案協(xié)同簽名流程

把通信方B第2步計(jì)算的橢圓曲線點(diǎn)的公式在數(shù)學(xué)上展開(kāi)：

令

(4)

則(x1,y1)=[k]G.

式(4)中k相當(dāng)于基于完整私鑰d作ECDSA原始簽名運(yùn)算步驟2)的隨機(jī)數(shù).

此外,當(dāng)實(shí)際場(chǎng)景安全要求較低時(shí),方案可刪除基于理想函數(shù)的零知識(shí)證明相關(guān)協(xié)議,構(gòu)成半誠(chéng)實(shí)模型下的協(xié)同簽名方案,提高運(yùn)算效率.

3.3 協(xié)同簽名正確性證明

要利用C-ECDSA方案進(jìn)行簽名,必須要證明其協(xié)同簽名與標(biāo)準(zhǔn)ECDSA簽名算法是等價(jià)的.

定理1.C-ECDSA方案協(xié)同簽名結(jié)果和ECDSA原始簽名結(jié)果等價(jià).

證明.根據(jù)ECDSA簽名算法可知,要證明C-ECDSA方案協(xié)同簽名結(jié)果和完整私鑰簽名結(jié)果是等價(jià)的,只需要證明s=k-1(e+rd).

根據(jù)式(4),令

根據(jù)式(3),有

證畢.

4 安全性分析

C-ECDSA方案協(xié)同產(chǎn)生密鑰對(duì)和協(xié)同簽名算法的安全性基于原始ECDSA產(chǎn)生密鑰對(duì)和簽名算法安全性.

定理2.C-ECDSA協(xié)同運(yùn)算過(guò)程中雙方傳遞的通信數(shù)據(jù)不泄露雙方私有敏感數(shù)據(jù).

在密鑰對(duì)產(chǎn)生過(guò)程中,公開(kāi)數(shù)據(jù)P1,P2,P3是安全的,基于橢圓曲線離散對(duì)數(shù)難題,無(wú)法通過(guò)P1,P2,P3推算出任何和私鑰d及其分量d1,d2,d3的有關(guān)數(shù)據(jù).

簽名過(guò)程中,客戶端計(jì)算Q,服務(wù)端計(jì)算r,s1,s2,從Q,r,s1,s2無(wú)法得到任何與私鑰d及其分量d1,d2,d3以及隨機(jī)數(shù)k的有關(guān)信息.

綜上,協(xié)同運(yùn)算過(guò)程雙方傳遞通信的數(shù)據(jù)不會(huì)泄露雙方任何私有敏感數(shù)據(jù).

定理3.假設(shè)原始ECDSA簽名方案是不可偽造的,在隨機(jī)諭示器和零知識(shí)證明模型下,本文提出的兩方ECDSA協(xié)同簽名協(xié)議滿足存在性不可偽造.

證明.本文方案的安全性證明遵從模擬規(guī)約的證明方法,假設(shè)概率多項(xiàng)式時(shí)間敵手E以不可忽略的概率ε在C-ECDSA協(xié)同簽名方案中偽造成功,那么將構(gòu)造一個(gè)模擬器在原始ECDSA簽名方案中充當(dāng)偽造者,且偽造成功的概率也是不可忽略的.由于本文方案包括通信方A和通信方B這2個(gè)角色,下面分別考慮A和B被攻擊2種情況,并分別說(shuō)明模擬密鑰生成和模擬協(xié)同簽名協(xié)議.

4.1 通信方A被攻擊

假設(shè)通信方A被敵手E攻擊(腐化),下面構(gòu)造一個(gè)模擬協(xié)議,其中S是模擬器,其任務(wù)是提取被腐化的通信方A的輸入,生成一個(gè)敵手不可區(qū)分的執(zhí)行視圖,并利用敵手構(gòu)造的偽造簽名攻擊原始ECDSA簽名方案.

1) 模擬生成密鑰對(duì).

A1.模擬器S詢問(wèn)ECDSA密鑰生成諭示器FECDSA,得到一個(gè)公鑰P;

A2.模擬器S向通信方A(即敵手E)發(fā)起協(xié)同產(chǎn)生密鑰對(duì)指示;

A3.當(dāng)接收到敵手E發(fā)來(lái)的P1,以及發(fā)給理想函數(shù)Fzk的P1關(guān)于G的離散對(duì)數(shù)為d1的證明,模擬器S驗(yàn)證P1=[d1]G是否成立,若不成立則終止協(xié)議;否則執(zhí)行下一步;

A4.模擬器S產(chǎn)生隨機(jī)點(diǎn)P2,并計(jì)算P3=P2-P,把P2和P3發(fā)給敵手E;

A5.模擬器S模擬Fzk向敵手E發(fā)送關(guān)于P2和P3的零知識(shí)證明有效;

A6.模擬器S存儲(chǔ)P,P2,P3,d1,若敵手E誠(chéng)實(shí)計(jì)算,必定會(huì)通過(guò)計(jì)算P2-P3得到正確的P.

2) 模擬協(xié)同簽名.

A1.模擬器S執(zhí)行簽名諭示器FECDSA,得到一個(gè)關(guān)于消息摘要e的簽名結(jié)果(r,s);

A2.模擬器S向敵手E發(fā)起協(xié)同簽名請(qǐng)求;

A3.模擬器S接收到敵手E發(fā)來(lái)的Q,以及發(fā)給Fzk的Q關(guān)于G的離散對(duì)數(shù)為k1的證明;

A4.模擬器S驗(yàn)證Q=[k1]G是否成立,若不成立則終止協(xié)議,否則繼續(xù);

A5.模擬器S從簽名中恢復(fù)出R=(x1,y1)=[s-1]([e]G+[r]P),從而得到r=x1modn;

A6.模擬器S隨機(jī)選擇k3和k2并計(jì)算s2=k3k2r+k3r,s1=k1s+d1s2,將r,s1,s2發(fā)送給敵手E;

A7.模擬器S模擬Fzk向敵手E發(fā)送關(guān)于R的零知識(shí)證明有效;

A8.若敵手E誠(chéng)實(shí)計(jì)算,必定會(huì)輸出正確的ECDSA簽名(r,s).

3) 不可區(qū)分性分析.

類(lèi)似地,協(xié)同簽名的現(xiàn)實(shí)執(zhí)行環(huán)境和模擬執(zhí)行環(huán)境的區(qū)別是R的計(jì)算方法和s1,s2的計(jì)算方法.協(xié)議現(xiàn)實(shí)執(zhí)行環(huán)境R由隨機(jī)數(shù)k2,k3和點(diǎn)Q計(jì)算得到,模擬執(zhí)行環(huán)境中R由簽名信息r,s和公鑰P中恢復(fù)出R=[s-1]([e]G+[r]P),由于r,s和公鑰P是FECDSA隨機(jī)選取的,所以2個(gè)R分布相同,均滿足均勻隨機(jī)分布.現(xiàn)實(shí)執(zhí)行環(huán)境中,s1,s2根據(jù)k2,k3,d2,e,r計(jì)算得到,分布是隨機(jī)的;模擬執(zhí)行環(huán)境中,s1,s2根據(jù)k1,k2,k3,d1,s,r計(jì)算得到,分布也是隨機(jī)的,二者均滿足隨機(jī)分布,敵手視角不可區(qū)分.此外,如果敵手E偏離協(xié)議,模擬器可以通過(guò)驗(yàn)證Q和s來(lái)判斷,如果驗(yàn)證失敗則終止協(xié)議,這與現(xiàn)實(shí)執(zhí)行環(huán)境一致.最后模擬器輸出有效簽名(r,s),即從FECDSA得到的簽名.綜上所述,對(duì)于敵手E來(lái)說(shuō),模擬執(zhí)行環(huán)境和現(xiàn)實(shí)執(zhí)行環(huán)境是不可區(qū)分的.

4) 簽名偽造.

由于敵手E攻擊通信方A后,無(wú)法區(qū)分模擬執(zhí)行環(huán)境和現(xiàn)實(shí)執(zhí)行環(huán)境,故模擬器可以調(diào)用敵手E的偽造簽名攻擊原始ECDSA簽名方案.

4.2 通信方B被攻擊

假設(shè)通信方B被敵手E攻擊(被腐化),下面是構(gòu)造一個(gè)模擬協(xié)議：

1) 模擬生成密鑰對(duì).

A1.模擬器S詢問(wèn)ECDSA密鑰生成諭示器FECDSA,得到一個(gè)公鑰P;

A2.模擬器S產(chǎn)生一個(gè)隨機(jī)點(diǎn)P1發(fā)送給敵手E;

A3.模擬器S模擬Fzk向敵手E發(fā)送關(guān)于P1的零知識(shí)證明有效;

2) 模擬協(xié)同簽名.

A1.模擬器S詢問(wèn)簽名諭示器FECDSA,得到一個(gè)關(guān)于消息摘要e的簽名結(jié)果(r,s);

A2.模擬器S從簽名中恢復(fù)R=[s-1]([e]G+[r]P),模擬器S通過(guò)獲取敵手E的隨機(jī)數(shù)k2,k3和私鑰分量d3計(jì)算Q=[k3(k2+d3)]R,并將Q發(fā)送給敵手E;

A3.模擬器S模擬Fzk向敵手E發(fā)送關(guān)于Q的零知識(shí)證明有效;

3) 不可區(qū)分性分析.

類(lèi)似通信方A被攻擊的情況,本文簡(jiǎn)要分析通信方B被攻擊時(shí)敵手視圖不可區(qū)分.

4) 簽名偽造.

由于敵手E攻擊通信方B后,無(wú)法區(qū)分模擬執(zhí)行環(huán)境和現(xiàn)實(shí)執(zhí)行環(huán)境,故模擬器S可以調(diào)用敵手E的偽造簽名攻擊原始ECDSA簽名方案.

在模擬協(xié)議執(zhí)行過(guò)程中,敵手E生成的簽名驗(yàn)證公鑰P通過(guò)諭示器FECDSA獲得,故E在模擬協(xié)議中對(duì)協(xié)同簽名的偽造也可以作為對(duì)標(biāo)準(zhǔn)ECDSA的偽造.可見(jiàn),若敵手E以不可忽略的概率ε贏得協(xié)同簽名方案,那么模擬器S可以同樣的概率ε贏得原始簽名方案.由于原始ECDSA是可證明安全的,即模擬器S偽造簽名成功的概率是可忽略的,敵手E偽造成功的概率也是可忽略的,因此假設(shè)ε不可忽略是不成立的,說(shuō)明本文方案在通信方B被攻擊時(shí)是安全的.

證畢.

5 方案實(shí)現(xiàn)和性能評(píng)估

5.1 軟件架構(gòu)設(shè)計(jì)

下面給出本文方案的一個(gè)具體實(shí)現(xiàn)場(chǎng)景的軟件設(shè)計(jì).通信方A是智能終端上運(yùn)行的軟件密碼模塊,軟件形態(tài)為運(yùn)行在嵌入式Linux,Android系統(tǒng)上的客戶端APP;通信方B是協(xié)同簽名服務(wù)器,帶有PCI-E密碼卡,軟件形態(tài)是運(yùn)行在Linux操作系統(tǒng)上的服務(wù)端Server.

協(xié)同簽名算法通過(guò)C語(yǔ)言實(shí)現(xiàn).軟件架構(gòu)主要包括密碼服務(wù)接口模塊、大整數(shù)運(yùn)算模塊、橢圓曲線運(yùn)算模塊、ECDSA協(xié)同運(yùn)算模塊、隨機(jī)數(shù)模塊、網(wǎng)絡(luò)通信模塊等,如圖3所示：

圖3 軟件模塊結(jié)構(gòu)

最頂層是密碼服務(wù)接口模塊,向APP提供協(xié)同產(chǎn)生密鑰對(duì)、協(xié)同簽名接口.該模塊依賴ECDSA協(xié)同簽名模塊、數(shù)據(jù)存儲(chǔ)模塊和網(wǎng)絡(luò)通信模塊.服務(wù)端Server不單獨(dú)提供密碼服務(wù),作為軟件密碼模塊的配套使用.

ECDSA協(xié)同運(yùn)算模塊基于橢圓曲線運(yùn)算模塊和隨機(jī)數(shù)模塊封裝了協(xié)同產(chǎn)生密鑰對(duì)接口和協(xié)同簽名運(yùn)算接口.

隨機(jī)數(shù)模塊可產(chǎn)生指定比特長(zhǎng)度的隨機(jī)數(shù).

橢圓曲線運(yùn)算模塊基于大整數(shù)運(yùn)算模塊封裝了點(diǎn)加、倍點(diǎn)、點(diǎn)乘等運(yùn)算.

大整數(shù)運(yùn)算模塊提供大數(shù)的模加(c=(a+b) modn)、模減(c=(a-b) modn)、模乘(c=(a×b) modn)、模逆(c=a-1modn)等運(yùn)算.

網(wǎng)絡(luò)通信模塊用于建立客戶端和服務(wù)端之間的連接.

客戶端存儲(chǔ)模塊用于存儲(chǔ)自身的子私鑰等敏感數(shù)據(jù)信息(d1和P),客戶端支持存儲(chǔ)多個(gè)協(xié)同密鑰對(duì).

服務(wù)端存儲(chǔ)模塊用于存儲(chǔ)客戶端身份標(biāo)識(shí)、服務(wù)端子私鑰等敏感信息(d2,d3,P),服務(wù)端可存儲(chǔ)多個(gè)客戶端的協(xié)同密鑰對(duì).

5.2 性能分析

下面通過(guò)統(tǒng)計(jì)協(xié)同運(yùn)算過(guò)程中使用的主要運(yùn)算量和網(wǎng)絡(luò)傳輸數(shù)據(jù)量對(duì)本文方案和對(duì)照方案進(jìn)行分析,對(duì)照方案分別為L(zhǎng)indell[12]方案、Doerner等人[14]方案、王婧等人[16]方案.

采用符號(hào)KP表示橢圓曲線倍點(diǎn)運(yùn)算,KG表示橢圓曲線G點(diǎn)的倍點(diǎn)運(yùn)算,HH表示摘要運(yùn)算的耗時(shí),用PP表示一次同態(tài)運(yùn)算耗時(shí)(包括加密、解密、乘),NL表示Paillier公鑰長(zhǎng)度.與上述運(yùn)算比較,少量的點(diǎn)加、大數(shù)加、大數(shù)乘和哈希運(yùn)算的耗時(shí)可忽略不計(jì).用λ表示橢圓曲線運(yùn)算中域上元素長(zhǎng)度.

測(cè)試用的橢圓曲線參數(shù)(p,a,b,G,n)選擇NIST推薦的secp256r1,哈希算法選擇SHA-256,λ取值為256b.測(cè)試用客戶端身份標(biāo)識(shí)均按256b計(jì)算.

下面分析半誠(chéng)實(shí)模型下的各方案的理論運(yùn)算和通信開(kāi)銷(xiāo).Lindell[12]方案中,NL=8λ=2048;Doerner等人[14]方案中摘要計(jì)算的個(gè)數(shù)是在安全參數(shù)256的情況下統(tǒng)計(jì)的.本文方案中主要運(yùn)算開(kāi)銷(xiāo)是通信方A的1次固定點(diǎn)乘運(yùn)算和通信方B的1次非固定點(diǎn)乘運(yùn)算,總耗時(shí)為2KP.傳輸開(kāi)銷(xiāo)主要是IDA,e,Q和r,s1,s2,點(diǎn)Q長(zhǎng)度l(Q)=l(Qx,Qy)=2λ,通信有效數(shù)據(jù)長(zhǎng)度L=l(IDA)+l(e)+l(Q)+l(r)+l(s1)+l(s2)=32×8+λ+2λ+λ+λ+λ=256+6λ=1792b.半誠(chéng)實(shí)模型下各方案2個(gè)通信方的理論運(yùn)算開(kāi)銷(xiāo)如表1所示,理論通信開(kāi)銷(xiāo)如表2所示.

表1 半誠(chéng)實(shí)模型下理論運(yùn)算開(kāi)銷(xiāo)比較

表2 半誠(chéng)實(shí)模型下理論通信開(kāi)銷(xiāo)比較 b

惡意模型下,Lindell[12]方案增加執(zhí)行橢圓曲線離散對(duì)數(shù)的零知識(shí)證明協(xié)議;Doerner等人[14]方案增加執(zhí)行一致性檢測(cè)協(xié)議;王婧等人[16]方案和本文方案增加執(zhí)行橢圓曲線離散對(duì)數(shù)的零知識(shí)證明協(xié)議.各方案的理論計(jì)算開(kāi)銷(xiāo)如表3所示,理論通信開(kāi)銷(xiāo)如表4所示.

表3 惡意模型下理論運(yùn)算開(kāi)銷(xiāo)比較

表4 惡意模型下理論通信開(kāi)銷(xiāo)比較 b

在仿真測(cè)試中,測(cè)試主機(jī)CPU為Intel i7-7700 3.6GHz,對(duì)照組參考了王婧等人[16]方案提供的測(cè)試方法和數(shù)據(jù),如表5所示：

表5 仿真運(yùn)算開(kāi)銷(xiāo)比較 ms

6 方案延伸

本節(jié)給出由本協(xié)同簽名方案延伸的幾種私鑰拆分方法,差異部分如表6所示,其中A表示通信方A產(chǎn)生的敏感數(shù)據(jù)(其中di表示私鑰分量,ki表示隨機(jī)數(shù),i表示整數(shù)),B表示通信方B產(chǎn)生的敏感數(shù)據(jù).公式“d=”表示完整私鑰表達(dá)式,公式“k=”表示簽名隨機(jī)數(shù)k的表達(dá)式,表達(dá)式“si”表示通信方B計(jì)算的簽名中間數(shù)據(jù).

表6 本文方案延伸的幾種私鑰拆分方法

7 結(jié) 語(yǔ)

在互聯(lián)網(wǎng)場(chǎng)景下,協(xié)同簽名方案是解決智能終端軟件密碼模塊私鑰安全的關(guān)鍵.現(xiàn)有兩方和多方ECDSA協(xié)同簽名方案存在運(yùn)算效率偏低、通信開(kāi)銷(xiāo)過(guò)大等問(wèn)題,影響在智能終端用戶推廣.本文提出的C-ECDSA協(xié)同簽名方案,通過(guò)密鑰分存分算的算法設(shè)計(jì)充分保證協(xié)同運(yùn)算的安全性,實(shí)現(xiàn)對(duì)智能終端軟件密碼模塊簽名私鑰的隱私保護(hù),并較大提高協(xié)同簽名運(yùn)算效率.本文給出了方案的安全性分析及接近的幾種私鑰拆分方法.在性能開(kāi)銷(xiāo)上,理論分析和實(shí)測(cè)數(shù)據(jù)表明,本文方案具有運(yùn)算效率高、通信開(kāi)銷(xiāo)低的優(yōu)點(diǎn).

在實(shí)際應(yīng)用中,通信方A作為移動(dòng)智能終端的軟件密碼模塊,通信方B作為協(xié)同簽名服務(wù)器,本文方案可廣泛應(yīng)用于移動(dòng)金融、移動(dòng)政務(wù)、智能電表、V2X車(chē)聯(lián)網(wǎng)等互聯(lián)網(wǎng)領(lǐng)域.