陳林

兩種無證書代理簽名的密碼學(xué)分析及改進(jìn)

陳林

為了降低計(jì)算開銷，許春根提出一種無對(duì)運(yùn)算的無證書代理簽名方案；張俊茸提出一種無證書代理環(huán)簽名方案，融合了無證書密碼體制、代理簽名和環(huán)簽名的優(yōu)點(diǎn)。分析指出，許春根方案的代理密鑰產(chǎn)生算法存在嚴(yán)重缺陷，致使代理人無法進(jìn)行有效簽名；張俊茸方案存在原始簽名人密鑰泄露及仿冒授權(quán)攻擊、公鑰替換攻擊和匿名性缺陷。針對(duì)上述問題，提出了改進(jìn)方案，彌補(bǔ)了已有方案的安全缺陷，且計(jì)算性能較優(yōu)。

無證書；代理簽名；環(huán)簽名；雙線性對(duì)；公鑰替換攻擊

1 引言

無證書的公鑰密碼體制由Al-Riyamih等人[1]首次提出，被用于解決基于身份公鑰密碼體制中的密鑰托管問題，它同時(shí)又繼承了基于身份公鑰密碼體制的優(yōu)點(diǎn)，不使用公鑰證書，避免了基于證書公鑰系統(tǒng)的證書管理負(fù)擔(dān)。隨后幾年中，無證書的公鑰密碼體制得到了國內(nèi)外研究者的廣泛關(guān)注。

代理簽名的概念由Mambo等人[2]提出，是指原始簽名人把他的簽名權(quán)授給代理人，代理人代表原始簽名人行使他的簽名權(quán)。代理簽名已廣泛應(yīng)用于移動(dòng)代理系統(tǒng)、電子商務(wù)、電子拍賣等領(lǐng)域，其實(shí)用性較強(qiáng)，是數(shù)字簽名領(lǐng)域研究的熱點(diǎn)課題之一。代理簽名的研究方向主要有：將代理簽名概念進(jìn)行延伸提出新的數(shù)字簽名，如多重代理簽名、代理環(huán)簽名等；將代理簽名與其他密碼體制相結(jié)合，如代理盲簽名、門限代理簽名和無證書代理簽名等。

一些研究者將無證書的密碼體制與代理簽名相結(jié)合，提出無證書的代理簽名方案[3-7]。許春根等人[8]提出了一種基于離散對(duì)數(shù)問題的無證書代理簽名方案（XZHD方案），該方案不采用雙線性對(duì)（雙線性對(duì)運(yùn)算開銷較大），且其代理密鑰利用Schnorr短簽名產(chǎn)生，計(jì)算效率較高；張俊茸等人[9]提出了一種新的無證書代理環(huán)簽名方案（記為ZRL方案），融合了無證書密碼體制、代理簽名和環(huán)簽名三種密碼體制的優(yōu)點(diǎn)，具有較高的實(shí)用性。

本文對(duì)XZHD方案[8]和ZRL方案[9]進(jìn)行了密碼學(xué)分析，指出了這兩種方案的安全缺陷，并進(jìn)行了相應(yīng)改進(jìn)。分析表明，改進(jìn)方案是安全的，且計(jì)算性能較優(yōu)。本文研究工作基于無證書密碼體制、雙線性映射理論和相關(guān)困難問題假設(shè)，相關(guān)理論背景請(qǐng)參考文獻(xiàn)[1，8-9]。

2 XZHD簽名方案分析與改進(jìn)

2.1 XZHD無證書代理簽名方案

XZHD方案[8]是一種基于離散對(duì)數(shù)問題的無證書代理簽名方案，由系統(tǒng)生成、密鑰產(chǎn)生、代理密鑰產(chǎn)生、代理簽名和驗(yàn)證5個(gè)算法構(gòu)成，這里簡單描述如下：

系統(tǒng)生成：輸入安全參數(shù)k，輸出系統(tǒng)參數(shù) params= (p，q，g，y，H1，H2)。其中，p、q是兩個(gè)大素?cái)?shù)，且滿足q|p-1；g是生成元；y=gx為KGC的公鑰，對(duì)應(yīng)的主密鑰（MSK）為隨機(jī)選擇的是安全的單向散列函數(shù)。

