無需配對的無證書門限簽名方案

楊鄧奇，楊 健

（大理學(xué)院數(shù)學(xué)與計算機(jī)學(xué)院，云南大理 671003）

Client/Server計算模式中，服務(wù)器通?？梢宰鳛樽C書管理中心，負(fù)責(zé)系統(tǒng)中公鑰證書的管理工作，同時亦可作為簽名者一些重要的消息提供簽名服務(wù)，如身份分配、令牌發(fā)布時所需消息的簽名等。然而，一方面，在純分布式系統(tǒng)中找到一個可靠的節(jié)點作為中心服務(wù)器來管理數(shù)字證書、提供簽名服務(wù)是個困難的問題；另一方面，當(dāng)系統(tǒng)規(guī)模較大時，由單一的服務(wù)器提供簽名服務(wù)可能導(dǎo)致系統(tǒng)瓶頸的產(chǎn)生。因此，有學(xué)者提出基于秘密共享技術(shù)的門限簽名方案〔1-7〕，由多個節(jié)點共同為一些重要消息提供簽名服務(wù)?，F(xiàn)有的門限簽名方案可以分為3 類：①基于PKI 的門限簽名技術(shù)；②基于身份密碼系統(tǒng)（IBC）〔8〕的門限簽名技術(shù)〔1〕；③基于無證書公鑰密碼系統(tǒng)（CL-PKC）〔9〕的門限簽名技術(shù)。但是，基于PKI技術(shù)的門限簽名技術(shù)需要進(jìn)行復(fù)雜的證書管理，導(dǎo)致系統(tǒng)效率低下；基于IBC 的門限簽名方案存在密鑰托管問題；基于CL-PKC 的門限簽名方案克服了PKI 方案和IBC 方案中的效率和安全問題，具有更高的效率和更好的安全性?，F(xiàn)有的無證書簽名方案主要是基于雙線性對映射〔10〕設(shè)計，雙線性對運算是個非常耗時的操作〔11〕。因此，基于雙線性對的無證書門限簽名方案的效率較低。

本文基于無信賴者的秘密共享技術(shù)和無雙線性對無證書密碼系統(tǒng)，設(shè)計無證書門限簽名方案。方案安全性基于橢圓曲線離散對數(shù)問題（ECDLP）〔11〕，方案涉及主要運算為有限域上橢圓曲線標(biāo)量乘法（即點乘運算）。該門限簽名方案消除了基于CLPKC門限簽名方案中耗時的雙線性對運算，且不依賴可信中心來分發(fā)秘密共享技術(shù)中子密鑰。分析表明，該方案具有更好的安全性和效率。

1 預(yù)備知識

無證書密碼系統(tǒng)中存在一個密鑰生成中心（KGC）參與用戶私鑰的生成。系統(tǒng)中，每個用戶均有一個唯一用戶身份標(biāo)識（ID）；用戶私鑰均由兩個部分構(gòu)成，即KGC為其生成的部分私鑰和用戶自主選擇的秘密值兩部分。只有同時掌握部分私鑰和用戶秘密值，才能進(jìn)行密碼學(xué)的相關(guān)運算。

通用的無需配對的無證書簽名方案包括以下7個算法：

1）Setup 算法：由KGC運行該算法，算法生成系統(tǒng)公開參數(shù)params 和系統(tǒng)主密鑰s，即（params，s）=Setup（）。

2）PartialKeyExtract 算法：由 KGC 運行該算法，算法輸入?yún)?shù)params，主密鑰s和用戶ID，輸出用戶部分私鑰DID和對應(yīng)的部分公鑰PID，即（PID，DID）=PartialKeyExtract（params，s，ID）。

3）SetSecretValue 算法：由用戶運行該算法，算法輸入?yún)?shù)params和用戶ID，輸出用戶自主生成的秘密值xID，即xID=SetSecretValue（params，ID）。

4）SetPrivateKey 算法：由用戶運行該算法，算法輸入?yún)?shù)params，用戶部分私鑰DID和用戶秘密值xID，輸出用戶私鑰 SKID，SKID=SetPrivateKey（params，DID，xID）。

5）SetPublicKey 算法：由用戶運行該算法，算法輸入?yún)?shù)params，用戶部分公鑰PID，用戶部分私鑰xID和用戶ID，輸出用戶公鑰PKID，即PKID=SetPublicKey（prarms，PID，xID，ID）。

