湯鵬志，張慶蘭，楊俊芳

(華東交通大學(xué) 理學(xué)院;華東交通大學(xué) 系統(tǒng)工程與密碼學(xué)研究所，南昌 330013)

2003 年，Al－Riyami 和Paterson［1］第一次提出無證書密碼體制的概念，同時(shí)，并提出了首個(gè)無證書簽名方案。這種簽名方案的部分密鑰是由用戶和KGC 共同協(xié)議產(chǎn)生，解決了基于身份的密碼系統(tǒng)中的密鑰托管問題。2004 年，Yum 等［2］首次提出無對映射的無證書簽名方案。但是，Hu 等［3］指出文獻(xiàn)［2］中的方案不能抵抗公鑰替換攻擊，并在此基礎(chǔ)上，提出了一個(gè)改進(jìn)的無雙線性對的無證書簽名方案。此后，大量的無證書簽名方案被提出。［4－9］

1996 年，Mambo，Usuda 和Okamoto［10，11］提出了代理簽名。此后，大多數(shù)的代理簽名方案是在基于證書，或者基于身份的密碼體制的基礎(chǔ)上提出的。2005 年，Li 等［12］第一次提出了一個(gè)無證書代理簽名方案。但是，Lu 等［13］指出文獻(xiàn)［12］的方案，任何人都能夠冒充代理簽名者，偽造一個(gè)有效的代理簽名的缺陷，同時(shí)也給出了改進(jìn)的方案。2010年，許春根等人［14］提出了一種基于離散對數(shù)問題的無證書代理簽名方案，該方案代理密鑰利用Schnorr 短簽名產(chǎn)生，計(jì)算效率較高;2012 年，張俊茸等人［15］給出了一種新的無證書代理環(huán)簽名方案，將無證書密碼體制、代理簽名和環(huán)簽名三種密碼體制的優(yōu)點(diǎn)結(jié)合起來，具有比較高的實(shí)用性。2012 年，王圣寶等人［16］提出了一種無雙線性配對的無證書簽名方案。通過對文獻(xiàn)［14］中的方案的分析，發(fā)現(xiàn)方案存在公鑰被替換的風(fēng)險(xiǎn)，然后結(jié)合代理簽名，給出了一種改進(jìn)的基于無對映射的無證書代理簽名方案。

1 困難問題

定義1 (DLP 假設(shè))設(shè)G 是階為q 的一個(gè)循環(huán)群，P 為G 的生成元，對于任意的u ∈Z*q ，已知uP，P，計(jì)算u 是離散對數(shù)問題，在概率多項(xiàng)式時(shí)間(PPT)內(nèi)，對于任意算法Α，解決DLP困難問題 的優(yōu)勢AdvDLP(Α) = Pr［Α(uP，P) =是可忽略的。

2 文獻(xiàn)［16］中的無證書簽名方案與安全性分析

2.1 回顧文獻(xiàn)［16］中的簽名方案

具體方案見文獻(xiàn)［16］中的新方案。

2.2 文獻(xiàn)［16］中方案的安全性分析

通過對文獻(xiàn)［16］中方案的安全性分析發(fā)現(xiàn)，方案存在公鑰替換攻擊，具體的攻擊方案參考文獻(xiàn)［17］。假設(shè)A 為簽名者，B 為簽名驗(yàn)證者，AI可以查詢或者替換A 的公鑰。A 的私鑰為(xA，DA)，公鑰為(XA，RA)，B 的私鑰為(xB，DB)，公鑰為(XB，RB)。第一類型的攻擊者AI冒充簽名者A 對消息m 進(jìn)行簽名:

⑴攻擊者AI隨機(jī)選擇，w ∈，計(jì)算=P = wP－RA－H1(IDA，RA)y;

⑵AI用替換A 的公鑰XA(替換A 的私鑰xA)，將發(fā)送給B，B 把當(dāng)成A 的公鑰;

⑶簽名:AI隨機(jī)選擇整數(shù)a ∈Z*q ，然后并計(jì)算TA= aP，h*= H2(TA|||| IDA|| m)，=將簽名σ =發(fā)送給簽名驗(yàn)證者B;