密鑰產(chǎn)生：輸入(params，IDi)，KGC隨機(jī)選擇計(jì)算w0i=gs0i和d0i=s0i+xqi。這里，qi=H1(IDi，w0i)，返回d0i為IDi的部分私鑰和w0i為 IDi的部分公鑰。用戶 IDi隨機(jī)選擇zi∈Z*q作為其長期私有秘密，計(jì)算Si=zi+d0i作為其私鑰；然后計(jì)算ui=gzi，設(shè)置公鑰為(ui，w0i)。

代理密鑰產(chǎn)生：假設(shè)實(shí)體A委托實(shí)體B進(jìn)行代理簽名，A產(chǎn)生授權(quán)許可信息mw，此授權(quán)信息包含A的身份信息以及A和B的授權(quán)關(guān)系，同時(shí)也包含該代理簽名的使用限制內(nèi)容；A隨機(jī)選sp=SAe+k mod q，并將 (mw，sp，K)發(fā)送給B；B計(jì)算 qA= H1(IDA，w0A)，并驗(yàn)證等式 gsp=w0AyqAeuAK是否成立，如果不成立，則要求A重新執(zhí)行或終止協(xié)議；否則B計(jì)算代理簽名密鑰sw=sp+SBe–k(mod q)=(d0A+zA+d0B+zB)e(mod q)。

簽名驗(yàn)證：驗(yàn)證者首先計(jì)算e=H2(mw，K)，qA=H1(IDA，w0A) 和qB=H1(IDB，w0B)，然后計(jì)算

驗(yàn)證v=H2(M，R)是否成立；若成立則簽名正確。

2.2 XZHD無證書代理簽名方案缺陷分析與改進(jìn)

XZHD無證書代理簽名方案存在以下兩個(gè)缺陷。

（1）代理密鑰產(chǎn)生算法中等式gsp=w0AyqAeuAK不成立：

（2）代理密鑰生成錯(cuò)誤。根據(jù)代理密鑰產(chǎn)生算法，k是A隨機(jī)選擇的參數(shù)，并未發(fā)送給B（A發(fā)送K=gk給B，根據(jù)DLP[8]假設(shè)，B不能通過K計(jì)算得到k）。由于B得不到隨機(jī)參數(shù)k，他不能計(jì)算代理密鑰 sw=sp+SBe–k(mod q)。因此，如果依照原有算法，B將無法產(chǎn)生有效簽名。

針對(duì)這一問題，本文首先對(duì)代理密鑰產(chǎn)生算法做以下修改：

然后修改簽名驗(yàn)證算法如下（其他保持不變）：

修改后算法的正確性由下式驗(yàn)證：

可見，修改后的方案改進(jìn)了原有方案的缺陷，是可證明正確的，且上述修改保留了原有簽名和驗(yàn)證算法的核心部分，是可證明安全的。此外，修改后算法減少了2次指數(shù)運(yùn)算，計(jì)算性能更優(yōu)。

3 ZRL簽名方案的分析與改進(jìn)

3.1 ZRL無證書代理環(huán)簽名方案

ZRL方案[9]是一種無證書的代理環(huán)簽名方案，簡單描述如下。

系統(tǒng)生成：產(chǎn)生并發(fā)布系統(tǒng)參數(shù) param={Gl，G2，e，q，P，P0，H1，H2}。其中，Gl是階為q的加法循環(huán)群，生成元為P；G2是階為q的乘法循環(huán)群；e:Gl×Gl→G2是雙線性映射；P0=sP為KGC的公鑰，對(duì)應(yīng)的s∈是KGC的主密鑰；H1:{0，1}*→G1和H2:{0，1}*→是安全的散列函數(shù)。

