一種基于ECC 具有時(shí)間限制的動(dòng)態(tài)秘密共享方案

曹 陽，洪 歧，陳 勇，李 軍

(陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中723000)

0 引言

基于Lagrange插值多項(xiàng)式(t，n)門限秘密共享方案是Shamir［1］在1979提出的，隨后學(xué)者對(duì)其進(jìn)行了大量研究。文獻(xiàn)［2］中各參與者的秘密份額是由分發(fā)者分發(fā)的，增加了通信、計(jì)算及存儲(chǔ)的復(fù)雜度;文獻(xiàn)［3］解決了參與者的子秘密更新問題，但更新不定期［4］;文獻(xiàn)［5］以時(shí)間為代價(jià)實(shí)現(xiàn)了共享秘密的定期動(dòng)態(tài)更新;文獻(xiàn)［6］提出的是基于XTR的秘密共享方案;文獻(xiàn)［7］提出的秘密共享方案是在秘密分發(fā)者安全存儲(chǔ)各參與者秘密份額的前提下，參與者的加入與退出不改變其他參與者的秘密份額［8］;文獻(xiàn)［9］提出的是基于RSA可驗(yàn)證的動(dòng)態(tài)多重秘密共享方案;文獻(xiàn)［10］實(shí)現(xiàn)了參與者之間相互驗(yàn)證子秘密，防止了參與者之間的欺詐行為。但以上文獻(xiàn)提出的秘密共享方案都具有一定的局限性，基于大數(shù)分解、離散對(duì)數(shù)的難解問題及Shamir的門限方案提出了具有時(shí)間限制的動(dòng)態(tài)秘密共享方案。該方案實(shí)現(xiàn)了參與者秘密份額由自己生成，秘密更新不需要秘密分發(fā)者的參與，參與者只需要維護(hù)自己的一份秘密份額就可以共享任意多個(gè)秘密;秘密份額必須在有效時(shí)間范圍內(nèi)更新才有效，無需額外通信量;參與者的加入與退出不影響其他參與者秘密份額的改變;秘密恢復(fù)在有效期內(nèi)對(duì)秘密份額進(jìn)行驗(yàn)證，防止欺騙行為。

1 相關(guān)知識(shí)

1.1 橢圓曲線

橢圓曲線［11］指的是由韋爾斯特拉斯(Weierstrass)方程

y2+a1xy+a3y=x3+a2x2+a4x+a6

所確定的平面曲線。系數(shù)ai(i=1，2，…，6)可以是有理數(shù)域、實(shí)數(shù)域、復(fù)數(shù)域，還可以是有限域E(Fp)，橢圓曲線密碼體制(elliptic curve cryptosystem，ECC)中用到的橢圓曲線都定義在有限域上的。

1.2 橢圓曲線離散對(duì)數(shù)問題

G是橢圓曲線E(Fp)上的基點(diǎn)，N為G的階(N為一個(gè)安全的大素?cái)?shù))，如整數(shù)m(0＜m＜N－1)存在，Q=mG，則稱m為Q的以G為基的離散對(duì)數(shù)。對(duì)于E(Fp)上的一點(diǎn)G，對(duì)任意的Q，求整數(shù)m，使得Q=mG的問題稱為橢圓曲線上的離散對(duì)數(shù)問題(elliptic curve discrete logarithm problem，ECDLP)［11-12］，橢圓曲線密碼體制正是利用這個(gè)困難問題設(shè)計(jì)而來。

1.3 最小授權(quán)子集

設(shè)A={P1，P2，…，Pn}為用戶集P構(gòu)成的訪問結(jié)構(gòu)，Bj={P1j，P2j，…，Pij}(1 ≤ i≤m，1 ≤j≤n)是A的用戶子集，Bj∈A，若?a∈Bj，Bj－a?A，則稱Bj為A的最小授權(quán)子集［6］，A為授權(quán)集。令Pij∈ Bj，［T1i，T2i］為參與者 Pij的有效期 (1 ≤ i≤m)，稱［T1Bj，T2Bj］=［T11，T21］∩［T12，T22］∩…∩［T1m，T2m］=∩mi［T1i，T2i］為最小授權(quán)子集 Bj的有效期［6］。本文中提到的授權(quán)子集都指的是最小授權(quán)子集。