⑷簽名驗(yàn)證:當(dāng)B 接收到簽名σ = (h*，，)和RA，計(jì)算h1= H1(IDA，RA)，

由上述等式分析可知，攻擊者AI偽造的簽名通過了驗(yàn)證者B 的驗(yàn)證。

所以，當(dāng)攻擊者AI替換用戶的公鑰之后，簽名驗(yàn)證者B 無法察覺，即該簽名方案有被偽造的的可能。

3 方案改進(jìn)

3.1 系統(tǒng)參數(shù)選取階段

KGC 利用算法L(1k)，生成參數(shù)(G1，q，P)，其中G1是階為素?cái)?shù)q 的循環(huán)加法群，P 為G1的生成元。并且在G1中離散對數(shù)是難解的。選擇安全hash 函數(shù):H1:{0，1}*× G1× G1→，H2:{0，1}*× {0，1}*× {0，1}*→G1，H3:{0，1}*× {0，1}*→G1，H4:{0，1}*×{0，1}*×{0，1}*×G1×G1→G1，KGC 選擇s 作為系統(tǒng)主私鑰，計(jì)算系統(tǒng)主公鑰Ppub= sP。系統(tǒng)公開參數(shù)為{G1，P，q，Ppub，H1，H2，H3，H4}。

3.2 用戶密鑰生成階段

對于身份為IDi的用戶，隨機(jī)選擇整數(shù)xi∈Z*

q ，計(jì)算PKi= xiP 作為用戶的長期公鑰，然后將PKi發(fā)送給KGC，KGC 隨機(jī)選取ri∈Z*q ，計(jì)算部分公鑰Ri= riP，部分私鑰Xi= ri+ sQi，其中Qi= H1(IDi，Ri，PKi)。KGC 將Ri公開，通過安全信道將Xi發(fā)送給用戶。用戶接收到KGC 生成的部分密鑰后，可以驗(yàn)證等式Ri+ H1(IDi，Ri，PKi)Ppub= XiP 是否成立，若成立，則說明KGC 生成的密鑰合法，接受該密鑰，否則拒絕。這樣，身份為IDi的用戶的完整私鑰是(xi，Xi)，完整公鑰是(Ri，PKi)。

3.3 代理密鑰生成階段

⑴代理授權(quán)階段

假設(shè)A 為原始簽名者，B 為代理簽名者，原始簽名A 人給出一個(gè)授權(quán)證書mw，授權(quán)證書描述了原始簽名人，代理簽名人的身份信息，授權(quán)范圍，代理期限等。A 隨機(jī)選擇kA∈Z*q ，計(jì)算KA= kAPpub，Sw= xAH2(IDA，KA，mw)+XA，A 將授權(quán)簽名(Sw，mw，KA)發(fā)送給代理簽名者B。

⑵代理密鑰生成階段

代理簽名者B 收到(Sw，mw，KA)之后，計(jì)算QA= H1(IDA，RA，PKA)，然后驗(yàn)證等式SwP = PKA·H2(IDA，KA，mw)+ RA+ QAPpub是否成立。如果成立，則生成代理簽名私鑰xp= Sw+ xB·H3(mw，IDB)，否則，終止代理過程。

3.4 代理簽名階段

3.5 代理簽名驗(yàn)證階段

當(dāng)驗(yàn)證者收到B 的簽名σ = (s，h)后，計(jì)算QA= H1(IDA，RA，PKA)，QB= H1(IDB，RB，PKB)，然后驗(yàn)證s(PKA·H2(IDA，KA，mw)+ RA+ (QA+QB)Ppub+PKB·H3(mw，IDB)+RB+hP)= TB是否成立。若成立，則σ = (s，h)是一個(gè)有效的代理簽名，否則，簽名無效。

4 安全與效率分析

4.1 方案正確性

驗(yàn)證等式成立，所以該代理簽名有效。

4.2 隨機(jī)預(yù)言機(jī)下可證安全性

對于無證書簽名方案一般都存在以下兩類攻擊者:

