一種無證書簽名方案的分析與改進(jìn)

史華婷，萬中美

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

一種無證書簽名方案的分析與改進(jìn)

史華婷，萬中美

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

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

無證書簽名；標(biāo)準(zhǔn)模型；NGBDH問題；Many-DH問題

0 引 言

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

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

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

針對李艷瓊的方案進(jìn)行了安全分析,給出了兩種具體的攻擊方法,指出其不能抵抗公鑰替換攻擊和惡意的KGC攻擊,并提出了一種改進(jìn)的無證書簽名方案?；贜GBDH問題和Many-DH問題的困難性假設(shè),證明改進(jìn)方案在標(biāo)準(zhǔn)模型下是存在性不可偽造的。

1 預(yù)備知識

1.1 雙線性映射

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

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

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

1.2 困難性問題

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

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

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

2.1 攻擊1

對方案實(shí)施如下惡意的KGC攻擊：

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

因?yàn)闈M足：

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

2.2 攻擊2

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

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

3 新的無證書簽名方案

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

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

(4)取G1中的點(diǎn)Q,定義函數(shù)f(Q),如果Q的x坐標(biāo)為奇數(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)驗(yàn)證算法：驗(yàn)證者使用params和pkID對(m,σ)進(jìn)行驗(yàn)證：

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

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

4 安全模型

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

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

4.1 游戲1

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

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

2)詢問：AI進(jìn)行如下詢問:

(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è)置：輸入安全參數(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)勢贏得游戲，那么就稱無證書簽名方案在適應(yīng)性選擇消息攻擊下是存在性不可偽造的。

5 安全證明

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

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

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

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

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

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

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

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

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

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

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

定義3個(gè)事件A*,B*,Ai：

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

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

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

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

(1)公鑰詢問：AII詢問身份ID的公鑰,C檢查列表L。若存在,直接返回pkID給敵手AII。若不存在,C隨機(jī)選取xID∈Zq,計(jì)算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運(yùn)行簽名算法生成消息m的簽名σ,并返回給AII。否則,C隨機(jī)選擇r1∈Zq,使f(gr1)=1(如果f(gr1)=0,C再選r1∈Zq,使f(gr1)=1)。隨后,C隨機(jī)選擇rm∈Zq,按如下生成σ=(V,Ru,Rm)：

6 結(jié)束語

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

[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].計(jì)算機(jī)學(xué)報(bào),2009,32(5):940-945.

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

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

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

[10] 馮登國.可證明安全性理論與方法研究[J].軟件學(xué)報(bào),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] 魏春艷,蔡曉秋.標(biāo)準(zhǔn)模型下的高效無證書短簽名方案[J].計(jì)算機(jī)工程,2012,38(13):119-121.

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

[16] 李繼國,姜平進(jìn).標(biāo)準(zhǔn)模型下可證安全的基于身份的高效的簽名方案[J].計(jì)算機(jī)學(xué)報(bào),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)絡(luò)出版時(shí)間：2017-03-07

國家自然科學(xué)基金資助項(xiàng)目(61103183)

史華婷(1991-),女,碩士,研究方向?yàn)槊艽a學(xué)理論與技術(shù);萬中美,副教授,碩士生導(dǎo)師,研究方向?yàn)樾畔踩?、密碼學(xué)理論與技術(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