2 方案構(gòu)成

設(shè)SD為可信第三方秘密分發(fā)者，NB(notice board)為公告牌，SD通過公告牌將秘密k分為m個(gè)子秘密分發(fā)給授權(quán)子集Bj中的m個(gè)不同的參與者{P1j，P2j，…，Pij}(1 ≤i≤m)共享，當(dāng)且僅當(dāng)授權(quán)子集中的s個(gè)或s以上個(gè)參與者聯(lián)合才能恢復(fù)秘密k，而非授權(quán)子集中的參與者聯(lián)合不能恢復(fù)秘密k的任何信息。公告牌上的內(nèi)容只有SD才能更新和修改，其他人只能查看下載。本方案由初始化參數(shù)選取、注冊(cè)、秘密份額生成、秘密恢復(fù)、秘密份額及秘密的更新5部分組成。

2.1 初始化參數(shù)的選取

1)在橢圓曲線E(Fp)上選取基點(diǎn)G，N(N為一個(gè)安全的大素?cái)?shù))，N為G的階，SD在NB上發(fā)布G，N;

2)參與者Pij隨機(jī)選擇一個(gè)整數(shù)ri(1＜ri＜N)，計(jì)算Gi=riG，Pij保密ri，將Gi發(fā)送給SD;

3)SD選取整數(shù)r0(1＜r0＜N)，計(jì)算G0=r0G;

4)SD與Pij共同協(xié)商一個(gè)哈希函數(shù)H()，要求沖突的概率足夠小;

5)SD在NB上公布參數(shù)Gi，G0，H()。

2.2 注 冊(cè)

設(shè)有β個(gè)授權(quán)子集參與秘密共享。

1)SD 選取 β 個(gè)不同的數(shù)d1，d2，…，dβ∈［1，N－1］來標(biāo)識(shí)A中的每個(gè)授權(quán)子集;

2)SD將時(shí)間劃分成一些小區(qū)間，時(shí)間的長(zhǎng)度可以小時(shí)、天、日期、月等為單位，如 1，2，3，…，L，L表示系統(tǒng)中存在的最長(zhǎng)時(shí)間;

3)SD為每個(gè)授權(quán)子集Bj中的秘密共享成員設(shè)定有效期［T1ij，T2ij］，并在 NB 上發(fā)布;

4)SD根據(jù)各成員的有效期，計(jì)算出每個(gè)授權(quán)子集的有效期，并在NB上發(fā)布;

5)SD隨機(jī)選取2m個(gè)不同的數(shù)ai，bi(1≤i≤m)，計(jì)算HT1ij(ai)，HL－T2ij(bi)，通過安全信道分別發(fā)送給對(duì)應(yīng)的參與者，同時(shí)銷毀ai，bi。

2.3 秘密份額生成

秘密份額生成的過程由秘密分發(fā)者SD和參與者共同完成，生成過程如下。

1)SD隨機(jī)選取一整數(shù)l(1＜l＜N)，l必須與其他秘密分發(fā)選取的隨機(jī)數(shù)不同，計(jì)算s=lG，并將s在公告牌上公布;

2)A 中的每個(gè)一授權(quán)子集 Bj={P1j，P2j，…，Pij}(1≤i≤m)，參與者Pij隨機(jī)選取一整數(shù)j(1＜j＜ N)，計(jì)算eij=jG，e'ij=jG0，令c0ij=sri⊕e'ij。并將c0ij，eij發(fā)送給秘密分發(fā)者SD，如果一個(gè)參與者同時(shí)在多個(gè)授權(quán)子集中，則該參與者只發(fā)送一個(gè)c0ij，eij給 SD;

