史華婷，萬中美

(河海大學 理學院,江蘇 南京 211100)

一種無證書簽名方案的分析與改進

史華婷，萬中美

(河海大學 理學院,江蘇 南京 211100)

無證書公鑰密碼體制雖然解決了基于身份密碼體制中的密鑰托管問題,但是當隨機預言模型被具體的哈希函數(shù)實例化時,將會導致無證書簽名方案在現(xiàn)實生活中的不安全。標準模型下的證明為無證書簽名方案提供充分的保障。通過兩種具體的攻擊方法,對李艷瓊提出的標準模型下的無證書簽名方案進行安全性分析,指出其不能抵抗公鑰替換攻擊和惡意的KGC攻擊。針對存在的安全問題,對原來的無證書簽名方案進行改進,并加強方案與公鑰、私鑰等參數(shù)的聯(lián)系,從而達到安全要求。在標準模型下,基于NGBDH問題和Many-DH問題的困難性假設,改進的無證書簽名方案在自適應選擇消息攻擊下是存在性不可偽造的。與李艷瓊提出的方案相比,改進后的無證書簽名方案在安全性上有了更高的優(yōu)勢。

無證書簽名；標準模型；NGBDH問題；Many-DH問題

0 引 言

為了解決基于身份密碼體制[1]中的密鑰托管問題,Al-Riyami和Paterson[2]在2003年亞密會議上引入了無證書公鑰密碼體制的概念。無證書公鑰密碼體制區(qū)別于基于身份密碼體制,它需要一個可信密鑰生成中心(Key Generation Center,KGC),負責生成用戶的部分私鑰。在無證書公鑰密碼體制中,私鑰不是由KGC單獨生成的,需要用戶隨機選擇一個秘密值和部分私鑰組合,才能生成完整的私鑰,這就克服了密鑰托管問題。

Yum和Lee[3]在2004年提出了一個由兩種屬性構(gòu)建的無證書簽名的通用結(jié)構(gòu)。但是,Hu和Wong[4]發(fā)現(xiàn)該方案是不安全的,其不能抵抗第一類公鑰替換攻擊,并對其進行了改進。為了提高計算效率,Zhang等[5]提出了一種安全的無證書簽名方案。文獻[6]給出了一類無證書簽名方案的構(gòu)造方法,并對其進行安全性證明。文獻[7]提出了一種高效的簽名方案,但是文獻[8]發(fā)現(xiàn)其是不安全的,并提出了改進方案。文獻[9]對文獻[8]在安全性和效率上存在的不足進行改進,提出了不使用雙線性對的簽名方案。

文獻[10]指出，隨機預言模型下的可證安全并不是嚴格意義上的安全,標準模型可以保持隨機預言模型中的安全特性?；谝陨蠁栴},Liu等[11]在2007年亞密會議上提出了第一個標準模型下的無證書簽名方案。隨后,Xiong[12]、Yu[13]等又對Liu等[11]的提出方案進行改進。文獻[14]提出了一種標準模型下的無證書短簽名方案,并進行了安全性分析。李艷瓊[15]根據(jù)文獻[16]構(gòu)造了一種新的無證書簽名方案,但是它不能抵抗兩類攻擊。

針對李艷瓊的方案進行了安全分析,給出了兩種具體的攻擊方法,指出其不能抵抗公鑰替換攻擊和惡意的KGC攻擊,并提出了一種改進的無證書簽名方案。基于NGBDH問題和Many-DH問題的困難性假設,證明改進方案在標準模型下是存在性不可偽造的。

1 預備知識

1.1 雙線性映射

設G1是由g產(chǎn)生的階為素數(shù)q的乘法循環(huán)群,G2為同階乘法循環(huán)群。雙線性映射e:G1×G1→G2,滿足以下條件：

(2)非退化性：e(g,g)≠1。

(3)可計算性：存在有效的算法計算e。

1.2 困難性問題

設算法C解決G上的Many-DH問題的概率ε為：

Pr[A(g,gα,gβ,gγ,gαβ,gαγ,gβγ)=gαβγ]≥ε

