一種關于SM9的安全密鑰分發方案

許盛偉 任雄鵬 袁 峰 郭春銳 楊 森

1(北京電子科技學院 北京 100070)2(西安電子科技大學通信工程學院 陜西 西安 710071)

0 引 言

根據認證用戶的公鑰形式的不同，可以將公鑰密碼體制分為四種：基于證書、基于身份、基于無證書、基于自認證的公鑰密碼體制[1]。隨著移動互聯網和通信技術的發展，基于身份的密碼體制的輕便易用性使其具有巨大的應用潛力。

1984年Shamir[2]首次提出基于身份的公鑰密碼體制的思想，直至2001年Boneh[3]提出第一個基于身份的加密算法。2007年12月國家密碼管理局組織專家完成了標識密碼算法的標準化工作，2008年確定了SM9密碼算法型號，2014年完成了SM9算法曲線的選定工作，2016年國家密碼管理局正式發布SM9為密碼行業標準算法[4]。2017年11月SM9標識簽名算法成為ISO/IEC國際標準[5]，2018年4月在ISO/IECJTC1/SC27國際網絡安全標準化工作會議上SM9標識加密算法、SM9密鑰協商協議獲得國際標準提案立項[6]，對于推動國產密碼算法在國際上的應用具有重大意義。由于IBC體制下用戶私鑰均由密鑰產生中心集中生成，導致了密鑰托管和私鑰安全分發問題，其安全性只達到了Girauit等[7]提出的Level1，這將嚴重阻礙其未來的發展。

針對身份密碼體制的密鑰托管和私鑰安全分發問題截止目前已有大量研究[8]。Sui等[9]基于雙線性對提出了可分離且匿名的標識私鑰分發方案，系統需要本地注冊中心LRA和KGC兩個責任主體，分發私鑰時不需要安全通道，任何竊聽者都無法知道申請私鑰者的身份，但該方案中存在消息完整性保護攻擊和潛在的KGC泄漏攻擊。文獻[10-11]針對上述問題分別基于雙線性對給出改進的私鑰分發方案。但是上述方案均未解決密鑰托管問題。Wang等[12]給出了關于BF-IBE的基于秘密共享的密鑰分發方案，將該方案應用于即時通信系統(IM系統)中，雖解決了密鑰托管問題，但面臨數據庫泄露攻擊和篡改攻擊。Pedersen等[13]提出了參與方可驗證且沒有秘密分發者的秘密共享方案。Gennaro等[14]指出Pedersen的方案不能保證生成密鑰的均勻隨機分布，提出了更為安全的分布式密鑰生成協議。Geisler等[15]提出了關于Sakai-Kasahara-IBE的分布式密鑰生成方案，其解決了密鑰托管問題，但是未提出安全的私鑰分發方案。文獻[16]利用可驗證的門限方案提出了標識私鑰共享方案只解決了密鑰托管問題。為同時較好地解決用戶私鑰安全分發與密鑰托管問題，文獻[17]提出了基于橢圓曲線密碼體制的動態密鑰分發協議，利用托管代理有效阻止用戶或密鑰管理中心的欺詐，但是其托管私鑰時利用了公鑰加密，計算代價較大。文獻[18]提出了新的用戶私鑰分發協議，但該協議中使用了影響效率的雙線性對運算。文獻[19]提出了一種有托管代理參與的IBC密鑰生成與托管方案，遺憾的是，該方案也使用了雙線性對運算，計算效率較低。目前經典的IBE體制主要包括三種類型[1]：Boneh-Franklin IBE、Sakai-Kasahara IBE和Boneh-Boyen IBE。由于SM9的密鑰產生算法不同于這三種密碼體制，目前還未有關于SM9的密鑰托管以及用戶私鑰分發的研究。

