楊鄧奇，楊 健

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

Client/Server計(jì)算模式中，服務(wù)器通?？梢宰鳛樽C書管理中心，負(fù)責(zé)系統(tǒng)中公鑰證書的管理工作，同時(shí)亦可作為簽名者一些重要的消息提供簽名服務(wù)，如身份分配、令牌發(fā)布時(shí)所需消息的簽名等。然而，一方面，在純分布式系統(tǒng)中找到一個(gè)可靠的節(jié)點(diǎn)作為中心服務(wù)器來管理數(shù)字證書、提供簽名服務(wù)是個(gè)困難的問題；另一方面，當(dāng)系統(tǒng)規(guī)模較大時(shí)，由單一的服務(wù)器提供簽名服務(wù)可能導(dǎo)致系統(tǒng)瓶頸的產(chǎn)生。因此，有學(xué)者提出基于秘密共享技術(shù)的門限簽名方案〔1-7〕，由多個(gè)節(jié)點(diǎn)共同為一些重要消息提供簽名服務(wù)。現(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è)計(jì)，雙線性對運(yùn)算是個(gè)非常耗時(shí)的操作〔11〕。因此，基于雙線性對的無證書門限簽名方案的效率較低。

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

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

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

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

1）SNi（i=1，2，…，n）隨機(jī)選擇一個(gè)秘密值bi∈GF（p）和一個(gè)t-1次多項(xiàng)式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，計(jì)算Bi，k=ai，kP（k=0，1，…，t-1）并將其發(fā)送給其他n-1個(gè)SN節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

2.3 簽名與驗(yàn)證

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

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

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

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

驗(yàn)證過程證明：

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

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

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

驗(yàn)證過程的正確性證明:

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

3 安全與性能

3.1 安全性分析目前CL-PKC安全模型通?？紤]兩種類型的攻擊：公鑰置換攻擊和主密鑰攻擊。在CL-PKC中，節(jié)點(diǎn)公鑰為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)。因?yàn)?，攻擊者不知道系統(tǒng)主密鑰s，系統(tǒng)主密鑰s參與部分私鑰生成的計(jì)算是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 來驗(yàn)證SNA的簽名。如果攻擊者C 要假冒簽名者SNA的身份偽造簽名，則攻擊者C 選擇秘密值x′A，隨機(jī)數(shù)r′A，計(jì)算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 要生成一個(gè)能被PK′A驗(yàn)證的簽名，則 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，因此，它無法計(jì)算部分私鑰D′A。所以攻擊者C 無法偽造一個(gè)有效的簽名。

2）主密鑰攻擊

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

3）抗KGC主動(dòng)攻擊和共謀

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

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

表1 性能比較

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

4 小結(jié)

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

〔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ì)算機(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.