2 李艷瓊方案的安全性分析

2.1 攻擊1

對方案實施如下惡意的KGC攻擊：

(2)竊聽在公鑰pkID*下身份ID*對消息m的簽名σ=(V,Ru,Rm),在相同公鑰下KGC生成身份ID*對任意m*的有效簽名。

因為滿足：

所以偽造的簽名σ*=(V*,Ru*,Rm*)是有效的,即該方案不能抵抗惡意的KGC攻擊。

2.2 攻擊2

敵手AI用新公鑰偽造用戶ID*的簽名：

顯然,偽造的簽名σ*滿足驗證算法,所以該方案不能抵抗公鑰替換攻擊。

3 新的無證書簽名方案

1)系統(tǒng)參數(shù)設置算法：給定安全參數(shù)k,KGC執(zhí)行以下步驟：

(1)隨機選擇兩個階為素數(shù)q的乘法循環(huán)群G1、G2,g為G1的生成元。存在一個雙線性映射e:G1×G1→G2。

(4)取G1中的點Q,定義函數(shù)f(Q),如果Q的x坐標為奇數(shù),則f(Q)=1；否則,f(Q)=0。

系統(tǒng)的公開參數(shù)為params={G1,G2,e,g,g1,g2,u',m0,m1,v,U,H0,H,f}。

6)驗證算法：驗證者使用params和pkID對(m,σ)進行驗證：

(1)驗證e(pkID,1,pkID,2)=e(g1,v)；若不成立,則終止。

(2)計算b=f(Ru),h=H(m,ID,pkID,2,Ru,Rm,mb,v)。

4 安全模型

無證書簽名方案的敵手模型與文獻[15]中的類似,第一類敵手AI作為第三方攻擊者,可以替換任意用戶的公鑰,但不知道主密鑰和部分私鑰。第二類敵手AII作為一個惡意的KGC,知道主密鑰,但不可以替換用戶的公鑰。

下面通過兩種游戲定義無證書簽名方案的安全模型。

4.1 游戲1

敵手AI和挑戰(zhàn)者C之間的游戲如下：

1)系統(tǒng)參數(shù)設置：輸入安全參數(shù)k,KGC生成params和msk。C將params發(fā)送給AI,msk保密。

2)詢問：AI進行如下詢問:

(1)部分私鑰詢問：C接收到AI對身份ID的部分私鑰的詢問,返回pskID給AI。

(2)公鑰詢問：AI詢問身份ID的pkID,C返回pkID給AI。

(4)私鑰詢問：C接收到AI對身份ID的私鑰詢問,返回skID給AI。

(5)簽名詢問：AI可以詢問身份為ID的用戶對任意消息m的簽名,C返回簽名給AI。

3)偽造：AI輸出身份為ID*的用戶對消息m*的簽名σ*。如果AI滿足以下條件且Verify(params,ID*,pkID*,m*,σ*)=1,那么AI就贏得了游戲：

(1)AI沒有發(fā)出對ID*的部分私鑰詢問。

(2)AI沒有發(fā)出對ID*的私鑰詢問。

(3)AI沒有發(fā)出對(ID*,m*)的簽名詢問。

那么,AI成功的概率定義為AI贏得游戲1的概率。

4.2 游戲2

敵手AII和挑戰(zhàn)者C之間的游戲如下：

1)系統(tǒng)參數(shù)設置：輸入安全參數(shù)k,KGC生成params和msk,并將params、msk發(fā)送給AII。

2)詢問：AII發(fā)出和游戲1相同的私鑰詢問、公鑰詢問、公鑰替換詢問和簽名詢問。

3)偽造：AII輸出身份為ID*的用戶對消息m*的簽名σ*。如果AII滿足以下條件且Verify(params,ID*,pkID*,m*,σ*)=1,那么AII就贏得了游戲。

(1)AII沒有詢問過身份ID*的私鑰。

(2)AII沒有替換身份ID*的公鑰。

(3)AII沒有詢問過身份ID*對消息m*的簽名。

那么,AII成功的概率定義為AII贏得游戲2的概率。

