基于改進的動態密鑰托管方案的研究及其應用

李 林，李志華

（江南大學 物聯網工程學院 計算機科學系，江蘇 無錫214122）

0 引 言

Nechvatal提出了門限密鑰托管概念。針對此國內外眾多學者進行了深入研究與探討［1－6］。目前提出的密鑰托管方案要么需要維持安全的通信信道，要么存在過大的計算與存儲開銷，要么過于依賴可信的密鑰管理中心 （key management center，KMC），要么存在逃避托管、篡改與無法驗證的問題。本文通過引入相對于RSA、ElGamal體制更具有優勢的ECC加密體制［7］，設計了改進的動態密鑰分發協議，同時將密鑰分發協議與組合公鑰 （combined public key，CPK）密碼體制相結合，應用到動態密鑰托管方案中，從而加快了密鑰份額驗證過程，節省了計算與存儲開銷，解決了逃避托管和篡改的問題，具有良好的動態性和安全性，效率比較高。

1 動態密鑰分發協議的改進

本文對KMC 權力進行限制，提出了改進的基于橢圓曲線密碼體制的動態密鑰分發 （ECC－based improved dynamic key distribution，EIDKD）協議，有效防止了KMC的被攻破與欺詐。

EIDKD 協議描述如下：

步驟1 分發者隨機選取密鑰s′∈Z＊P作為自己的部分私鑰，并計算y＝s′G，最后將y傳遞給KMC，秘密保存s′；

步驟2 KMC隨機選取d，s″∈Z＊P，計算

將（P，g，Y）公開，并將（y1，y2）傳遞給分發者；

步驟3 分發者利用接收到的（y1，y2）恢復出s″＝y2－s′y1，然后計算

若S ＝0則重新注冊，否則將S 作為托管私鑰，并作下列操作：

（1）分發者隨機選取aj（j＝1，…，k－1）構造G（FP）上的k－1次多項式

其中，令a0＝S，并計算Aj＝ajG（j＝0，…，k－1），公開Aj，aj銷毀；

（2）分發者獲取托管代理的身份，計算xi＝F（Ii）（i＝1，…，n），并隨機選取α∈GF（p），計算si＝xiG 作為托管代理的托管屏蔽子密鑰，并計算

將si利用Hi的公鑰加密后傳遞給Hi，公開α及有序數組（y1，…，yn）與（l1，…，ln）。

（3）分發者對每一個合格子集Fi＝｛Hi1，…，Hik｝，A由（0，S）及（Ii1，F（Ii1）），…，（Iik，F（Iik））利用Lagrange插值多項式［8］構造出k次多項式

計算并公開Fi（α）。

EIDKD 協議時間復雜度描述如下：在素域FP中加法運算、減法運算及小系數乘法運算的速度比乘法和求逆運算要快的多，為簡單起見，這幾種運算時間可以忽略不計。在仿射坐標A 下，M 表示乘法運算，I表示求逆運算，S表示平方運算，通常他們的計算時間有如下的等價關系［9］：I＝6 M，S ＝0.8 M。設k 的比特數為l，k 的Hamming 重量為w ≈。設點加時間復雜度為TEA，倍點時間復雜度為TD＝TEA，則k倍點運算時間復雜度TEM為

而門限密鑰共享算法的時間復雜度為O（nt－1），hash函數的時間復雜度為TH。因此EIDKD 協議的時間復雜度為（n＋k＋4）TEM＋3TEA＋2nTH＋o（nt－1）。

2 基于改進動態分發協議的密鑰托管方案

為了更好地闡述本方案，本文作如下形式化定義，假設一個密鑰托管系統用五元組＜ ｛U｝，｛H｝，｛W｝，｛KMC｝，｛V｝＞描述如下：

其中：＃ ｛W｝、＃ ｛KMC｝可能不是1，｛V｝指可信的第三方承擔公開驗證功能，是可選的；各集合元素之間通過交互式或非交互式協議相聯系；密鑰管理中心｛KMC｝，負責為用戶頒發證書以及與密鑰分發者共同生成托管私鑰；用戶集合 ｛U｝，假設其中要進行密鑰托管的用戶設為A，其私鑰設為S；托管代理 ｛H｝，由Hi（i ＝1，…，n）組成，被授權進行用戶密鑰的托管工作；監聽服務器｛W｝，經必要授權可以與｛H｝，｛KMC｝，｛V｝等執行相應的協議達到監聽用戶通信的目的。

