兩種無證書代理簽名的密碼學分析及改進

陳林

兩種無證書代理簽名的密碼學分析及改進

陳林

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

無證書；代理簽名；環簽名；雙線性對；公鑰替換攻擊

1 引言

無證書的公鑰密碼體制由Al-Riyamih等人[1]首次提出，被用于解決基于身份公鑰密碼體制中的密鑰托管問題，它同時又繼承了基于身份公鑰密碼體制的優點，不使用公鑰證書，避免了基于證書公鑰系統的證書管理負擔。隨后幾年中，無證書的公鑰密碼體制得到了國內外研究者的廣泛關注。

代理簽名的概念由Mambo等人[2]提出，是指原始簽名人把他的簽名權授給代理人，代理人代表原始簽名人行使他的簽名權。代理簽名已廣泛應用于移動代理系統、電子商務、電子拍賣等領域，其實用性較強，是數字簽名領域研究的熱點課題之一。代理簽名的研究方向主要有：將代理簽名概念進行延伸提出新的數字簽名，如多重代理簽名、代理環簽名等；將代理簽名與其他密碼體制相結合，如代理盲簽名、門限代理簽名和無證書代理簽名等。

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

本文對XZHD方案[8]和ZRL方案[9]進行了密碼學分析，指出了這兩種方案的安全缺陷，并進行了相應改進。分析表明，改進方案是安全的，且計算性能較優。本文研究工作基于無證書密碼體制、雙線性映射理論和相關困難問題假設，相關理論背景請參考文獻[1，8-9]。

2 XZHD簽名方案分析與改進

2.1 XZHD無證書代理簽名方案

XZHD方案[8]是一種基于離散對數問題的無證書代理簽名方案，由系統生成、密鑰產生、代理密鑰產生、代理簽名和驗證5個算法構成，這里簡單描述如下：

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

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

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

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

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

2.2 XZHD無證書代理簽名方案缺陷分析與改進

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

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

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

針對這一問題，本文首先對代理密鑰產生算法做以下修改：

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

修改后算法的正確性由下式驗證：

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

3 ZRL簽名方案的分析與改進

3.1 ZRL無證書代理環簽名方案

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

系統生成：產生并發布系統參數 param={Gl，G2，e，q，P，P0，H1，H2}。其中，Gl是階為q的加法循環群，生成元為P；G2是階為q的乘法循環群；e:Gl×Gl→G2是雙線性映射；P0=sP為KGC的公鑰，對應的s∈是KGC的主密鑰；H1:{0，1}*→G1和H2:{0，1}*→是安全的散列函數。

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

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

代理簽名：當要對消息m進行簽名時，代理簽名人B按以下步驟執行：

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

3.2 ZRL無證書代理環簽名方案安全性分析

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

3.2.1 原始簽名人密鑰泄露及仿冒授權

在代理密鑰產生算法中，只要獲取Sw，任意實體均可通過下式計算得到原始簽名人A的代理授權密鑰：

當產生新的代理密鑰時，攻擊者產生新的代理授權許可信息w′，計算Sw′=H2(w′)(xaP0+Sa)=H2(w′)Sw/H2(w)并發送(w′，Sw′)發送給代理簽名人。代理簽名人可通過下式驗證等式：

可見攻擊者成功仿冒原始簽名人A產生了代理授權。

3.2.2 公鑰替換攻擊

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

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

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

驗證者計算：

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

3.2.3 密鑰托管

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

首先，AII敵手通過下式計算代理授權簽名：

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

“國……國亡了！我……我也……老了！你們還年青，你們去救國吧！我的老骨頭再……再也不中用了！我是個老亡國奴，我不會眼見你們把日本旗撕碎，等著我埋在墳里……也要把中國旗子插在墳頂，我是中國人！我要中國旗子。我不當亡國奴，生是中國人，死是中國鬼……不……不是亡……亡國奴……“

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

3.2.4 匿名性缺陷

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

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

3.3 ZRL無證書代理環簽名方案改進

3.3.1 改進方案

本文對ZRL簽名方案進行如下改進。

系統生成：與原方案相同。

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

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

代理簽名：當要對消息m進行簽名時，代理簽名人B按以下步驟執行。

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

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

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

3.3.2 改進方案分析

（1）分析改進方案的正確性

改進方案代理密鑰授權驗證的正確性可通過下列等式證明：

簽名及簽名驗證的正確性由下式證明：

（2）分析改進方案的安全性

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

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

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

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

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

針對3.2.3小節中描述的安全缺陷，本文在原方案的基礎上增加了臨時參數ta和ha，由于ha與L無關，雖然hi與Pi一一對應，但是，通過最終簽名結果和簽名驗證公式，不能確定hb（只能得到b∈{1，2，…，n}），所以不能確定Pb和IDb。可見改進后的代理環簽名方案實現了真正的匿名性。

（3）分析改進方案的計算性能

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

4 結束語

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

[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].軟件學報，2009，20（3）：692-701.

[5]孫士鋒，溫巧燕.對一類無證書強代理簽名方案的攻擊及改進[J].北京郵電大學學報，2010，33（1）：80-83.

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

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

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

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

CHEN Lin

四川理工學院 計算機學院，四川 自貢 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—），男，講師，主要研究方向：信息安全，計算機教育。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