(類型1)攻擊者AI無法獲得系統(tǒng)的主密鑰，但是可以替換任意用戶的長期公鑰;

(類型2)攻擊者AII不能替換用戶的長期公鑰，但可以獲得系統(tǒng)的主密鑰。

定理2 (類型1 攻擊下的不可偽造性)在隨機(jī)預(yù)言機(jī)模型和DL 困難問題假設(shè)下，對于類型1的攻擊者AI，改進(jìn)的方案在適應(yīng)性選擇消息和選擇身份攻擊下是存在性不可偽造的。

證明:假設(shè)算法C 能解決DL 問題，即輸入y= uP，輸出u。以算法C 模擬挑戰(zhàn)者，與攻擊者AI進(jìn)行交互游戲。假設(shè)AI在概率多項(xiàng)式時(shí)間內(nèi)，可向挑戰(zhàn)者C 進(jìn)行多項(xiàng)式有限次H1詢問，H2詢問，H3詢問，H4詢問，部分私鑰提取詢問，部分公鑰提取詢問，長期密鑰提取詢問，代理密鑰提取詢問，公鑰替換詢問，代理簽名詢問;列表LH1、LH2、LH3、LH4、LBS、LBG、LCM、LPR、LGT、LQM用于記錄每次詢問的情況。

系統(tǒng)參數(shù)設(shè)置:挑戰(zhàn)者C，生成系統(tǒng)參數(shù){G1，q，P，Ppub，H1，H2，H3，H4}，并將系統(tǒng)參數(shù)發(fā)送給攻擊者AI;假設(shè)系統(tǒng)主公鑰Ppub= uP，u (未知)為系統(tǒng)主密鑰;目標(biāo)用戶ID*= IDk。

(1)H1詢問

當(dāng)挑戰(zhàn)者C 收到攻擊者AI關(guān)于(IDi，Ri，PKi)的H1詢問，C 先查詢列表LH1，如果(IDi，Ri，PKi，h1i)在列表LH1中，則C 將h1i返回給A1;否則，C隨機(jī)選擇h1i∈Z*q ，將其作為回答返回給AI，并且將(IDi，Ri，PKi，h1i)添加到列表LH1中。

(2)H2詢問

當(dāng)挑戰(zhàn)者C 收到攻擊者AI關(guān)于(IDi，Ki，mw)的H2詢問，C 首先查詢列表LH2，如果(IDi，Ki，mw，h2i)在列表LH2中，則C 將h2i返回給AI;否則，C 隨機(jī)選擇h2i，將h2i作為回答返回給AI，并且將(IDi，Ki，mw，h2i)添加到列表LH2中。

(3)H3詢問

當(dāng)挑戰(zhàn)者C 收到攻擊者AI關(guān)于(IDi，mw)的H3詢問，Q 首先查詢列表LH3，如果(IDi，mw，h3i)在列表LH3中，則C 將h3i返回給AI;否則，C 隨機(jī)選擇h3i，將h3i作為回答返回給AI，并且將(IDi，mw，h3i)添加到列表LH3中。

(4)H4詢問

當(dāng)挑戰(zhàn)者C 收到攻擊者AI關(guān)于(IDi，IDj，m，Ti，PKi)的H4詢問，Q 首先查詢列表LH4，如果(IDi，IDj，m，Ti，PKi，hi)在列表LH4中，則C 將hi返回給AI;否則，C 隨機(jī)選擇hi，將hi作為回答返回給AI，并且將(IDi，IDj，m，Ti，PKi，hi)添加到列表LH4中。

(5)部分私鑰提取詢問

當(dāng)C 收到AI關(guān)于IDi的部分私鑰詢問，C 首先查詢列表LBS，如果(IDi，Xi)在列表LBS中，則Q將Xi返回給AI;否則:

(a)當(dāng)i = k 時(shí)，終止算法;

(b)當(dāng)i ≠k 時(shí)，Q 先執(zhí)行H1詢問得到h1i，隨機(jī)選擇ri∈Z*q ，計(jì)算Xi= ri+ sh1i，將計(jì)算得到的Xi作為答復(fù)發(fā)送給AI，并將(IDi，Xi)記錄到列表LBS中。