密鑰產(chǎn)生：輸入(params，IDi)，KGC計(jì)算Qi=H1(IDi) 和Di=sQi，返回Di為IDi的部分私鑰。用戶IDi隨機(jī)選擇xi∈作為其長期私有秘密，計(jì)算Si=xiDi和Yi=xi(P+Qi)，將(xi，Si)作為其私鑰，Yi設(shè)置為公鑰。

代理密鑰產(chǎn)生：假設(shè)實(shí)體A委托L={ID1，ID2，…，IDn} （L為包括真實(shí)簽名人在內(nèi)的n個(gè)環(huán)成員身份的集合）中實(shí)體B(B∈L)進(jìn)行代理簽名，A產(chǎn)生授權(quán)許可信息w，此授權(quán)信息包含A的身份信息以及該代理簽名的使用期限和范圍等限制內(nèi)容；A計(jì)算Sw=H2(w)(xaP0+Sa)，并將(w，Sw)發(fā)送給B；B驗(yàn)證e(Sw，P)=e(Ya，H2(w)P0)是否成立，如果不成立，則要求A重新執(zhí)行或終止協(xié)議；否則B計(jì)算代理簽名密鑰Sp=Sw+H2(w)(xbP0+Sb)。

代理簽名：當(dāng)要對(duì)消息m進(jìn)行簽名時(shí)，代理簽名人B按以下步驟執(zhí)行：

（1）隨機(jī)選擇ti∈Z*q，計(jì)算Ti=tiP，hi=H2(m，L，Ti)(i= 1，2，…，n且i≠b)；

3.2 ZRL無證書代理環(huán)簽名方案安全性分析

ZRL無證書代理環(huán)簽名方案存在以下安全缺陷。

3.2.1 原始簽名人密鑰泄露及仿冒授權(quán)

在代理密鑰產(chǎn)生算法中，只要獲取Sw，任意實(shí)體均可通過下式計(jì)算得到原始簽名人A的代理授權(quán)密鑰：

當(dāng)產(chǎn)生新的代理密鑰時(shí)，攻擊者產(chǎn)生新的代理授權(quán)許可信息w′，計(jì)算Sw′=H2(w′)(xaP0+Sa)=H2(w′)Sw/H2(w)并發(fā)送(w′，Sw′)發(fā)送給代理簽名人。代理簽名人可通過下式驗(yàn)證等式：

可見攻擊者成功仿冒原始簽名人A產(chǎn)生了代理授權(quán)。

3.2.2 公鑰替換攻擊

無證書密碼體制存在兩類敵手[1](AI，AII):AI是一個(gè)外部攻擊者，他可以替換任何實(shí)體的公鑰，但不能獲得KGC的主密鑰和特定實(shí)體的部分私鑰；AII模擬惡意但受限的KGC，他擁有KGC的主密鑰，但不能替換特定實(shí)體的公鑰以及取得其私有秘密（無證書密碼體制的安全模型請(qǐng)參考文獻(xiàn)[1]，這里不再詳細(xì)描述）。

在ZRL簽名方案中，假設(shè)AI敵手替換簽名者（A和B）的公鑰，將A的公鑰Ya替換為Ya′=xa′P，B的公鑰Yb替換為Yb′=xb′P。這里，xa′，xb′∈Z*q是攻擊者隨機(jī)選取的公鑰參數(shù)。由于Yi=xi(P+Qi)中嵌入了隨機(jī)參數(shù)xi（xi為IDi的私有秘密），且無證書密碼體制下不使用公鑰證書，上述公鑰替換行為（除被替換者外）不可驗(yàn)證?？梢?，這是成功的公鑰替換行為。

AI敵手按簽名算法產(chǎn)生代理簽名(m，L，T1，T2，…，Tn，V)。

驗(yàn)證者計(jì)算：

可見，如果AI敵手成功將A和B的公鑰Ya和Yb替換為Ya′和Yb′，那么他能夠成功偽造A和B代理環(huán)簽名。

3.2.3 密鑰托管

對(duì)于AII敵手，即一個(gè)惡意但受限的KGC，可以偽造原始簽名人的代理授權(quán)簽名和計(jì)算得到代理密鑰，進(jìn)而可以成功偽造代理簽名。