3)SD檢查收到的c0ij，eij，保證不同的參與者有不同的c0ij，eij，以免不同的參與者擁有相同的秘密份額。如果相同，參與者就必須重新選取初始秘密份額，直到各參與者都擁有不同的秘密份額，并將參與者的信息c0ij，eij在公告牌上公布;

4)SD計(jì)算e'ij=r0eij=r0jG ，sri=cij⊕e'ij，令x0ij=sr，利用公告信息驗(yàn)證sriG是否等于sGi，若相等，則接收x0ij;

5)SD從［1，N －1］中任選整數(shù)b，q，生成Lagrange多項(xiàng)式f(x)=(bx+k)mod q，計(jì)算f(1)，將(1，f(1))在公告牌上公布;

6)SD為每個(gè)授權(quán)子集Bj計(jì)算Xj=H(d1x01j⊕d2x02j⊕…⊕djx0ij)，f(Xj)，并將f(Xj)，dj在公告牌上公布。

2.4 秘密恢復(fù)

秘密恢復(fù)是由秘密生成者SG(secret generator)來完成的，SG可以是Bj中的參與者，也可以是非Bj中的其他成員。秘密恢復(fù)工作是在t+1次更新前，t次更新后進(jìn)行的。

1)Bj中的參與者Pij隨機(jī)選取一整數(shù)(1＜j＜N)，計(jì)算eij=jG，e'ij=jG0，令ctij=sri⊕ e'ij，將ctij，eij發(fā)送給 SG;

2)SG從公告牌上下載((1，f(1))，f(Xj))和dj的有效期;

3)SG判斷dj是否在有效期內(nèi)，如果在，則繼續(xù)第4)步，如果不在，則向Bj中的每一個(gè)參與者發(fā)送一個(gè)報(bào)怨;

4)計(jì)算e'ij=r0eij=r0jG，則sri=ctij⊕ e'ij，令xtij=sr，利用公開信息，驗(yàn)證sriG是否等于sGi，如ijiii果相等，接收xtij，驗(yàn)證通過，否則放棄;

5)SG根據(jù)Xj=H(d1x1tj⊕d2x2tj⊕…⊕djxtij)和((1，f(1))，f(Xj))，利用Lagrange恢復(fù)多項(xiàng)式，從而恢復(fù)出秘密k。

2.5 秘密份額及秘密信息的更新

秘密分發(fā)者 SD 在時(shí)刻 t=1，2，3，…，L進(jìn)行如下工作。

1)Bj中的每一個(gè)參考者 Pij在 t時(shí)刻，若t∈ ［T1ij，T2ij］則 計(jì) 算utij= Ht(aij)HL－t(bij)=［Ht－T1ij(HT1ij(aij))］［HT2ij－t(HL－T2ij(bij))］;

2)Pij計(jì)算xtij=xtij－1+utij，更新所持有的秘密份額，銷毀 xtij－1;

3)如果需要更新秘密信息為k'，則SD從［1，N－1］中隨機(jī)選擇一個(gè)整數(shù) b'，q，計(jì)算f(x)=(k'+b'x)mod q，然后將f(1)公布在公告牌上，如果不需要更新秘密信息則執(zhí)行下一步;

4)SD為每個(gè)授權(quán)子集Bj計(jì)算Xj=H(d1x1tj⊕d2x2tj⊕…⊕djxtij)，f(Xj)，將f(Xj)，dj公布在公告牌上。

3 方案討論

3.1 多重秘密共享

