托管者有權(quán)重的動(dòng)態(tài)門限多重密鑰托管方案

李 林， 曹 瑀， 李志華*

(1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫214122;2.大連理工大學(xué)軟件學(xué)院，遼寧大連116024)

密鑰托管技術(shù)主要解決安全密鑰的分配與管理問題，它廣泛運(yùn)用于密鑰保護(hù)與數(shù)據(jù)保密中，任何得到合法授權(quán)的密鑰合成者可以從托管代理保存的密鑰份額中恢復(fù)出安全密鑰。

自Nechvatal提出門限密鑰托管概念之后，國(guó)內(nèi)外眾多學(xué)者針對(duì)此進(jìn)行了深入的研究與探討。目前提出的大多數(shù)方案基于運(yùn)算量與時(shí)間復(fù)雜度相對(duì)較高的RSA和ElGamal密碼體制［1-2］;托管者權(quán)重單一且密鑰份額只能使用一次［3］，而在實(shí)際運(yùn)用中往往需要在一組托管代理組中共享托管多組密鑰;需要維持安全的通信信道;存在逃避托管和無(wú)法驗(yàn)證子密鑰的問題。

針對(duì)以上問題，文中在文獻(xiàn)［2］的基礎(chǔ)上，通過引入相對(duì)于RSA，ElGamal體制更具有優(yōu)勢(shì)的ECC密碼體制和Shamir門限方案，利用ECC上的雙線性對(duì)理論［4］及身份密碼系統(tǒng)原理［5］，設(shè)計(jì)了門限值可變的動(dòng)態(tài)多密鑰托管方案。其中，每個(gè)托管代理具有不同的權(quán)重值，且其權(quán)重可以根據(jù)實(shí)際需要而變動(dòng)［6-7］;同時(shí)，組合公鑰(Combined Public Key，CPK)密碼體制［8］的應(yīng)用可以實(shí)現(xiàn)密鑰份額與密鑰托管代理的相互認(rèn)證，解決了逃避托管與密鑰份額篡改問題，且方案通信均在公共信道上進(jìn)行，具有良好的應(yīng)用前景。

1 方案初始化

設(shè) Si={si1，si2，si3，…，sik}i∈［1，m］為方案中m組待托管密鑰，p1，p2，…，pn為n個(gè)有權(quán)重的密鑰托管代理，MD為多密鑰分發(fā)者，DC為多密鑰合成者。其中，MD和DC可以是密鑰管理中心(Key Management Center，KMC)，也可以是某個(gè)安全的密鑰托管代理。本方案需要一個(gè)公告牌，MD可以在公告牌上發(fā)布或者更新密鑰參數(shù)信息，供托管方案中其他成員下載。

1.1 系統(tǒng)參數(shù)初始化

在多重密鑰托管方案中，設(shè)E(Fq)為有限域上的一條安全的橢圓曲線［9］，G1和G2分別為兩個(gè)q階的加法群和乘法群，G為G1的生成元，且它們之間存在雙線性映射e:G1×G1→G2;h:{0，1}*→G1和h1:{0，1}*→為兩個(gè)單向hash函數(shù);hk(·)為帶密鑰的鑰控單向hash函數(shù);(Ek，Dk)為某對(duì)稱算法的加解密算法，E2是橢圓曲線公開密鑰加密算法。然 后 在 公 告 牌 上 公 布 {E(Fq)，e，G，q，h0，h1，hk(·)}。

1.2 托管代理初始化

密鑰托管代理的公私鑰對(duì)由基于ECC的CPK算法初始化生成，KMC隨機(jī)選取r∈［1，q-1］，其橢圓曲線E(Fq)上一點(diǎn)Pk=rG=(Xr，Yr);利用整數(shù)矢量kij秘密構(gòu)造私鑰種子矩陣SSK，則對(duì)應(yīng)的公鑰種子矩陣PSK由點(diǎn)矢量kijG=(xij，yij)構(gòu)成，公開{Ii，PSK};KMC對(duì)每個(gè)托管代理身份It(設(shè)序列位數(shù)為h)利用hash函數(shù)h1作行映射后，私鑰為

其中，rmapkh為SSK中的第k列中的第mapk個(gè)值。任何托管代理均可利用公開的{It，PSK}計(jì)算出公鑰:

2 動(dòng)態(tài)多重密鑰共享協(xié)議