6）Sign算法：由簽名用戶運行該算法，算法輸入?yún)?shù)params，用戶私鑰SKID，用戶ID 和消息m，輸出簽名σ，即σ=Sign（params，SKID，ID，m）。

7）Verify算法：由驗證簽名的用戶運行該算法，算法輸入?yún)?shù)params，用戶公鑰PKID，用戶ID 和簽名σ，輸出驗證結(jié)果“Accept”或“Reject”。

2 無需配對的無證書門限簽名方案

本文考慮系統(tǒng)中沒有可信中心服務(wù)器的純分布式網(wǎng)絡(luò)環(huán)境的門限簽名技術(shù)。因系統(tǒng)中沒有可信第三方，主密鑰不能由單個節(jié)點掌握，秘密共享技術(shù)中打造和分發(fā)主密鑰的子密鑰（后稱子主密鑰）也不能由單個節(jié)點負(fù)責(zé)，即要求系統(tǒng)中沒有任何節(jié)點單獨掌握系統(tǒng)主密鑰。因此，首選需要在系統(tǒng)中挑選若干個節(jié)點來共同協(xié)商系統(tǒng)的主密鑰并為系統(tǒng)中的重要消息提供多節(jié)點共同簽名服務(wù)。記選中的節(jié)點為SN，假設(shè)選擇了n個節(jié)點，記為SNi（i=1，2，…，n），節(jié)點SNi對應(yīng)的ID 記為設(shè)計無證書簽名方案如下。

2.1 SN 初始化初始化階段n個SN 節(jié)點協(xié)商系統(tǒng)公開參數(shù) ＜p，q，G，P，P0，H1，H2＞，其中p，q為2 個素數(shù)，使得q|p-1；P是安全橢圓曲線上循環(huán)加法群的一個生成元；q是P的階；H1:{0，1}*×G×G |→Zq*，H2:{0，1}*|→Zq*為兩個哈希函數(shù)；P0為系統(tǒng)公開密鑰，由n個SN節(jié)點按照下列方式協(xié)商生成：

1）SNi（i=1，2，…，n）隨機(jī)選擇一個秘密值bi∈GF（p）和一個t-1次多項式fi（x）：fi(x)=ai,0+ai,1x+…+ai,t-1xt-1modp，ai，j∈GF（p）（j=0，1，…，t-1），s.t.fi（0）=ai，0=bi，計算Bi，k=ai，kP（k=0，1，…，t-1）并將其發(fā)送給其他n-1個SN節(jié)點。

2）SNi（i=1，2，…，n）節(jié)點將其他n-1 個節(jié)點的ID 代入多項式，計算fi(IDSNj) 并將其通過安全信道發(fā)送給SNj（j=1，2，…n，j≠i）。

3）SNj收到來自其他n-1 個SNi（i=1，2，…n，i≠j）節(jié)點計算的fi(IDSNj)后，通過（1）式驗證：

如果（1）成立，則fi(IDSNj) 是有效的，否則是無效的。

4）當(dāng)SNi（i=1，2，…，n）收到所有來自其他n-1個SN 節(jié)點的fj(IDSNi)（j=1，2，…，n，j≠i）并驗證其有效性后，計算并將其廣播給其他n-1個SN節(jié)點。

5）SNi（i=1，2，…，n）收到來自其他n-1 個 SN節(jié)點的后，計算其 中令s=即為系統(tǒng)私鑰，稱為主密鑰。P0=sP為系統(tǒng)公鑰。令則si為SNi（i=1，2，…，n）所掌握的主密鑰的子密鑰，即子主密鑰，需要保密。

2.2 SN 密鑰生成在這個階段，節(jié)點 SNi（i=1，2，…，n）生成自己的公私鑰對。

1）SNi（i=1，2，…，n）隨機(jī)選擇秘密值，計算公鑰Xi=xiP，Ri=riLiP，并將 ＜IDBNi,Ri,Xi＞發(fā)送給SNj（j=1，2，…，n，j≠i）。

2）SNi（i=1，2，…，n）收到來自其他n-1個節(jié)點的后，計算設(shè) 置 SNi的 公鑰即為，私鑰為

2.3 簽名與驗證

2.3.1 簽名 假設(shè)用戶A 需要對消息m進(jìn)行簽名，它首先從n個SN節(jié)點中選擇t個，并告知每個SN節(jié)點它所選擇t個SN 節(jié)點的ID 字符串，即廣播給t個SN節(jié)點。然后將消息m發(fā) 送 給 簽 名 節(jié) 點 SN1，SN2，…，SNt。 SNi（i=1，2，…，t）收到用戶A 關(guān)于消息m的簽名請求后，完成以下操作：