方案中每個(gè)參與者Pij只需維護(hù)自己的秘密份額。如果m個(gè)參與者共享n個(gè)秘密k1，k2，…kn，當(dāng)且僅當(dāng)A中的每一個(gè)授權(quán)子集Bj中的參與者共同合作才能恢復(fù)出秘密，其他未被恢復(fù)的秘密的安全性并不會(huì)因?yàn)榇嗣孛艿幕謴?fù)而受到影響。秘密分發(fā)時(shí)，分發(fā)者SD均隨機(jī)生成整數(shù)l(1＜l＜N)且與其他的隨機(jī)數(shù)不同，計(jì)算s=lG，參與者計(jì)算sri，根據(jù)橢圓曲線離散對(duì)數(shù)的難解性，攻擊者無法從sri計(jì)算出ri。公告牌上公布了f(1)，但在構(gòu)造多項(xiàng)式時(shí)，為每個(gè)秘密生成了一個(gè)參數(shù)b，并且為每個(gè)授權(quán)子集計(jì)算了f(Xj)。秘密共享時(shí)參與者之間并不會(huì)泄露私有秘密份額，加上秘密份額具有時(shí)間限制，攻擊者就無法利用本次秘密共享結(jié)果去計(jì)算恢復(fù)其他秘密，當(dāng)然也不會(huì)因?yàn)橹貜?fù)使用秘密份額而影響系統(tǒng)的安全性。

3.2 參與者的加入/退出

應(yīng)用中，參與者的加入/退出都會(huì)引起訪問結(jié)構(gòu)的改變，但并不影響其他參與者秘密份額的改變。當(dāng)增加一個(gè)新的參與者Pn+1時(shí)，SD為新增加的參與者Pn+1確定對(duì)秘密共享的有效期［T1n+1，T2n+1］，并發(fā)布在公告牌上。SD隨機(jī)選取2個(gè)不同的數(shù)an+1，bn+1，計(jì)算HT1(n+1)j(an+1)，HL－T2(n+1)j(bn+1)，通過安全信道分別發(fā)送給對(duì)應(yīng)的參與者，同時(shí)銷毀 an+1，bn+1。Pn+1從［1，N － 1］中隨機(jī)選取整數(shù) jn+1，rn+1，計(jì)算en+1=jn+1G，e'n+1=jG0，cn+1=srn+1⊕e'n+1，并將srn+1⊕e'n+1，en+1發(fā)送給SD。SD檢查驗(yàn)證，保證不同的參與者有不同的秘密份額，即對(duì)任意的xi(i=1，…，n)，xi≠xi+1。如果參與者 Pn+1的加入導(dǎo)致授權(quán)子集的增加，SD需在［1，N－1］選取一個(gè)整數(shù)dn+1，標(biāo)識(shí)增加的授權(quán)子集，并按2.3中的5)和6)計(jì)算公布相關(guān)信息。當(dāng)刪除參與者Pij時(shí)，可能導(dǎo)致某些授權(quán)子集變成非授權(quán)子集，SD需在公告牌上刪除Pij的相關(guān)信息，及與Pij相關(guān)的授權(quán)子集信息、有效期標(biāo)識(shí)。為了安全起見，應(yīng)該更新共享秘密。

3.3 方案安全性分析

1)方案是安全的。

證明:t時(shí)刻，攻擊者將要根據(jù)公開信息 (1，f(1))以及各授權(quán)子集的信息f(Xj)，dj獲取秘密k，必須得到 Xj，由 Xj=H(d1x1tj⊕d2x2tj⊕…⊕dxt)可知，要獲得X還必須同時(shí)獲得授權(quán)子集中的所有參與者Pij的有效期限和秘密份額xtij。假設(shè)攻擊者截取ctij，eij，試圖計(jì)算出秘密份額xtij，由于e'ij=rteij=rtjG，sri=ctij⊕ e'ij，xtij=sri，但要計(jì)算出正確的秘密份額還必須獲得參與者與秘密分發(fā)者的秘密數(shù)，由橢圓曲線離散對(duì)數(shù)問題知，攻擊者無法計(jì)算出xtij，也就無法獲取秘密k，因此方案是安全的。

2)秘密份額及秘密更新是安全的。

證明:時(shí) 刻 t=1，2，3，…，L，若 t ∈［T1ij，T2ij］，參與者Pij需要更新自己的秘密份額。秘密份額的更新是通過SD和參與者Pij在秘密生成過程中共同擁有的哈希函數(shù) HT1ij(ai)，HL－T2ij(bi)，計(jì)算utij= Ht(aij)HL－t(bij)=［Ht－T1ij(HT1ij(aij))］×［HT2ij－t(HL－T2ij(bij))］來更新秘密份額 xtij=xtij－1+utij。