文中基于橢圓曲線密碼體制提出了動(dòng)態(tài)的多密鑰共享(ECC-based dynamic multi-key sharing protocol，EDMSP)協(xié)議，包括多密鑰分發(fā)、子密鑰份額驗(yàn)證、多密鑰重構(gòu)等部分。

2.1 多密鑰的分發(fā)

多密鑰分發(fā)者M(jìn)D利用下面的算法將m組密鑰Si={si1，si2，si3，…，sik}分發(fā)給密鑰托管組P={p1，p2，…，pn}，其權(quán)重為 W={w1，w2，…，wn}。對(duì)于每組密鑰而言，該協(xié)議可以認(rèn)作為一個(gè)(ti，n)門限密鑰共享方案，密鑰分發(fā)過程如下:

1)MD從［1，q-1］中隨機(jī)選取整數(shù) ri0∈［1，q-1］，計(jì)算 Ri0=rioG。

2)MD隨機(jī)構(gòu)造m個(gè)ti-1次多項(xiàng)式:

其中，ai0=SMD;aiti-1≠0，且ai1，…，aiti-1∈GF(Q)。

3)MD 計(jì)算 Aij=aijG(j=0，2，…，ti-1)，

其中，8表示按位異或運(yùn)算。銷毀aij并公布s'il。

4)MD隨機(jī)選取 α∈ GF(p)，計(jì)算 Dit=fi(It)Ri0(t=1，2，…，n)以及 git=h(Dit·+ri0Qt)，lit=f(It)-h(Dit·+ α·giti)，將{It，Wt，Dit}傳遞給密鑰托管者It，并公布有序數(shù)組{α，lit，It，Wt}。

5)MD隨機(jī)選取bi0∈，計(jì)算

并將(cit，sit，Rit)傳遞給密鑰托管組 P，ri0銷毀。

2.2 子密鑰份額驗(yàn)證

1)pi獲取(cit，sit，Rit)后，計(jì)算

2)pi利用得到的 kit解密 Dkit，1(cit)，并驗(yàn)證等式rit=hkit，2(ri0)是否成立。若成立，則臨時(shí)密鑰傳遞成功;否則，向MD傳遞錯(cuò)誤信息，并停止通信。

2.3 多密鑰重構(gòu)

2)DC將計(jì)算得到的ti個(gè)數(shù)值對(duì)(Iti，fi(Iti))利用拉格朗日多項(xiàng)式插值重構(gòu)［11］，具體如下:

3)DC計(jì)算Aij=aijG，并與公告牌上的{Aij}比較，驗(yàn)證恢復(fù)出來(lái)的常數(shù)項(xiàng)的正確性。若正確，則計(jì)算sil=s'il8ai08…8aij，從而得到共享的秘密組Si={si1，si2，si3，…，sik}。

3 基于動(dòng)態(tài)多重密鑰共享協(xié)議的密鑰托管方案

在密鑰托管方案中，{KMC}負(fù)責(zé)頒發(fā)證書，監(jiān)聽服務(wù)器{W}，經(jīng)必要授權(quán)可以與密鑰托管組P，{KMC}、密鑰合成者DC等執(zhí)行相應(yīng)的協(xié)議監(jiān)聽用戶通信。

基于動(dòng)態(tài)多密鑰共享協(xié)議的多密鑰托管方案(EDMSP-based key escrow scheme，EKES)描述如下。

3.1 證書頒發(fā)

在EDMSP協(xié)議中子密鑰驗(yàn)證階段，當(dāng)密鑰托管子集pi中的每個(gè)成員驗(yàn)證通過收到的托管密鑰份額后，計(jì)算簽名 ssti= sigIt(h(MD，giti，ziti=h(diti+ri0·Sti·G)·Gmodp))，并將(MD，giti，ziti，ssti)傳遞給KMC。

密鑰管理中心接收到密鑰托管子集pi的(MD，giti，ziti，ssti)后，驗(yàn)證 ziti=gitiGmodp 和簽名是否成立。若成立，則可以確認(rèn)簽名ssti有效，并計(jì)算簽名sK=sigKMC(h(MD，G，p，QMD))，并為 MD 頒發(fā)證書 C(MD)=(MD，p，G，QMD，sK)，認(rèn)定組密鑰 Si托管成功。

3.2 通信協(xié)議的設(shè)計(jì)

當(dāng)用戶B獲取到證書C(MD)時(shí)，秘密選取Ktmp，l∈，(其中Ktmp作為臨時(shí)會(huì)話密鑰加密消息)，并向 MD 發(fā)送{Ek(M，Ktmp)，LEAF}。

其中:

S(H(M，T))為B用橢圓曲線私鑰對(duì)H(M，T)的簽名［12］。

MD收到{Ek(M，Ktmp)，LEAF}后計(jì)算 Ktmp=v-SMD·u，利用Ktmp計(jì)算明文M=D(C，Ktmp)，求取H(M，T)。若H(M，T)滿足簽名方案，MD可以確認(rèn)收到的M是有效，開始通信并傳遞組密鑰。

3.3 監(jiān)聽協(xié)議的設(shè)計(jì)

監(jiān)聽服務(wù)器接收到合法的監(jiān)聽授權(quán)時(shí)，利用監(jiān)聽協(xié)議對(duì)監(jiān)聽對(duì)象的通信內(nèi)容進(jìn)行有效監(jiān)聽。

1)監(jiān)聽服務(wù)器{W}首先將授權(quán)證書和監(jiān)聽到的LEAF分別出示給任意合格托管組Pi中的每一個(gè)托管代理Iti，托管代理驗(yàn)證證書的有效性與時(shí)效性后計(jì)算:

并將LEAFIti回傳給監(jiān)聽服務(wù)器。

2)監(jiān)聽服務(wù)器接收到LEAFIti后，驗(yàn)證時(shí)效性及h(Qiti，Iti，T)是否滿足簽名方案。若滿足，則監(jiān)聽服務(wù)器認(rèn)為托管代理誠(chéng)實(shí)出示了Qij，并計(jì)算:

由Ktmp=v-lQMD恢復(fù)出Ktmp，再由Ktmp解密出通信明文M=D(C，Ktmp)，最后驗(yàn)證H(M，T)是否滿足簽名。若滿足，則監(jiān)聽服務(wù)器實(shí)現(xiàn)用戶B的通信監(jiān)聽。

4 方案分析和證明

4.1 正確性分析

定理1 方案具有身份認(rèn)證功能。在子密鑰份額驗(yàn)證階段，由雙線性變換性質(zhì)［13］可知，只有對(duì)應(yīng)身份的托管代理才可以進(jìn)行解簽密，有 e(Qt，sit)e(St，Rit)=e(Qt，QMD)bi0恒成立。

證

證畢。

證

證畢。

定理3 EDMSP協(xié)議具備前向安全性，即在多密鑰分發(fā)階段，即使多密鑰分發(fā)者私鑰泄露也不會(huì)影響之前所共享的核心參數(shù)ri0的安全性。

證當(dāng)多密鑰分發(fā)者的私鑰SMD泄露時(shí)，攻擊者想要利用Rit=ritQMD計(jì)算得到rit面臨著破解橢圓曲線離散對(duì)數(shù)難題(Elliptic Curve Discrete Logarithm Problem，ECDLP)。在多項(xiàng)式時(shí)間內(nèi)，計(jì)算上是不可行的。同理，攻擊者也無(wú)法計(jì)算出參數(shù)bi0。因此，攻擊者無(wú)法計(jì)算出 kit=(kit，1，kit，2)。在分發(fā)者私鑰泄漏的情況下，無(wú)法解密得到核心參數(shù)ri0，因此無(wú)法進(jìn)行后續(xù)攻擊行為。由此證明了協(xié)議具有前向安全性。

4.2 安全性分析

文中提出的多密鑰托管方案的安全性基于ECC密碼體制、Shamir門限方案以及單向hash函數(shù)的安全性，分析如下:

2)在密鑰分發(fā)階段，由于傳遞的是影子份額［15］，方案中密鑰托管代理和惡意的攻擊者無(wú)法從公開的參數(shù)獲取任何關(guān)于aij以及fi(It)的私密信息。攻擊者想要破解這些信息意味著要破解橢圓曲線上的離散對(duì)數(shù)難題，在計(jì)算上是不可行的。因此，可以防范外部攻擊者對(duì)合法托管代理的攻擊。

3)在密鑰重構(gòu)階段，由定理2可知，只有正確的密鑰托管者提供的正確份額才能參與組密鑰的重構(gòu)，有效防止了托管代理對(duì)DC的欺詐，即實(shí)現(xiàn)了密鑰份額的驗(yàn)證。

4)方案中KMC驗(yàn)證了托管代理密鑰份額的有效性和真實(shí)性后為MD生成證書，有效地避免了分發(fā)者逃避托管。在監(jiān)聽階段，監(jiān)聽服務(wù)器收到托管代理的LEAFIti后，驗(yàn)證其是否來(lái)源于誠(chéng)實(shí)的托管代理，再計(jì)算Q與當(dāng)次的會(huì)話密鑰Ktmp，而不是用戶的任何私鑰信息，且每次通信用戶B都會(huì)隨機(jī)選取l。因此，避免了“一次監(jiān)聽，永久監(jiān)聽”的問題。