1）SNi隨機(jī)選擇計算Ti=aiP，并發(fā)送元組給SNj（j=1，2，…，t，j≠i）。

2）SNi收到來自其他t-1個SNj（j=1，2，…，t，j≠i）節(jié)點的所有元組后，計算σi=aie+γ(xi+DiLi)，生成消息m的子簽名（σi，γ，Ti）并將其發(fā)送給用戶A（此處，R和X可以通過預(yù)計算的方式以提高簽名效率）。

2.3.2 驗證 用戶A收到來自t個SN節(jié)點的子簽名（σi，γ，Ti）（i=1，2，…，t）后，計算Qi=σie-1?P-并驗證Qi=Ti是否成立，若成立，則接受σi；否則拒絕σi并請求SNi重簽。

驗證過程證明：

若所有σi（i=1，2，…，t）均通過驗證，則用戶A計算即為節(jié)點SN1，SN2，…，SNt對消息m的聯(lián)合簽名。

若系統(tǒng)中另一用戶B 要對A 發(fā)送的帶有SN 節(jié)點簽名的消息m進(jìn)行驗證，則A 發(fā)送元組＜σ，γ，T，ID＞，其過程如下：

Q=σe-1?P-γXe-1-γRe-1-γH1(ID,Rˉ,Xˉ)e-1?P0，并 判斷H1(ID,Q,X)=γ是否成立，若成立，則接受簽名σ；否則拒絕簽名σ。

驗證過程的正確性證明:

所以H1(ID,Q,X)=H1(ID,T,X)=γ。

3 安全與性能

3.1 安全性分析目前CL-PKC安全模型通?？紤]兩種類型的攻擊：公鑰置換攻擊和主密鑰攻擊。在CL-PKC中，節(jié)點公鑰為PK=＜X，R＞，私鑰為SK=＜x，D＞，其中D=r+sH1（ID，R，X）為部分私鑰。

1）公鑰置換攻擊

在公鑰置換攻擊中，攻擊者可以置換用戶的公鑰，但不知道系統(tǒng)主密鑰。在CL-PKC 中，用戶私鑰SK 與用戶秘密值x、隨機(jī)數(shù)r、用戶身份標(biāo)識ID和系統(tǒng)主密鑰s相關(guān)。因為，攻擊者不知道系統(tǒng)主密鑰s，系統(tǒng)主密鑰s參與部分私鑰生成的計算是CL-PKC密碼系統(tǒng)抵抗公鑰置換攻擊的基礎(chǔ)。為方便起見，假設(shè)系統(tǒng)中的簽名者為SNA，其發(fā)送＜IDA，PKA，m，Sign（m，SKA）＞ 給用戶B。 用戶 B 可以利用SNA的公鑰PKA，身份標(biāo)識IDA和系統(tǒng)公開參數(shù)params 來驗證SNA的簽名。如果攻擊者C 要假冒簽名者SNA的身份偽造簽名，則攻擊者C 選擇秘密值x′A，隨機(jī)數(shù)r′A，計算X′A=x′AP，R′A=r′AP，并用PK′A=＜X′A，R′A＞置換 PKA。然后攻擊者 C 發(fā)送＜IDA，PK′A，m，Sign′（m，SKA）＞ 給用戶B。假設(shè)簽名算法是不可偽造的，則攻擊者C 要生成一個能被PK′A驗證的簽名，則 C 必須掌握 PK′A對應(yīng)的私鑰SK′A。但是 SK′A=＜x′A，D′A＞，D′A=r′A+sH1（IDA，RA，X′A）。攻擊者C 不知道系統(tǒng)主密鑰s，因此，它無法計算部分私鑰D′A。所以攻擊者C 無法偽造一個有效的簽名。

2）主密鑰攻擊

主密鑰攻擊中攻擊者掌握系統(tǒng)主密鑰，但不能置換用戶公鑰。如果攻擊者C 要假冒SNA的身份偽造簽名，它必須知道SNA公鑰PKA對應(yīng)的完整私鑰SKA=＜xA，DA＞。但是因為攻擊者C不能替換SNA的公鑰，也無法知道SNA選擇的秘密值xA，所以攻擊者C 無法獲取SNA完整的私鑰，無法偽造有效的簽名。

3）抗KGC主動攻擊和共謀