定義3：如果上述兩類敵手都能以不可忽略的優(yōu)勢贏得游戲，那么就稱無證書簽名方案在適應性選擇消息攻擊下是存在性不可偽造的。

5 安全證明

證明：輸入(g,gα,gβ),計算(gαβγ,gγ),利用算法C解決NGBDH問題。C包含了初始為空的列表L={ID,pskID,xID,pkID,skID}。

2)詢問：在詢問階段，算法C回復AI的一系列詢問。

(1)部分私鑰詢問：AI詢問身份ID的pskID,C檢查列表L,若存在,直接返回pskID給敵手AI。若不存在,C檢查Ju(u)=0modq：若Ju(u)=0modq,C終止模擬；若Ju(u)≠0modq,C隨機選取r∈Zq,計算部分私鑰：

C返回pskID給AI,并將元組添加到L。

(4)私鑰詢問：C接收到AI發(fā)出的對身份ID的私鑰詢問,檢查列表L。若存在,直接返回skID給敵手AI；若不存在,檢查Ju(u)=0modq。如果Ju(u)=0modq,C終止模擬；否則,C發(fā)出部分私鑰詢問獲得身份ID的pskID,運行用戶密鑰生成算法獲取(xID,pkID),運行私鑰生成算法獲得skID。C返回元組給AI并添加到L。

(5)簽名詢問：AI詢問消息m的簽名,C執(zhí)行以下步驟：

若Ju(u)≠0modq,C檢查L,若存在(pkID，skID),則C運行簽名算法生成消息m的簽名σ,并返回給AI。

否則,C選擇r1∈Zq,使f(gr1)=1(如果f(gr1)=0,C再選r1∈Zq,使f(gr1)=1)。隨后,C隨機選擇rm∈Zq,按如下生成σ=(V,Ru,Rm)：

4)概率計算：算法C在模擬過程中沒有終止,必須滿足以下條件：

(1)部分私鑰詢問滿足Ju(u)≠0modq。

(2)所有的私鑰詢問滿足Ju(u)≠0modq。

定義3個事件A*,B*,Ai：

A*：Ju(u*)=0modq；

Ai：Ju(ui)≠0modl,i=1,2,…,qI。

證明：輸入(g,gα,gβ,gγ,gαβ,gαγ,gβγ),計算gαβγ。利用算法C解決Many-DH問題,C包含了一個初始為空的列表L={ID,xID,pkID,skID}。

2)詢問階段：AII發(fā)出以下詢問。

(1)公鑰詢問：AII詢問身份ID的公鑰,C檢查列表L。若存在,直接返回pkID給敵手AII。若不存在,C隨機選取xID∈Zq,計算pkID=(pkID,1,pkID,2)=(gαγxID,g)作為身份ID的公鑰。C返回pkID給AII,并將元組添加到L。

C返回skID給AII,并將元組添加到L。

(4)簽名詢問：AII詢問消息m的簽名,C執(zhí)行以下步驟：

若Ju(u)≠0modq,C檢查L,若(pkID,skID)存在,則C運行簽名算法生成消息m的簽名σ,并返回給AII。否則,C隨機選擇r1∈Zq,使f(gr1)=1(如果f(gr1)=0,C再選r1∈Zq,使f(gr1)=1)。隨后,C隨機選擇rm∈Zq,按如下生成σ=(V,Ru,Rm)：

6 結(jié)束語

通過具體的攻擊方法,對李艷瓊的方案進行了安全性分析,指出其不能抵抗公鑰替換攻擊和惡意的KGC攻擊。為此，提出了一種改進的無證書簽名方案,克服了原方案的安全缺陷。基于NGBDH問題和Many-DH問題，在標準模型下證明了改進方案的安全性。與原方案相比，改進方案增強了與公鑰、私鑰等參數(shù)的聯(lián)系，具有更強的安全性。在今后的研究中,構(gòu)造安全高效的標準模型下的無證書簽名方案仍是研究的重點。