4.3 性能分析

從以下幾方面分析文中方案的性能:

1)對(duì)于時(shí)間復(fù)雜度。由安全性證明可知，該方案不需要維持安全信道，降低了方案的實(shí)現(xiàn)代價(jià)。在密鑰分發(fā)階段，由于橢圓曲線倍點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為o(n2)遠(yuǎn)小于模冪運(yùn)算與大數(shù)運(yùn)算，且密鑰長(zhǎng)度較短，因此該方案的時(shí)間復(fù)雜度低于其他方案。

2)對(duì)于動(dòng)態(tài)性。當(dāng)托管代理組P新增代理In+1時(shí)，首先計(jì)算出公私鑰對(duì){SIn+1，QIn+1}，然后計(jì)算Di(n+1)=fi(In+1)Ri0，并將{In+1，Di(n+1)，Wn+1}傳遞給密鑰托管代理。若方案中某個(gè)密鑰托管代理It不可信或密鑰份額泄漏時(shí)，只需回收該用戶身份It與托管份額，重新選擇一個(gè)多項(xiàng)式即可。

3)對(duì)于安全性基礎(chǔ)。橢圓曲線密碼體制的安全強(qiáng)度以及橢圓曲線離散對(duì)數(shù)問題的難解性都遠(yuǎn)大于傳統(tǒng)的離散對(duì)數(shù)系統(tǒng)以及大數(shù)分解問題，且采用橢圓曲線上的雙線性對(duì)理論，可以使方案以較短的密鑰長(zhǎng)度得到相對(duì)于其他密碼系統(tǒng)同等的安全強(qiáng)度，取消了方案中臨時(shí)密鑰傳遞過程中多余的交互過程，從而降低了通信復(fù)雜度，更加符合實(shí)際的應(yīng)用需求。

4)對(duì)于前向安全性。當(dāng)多密鑰分發(fā)者的私鑰SMD泄露時(shí)，由定理3與安全性分析可知，MD傳遞的臨時(shí)會(huì)話私鑰ri0是不會(huì)被任何攻擊者獲取，所以攻擊者無(wú)法計(jì)算出傳遞給托管代理的密鑰份額diti。因此，MD的私鑰泄露不會(huì)對(duì)前面?zhèn)鬟f的密鑰份額造成安全威脅，即方案具備前向安全性。

5)由于在密鑰分發(fā)階段，不同的密鑰組構(gòu)造的曲線fi(x)以及選取的隨機(jī)整數(shù)ri0不同，由安全性證明可知，一組密鑰的重構(gòu)不會(huì)影響其他托管組密鑰的安全性與重構(gòu)。同時(shí)方案中托管代理的密鑰由用戶身份計(jì)算產(chǎn)生，因此在多組密鑰共享托管時(shí)，實(shí)現(xiàn)了托管密鑰與代理身份的對(duì)應(yīng)認(rèn)證，且各托管代理的密鑰以及影子份額可以重復(fù)利用。

表1列出了文中方案與其他方案的對(duì)比結(jié)果。

表1 文中方案與現(xiàn)有方案的性能比較Tab.1 Performance comparisons of the scheme with existing schemes

5結(jié)語(yǔ)

文中基于動(dòng)態(tài)多密鑰共享協(xié)議提出了參與者有權(quán)重的門限多密鑰托管方案。方案中密鑰分發(fā)者可以根據(jù)密鑰的重要性動(dòng)態(tài)調(diào)整門限值，而且可以根據(jù)密鑰托管者的等級(jí)調(diào)整權(quán)重值，當(dāng)權(quán)限值相同時(shí)，方案可退化為普通的門限托管方案。該方案還可以防止密鑰分發(fā)者與托管代理的欺詐，特別是雙線性對(duì)的運(yùn)用，方案可以在不增加信息交互的情況下傳遞參數(shù)，降低了通信開銷，具有良好的前向保密性。因此，文中提出的密鑰托管方案具有良好的應(yīng)用前景。

［1］楊捷，李繼國(guó).基于密鑰協(xié)商的門限多秘密共享方案［J］.計(jì)算機(jī)工程，2010，36(20):153-154.