基于改進動態密鑰分發協議的密鑰托管 （EIDKDbased key escrow scheme，EKES）方案描述如下。

2.1 托管代理初始化

本文在文獻 ［10］的基礎上利用基于ECC 的CPK 密碼體制進行下列操作完成托管代理的初始化工作：

（1）KMC選取r∈Zq，則對應的公鑰PK為橢圓曲線E上一點rG ＝（Xr，Yr）；

（2）KMC由整數矢量rij生成私鑰種子SSK，對應的公鑰種子矩陣PSK 由對應的點矢量rijG ＝（xij，yij）構成，KMC 秘密保存SSK，并公開PSK；

（3）KMC對Ii（i＝1，…，n）給定的序列IDIi∈｛0，1｝（設序列位數為h） 作行映射，將h 個映射函數Fk（x）（Fk（x）為hash函數）分別作用于IDIi，有

其中，mapk對應SSK 中的第k列中的第mapk個值，設為rmapkh。因此私鑰為

KMC將skIi秘密的分發給初始化的密鑰托管代理Ii，并公開參與初始化的密鑰托管代理給定的IDIi；

（4）Ii根據KMC公開的PSK 利用公開的公鑰算法類似的計算

每個密鑰托管代理均可以通過計算獲得彼此的公鑰。

2.2 EKES方案的設計

EKES方案由密鑰分發、子密鑰份額驗證、證書頒發、密鑰恢復等組成，共同完成托管密鑰的秘密共享與安全恢復。

2.2.1 密鑰分發階段

密鑰分發階段用戶A 利用EIDKD 協議完成用戶托管密鑰的生成以及托管子密鑰的分發。

2.2.2 子密鑰份額驗證

托管代理Hi（i＝1，…，n）收到s′i后解密得到的子密鑰份額si，通過驗證等式 （10）檢驗正確性

若式 （9）成立，則托管代理收到的密鑰份額是正確的，否則認定是不真實的。

當Fi中的每個托管代理驗證收到的密鑰份額通過后，計算簽名：ss＝sigHi（h（IDA，gij，zij＝h（sij＋α）Gmodp）），并將（IDA，gij，zij，ss）傳遞給KMC。

2.2.3 證書頒發

密鑰管理中心KMC收到每個托管代理的（IDA，gij，zij，ss）后，驗證簽名和zij＝gijGmodp是否成立，若成立則可以確認接收的簽名有效，計算簽名sK＝sigKMC（h（IDA，G，p，Y）），為用戶A頒發證書C（A）＝（IDA，p，G，Y，sK），否則用戶A注冊失敗，認定用戶未誠實托管密鑰。

2.2.4 密鑰恢復

假設合格托管代理集合中的一個最小合格子集為Fi＝｛Hi1，…，Hik｝，則當Hi收到子集中的所有的屏蔽子密鑰后，計算gij并驗證式 （8），若成立則接收到的是有效份額，否則是無效信息并要求重新發送，從而F（Iij）＝lij＋gij也是有效的，且（Ii1，F（Ii1）），…，（Iik，F（Iik））及（α，Fi（α））為式 （5）上的k＋1個點。因此，每一個最小合格子集中的成員可以利用多項式插值重構出共享密鑰［11］

2.3 用戶間通信協議的設計

當用戶A、B使用EKES方案進行通信時，用戶B 獲取用戶A 的公鑰證書C（A）后，秘密選取KAB，l∈Z＊q（其中KAB作為用戶之間的會話密鑰加密消息），并向用戶A 發送｛E1（M，KAB），LEAF｝，其中

E1是一個標準對稱密鑰加密算法；E2是橢圓曲線公開密鑰加密算法，即

S（H（M，T））是B用橢圓曲線私鑰對H（M，T）的簽名。

用戶A 收到｛E1（M，KAB），LEAF｝后，計算KAB＝v－S·u，利用KAB解密出明文M ＝D（C，KAB），并求取H（M，T）。若H（M，T）滿足簽名方案，A 可以確認收到的M 是有效，開始通信。

2.4 監聽協議的設計