(6)部分公鑰提取詢問

當(dāng)C 收到AI關(guān)于IDi的部分公鑰詢問，C 首先查詢列表LBG，如果(IDi，Ri)在列表LBG中，則C將Ri返回給AI;否則，C 隨機(jī)選擇ri，計(jì)算Ri=riP，將Ri發(fā)送給AI，同時(shí)把(IDi，Ri)記錄到列表LBG中。

(7)用戶長期密鑰提取詢問

當(dāng)C 收到AI關(guān)于IDi的長期密鑰鑰提取詢問，C 先檢查列表LCM，若(IDi，xi，PKi)在列表LCM中，那么C 將相應(yīng)的(xi，PKi)發(fā)送給AI;否則，C 隨機(jī)選擇xi∈Z*q ，計(jì)算PKi= xiP，將(xi，PKi)發(fā)送給AI，將(IDi，xi，PKi)添加到列表LCM。

(8)公鑰替換詢問

當(dāng)C 收到AI關(guān)于IDi的公鑰替換詢問時(shí)，C 隨機(jī)選擇x'i∈Z*q ，計(jì)算PK'i，用PK'i替換用戶公鑰PKi，并將(IDi，x'i，PK'i)記錄到列表LTH中。

(9)代理密鑰詢問

當(dāng)C 收到AI關(guān)于IDi的代理密鑰提取詢問，C先檢查列表LPR，若(IDi，xi，PKi)在列表LCM中，那么C 將相應(yīng)的(xi，PKi)發(fā)送給AI;否則，C 隨機(jī)選擇ki∈Z*q ，計(jì)算Ki= kiPpub，執(zhí)行H2、H3詢問和部分私鑰詢問獲得h2i、h3i和Xi，計(jì)算Swi=xi·h2i+ Xi，xpi= Swi+ xi·h3i。將xpi發(fā)送給AI，將(IDi，xpi)添加到列表LPR。

(10)代理簽名詢問

當(dāng)C 收到AI關(guān)于(IDi，IDj)和mi的代理簽名詢問時(shí)，其中IDi為代理簽名者，原始簽名者為IDj。C 首先查詢列表LQM，若(IDi，IDj，mi，hi，si)已經(jīng)在列表中，則將相應(yīng)的代理簽名數(shù)據(jù)發(fā)送給AI;否則:

(b)當(dāng)i = k 時(shí)，C 隨機(jī)選擇hk，sk∈Z*q ，執(zhí)行H1詢問、H1獲得h1k和h3k，查詢列表LBG和LCM獲得Rk和PKk，計(jì)算Tk= sk·(Swk+PKk·h3k+Rk+ h1k·Ppub+ hkP)。將相應(yīng)的代理簽名數(shù)據(jù)σk=(hk，sk，mk)發(fā)送給AI，并將(IDk，IDj，mk，hk，sk)添加到列表LQM中。

偽造過程:AI執(zhí)行多項(xiàng)式有限次詢問后，在多項(xiàng)式時(shí)間內(nèi)，以不可忽略的概率，可以輸出對消息m 的有效的簽名數(shù)據(jù)，即AI隨機(jī)選擇a，s'i∈Z*

由上述過程可知，AI通過向C 進(jìn)行多項(xiàng)式有限次詢問后，偽造出一個(gè)有效的簽名，挑戰(zhàn)者C根據(jù)偽造出的簽名，在多項(xiàng)式內(nèi)，解決了DLP，但是這與DLP 的困難性矛盾，所以在隨機(jī)預(yù)言機(jī)模型和DLP 困難性的假設(shè)下，該方案是存在性不可偽造的。

定理4 (類型2 攻擊下的不可偽造性)在隨機(jī)預(yù)言機(jī)模型和DLP 困難問題假設(shè)下問題假設(shè)下，對于類型2 的攻擊者AII，改進(jìn)的方案在適應(yīng)性選擇消息和選擇身份攻擊下是存在性不可偽造的。

證明:假設(shè)算法C 能解決DL 問題，即輸入y= vP，輸出v(v 為代理簽名者的私鑰)。