YANG Jie，LI Jiguo.Threshold multi-secret sharing scheme based on key agreement［J］.Computer Engineering，2010，36(20):153-154.(in Chinese)

［2］喬曉林，張建中.一種動(dòng)態(tài)門限多組秘密共享方案［J］.計(jì)算機(jī)工程，2010，36(22):143-146.

QIAO Xiaolin，ZHANG Jianzhong.Dynamic threshold multi-group-secret sharing scheme［J］.Computer Engineering，2010，36(22):143-146.(in Chinese)

［3］周孟創(chuàng)，余昭平.一個(gè)無(wú)可信中心的動(dòng)態(tài)(t，n)門限密鑰共享方案［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(8):3061-3063.

ZHOU Mengchuang，YU Zhaoping.Dynamic(t，n)threshold key sharing scheme without trusted party［J］.Application Research of Computers，2011，28(8):3061-3063.(in Chinese)

［4］黃偉達(dá)，姚國(guó)祥，沈瑞雪.基于雙線性對(duì)的動(dòng)態(tài)門限多秘密共享方案［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33(3):901-905.

HUANG Weida，YAO Guoxiang，SHEN Ruixue.Dynamic threshold multi-secret sharing scheme based on bilinear pairing［J］.Computer Engineering and Design，2012，33(3):901-905.(in Chinese)

［5］龐遼軍，裴慶祺，王育民，等.基于ID的門限多重秘密共享方案［J］.軟件學(xué)報(bào)，2008，19(10):2739-2745.

PANG Liaojun，PEI Qingqi，WANG Yumin，et al.An identity(ID)-based threshold multi-secret sharing scheme［J］.Journal of Software，2008，19(10):2739-2745.(in Chinese)

［6］王偉，周順先.參與者有權(quán)重的多重秘密共享方案［J］.計(jì)算機(jī)應(yīng)用，2010，30(12):3334-3336.

WANG Wei，ZHOU Shunxian.Multi-secret sharing scheme among weighted participants［J］.Journal of Computer Applications，2010，30(12):3334-3336.(in Chinese)

［7］Yoo Seongmin，Park Pyungkoo，Ryou Jaecheol，et al.Key sharing scheme based on one weighted threshold secret sharing［C］//Advanced Communication Technology(ICACT).Pyeongchang:IEEE，2013.

［8］邵春雨，蘇錦海.基于組合公鑰的用戶公鑰認(rèn)證算法［J］.計(jì)算機(jī)工程，2011，37(4):145-146.

SHAO Chunyu，SU Jinhai.User public key authentication algorithm based on combined public key［J］.Computer Engineering，2011，37(4):145-146.(in Chinese)

［9］國(guó)家密碼管理局.GM/T 0003.1—2012.SM2橢圓曲線公鑰密碼算法［S］.北京:國(guó)家標(biāo)準(zhǔn)出版社，2012.

［10］喬曉林，張建中.基于ECC的多組織間的多級(jí)秘密共享方案［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(20):56-57.

QIAO Xiaolin，ZHANG Jianzhong.Multi-stage secret sharing scheme among multiple organizations based in ECC［J］.Computer Engineering and Applications，2011，47(20):56-57.(in Chinese)

［11］luksan L，Matonoha C，Vlcek J.On lagrange multipliers of trust region subproblems［J］.Bit Numerical Mathematics，2008，48(4):763-768.

［12］孫榮燕，蔡昌曙，周洲，等.國(guó)密SM2數(shù)字簽名算法與ECDSA算法對(duì)比分析研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2013(2):60-62.

SUN Rongyan，CAI Changshu，ZHOU Zhou，et al.The comparision between digital signature based on SM2 and ECDSA［J］.Network Security Technology and Application，2013(2):60-62.(in Chinese)

［13］張建中，張艷麗.一個(gè)雙線性對(duì)上公開可驗(yàn)證多秘密共享方案［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(25):82-84.

ZHANG Jianzhong，ZHANG Yanli.Public verifiable multi-secret sharing scheme on bilinear pairing［J］.Computer Engineering and Applications，2011，47(25):82-84.(in Chinese)

［14］張永，張歡.基于橢圓曲線的密鑰共享方案［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50(8):90-92.

ZHANG Yong，ZHANG Huan.Secret sharing scheme based on elliptic curve［J］.Computer Engineering and Applications，2014，50(8):90-92.(in Chinese)

［15］Manik Lal Das.A key escrow-free identity-based signature scheme without using secure channel［J］.Cryptologia，2010，35(1):58-72.