首先，AII敵手通過下式計(jì)算代理授權(quán)簽名：

這里，Ya為A的公鑰，任何實(shí)體可輕易獲得。其次，AII敵手通過同樣方式計(jì)算代理密鑰：Sp=Sw+H2(w)sYb=Sw+H2(w)(xbP0+Sb)

“國……國亡了！我……我也……老了！你們還年青，你們?nèi)ゾ葒?！我的老骨頭再……再也不中用了！我是個(gè)老亡國奴，我不會(huì)眼見你們把日本旗撕碎，等著我埋在墳里……也要把中國旗子插在墳頂，我是中國人！我要中國旗子。我不當(dāng)亡國奴，生是中國人，死是中國鬼……不……不是亡……亡國奴……“

然后，AII敵手可仿冒授權(quán)人A和代理人B產(chǎn)生有效的代理環(huán)簽名。可見，張俊茸等人提出的無證書代理環(huán)簽名方案不具有抗密鑰托管[1]特性（該特性是無證書密碼體制優(yōu)于基于身份密碼體制的關(guān)鍵特性）。

3.2.4 匿名性缺陷

張俊茸等人聲稱ZRL簽名方案具有無條件匿名性。但是，在簽名驗(yàn)證等式中，需要計(jì)算下面公式：

式中hi與Yi一一對(duì)應(yīng)，因此可以通過確定hi來確定Yi。同時(shí)，在簽名驗(yàn)證時(shí)還需要確定參數(shù)hb，才能成功計(jì)算hbH2(w)Ya（需要通過將hi一一代入簽名驗(yàn)證等式中計(jì)算hiH2(w)Ya，驗(yàn)證成功者即為hb）?？梢姡ㄟ^hb可以確定Yb，通過Yb可以確定代理簽名者的身份IDb（Yi與IDi一一對(duì)應(yīng)）。因此，ZRL簽名方案不具有無條件匿名性，任何實(shí)體可通過計(jì)算簽名驗(yàn)證公式確定代理簽名者的身份。

3.3 ZRL無證書代理環(huán)簽名方案改進(jìn)

3.3.1 改進(jìn)方案

本文對(duì)ZRL簽名方案進(jìn)行如下改進(jìn)。

系統(tǒng)生成：與原方案相同。

密鑰產(chǎn)生：輸入(params，IDi)，KGC計(jì)算Qi=H1(IDi) 和Di=sQi，返回Di為IDi的部分私鑰。用戶IDi隨機(jī)選擇xi∈作為其長期私有秘密，計(jì)算Pi=xiP，將(xi，Di)作為其私鑰，Pi設(shè)置為公鑰。

代理密鑰產(chǎn)生：假設(shè)實(shí)體A委托L={ID1，ID2，…，IDn}中實(shí)體B(B∈L)進(jìn)行代理簽名，A產(chǎn)生授權(quán)許可信息w，此授權(quán)信息包含A的身份信息以及該代理簽名的使用期限和范圍等限制內(nèi)容；A隨機(jī)選Sw=u(Da+xaQa+kQa)，并將 (w，K，Sw)發(fā)送給B；B驗(yàn)證e(Sw，P)=e(uQa，P0+Pa+K)是否成立，如果不成立，則要求A重新執(zhí)行或終止協(xié)議；否則B產(chǎn)生代理簽名密鑰Sp=(Sw，xb，Db)。

代理簽名：當(dāng)要對(duì)消息m進(jìn)行簽名時(shí)，代理簽名人B按以下步驟執(zhí)行。

（1）隨機(jī)選擇 ti∈計(jì)算 Ti=tiQi，hi=H2(m，L，Ti) (i=1，…，n且i≠b)。

（2）隨機(jī)選擇 ta，tb∈Z*q，計(jì)算 Ta=taQa，ha=H2(m，L，和輸出簽名Ta，T1，…，Tn，U，V)。這里，a?{1，2，…，n}，b∈{1，2，…，n}，u=H2(w)。

