托管者有權重的動態門限多重密鑰托管方案

李 林， 曹 瑀， 李志華*

(1.江南大學物聯網工程學院，江蘇無錫214122;2.大連理工大學軟件學院，遼寧大連116024)

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

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

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

1 方案初始化

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

1.1 系統參數初始化

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

1.2 托管代理初始化

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

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

2 動態多重密鑰共享協議

文中基于橢圓曲線密碼體制提出了動態的多密鑰共享(ECC-based dynamic multi-key sharing protocol，EDMSP)協議，包括多密鑰分發、子密鑰份額驗證、多密鑰重構等部分。

2.1 多密鑰的分發

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

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

2)MD隨機構造m個ti-1次多項式:

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

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

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

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

5)MD隨機選取bi0∈，計算

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

2.2 子密鑰份額驗證

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

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

2.3 多密鑰重構

2)DC將計算得到的ti個數值對(Iti，fi(Iti))利用拉格朗日多項式插值重構［11］，具體如下:

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

3 基于動態多重密鑰共享協議的密鑰托管方案

在密鑰托管方案中，{KMC}負責頒發證書，監聽服務器{W}，經必要授權可以與密鑰托管組P，{KMC}、密鑰合成者DC等執行相應的協議監聽用戶通信。

基于動態多密鑰共享協議的多密鑰托管方案(EDMSP-based key escrow scheme，EKES)描述如下。

3.1 證書頒發

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

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

3.2 通信協議的設計

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

其中:

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

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

3.3 監聽協議的設計

監聽服務器接收到合法的監聽授權時，利用監聽協議對監聽對象的通信內容進行有效監聽。

1)監聽服務器{W}首先將授權證書和監聽到的LEAF分別出示給任意合格托管組Pi中的每一個托管代理Iti，托管代理驗證證書的有效性與時效性后計算:

并將LEAFIti回傳給監聽服務器。

2)監聽服務器接收到LEAFIti后，驗證時效性及h(Qiti，Iti，T)是否滿足簽名方案。若滿足，則監聽服務器認為托管代理誠實出示了Qij，并計算:

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

4 方案分析和證明

4.1 正確性分析

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

證

證畢。

證

證畢。

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

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

4.2 安全性分析

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

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

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

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

4.3 性能分析

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

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

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

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

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

5)由于在密鑰分發階段，不同的密鑰組構造的曲線fi(x)以及選取的隨機整數ri0不同，由安全性證明可知，一組密鑰的重構不會影響其他托管組密鑰的安全性與重構。同時方案中托管代理的密鑰由用戶身份計算產生，因此在多組密鑰共享托管時，實現了托管密鑰與代理身份的對應認證，且各托管代理的密鑰以及影子份額可以重復利用。

表1列出了文中方案與其他方案的對比結果。

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

5結語

文中基于動態多密鑰共享協議提出了參與者有權重的門限多密鑰托管方案。方案中密鑰分發者可以根據密鑰的重要性動態調整門限值，而且可以根據密鑰托管者的等級調整權重值，當權限值相同時，方案可退化為普通的門限托管方案。該方案還可以防止密鑰分發者與托管代理的欺詐，特別是雙線性對的運用，方案可以在不增加信息交互的情況下傳遞參數，降低了通信開銷，具有良好的前向保密性。因此，文中提出的密鑰托管方案具有良好的應用前景。

［1］楊捷，李繼國.基于密鑰協商的門限多秘密共享方案［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］喬曉林，張建中.一種動態門限多組秘密共享方案［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］周孟創，余昭平.一個無可信中心的動態(t，n)門限密鑰共享方案［J］.計算機應用研究，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］黃偉達，姚國祥，沈瑞雪.基于雙線性對的動態門限多秘密共享方案［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］.軟件學報，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］王偉，周順先.參與者有權重的多重秘密共享方案［J］.計算機應用，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］邵春雨，蘇錦海.基于組合公鑰的用戶公鑰認證算法［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］國家密碼管理局.GM/T 0003.1—2012.SM2橢圓曲線公鑰密碼算法［S］.北京:國家標準出版社，2012.

［10］喬曉林，張建中.基于ECC的多組織間的多級秘密共享方案［J］.計算機工程與應用，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］孫榮燕，蔡昌曙，周洲，等.國密SM2數字簽名算法與ECDSA算法對比分析研究［J］.網絡安全技術與應用，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］張建中，張艷麗.一個雙線性對上公開可驗證多秘密共享方案［J］.計算機工程與應用，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］.計算機工程與應用，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.