①當(dāng)T1ij≤ T2ij＜t時(shí)，只能求出 Ht(aij)=［Ht－T1ij(HT1ij(aij))］，但無法求出 HL－t(bij);

②當(dāng)t＜ T1ij≤ T2ij時(shí)，只能求出 HL－t(bij)=［HT2ij－t(HL－T2ij(bij))］，但無法求出 Ht(aij);

③當(dāng)且僅當(dāng)T1ij≤t≤T2ij時(shí)，才能同時(shí)求出Ht(aij)，HL－t(bij)。

綜上所述，只有參與者在有效期內(nèi)，才能更新自己的秘密份額。由于參與者與分發(fā)者之間不存在通信，加上哈希函數(shù)的單向性及求解的困難性知，Pij以外的參與者是無法得到Pij的秘密份額，所以秘密份額更新是安全的。

通過計(jì)算f(x)=(k'+b'x)mod q可將秘密k更新為k'，b'，q是SD從［1，N－1］中隨機(jī)選擇一個(gè)整數(shù)。

3)方案防止參與者的欺騙。

證明:秘密恢復(fù)過程第4)步，計(jì)算e'ij=r0eij=r0jG，則sri=ctij⊕e'ij，SG驗(yàn)證sriG是否等于sGi，若相等，說明參與者Pij提供了正確的信息，繼續(xù)進(jìn)行秘密恢復(fù)工作，否則參與者可能存在欺騙行為，放棄秘密恢復(fù)。

4)方案具有前向安全性。

證明:秘密份額生成過程中，參與者Pij在公開信道上向SD發(fā)送的c0ij，eij，攻擊者截取 c0ij，eij也無法計(jì)算出sri，因?yàn)閑'ij=r0eij=r0jG，sri=c0ij⊕ e'ij，其安全性是建立在橢圓曲線離散對(duì)數(shù)的安全性之上。

3.4 同類方案相比

下面主要從安全性能、通信復(fù)雜度、計(jì)算復(fù)雜度、運(yùn)算量四方面與引言中提到的文獻(xiàn)［2］方案相比。

安全性能方面:秘密更新必須在有效期內(nèi)完成，參與者和秘密分發(fā)者之間不存在通信，加上哈希函數(shù)的單向性及離散對(duì)數(shù)求解的困難性知，秘密更新的安全性進(jìn)一步加強(qiáng)。

通信復(fù)雜度:參與者秘密份額是由參與者自己生成，且只需維護(hù)自己的一份秘密份額就可以共享任意多個(gè)秘密，降低了通信的復(fù)雜度，進(jìn)而減少存儲(chǔ)空間。

計(jì)算復(fù)雜度:由文獻(xiàn)［8］知Lagrange多項(xiàng)式的計(jì)算復(fù)雜度比高次多項(xiàng)式的計(jì)算復(fù)雜度低，加之秘密份額的更新是通過哈希函數(shù)完成，秘密分發(fā)者與參與者之間不需要同步更新，也不存在傳輸量問題，所以方案降低了通信、計(jì)算的復(fù)雜度，提高了更新效率。

運(yùn)算量:增加授權(quán)子集時(shí)，秘密分發(fā)者SD增加的計(jì)算量主要是哈希運(yùn)算，因而運(yùn)算量不會(huì)大幅度增加。

4 總結(jié)

本文基于大數(shù)分解、離散對(duì)數(shù)的難解問題及Shamir的門限方案提出了具有時(shí)間限制的動(dòng)態(tài)秘密共享方案。方案實(shí)現(xiàn)了參與者Pij秘密份額的生成，更新不需要秘密分發(fā)者SD的參與，參與者只需要維護(hù)自己的一份秘密份額就可以共享任意多個(gè)秘密;秘密份額更新必須在有效的時(shí)間范圍內(nèi)更新才有效，參與者和秘密分發(fā)者無需同步更新，也不存在通信量的問題;參與者的加入/退出不影響其他參與者秘密份額的改變，當(dāng)引起授權(quán)子集的增加時(shí)，計(jì)算量主要是秘密分發(fā)者進(jìn)行的哈希運(yùn)算，參與者的計(jì)算量不會(huì)隨授權(quán)子集的增加而增加;秘密恢復(fù)在有效期對(duì)秘密份額進(jìn)行驗(yàn)證，防止欺騙行為。方案的安全性基于大數(shù)分解、橢圓曲線離散對(duì)數(shù)問題的難解性及Shamir的門限方案的安全性。