本文首先分析指出Wang等關于BF-IBE的密鑰分發方案未能滿足的抗數據庫泄露攻擊、篡改攻擊，同時考慮到Geisler等關于SK-IBE的密鑰產生方案未實現安全密鑰分發，針對SM9獨特的密鑰產生算法，通過改進并結合兩者，提出關于SM9的無對運算的可分離匿名分布式密鑰分發(SADKI)方案。該方案實現了SM9算法的用戶私鑰的安全高效分發，解決了密鑰托管問題。不僅具備抗KGC數據庫泄露攻擊、篡改攻擊、安全分布式密鑰生成、公共信道傳輸、抵抗離線口令破解、可分離、匿名等安全屬性，較前述方案還消除了雙線性對運算，具有較高的運算效率。

1 困難問題

1.1 ECDL困難問題

已知橢圓曲線E(Fqm)(m≥1)，階為n的點P∈E(Fqm)，Q屬于以P為生成元生成的循環群中即Q∈〈P〉。ECDL困難問題是指，給定P與Q，確定整數l∈[0,n-1]，使得Q=lP成立是困難的。

1.2 ECDH困難問題

已知橢圓曲線E(Fqm)(m≥1)，階為n的點P∈E(Fqm)，ECDH困難問題是指，給定aP與bP，計算abP是困難的。

2 Wang等[12]密鑰分發方案

2.1 方案描述

方案分為系統初始化和用戶注冊、私鑰分發三個步驟。

(1) 系統初始化。KGCs產生并公布系統參數(G1,G2,P,q,e,H0,H1,Pi)，其中(1≤i≤n)，Pi=siP是每個子密鑰產生中心的公鑰，si是子系統密鑰。

(2) 用戶注冊。用戶通過本地注冊中心LRA離線認證，從而獲得申請一次性口令pwd，同時元組(H0(ID),H0(pwd),H1(pwd))存儲在IM應用服務器的數據庫中，用來認證申請私鑰時的用戶身份。

IM服務器通過下式驗證用戶身份的有效性：

e(Q,T)=e(H0(ID),H0(pwd))e(Q,H0(pwd))H1(pwd),若成立，IM服務器對(H0(ID),wiP)進行BLS短簽名發送給PKGi。PKGi驗證簽名后保存元組(H0(ID),wiP)到數據庫中。

2.2 方案分析

經下述分析，該方案存在潛在的數據庫泄露攻擊與攻擊者的篡改攻擊。

(1) 數據庫泄露攻擊。若IM應用服務器數據庫發生泄露，攻擊者獲得(H0(ID),H0(pwd),H1(pwd))后，選取隨機數r和應用登錄口令pwd0然后計算Q、T、wi。按照方案流程，IM服務器和PKGi均能驗證相應等式成立，從而可以成功偽裝合法用戶得到私鑰。故該方案不能抗潛在的數據庫泄露攻擊。

3 關于SK-IBE的密鑰產生方案[15]

3.1 SK-IBE的密鑰產生算法

3.2 方案描述

文獻[15]利用了Shamir門限方案[20]和Cramer等[21-22]中的多方計算協議提出以下方案。

(1) Setup。借助Shamir(t,m)門限方案秘密共享系統私鑰x，設t-1次多項式為Q(X)∈Zq(X)且Q(0)=x，m臺服務器分別獲得x的秘密共享值xi=Q(i)并秘密保存，其中1≤i≤m。每個服務端計算Ri=xiP1并公開(i,Ri)。

(2) Extract(ID)。假設n個服務端是在線的，分別執行下面的協議：

① 服務端分別自行計算zi=xi+H(ID)，該值為z=x+H(ID)的秘密共享值。

② 服務端通過Shamir門限方案分別獲得隨機數r的共享值ri。

③ 服務端各自調用Cramer等的多方計算協議并公布si，該值是s=zr(modq)的共享值。

④ 服務端利用公布的si恢復出s。

⑤ 服務端自行計算并秘密保存wi=ris-1(modq)。

通過下式恢復用戶私鑰:

(1)

式中：

(2)

注意：只有滿足n≥2t才能恢復秘密值，因為該方案中在Extract(ID)階段需要調用多方計算協議。

4 關于SM9的SADKI方案

4.1 SM9密鑰產生算法