監聽服務器接收到監聽授權時，可以利用監聽協議對用戶通信內容進行有效監聽。

（1）監聽服務器 ｛W｝首先將授權證書和監聽到的LEAF分別出示給任意最小合格子集Fi中的每一個托管代理Hij，托管代理驗證證書的有效性與時效性后計算

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

（2）監聽服務器接收到LEAFHij后，驗證時效性及h（Qij，Iij，T）是否滿足簽名方案，若滿足，則監聽服務器認為托管代理誠實的出示了Qij，并計算

由KAB＝v－Q 恢復出KAB，再由KAB解密出通信明文M ＝D（C，KAB），最后驗證H（M，T）是否滿足簽名，若滿足則監聽服務器實現對用戶A 與B的通信監聽。

3 方案評價

3.1 安全性與動態性分析

本文提出的動態密鑰托管方案基于Shamir門限方案、單向hash函數和ECC密碼體制的安全性，分析如下：

（1）方案中的托管密鑰S由用戶與KMC共同產生，而非由用戶單獨產生或對密鑰管理中心絕對信任，用戶無法欺詐，避免閾下信道攻擊。方案中KMC驗證托管密鑰份額的有效性和真實性后生成用戶證書，有效避免用戶逃避托管。

（2）方案中用戶傳遞屏蔽子密鑰時，密鑰托管代理無法從si中恢復出子密鑰xi，攻擊者無法從公開參數Aj和G求出保密系數aj，因而aj是安全的，子密鑰xi是安全的。

（3）密鑰托管代理接收到屏蔽子密鑰si后，驗證式（10）是否成立，因為

通過上式推導可以得出只有托管代理Hi收到si確實是用戶傳送的，式 （10）才能成立，可以防止用戶對托管代理的欺詐。由于Hi接收到的是屏蔽子密鑰，無法對子密鑰xi進行篡改，可以防范外部攻擊者對合法托管代理的攻擊。

（4）在監聽階段，監聽服務器收到托管代理的LEAFHij后，驗證其是否來源于誠實的托管代理后，計算Q 與當次的會話密鑰KAB，而不是用戶的任何私鑰信息，且每次通信用戶B 都會隨機選取l，因此解決了 “一次監聽，永久監聽”的問題。

（5）若方案中用戶的托管密鑰需要定期更新，只需重新協商托管密鑰S′并利用新的α′（α≠α）和F′（x）更新有序數組，不必更換托管代理的托管子密鑰；若方案需要增加一個密鑰托管代理Hn＋1，即分配第n＋1 個子密鑰份額，設Hn＋1的身份為In＋1，KMC計算xn＋1＝F（In＋1）以及屏蔽子密鑰sn＋1，計算并公開yn＋1與ln＋1即可；若方案中某個密鑰托管代理Hi不可信或密鑰份額泄漏，只需回收該用戶身份Ii與托管私鑰以及將代理數n改為n－1即可。

3.2 性能分析

下面將本文的方案和文中代表方案進行比較：

表1中有關符號定義如下：

TMM：計算模乘所用的時間。

TEXP：計算模冪所用的時間。

TH：計算單向hash函數h所用的時間。

各計算量根據以下關系進行統計：TEXP≈240TMM；TMM相當于一次乘法與一次除法。

表1 方案的性能比較

從表1可以看出：①對于安全信道，本文方案基于橢圓曲線離散對數的難解性，不需維持安全秘密信道，減少了計算與通訊開銷；②對于安全性基礎，橢圓曲線密碼體制的單位比特強度以及離散對數問題的難解性都遠高于傳統的離散對數系統；③對于托管代理子密鑰的產生，本方案的托管密鑰通過托管代理的身份計算產生，實現了托管密鑰份額與托管代理的身份對應，便于托管子密鑰的安全認證以及防止欺騙；④本文的密鑰托管方案可以提供托管代理的身份認證，而方案 ［2］只能通過公告牌來公布有效的參與者；⑤對于時間復雜度，由于模冪運算遠遠大于倍點運算所用的時間，由表1看出本文所提方案的時間復雜度比其它方案低。

4 EKES方案在PCI－E密碼卡中的應用

