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

楊鄧奇，楊 健

（大理學院數學與計算機學院，云南大理 671003）

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

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

1 預備知識

無證書密碼系統中存在一個密鑰生成中心（KGC）參與用戶私鑰的生成。系統中，每個用戶均有一個唯一用戶身份標識（ID）；用戶私鑰均由兩個部分構成，即KGC為其生成的部分私鑰和用戶自主選擇的秘密值兩部分。只有同時掌握部分私鑰和用戶秘密值，才能進行密碼學的相關運算。

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

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

2）PartialKeyExtract 算法：由 KGC 運行該算法，算法輸入參數params，主密鑰s和用戶ID，輸出用戶部分私鑰DID和對應的部分公鑰PID，即（PID，DID）=PartialKeyExtract（params，s，ID）。

3）SetSecretValue 算法：由用戶運行該算法，算法輸入參數params和用戶ID，輸出用戶自主生成的秘密值xID，即xID=SetSecretValue（params，ID）。

4）SetPrivateKey 算法：由用戶運行該算法，算法輸入參數params，用戶部分私鑰DID和用戶秘密值xID，輸出用戶私鑰 SKID，SKID=SetPrivateKey（params，DID，xID）。

5）SetPublicKey 算法：由用戶運行該算法，算法輸入參數params，用戶部分公鑰PID，用戶部分私鑰xID和用戶ID，輸出用戶公鑰PKID，即PKID=SetPublicKey（prarms，PID，xID，ID）。

6）Sign算法：由簽名用戶運行該算法，算法輸入參數params，用戶私鑰SKID，用戶ID 和消息m，輸出簽名σ，即σ=Sign（params，SKID，ID，m）。

7）Verify算法：由驗證簽名的用戶運行該算法，算法輸入參數params，用戶公鑰PKID，用戶ID 和簽名σ，輸出驗證結果“Accept”或“Reject”。

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

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

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

1）SNi（i=1，2，…，n）隨機選擇一個秘密值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）并將其發送給其他n-1個SN節點。

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

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

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

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

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

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

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

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

2.3 簽名與驗證

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

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

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

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

驗證過程證明：

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

若系統中另一用戶B 要對A 發送的帶有SN 節點簽名的消息m進行驗證，則A 發送元組＜σ，γ，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中，節點公鑰為PK=＜X，R＞，私鑰為SK=＜x，D＞，其中D=r+sH1（ID，R，X）為部分私鑰。

1）公鑰置換攻擊

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

2）主密鑰攻擊

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

3）抗KGC主動攻擊和共謀

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

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

表1 性能比較

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

4 小結

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

〔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〕.計算機工程與數字，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，Franklin 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.