(1) 系統參數組。系統參數組包括階為素數N的加法循環群G1、G2，生成元分別為P1、P2；密碼雜湊函數H()，密碼函數H1(Z,n)，該函數需要調用H()，輸入為比特串Z和整數n，輸出為整數∈[1,n-1]，還有其他系統參數詳見文獻[23]。

(2) 密鑰產生。KGC產生隨機數ke∈[1,N-1]作為主密鑰，計算G1中的元素Ppub-e=ke×P1作為加密主公鑰，則加密主密鑰對為(ke,Ppub-e)。KGC秘密保存ke，公開Ppub-e。KGC選擇并公開用一個字節標識的加密私鑰生成函數識別符hid。

4.2 SADKI方案

方案涉及符號總結于表1。

表1 符號說明

下面介紹方案的具體通信過程：

用戶A在本地注冊機構進行離線認證后獲得一次性口令pwd，并且LRA將[HID,H(pwd)P1]安全存儲到KGCi的待定私鑰數據庫中。

(2) User→KGC。用戶獲得口令pwd后選擇隨機數r，計算U=rP2，H(pwd)Ppubi，防止申請報文篡改，需要計算M=H(HID,U,H(pwd)Ppubi)，最后發送HID，U，M給KGCi。

(3) KGC→User。KGCi收到H′ID、U′、M′后，將H′ID作為索引尋找對應的H(pwd)P1，計算keiH(pwd)P1并判斷M′=H(H′ID,U′,keiH(pwd)P1)是否成立從而驗證消息的有效性。若成立，則KGCi依次執行下面方案：

①KGCi計算zi=keiH′ID+1，其值是z=ke-1H′ID+1的共享值。

②KGCi利用Shamir門限方案獲得隨機數R的共享值Ri。

③KGCi各自調用Cramer等的多方協議計算si，該值是s=zR(modN)的共享值。

④KGCi分別公布si，從而計算s。

⑤KGCi自行計算并秘密保存wi=Ris-1(modN)。

⑥KGCi計算σi=wiU′和M1=H(σi,keiH(pwd)P1)并發送給用戶。

(4) 提取私鑰。用戶接受到σ′i和M′1后，判斷M′1=H(σ′i,H(pwd)Ppubi)是否成立從而驗證消息的有效性，若成立，計算c′ir-1σ′i，用戶接收到KGCi的n個有效回復(2t≤n≤m)后，計算下式得到用戶私鑰deA：

(3)

最后，用戶申請成功后，可以刪除數據庫中的元組〈HID,H(pwd)P1〉，這樣數據庫中只保留待定發布私鑰的元組，避免增長到傳統PKI證書庫的巨大規模。一次性口令也會失效，避免非法用戶得到口令后重新申請私鑰的泄露風險。

5 正確性分析

KGCi收到用戶發來申請私鑰的消息后，由于H(pwd)Ppubi=keiH(pwd)P1，故KGCi通過H(HID,U,H(pwd)Ppubi)=H(H′ID,U′,keiH(pwd)P1)可以驗證消息有效性。

下面證明KGCi需秘密共享的z值為ke-1HID+1，依據SM9私鑰產生算法有：

ke×(HID+ke)-1(modN)P2=

(ke-1HID+ke-1×ke)-1(modN)P2=

(ke-1HID+1)-1(modN)P2=

z-1(modN)P2

(4)

可知須改進Geisler等方案中的z值為ke-1HID+1。

下面證明zi=keiHID+1是z的共享值：

(5)

從而可知各個zi是z的共享值。

Rs-1P2=RR-1z-1P2=z-1P2=deA

(6)

從而用戶私鑰可以被正確恢復。

6 安全性和效率分析

6.1 安全性分析

(1) 不需要安全通道。即使敵手輕易截獲傳輸通道中的消息σi、U，想要得到私鑰前需計算r-1σi，由于r是用戶選取的隨機值，只能從U=rP2計算得到r，這是一個ECDL離散對數困難問題，從而只有掌握隨機值r的合法者才能得到私鑰，因此密鑰分發中可以在公共信道傳輸。

