陈林

两种无证书代理签名的密码学分析及改进

陈林

为了降低计算开销，许春根提出一种无对运算的无证书代理签名方案；张俊茸提出一种无证书代理环签名方案，融合了无证书密码体制、代理签名和环签名的优点。分析指出，许春根方案的代理密钥产生算法存在严重缺陷，致使代理人无法进行有效签名；张俊茸方案存在原始签名人密钥泄露及仿冒授权攻击、公钥替换攻击和匿名性缺陷。针对上述问题，提出了改进方案，弥补了已有方案的安全缺陷，且计算性能较优。

无证书；代理签名；环签名；双线性对；公钥替换攻击

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