攻擊者AII在多項(xiàng)式時(shí)間內(nèi)，可向C 進(jìn)行多項(xiàng)式有限次H1詢問，H2詢問，H3詢問，H4詢問，部分密鑰提取詢問，用戶長期私鑰提取詢問，公鑰提取詢問，代理密鑰詢問，代理簽名詢問;列表LH1、LH2、LH3、LH4、LBM、LSK、LPK、LPR、LQM用于記錄每次詢問的情況。

(1)H1、H2、H3和H4詢問過程與定理1 相同

(2)部分密鑰提取詢問

當(dāng)C 收到AII關(guān)于IDi的部分密鑰詢問，C 首先查詢列表LBM，如果(IDi，Ri，Xi)在列表LBM中，則C 將(Ri，Xi)返回給AII;否則:C 先執(zhí)行H1詢問，獲得h1i，隨機(jī)選擇ri∈Z*q ，計(jì)算Ri= riP，Xi= ri+ sh1i，把(Ri，Xi)發(fā)送給AII，并將(IDi，Ri，Xi)記錄在列表LBM中。

(3)用戶長期私鑰提取詢問

當(dāng)C 收到AII關(guān)于IDi的長期私鑰提取詢問，Q先檢查列表LSK。若(IDi，xi)在列表LSK中，那么C 將相應(yīng)的xi發(fā)送給AII;否則:

(a)當(dāng)i ≠k 時(shí):C 隨機(jī)選擇xi∈z*q ，計(jì)算PKi= xiP。把(IDi，xi)添加到列表LSK中，并將相應(yīng)的xi發(fā)送給C;

(b)當(dāng)i = k 時(shí):終止算法。

(4)用戶長期公鑰提取詢問

當(dāng)C 收到AII關(guān)于IDi的公鑰提取詢問，C 首先檢查列表LPK。若(IDi，xi，PKi)在列表LPK中，則將PKi返回給A2;否則:

(a)當(dāng)i ≠k 時(shí):C 隨機(jī)選擇xi∈Z*q ，計(jì)算PKi= xiP 將PKi發(fā)送給AII，并把(IDi，xi，PKi)添加到列表。

(b)當(dāng)i = k 時(shí):用戶IDk的公鑰為PKk= uP，用⊥來表示用戶的長期私鑰，將PKk發(fā)送給AII，并把(IDi，⊥，PKi)添加到列表LPK中。

(5)代理密鑰提取詢問

當(dāng)C 收到AII關(guān)于IDi的代理密鑰提取詢問，C先檢查列表LPR，若(IDi，xi，PKi)在列表LCM中，那么C 將相應(yīng)的(xi，PKi)發(fā)送給AI;否則:

(a)當(dāng)i ≠k 時(shí)，C 隨機(jī)選擇ki∈Z*q ，計(jì)算Ki= kiPpub，執(zhí)行H2、H3詢問和部分私鑰詢問獲得h2i、h3i和Xi，計(jì)算Swi= xi·h2i+ Xi，xpi= Swi+ xi·h3i。將xpi發(fā)送給AI，將(IDi，xpi)添加到列表LPR。

(b)當(dāng)i = k 時(shí):終止算法。

(6)代理簽名詢問

偽造過程:AII執(zhí)行多項(xiàng)式有限次詢問后，在多項(xiàng)式時(shí)間內(nèi)，以不可忽略的概率，可以輸出對消息m 的有效的簽名數(shù)據(jù)，即AII隨機(jī)選擇a，s'i∈Z*

q ，計(jì)算T'i= (a + xi)P，h'i= H4(IDi，IDi，m，Ti，PKi)，h1i= H1(IDi，Ri，PKi)，然后輸出對m的偽造簽名σ'i= (h'i，s'i)。假設(shè)偽造簽名有效，挑戰(zhàn)者C 輸出作為DL 問題的答案;否則，C 無法解決DL 問題。