文獻(xiàn)〔8〕指出，CL-PKC 中，如果 KGC 發(fā)動主動攻擊（即同時具有置換公鑰的能力和訪問系統(tǒng)主密鑰的能力），則它可以偽造任何簽名，亦可完成任何密碼學(xué)操作。因此，所有當(dāng)前無證書密碼方案均不考慮攻擊者同時具備這兩種能力。在分布式系統(tǒng)中，很難找到一個絕對可靠的節(jié)點來充當(dāng)KGC，因此，無法防止KGC 發(fā)動主動攻擊。本文所提的方案，基于無信賴者的秘密共享技術(shù)，利用拉格朗日插值多項式f(x)，由n個SN 節(jié)點共同協(xié)商計算系統(tǒng)主密鑰s，不依賴于任何單個可信賴節(jié)點，沒有一個節(jié)點獨立掌握完整的系統(tǒng)主密鑰，故任何一個單獨的SN 節(jié)點都無法發(fā)動KGC 主動攻擊。對于t-1 次多項式來說f(x)，至少需要t對（ID，f（ID）），才能重構(gòu)多項式，即至少t個SN 節(jié)點共謀才能重構(gòu)出系統(tǒng)主密鑰。因此，攻擊者至少要獲取t個si或至少t個 SN 節(jié)點共謀才能發(fā)動 KGC 主動攻擊。

3.2 性能用P表示雙線性對運算，E表示指數(shù)運算，S表示橢圓曲線上的點乘運算，H表示哈希運算。將本文所提的門限簽名方案與現(xiàn)有方案進(jìn)行性能比較如表1所示，其中nu和nm分別表示用戶ID的長度和待簽消息m的長度。

表1 性能比較

雙線性對運算、指數(shù)運算和哈希運算的時間花費分別至少是橢圓曲線點乘運算時間花費的21倍、3倍和1倍。本文所提方案主要運算是橢圓曲線上的點乘運算，具有較高的運算效率。

4 小結(jié)

基于無信賴者的秘密共享技術(shù)和無需配對的無證書密碼技術(shù)設(shè)計了無需配對的無證書門限簽名方案。方案消除了基于PKI門限簽名方案中復(fù)雜的證書管理工作，消除了基于IBC 方案中固有的密鑰托管問題；同時方案去除了傳統(tǒng)CL-PKC 中耗時的雙線性對運算；方案不依賴于單個可信節(jié)點。因此，方案具有簡單、安全和高效的特點。

〔1〕Anitha T N，Jayanth A. Efficient threshold signature scheme〔J〕. International Journal of Advanced Computer Science and Applications，2012，3（1）:112-116.

〔2〕Xu Qiuliang，Chen Tzer-Shyong. An efficient threshold RSA digital signature scheme〔J〕. Applied Mathematics and Computation，2005，166（7）:25-34.

〔3〕Wang Licheng，Gao Zhenfu，Li Xiangxue，et al. Simulatability and security of certificateless threshold signatures〔J〕.Information Sciences，2007，177（6）:1382-1394.

〔4〕Xiong Hu，Li Fagen，Qin Zhiguang. Certificateless threshold signature secure in the standard model〔J〕.Information Sciences，2010，23（3）:175-203.

〔5〕Yuan Hong，Zhang Futai，Huang Xinyi，et al. Certificateless threshold signature scheme from bilinear maps〔J〕. Information Sciences，2010，180（23）:4714-4728.

〔6〕黃梅娟.新的基于身份的門限簽名方案〔J〕.計算機(jī)工程與數(shù)字，2013，41（4）:625-627.

〔7〕Sun Hua，Ge Yanqiang. On the Security of Certi_cateless Threshold Ring Signature without Random Oracles〔J〕.Journal of Computational Information Systems，2014，10（9）:3585-3592.

〔8〕Boneh D，F(xiàn)ranklin M. Identity-Based Encryption from the Weil Pairing〔C〕//Int’l Cryptology Conf.Advances in Cryptology，USA.2001:213-229.

〔9〕Baek J，Safavi-naini R，Susilo W. Certificateless public key encryption without pairing〔J〕. Information Security，2005，3650:134-148.

〔10〕Zhang L，Zhang F.A method to construct a class of certificateless signature schemes〔J〕.Journal of Computers，2009，32（5）:940-945.

〔11〕Wang S，Liu W，Xie Q. Certificateless signature scheme without bilinear pairings〔J〕.Journal on Communications，2012，33（4）:93-98.