簽名驗(yàn)證：驗(yàn)證者首先計(jì)算Qi=H1(IDi)，hi=H2(m，L，Ti) (i=a，1，…，n)和u=H2(w)，驗(yàn)證等式：是否成立；若成立則簽名正確。

3.3.2 改進(jìn)方案分析

（1）分析改進(jìn)方案的正確性

改進(jìn)方案代理密鑰授權(quán)驗(yàn)證的正確性可通過下列等式證明：

簽名及簽名驗(yàn)證的正確性由下式證明：

（2）分析改進(jìn)方案的安全性

為了改進(jìn)3.2.1小節(jié)描述的安全缺陷，本文引入臨時(shí)秘密參數(shù)k。顯然，每次代理授權(quán)都會(huì)需要一個(gè)臨時(shí)秘密k，那么在k未知的情況下，攻擊者（AI敵手或AII敵手）不能計(jì)算得到原始簽名人A的密鑰(Da+xaQa=Sw/u–kQa)。

針對(duì)3.2.2和3.2.3小節(jié)中描述的安全缺陷，本文在改進(jìn)方案的簽名和驗(yàn)證算法中直接嵌入對(duì)原始簽名人A的代理授權(quán)密鑰Sw的驗(yàn)證，即驗(yàn)證等式e(haSw，P)=e(hauQa，P0+Pa+K)。因此，改進(jìn)方案的安全性可歸結(jié)為代理授權(quán)簽名Sw的安全性（Sw可看做原始簽名人A對(duì)w的簽名）和代理者簽名(V–haSw=xbhbQb+utbDb)的安全性。

對(duì)于代理授權(quán)簽名Sw=u(Da+xaQa+kQa)，這里存在兩個(gè)求解CDH問題實(shí)例。對(duì)于 AI敵手，令 P0=sP和uQa=bP，求解uDa=suQa=sbP（這里，對(duì)AI敵手來說s和b未知）；對(duì)于 AII敵手，令Pa=xaP=aP和uQa=bP，求解uxaQa=abP（這里，對(duì) AII敵手來說 xa和b未知）。因此，如果CDH問題難解假設(shè)[1]成立，那么代理授權(quán)簽名滿足不可偽造性。

類似地，對(duì)于代理者簽名xbhbQb+utbDb，這里也存在兩個(gè)求解CDH問題實(shí)例。對(duì)于AI敵手，令P0=sP和utbQb= bP，求解utbDb=sutbQb=sbP（這里，對(duì) AI敵手來說s和b未知）；對(duì)于 AII敵手，令Pb=xbP=aP和hbQb=bP，求解xbhbQb=abP（這里，對(duì) AII敵手來說xb和b未知）。因此，如果CDH問題難解假設(shè)[1]成立，那么代理者簽名滿足不可偽造性。

可見，本文提出的無證書代理環(huán)簽名滿足不可偽造性。

針對(duì)3.2.3小節(jié)中描述的安全缺陷，本文在原方案的基礎(chǔ)上增加了臨時(shí)參數(shù)ta和ha，由于ha與L無關(guān)，雖然hi與Pi一一對(duì)應(yīng)，但是，通過最終簽名結(jié)果和簽名驗(yàn)證公式，不能確定hb（只能得到b∈{1，2，…，n}），所以不能確定Pb和IDb?？梢姼倪M(jìn)后的代理環(huán)簽名方案實(shí)現(xiàn)了真正的匿名性。

（3）分析改進(jìn)方案的計(jì)算性能

對(duì)運(yùn)算的計(jì)算開銷遠(yuǎn)遠(yuǎn)高于其他計(jì)算，因此，對(duì)運(yùn)算次數(shù)的多少直接決定了方案的計(jì)算性能。改進(jìn)后的方案僅需要3次對(duì)運(yùn)算。雖然，原方案聲稱僅需要2次對(duì)運(yùn)算，但是，正如3.2.4小節(jié)中分析的那樣，要確定真實(shí)的參數(shù)hb，需要將hi一一代入簽名驗(yàn)證等式中計(jì)算hiH2(w)Ya，驗(yàn)證成功者即為hb。因此，就平均概率而言，在實(shí)際應(yīng)用中，約需要（1/2）n次計(jì)算才能驗(yàn)證成功，則對(duì)運(yùn)算的平均計(jì)算次數(shù)約為n次，計(jì)算開銷較高。