［1］SHAMIR A.How to Share a Secret［J］.Communications of the ACM，1979，22(11):612-613.

［2］LIU Duo，HUANG Dongping，LUO Ping，et al.New Schemes for Sharing Points on an Elliptic Curve［J］.Computers and Mathematics with Applications，2008，56(6):1556-1561.

［3］LAIH C S，HAM L，LEE J Y，et al.Dynamic Threshod Schemes Based on the Definition of Cross Product in Dimensional Linear Space［J］.Joural of Information Science and Engineering，1991，7(1):13-23.

［4］肖立國(guó)，鐘誠(chéng).基于ECC的定期更新的可驗(yàn)證秘密共享方案［J］.計(jì)算機(jī)工程與科學(xué)，2006，28(7):25-27.XIAO Liguo，ZHONG Cheng.A Periodically Renewed Verifiable Secret Sharing Scheme Based on the Elliptic Curve Cryptosystem［J］.Computer Engineering ＆ Science，2006，28(7):25-27.

［5］張建中，張艷麗.一種子秘密可更新的動(dòng)態(tài)多秘密共享方案［J］.計(jì)算機(jī)工程，2011，37(20):117-119.ZHANG Jianzhong，ZHANG Yanli.Dynamic Multi-secret Sharing Scheme with Updatable Sub-secret［J］.Computer Engineering，2011，37(20):117-119.

［6］趙佳.可信認(rèn)證關(guān)鍵技術(shù)研究［D］.北京:北京交通大學(xué)，2008:59-67.ZHAO Jia.Research on Key Technology of Trusted Authentication［D］.Beijing:Beijing Jiaotong University，2008:59-67.

［7］PINCH R.On-line multiple secret sharing［J］.Electronics Letters，1996，32(12):1087-1088.

［8］龐遼軍，姜正濤.基于一般訪問結(jié)構(gòu)的多重秘密共享方案［J］.計(jì)算機(jī)研究與發(fā)展，2006，43(1):33-38.PANG Liaojun，JIANG Zhengtao.A Multi-Secret Sharing Scheme Based on the General Access Structure ［J］.Journal of Computer Research and Development，2006，43(1):33-38.

［9］王鋒，張建中.基于RSA的可驗(yàn)證的動(dòng)態(tài)多重秘密共享方案［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(6):1806-1808.WANG Feng，ZHANG Jianzhong. Dynamicverified threshold multi-secret sharing scheme based on RSA cryptosystem［J］Application Research of Computers，2008，25(6):1806-1808.

［10］戴元軍，馬春光.一種改進(jìn)的基于拉格朗日插值的(t，n)門限秘密共享［J］.北京郵電大學(xué)學(xué)報(bào)，2004，27(2):24-28.DAI Yuanjun，MA Chunguang.An Kind of(t，n)Threshold Secret Sharing Based on Lagrange Insert Value［J］.Journal of Beijing University of Posts and Telecommunications，2004，27(2):24-28.

［11］曹陽，郝玉潔，洪歧.一種基于ECDLP有身份認(rèn)證的ECDH密鑰協(xié)商方案［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2012，24(1):118-120.CAO Yang，HAO Yujie，HONG Qi.One ECDH key agreement scheme with authentication based on ECDLP［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2012，24(1):118-120.

［12］HANKERSON D，MENEZES A，VANSTONES S.Guide to Elliptic Curve Crypotography［M］.New York，USA:Springer-Verlag，2004.