在數據加密技術的應用中，硬件加密相比于軟件加密越來越成為人們關注的焦點，密碼卡以其獨特的物理安全性有著加密強度高、加密性能好、加密方式靈活等優點。作為密碼卡安全性設計的重要環節，密鑰管理的安全性決定了密碼卡的安全性，因此研究一套安全的密鑰托管方案對于密鑰管理的安全性有極其重要的作用。

4.1 PCI－E密碼卡硬件結構

密碼卡通過FPGA 的PCI－E 總線和主機連接，算法模塊和噪音芯片通過數據總線直接和FPGA 相連，FPGA 和ARM 模塊直接通過CPLD 隔離數據總線連接。包括：ARM 處理器模塊、FPGA、SM1密碼算法芯片、SM2密碼算法芯片、CPLD （復雜可編程邏輯器件），物理噪音發生器、電源調節器等。PCI－E密碼卡硬件結構如圖1所示。

4.2 托管代理初始化

圖1 PCI－E密碼卡硬件結構

在密碼卡設計中，托管代理Hi為一組原始初始化過的USBkey，每一個USBkey都有一串獨特的PID，PID 是在超級用戶狀態下利用代表身份的不超過51字節的種子通過PID 生成算法生成的，由于PID 的生成過程是不可逆的，保證了key的獨特性。

利用內置在USBkey內部的SPK 算法，在USBkey內生成身份公私鑰對存儲在key中，并將身份公鑰導入到密碼卡固定區域保存，KMC將（Ii，pkIi）公布。

4.3 主密鑰分發階段

主密鑰分發階段完成設備主密鑰的生成以及托管子密鑰的分發。

主密鑰分發階段描述如下：

步驟1 密碼卡隨機選取密鑰s′∈Zp并計算并傳遞y給KMC，秘密保存s′；

步驟2 KMC 隨機生成d，s″∈Zp，計算式 （1）、式（2）、式 （3）后將（P，g，Y）公開，并把（y1，y2）回傳給密碼卡；

步驟3 密碼卡恢復出s″，并計算S，若S ＝0則重新注冊，否則將S 作為密碼卡主密鑰，用密碼卡內的設備密鑰中的加密公鑰加密傳遞給KMC，并作下列操作：

（1）KMC隨機的選取aj構造G（FP）上的式 （5），計算并公開Aj，aj銷毀；

（2）插入初始化的USBkey，密碼卡獲取托管代理的身份，計算xi＝F（Ii），密碼卡隨機生成α，計算si＝xiG 作為托管代理的屏蔽子密鑰后，計算式 （6）、式 （7）、式 （8）后將si作為子密鑰份額利用pkIi加密后傳遞給Hi，然后公開α及有序數組（y1，…，yn）與（l1，…，ln）；

（3）KMC 對每一個合格子集Fi，由（Ii1，F（Ii1）），…，（Iik，F（Iik））及（0，S）利用Lagrange插值公式構造出k次多項式 （9），計算并公開Fi（α）。

4.4 子密鑰份額驗證

托管代理Hi收到si′后解密得到子密鑰份額si，驗證式 （10），若成立，則托管代理收到的密鑰份額正確，否則托管代理認定接收到的密鑰份額是不真實的。

當Fi中的每個托管代理驗證收到的密鑰份額通過后，計算簽名ss，并將（IDA，gij，zij，ss）傳遞給KMC。

4.5 證書頒發

KMC收到每個托管代理的（IDA，gij，zij，ss）后，驗證簽名和zij是否成立，若成立計算簽名sK，并為密碼卡頒發證書C（A）＝（IDA，p，G，Y，sK）。

4.6 主密鑰恢復

對任何一個最小合格子集Fi，KMC 匯集到Fi中所有成員的屏蔽子密鑰后，對每一個屏蔽子密鑰計算gij并驗證式 （8），若成立則接收到的是有效份額，F（Iij）成立，通過（α，Fi（α））及（Ii1，F（Ii1）），…，（Iik，F（Iik））k＋1 個點，利用式 （5）重構出主密鑰S′并導入到密碼卡中繼續后續操作。

4.7 PCI－E密碼卡的安全性能評價