4 結(jié)束語

本文對(duì)兩種無證書的代理簽名方案進(jìn)行了密碼學(xué)分析，分別指出了兩種簽名方案中存在的安全缺陷，并進(jìn)行了相應(yīng)的改進(jìn)。特別是無證書代理環(huán)簽名方案，融合了無證書密碼體制、代理簽名和環(huán)簽名三種密碼體制，復(fù)雜度較高，并且沒有成熟的安全性分析模型，其設(shè)計(jì)與分析存在較大難度。今后的工作將圍繞這一問題展開，結(jié)合無證書密碼體制的形式化模型、代理簽名和環(huán)簽名的隨機(jī)預(yù)言機(jī)模型，提出有效的用于分析無證書代理環(huán)簽名的形式化安全模型。

[1]Al-Riyami S S，Paterson K G.Certificateless public key cryptography[C]//ProceedingsofASIACRYPT 2003.Berlin：Springer-Verlag，2003，2894：452-473.

[2]Mambo M，Usuda K，Okamoto E.Proxy signatures for delegating signing operation[C]//Proceedings of 3rd ACM Conference on Computerand Communications Security.New York：ACM Press，1996：48-57.

[3]Du H，Wen Q.Efficient certificateless designated verifier signatures and proxy signatures[J].Chinese Journa1 of Electronics，2009，18（1）：95-100.

[4]陳虎，張福泰，宋如順.可證安全的無證書代理簽名方案[J].軟件學(xué)報(bào)，2009，20（3）：692-701.

[5]孫士鋒，溫巧燕.對(duì)一類無證書強(qiáng)代理簽名方案的攻擊及改進(jìn)[J].北京郵電大學(xué)學(xué)報(bào)，2010，33（1）：80-83.

[6]張建中，魏春艷.一種新的無證書代理簽名方案[J].計(jì)算機(jī)工程，2010，36（10）：168-169.

[7]余丹，楊曉元，陳海濱.無證書的代理盲簽名方案[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（13）：110-112.

[8]許春根，張傲紅，韓牟，等.一種基于離散對(duì)數(shù)問題的無證書代理簽名方案[J].南京理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，34（6）：733-737.

[9]張俊茸，任平安，李文莉.一種新的無證書的代理環(huán)簽名方案[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（2）：63-65.

CHEN Lin

四川理工學(xué)院 計(jì)算機(jī)學(xué)院，四川 自貢 643000

College of Computer,Sichuan University of Science&Engineering,Zigong,Sichuan 643000,China

To reduce the computational costs,XU Chungen proposed a certificateless proxy signature scheme without pairing; ZHANG Junrong proposed a certificateless proxy ring signature scheme that combined the advantages of the certificateless cryptosystem,the proxy signature and the ring signature.By the cryptanalysis,the paper points out that XU's scheme has a seriously flaw in the proxy key generation algorithm,which results in an agent cannot generate a valid proxy signature;the ZHANG's scheme has the original signer's key compromise attack,the public key replacement attack and the anonymity defect.To address the above problems,two improved schemes are proposed to make up the deficiencies existed in the two signature schemes above,and their computing performance is better than their prototypes.

certificateless;proxy signature;ring signature;bilinear pairing;public key replacement attack

A

TP309

10.3778/j.issn.1002-8331.1109-0011

CHEN Lin.Cryptanalysis and improvement for two certificateless proxy signature schemes.Computer Engineering and Applications,2013,49（7）：85-88.

陳林（1971—），男，講師，主要研究方向：信息安全，計(jì)算機(jī)教育。Email：clin1971@yahoo.cn

2011-09-02修回日期：2011-10-30

1002-8331（2013）07-0085-04

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0928.074.html