[1]ShamirA.Identity-basedcryptosystemsandsignatureschemes[C]//ProceedingsoftheCrypto’84.[s.l.]:[s.n.],1984:47-53.

[2]Al-RiyamiSS,PatersonKG.Certificatelesspublickeycryptography[C]//ProceedingsoftheAsiacrypt’2003.[s.l.]:[s.n.],2003:452-473.

[3]YumDH,LeePJ.Genericconstructionofcertificatelessencryption[C]//ProceedingsoftheACISP’2004.[s.l.]:[s.n.],2004:802-811.

[4] Hu B C,Wong D S,Zhang Z,et al.Key replacement attack against a generic construction of certificateless signature[C]//Lecture notes in computer science.[s.l.]:[s.n.],2006:235-246.

[5] Zhang Z,Wong D,Xu J,et al.Certificateless public key signature:security model and efficient construction[C]//Lecture notes in computer science.[s.l.]:[s.n.],2006:293-308.

[6] 張 磊,張福泰.一類無證書簽名方案的構(gòu)造方法[J].計算機學報,2009,32(5):940-945.

[7] 李鳳銀,劉培玉,朱振方.高效的無證書簽名方案[J].計算機工程與應用,2011,47(10):23-26.

[8] 劉 倩,范安東,張麗娜,等.一個高效的無證書簽名方案分析與改進[J].河南科技大學學報:自然科學版,2014,35(4):49-53.

[9] 劉二根,周華靜,王 霞,等.一個安全高效的無證書簽名方案的分析與改進[J].華東交通大學學報,2015,32(4):105-109.

[10] 馮登國.可證明安全性理論與方法研究[J].軟件學報,2005,16(10):1743-1756.

[11] Liu J K,Au M H,Susilo W.Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model:extended abstract[C]//Proceedings of the ASIACCS’2007.New York:ACM Press,2007:273-283.

[12] Xiong H,Qin Z G,Li F G.An improved certificateless signature scheme secure in the standard model[J].Fundamenta Informaticae,2008,88(1-2):193-206.

[13] Yu Y,Mu Y,Wang G,et al.Improved certificateless signature scheme provably secure in the standard model[J].IET Information Security,2012,6(2):102-110.

[14] 魏春艷,蔡曉秋.標準模型下的高效無證書短簽名方案[J].計算機工程,2012,38(13):119-121.

[15] 李艷瓊,李繼國,張亦辰.標準模型下安全的無證書簽名方案[J].通信學報,2015,36(4):185-194.

[16] 李繼國,姜平進.標準模型下可證安全的基于身份的高效的簽名方案[J].計算機學報,2009,32(11):2130-2136.

Analysis and Improvement of a Certificateless Signature Scheme

SHI Hua-ting，WAN Zhong-mei

(College of Science,Hohai University,Nanjing 211100,China)

Although certificateless cryptography solves the key escrow problem in the identity-based public cryptography,a CLS scheme may not be secure in the real world when the random oracles are instantiated by concrete hash functions.The security of certificateless signature scheme can be proved adequately in the standard model.Security analysis has been carried out for Li Yanqiong’s CLS scheme by detailed method attack,whose results show that the scheme is not secure against key replacement attacks and malicious KGC attack.In view of the existing secure problems,an improved certificateless signature scheme has been proposed,which enhances the contact with the public key,private key and other parameters,to achieve the safety requirements.Based on the NGBDH problem and Many-DH problem in the standard model,an improved CLS scheme is proved secure against existentially under adaptive chosen message attack.Compared with Li Yanqiong’s scheme,the improved CLS scheme has higher advantages in the security.

certificateless signature;standard model;NGBDH problem;Many-DH problem

2016-05-24

2016-09-08 網(wǎng)絡出版時間：2017-03-07

國家自然科學基金資助項目(61103183)

史華婷(1991-),女,碩士,研究方向為密碼學理論與技術(shù);萬中美,副教授,碩士生導師,研究方向為信息安全、密碼學理論與技術(shù)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0921.048.html

TP309

A

1673-629X(2017)05-0133-05

10.3969/j.issn.1673-629X.2017.05.028