PCI－E密碼卡中的密鑰均由安全芯片產生并保存在非易失性存儲器中，且均不能以明文的方式導出密碼卡，從源頭保證了密鑰的安全；密碼卡產生的主密鑰只能在卡內生成，掉電丟失，杜絕了主密鑰的泄露與外部竊取；密碼卡中的其它密鑰均由主密鑰加密存儲在密碼卡的flash中，保證了卡內密鑰的安全性；主密鑰的保存與恢復采用本文提出的動態密鑰托管方案分散給托管代理保存，保證了主密鑰較強的安全性與私密性，從而保證了密鑰管理與密碼卡較高的安全性。

5 結束語

本文基于改進的動態密鑰分發協議提出了門限密鑰托管方案，對每個托管子密鑰進行驗證而不會泄露子密鑰的信息，有效防止了用戶以及內部托管代理之間的互相欺騙。由于分發的密鑰由用戶與KMC 共同產生，有效避免了KMC欺詐和被攻破。特別是CPK 密碼體制的運用，可以簡化傳統方案中共享者之間以及共享者與密鑰管理中心、用戶之間的驗證過程，快速發現欺詐行為的發生。該方案還具有較強的安全性和動態性，可根據需要動態的刪減成員，給出了本方案在PCI－E 密碼卡密鑰管理設計中的應用實例。

［1］Shi Ruanhua，Zhong Hong，Huang Liusheng.A（t，n）－threshold verified multi－secret sharing scheme based on ECDLP ［C］／／SNPD，2007：9－13.

［2］ZHANG Wenjuan，ZHANG Jinhua.Security key escrow based on ElGamal cryptosystem ［J］.Software，2012，33 （6）：20－22 （in Chinese）. ［張文娟，張錦華.基于ElGamal密碼體制的安全密鑰托管方案 ［J］.軟件，2012，33 （6）：20－22.］

［3］YAN Hongbin，YUAN ding.Dynamic key escrow scheme to identity cheaters ［J］.Computer Engineering and Design，2008，29 （6）：1443－1445 （in Chinese）. ［閆鴻賓，袁丁.防欺詐的動態密鑰托管方案 ［J］.計算機工程與設計，2008，29（6）：1443－1445.］

［4］Qiang FAN.Key escrow scheme with the cooperation mechanism of multiple escrow agents ［J］.Przeglad Elektrotechniczny，2012：116－118.

［5］ZHANG Jiasheng，YANG Shiping.Intrusion－tolerant key distribution scheme based on RSA ［J］.Computer Engineering and Design，2009，30 （17）：3965－3968 （in Chinese）. ［張加勝，楊世平.基于RSA 的入侵容忍密鑰分發方案 ［J］.計算機工程與設計2009，30 （17）：3965－3968.］

［6］ZHOU Mengchuang.Dynamic（t，n）threshold sharing scheme without trusted party ［J］.Application Research of Computers，2011，28 （8）：3061－3063 （in Chinese）. ［周孟創.一個無可信中心的動態 （t，n）門限密鑰共享方案 ［J］.計算機應用研究2011，28 （8）：3061－3063.］

［7］MEI Ting.Research and development of the elliptic and hyper elliptic curve cryptosystem ［J］.Computer Engineering and Science，2007，29 （6）：10－14 （in Chinese）. ［梅挺.橢圓與超橢圓曲線密碼體制的研究與進展 ［J］.計算機工程與科學，2007，29 （6）：10－14.］

［8］luksan L，Matonoha C，Vlcek J.On lagrange multipliers of trustregion subproblems ［J］.Bit Numerical Mathematics，2008，48 （4）：763－768.

［9］GM／T 003.1－2012.Public key cryptographic algorithm SM2 based on elliptic curves－part1：General［S］ （in Chinese）.［GM／T 0003.1－2012.SM2橢圓曲線公鑰密碼算法 ［S］.］

［10］SHAO Chunyu，SU Jinhai.User public key authentication algorithm based on combined public key ［J］.Computer Engineering，2011，37 （4）：145－146 （in Chinese）. ［邵春雨，蘇錦海.基于組合公鑰的用戶公鑰認證算法 ［J］.計算機工程，2011，37 （4）：145－146.］

［11］ZHANG Yong，ZHANG Huan.Secret sharing scheme based on elliptic curve ［J］.Computer Engineering and Applications，2014，50 （8）：90－92 （in Chinese）. ［張永，張歡.基于橢圓曲線的密鑰共享方案 ［J］.計算機工程與應用，2014，50 （8）：90－92.］