由上述過程可知，AII通過向C 進(jìn)行多項(xiàng)式有限次詢問后，偽造出一個(gè)有效的簽名，挑戰(zhàn)者C根據(jù)偽造出的簽名，在多項(xiàng)式內(nèi)，解決了DLP，但是這與DLP 的困難性矛盾，所以在隨機(jī)預(yù)言機(jī)模型和DLP 困難性的假設(shè)下，該方案是存在性不可偽造的。

5 小結(jié)

在王圣寶［16］等人的方案的基礎(chǔ)上，與代理簽名相結(jié)合，給出了一種能抵抗公鑰替換攻擊的無對映射的代理簽名方案。改進(jìn)的代理簽名方案增加授權(quán)和代理密鑰生成的過程，安全性更高，而且改進(jìn)的方案沒有雙線性的運(yùn)算，效率高，計(jì)算量小。同時(shí)，也給出了在隨機(jī)預(yù)言機(jī)模型和困難問題的假設(shè)下，改進(jìn)方案的在兩種類型攻擊下的不可偽造性的具體的證明過程。

［1］ AL－RIYAMI SS，PATERSON KG.Certificateless public key cryptography［A］.Proc of Asiacrypt 2003 ［C］.Springer－Verlag，Berlin，2003:452－473.

［2］ YUM DH，LEE PJ.Generic construction of certificateless signature［A］.In Information Security and Privacy:9th Australasian Conference，ACISP 2004［C］.Springer－Verlag，2004:200－211.

［3］HU B，WONG D，ZHANG Z，et al.Key replacement attack against a generic construction of certificateless signature［A］.Proc of 11th Australasian Conference on Information Security and Privacy［C］.Melbourne，Australia，2006:235－246.

［4］ HUANG X，SUSILO W，MU Y，et al.On the security of certificateless signature schemes［A］.Asiacrypt 2003［C］.2005:13－25.

［5］ GORANTLA MC，SAXENA A.An efficient certificateless signature scheme［A］.Proc of CIS’05［C］.Springer－Verlag，2005:110－116.

［6］CAO X，PATERSON KG，KOU W.An Attack on a Certificateless Signature Scheme［R］.Cryptology ePrint Archive，2006.

［7］ CHOI KY，PARK JH，HWANG J，et al.Efficient certificateless signature schemes［A］.Proc of ACNS’07［C］.Springer－Verlag，2007:443－458.

［8］ SHIM KA.Breaking the short certificateless signature scheme［J］.Information Sciences，2009，179(3):303－306.

［9］ YUAN Y，LI D，TIAN L，et al.Certificateless signature scheme without random oracles［A］.ISA 2009［C］.2009:31－40.

［10］M Mambo，K Usuda，E Okamoto.Proxy signatures:Delegation of the Power to sign messages ［J］ .IEICE Trans.Fundamentals，1996，79(9):1338－1353.

［11］M Mambo，K Usuda，E Okamoto.Proxy signatures for delegating signing operation［A］.3rdACM Conference on Computer and Communications Security(CCS.96)［C］. New York:ACM Press，1996:48－57.

［12］Li X，Chen K，Sun L.Certificateless Signature and Proxy Signature Schemes from Bilinear Pairings［J］.Lithuanian Mathematical Journal，2005，45(1):76－83.

［13］Lu Rongbo，He Dake，Wang Changji.Cryptanalysis and Improvement of a Certificateless Proxy Signature Scheme from Bilinear Pairings［C］.Qingdao:Proc of the 8th ACIS International Conference on Software Engineering，Artificial Intelligence，Networking and Parallel/Distributed Computing，2007:285－290.

［14］許春根，張傲紅，陳海濱. 一種基于離散對數(shù)問題的無證書代理簽名方案［J］. 南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，34(6):733－737.

［15］張俊茸，任平安，韓牟，等. 一種新的無證書的代理環(huán)簽名方案［J］. 計(jì)算機(jī)工程與應(yīng)用，2012，48(2):63－65.

［16］王圣寶，劉文浩，謝琪. 無雙線性配對的無證書簽名方案［J］. 通信學(xué)報(bào)，2012，33(4):93－98.

［17］何德彪. 無證書簽密機(jī)制的安全性分析［J］.2013，24(3):618－622.