(2) 完整性保護。在用戶發送給KGC的消息HID、U、M中，若三者任意篡改，那么KGC可以立刻判斷出消息的有效性。故M為HID、U提供了完整性保護，保證KGC按照方案生成正確的私鑰，從而使合法請求者可以得到私鑰。

(3) 抵抗潛在KGC泄露攻擊。若存在某個KGC的數據庫泄露，非法用戶得到〈HID,H(pwd)P1〉后，需要偽造HID、U、M才可偽裝成其他用戶申請私鑰，但若想成功偽造M需要計算H(pwd)Ppubi，已知H(pwd)P1、Ppubi計算出H(pwd)Ppubi是一個ECDH困難問題。故該方案可以抵抗潛在KGC數據庫泄露攻擊。

(4) 分布式密鑰產生。由于用戶的私鑰由多方KGC合作生成，解決了單一KGC的密鑰托管問題和部分KGC不誠實問題。由于本方案用戶私鑰產生方案與文獻[15]類似，由該文中安全性分析可知本方案分布式密鑰產生具有安全性。

(5) 可分離。可分離性繼承自文獻[9]的方案。類似于基于證書的PKI系統，認證和證書生成的工作是分離的，分別由RA和CA負責。在本方案中，LRA負責申請私鑰的用戶身份認證，KGC僅僅驗證請求的有效性并負責私鑰分發工作。

(6) 匿名性。傳輸的消息與KGC數據庫中的數據均以H1(IDA‖hid,N)形式存在，所以敵手和KGC不會知道用戶的真實身份，從而敵手和KGC不會知道是哪個用戶成功請求到了私鑰。

(7) 抵抗離線口令破解。由于每個用戶擁有獨一無二的一次性口令并秘密保存，用戶成功申請到私鑰后，口令將會失效，所以即使非法用戶竊取到申請報文并成功離線破解口令，此時口令也已失效。

6.2 效率分析

與文獻[16-18]方案相比，本文方案不僅實現了SM9密碼算法私鑰的分布式密鑰產生，具備了抵抗KGC泄露攻擊等更強的安全屬性，更大的優勢在于無需雙線性對運算。用戶端需花費n+2個點乘運算，每個KGC只需2個點乘。由于橢圓曲線中對運算是點乘運算時間的20倍[22]左右，所以運算效率大大提高。

如表2所示P代表雙線性對運算，S代表橢圓曲線上的點乘運算，文獻[16]方案只解決密鑰托管問題，同時該過程需要安全通道秘密傳輸，并且服務端利用了雙線性對運算，效率較低；文獻[17]方案中雖解決了密鑰分發與密鑰托管問題，但是密鑰托管時需要安全通道傳輸，而且服務端計算代價較大；文獻[18]方案中安全性與本文方案相同，用戶端計算量比本文較有優勢，但是服務端利用了雙線性對運算，計算效率較低；文獻[9-12]的方案中用戶端計算量至少需要2P+3S，這相當于43個點乘運算，服務端至少需要1P+1S，只有當KGC數量n≥41時本文方案用戶端運算量才不小于其他方案。所以本方案不僅安全性具有優勢，計算效率也得到很大提高；由于本文分布式密鑰產生方法基于文獻[15]方案，故與該方案的運算量相當，但是本文方案具有用戶密鑰安全分發的優勢。

表2 本文方案與其他文獻方案安全性和效率對比

7 結 語

移動互聯網和通信技術的發展為國際標準SM9密碼算法帶來了廣泛的應用前景。針對SM9天生的密鑰托管局限性，本文指出文獻[12]方案的攻擊缺陷問題，基于SM9特有的密鑰產生方法，改進該密鑰分發方案和文獻[15]密鑰產生方案，提出了SM9的分布式私鑰產生方案，實現了無雙線性對的密鑰分發，減少了計算量，提高了安全性。最終分析表明該方案在安全性和效率方面均具有優勢。