基于离散对数的广义数字签名算法研究

丁家琳

摘    要： 回顾了Ren-Harn的广义环签名算法，但Ren-Harn的广义环签名并不能满足可转化性的定义。以Ren-Harn的方案为基础，提出了基于时间戳的Ren-Harn算法，即在算法中引入时间戳变量，同时构造出双线性映射的单向陷门函数。通过环签名算法的验证，改进方案不仅严格满足可转化性的定义，而且具有很好的安全性。在保障真实签名者对于环签名的独创性，防止信息的恶意篡改等方面有很深远的影响和意义。

关键词：环签名;可转化性;合成函数;广义环签名;时间戳

中图分类号：TP751                                            文献标识码：A

Study of General Digital Signature Algorithm Based

on Discrete Logarithm

DING Jia-lin?

（Network Security Division，Liaoning Province Meteorological Information Center，Shenyang， Liaoning 110166，China）

Abstract： The Ren-Harn generalized ring signature algorithm is reviewed， but the Ren-Harn generalized ring signature can't meet the definition of the transformation. On the basis of Ren-Harn scheme， the new Ren-Harn algorithm based on time stamp is proposed， and the variable of the time stamp in the algorithm is introduced. At the same time， the one-way trapdoor function of bi-linear mapping is constructed. Through the verification of ring signature algorithm， the improved scheme not only satisfies the definition of convertible strictly， but also has good security. It has a far-reaching influence and significance in the protection of the real signer for original ring signature， preventing the information from malicious tampering.

Key words：ring signature;convertibility;combining function;generalized ring signature;time stamp

2008年，Ren和Harn首次提出了基于ElGamal签名方案的广义环签名方案[1]。然而，王华群等人通过对广义环签名的密码分析，最后证明Ren和Harn的方案并不能滿足环签名的可转化特征[2-3]。因为每一个环成员都有能力宣称是自己产生的签名。但这并不意味着Ren和Harn的方案彻底失败了，广义环签名的提出本身就对密码学的发展起到了很大的促进作用。文中对Ren和Harn的方案加以改进，提出了基于时间戳的Ren-Harn算法，最终使得广义环签名满足可转化性。改进后的方案能够保障只有真实的签名者才有能力向验证者证实签名是自己生成的。

1   基础预备知识

对一些符号进行说明并简要阐释一些基本定义。

假定Bob想为信息m产生一个包含n个环成员（B1，B2，…，Bn）的环签名，其中Bob为Bs（1≤s≤n）。每一个环成员都拥有一个公钥-私钥对（Pi，Si）。

1.1   基本定义

定义1：（环签名）环签名方案是由以下两大算法组成的：

环签名算法（m，P1，P2，…，Pn）：已知信息m和n个环成员的公钥P1，P2，…，Pn，真实的签名者Bs能够使用自己的私钥Ss和其他环成员的公钥生成一个环签名σ。

环验证算法（m，σ）：已知信息m和环签名σ，又由于各个环成员的公钥都是公开的，验证者完全能够判断（m，σ）是否是一个有效的签名。

定义2：（可转化的环签名）如果一个环签名还包含以下两大算法就被称作可转化的环签名：

环转化：真实的签名者能够向验证者提供不可抵赖的证据以证实环签名是由自己而不是由其他的环成员产生的。

环转化验证：给定一个环签名（m，σ′）和一组环成员的公钥集合（P1，P2，…，Pn），验证者能够证实该签名是不是有环成员Bs产生的。

对于可转化的环签名有以下三点安全要求：

（1）签名者匿名性：验证者能够正确猜出签名者身份的概率仅为1/n;

（2）不可伪造性：任何一个非环成员都不可以伪造签名;

（3）对于非真实签名者的不可转化性：任何一个环成员Bi（i≠s），都无法将环签名转化为普通的数字签名。

定义3：（合成函数）合成函数Ck，v（y1，y2，…，yn）把一个密钥值k，一个初始化值v和一组任意值y1 = g1（x1），y2 = g2（x2），…，yn = gn（xn）∈{0，1}b当做输入，其中g1，g2，…，gn为陷门函数。它最终输出一个值z∈{0，1}b。因此，对于任意给定的k，v，s（1≤s≤n）和任意输入的定值yi（i≠s），合成函数相当于一个从ys到z的一对一映射。而且，这个映射还是高效可执行的。但是如果不知道私钥和陷门函数g1，g2，…，gn的反函数的话，将很难进行对于x1，x2，…，xn的验证方程。

参考文献[1]中的合成函数：

2   回顾Ren-Harn的广义环签名方案

首先回顾文献[8]中的Ren-Harn的广义环签名方案（以下简称Ren-Harn方案），然后给出了该方案的不足，即该方案并不能满足Ren-Harn所声称的可转化性[2]。

2.1   Ren-Harn方案

2008年，Ren-Harn提出了基于ElGamal签名方案的环签名，他们把它称为广义环签名，并声称该方案是可转化的。

在一个ElGamal签名方案中，p是一个大素数，g是Zp中的生成元，并且p、g被公开。签名者为自己随机选取私钥d∈Zp-1，那么公钥就可以通过e = gdmodp计算得出，私钥d需要保密。

假如m是需要被签名的信息，签名者随机从Zp-1中选取一个一次性秘密值l并且计算出α =  glmodp，β = （m - dα）l-1mod（p-1）。这样我们就可以把（α，β）当做信息m的有签名，签名的有效性可以通过验证式gm = eααβ来进行判断。

在Ren-Harn环签名方案中，定义gi（ai，bi） = （mi，αi，βi），这样会很容易计算扩展陷门置换gi的逆。但是如果我们将gi与工程映射pi（在这里有pi（mi，αi，βi） = mi）结合在一起，那么将很难计算fi = pi·gi的逆。事实上，fi是基于双线性映射Zp-1 × Z*p-1 →Zp-1的单向陷门函数[3]。通过图1更有助于我们理解fi、pi、gi三者之间的关系：

在Ren-Harn方案中，不再需要对称加密算法E，但是我们同样需要一个被公共定义的抗碰撞的hash函数h。下面，我们将呈现Ren-Harn方案中的环签名算法和环验证算法：

环签名算法：（m，e1，e2，…，en，ds，s）：m为将要被签名的信息，ds为签名者的私钥，e1，e2，…，en为各个环成员的公钥，签名者按如下步骤计算环签名：

1.选取密钥值：签名者Bs首先计算对称密钥值k = h（m），k值在这里其实就是信息m经过hash函数处理后的摘要值。签名者可以直接对k进行签名。

2.随机选取胶值：签名者随机选择一个初始化值v∈Zp。

3.为信息mi生成伪造签名（αi，βi）：真实的消息签名者任意选择ai∈Zp-1，bi∈Z*p-1（其中i = 1，2，...，n，i≠s），那么签名（αi，βi）可以从获得gi（ai，bi） = （mi，αi，βi）获得。

4.求解m：假设真实的签名者所签名信息的下标为is。令

上面所有式子里面出现的下标都属于Zn。因此，我们有v= v。为了形成一个环，令vm = v，这样可以得到m= v v，如图2所示。

5.利用签名者的陷门信息对m签名[4]：真实的签名者Bs首先随机选择l∈Z *p，但要求l和p - 1互素。这样m的签名为（αi，βi） = （glmodp（m- diαi）l-1mod（p-1）。

6.輸出环签名：信息m的签名被定义为（4n+2）元组，即σ = （e1，e2，…，en;i0，v，m1，m2，…，mn;α1 β1，α2 β2，…，αn βn;），其中i0∈Z n。

环验证算法（m，σ）：对于信息m的环签名σ =（e1，e2，…，en;i0，v，m1，m2，…，mn;α1 β1，α2 β2，…，αn βn），验证者可以按照如下步骤进行验证：

1.验证陷门置换[4]：验证者首先验证等式gmi=eαi

i  modp（i = 1，2，...，n）是否成立。如果等式成立，继续下一步验证，否则退出验证。

2.验证环等式：验证者验证等式：

v= h是否成立。若成立，验证者认为环签名有效，否则拒绝。

环签名的可转化性是基于离散对数知识的[5]，其中有l = logαs，l 是由真实的签名者Bs在生成环签名时随机从Z *p选取的。由αs计算l是一个DLP（离散对数问题），这在数学上还没有有效地解决方法。Ren-Harn在自己的方案中声称只有真实的签名者才知道αs的离散对数l，因此他能够向验证者证实自己的身份，而其他的环成员都做不到。接下来，我们将呈现这一结论是的不成立性，所有的环成员都可以向验证者宣布自己是真实的签名者。

2.2   Ren-Harn方案的不足

在文献[6]中，Ren-Harn声称自己的广义环签名是可转化的，即他们认为他们的方案能够通过可转化环签名定义中要求的环转化和环转化验证两大算法。但是王华群等人[6-7]对Ren-Harn方案提出了一种攻击方法。通过密码分析，我们看到Ren-Harn的环签名并不能满足可转化性，因为环里的每个成员都有能力通过公布秘密信息来声称是自己生成的环签名。这也就意味着Ren-Harn的方案失败了。

如果Bi是真实的签名者，即Bi = Bs，那么不用计算，他就能知道αs的离散对数l，因为l是他自己随机选取的。因此他可以向验证者证实自己的身份，从而实现了环签名向普通签名的转化。

如果Bi不是真实的签名者，他仍然可以宣布自己是真实的签名者。因为他能够通过gmi= eαi

i  eβi

i  modp得到mi = diαi + li βimod（p-1），进一步就可以计算li = （mi - diαi）β-1

i  mod（p-1）。这样的话，任何非真实的签名者也可以通过提供l来声称自己是真实的签名者，攻击方法成功。

从以上的密码分析来看，Ren-Harn的方案是不安全的，即对于非真实签名者的不可转化性。

3   改进后的方案及安全性分析

3.1   改进后的方案

在这一部分，对Ren-Harn方案加以改进，引入时间戳变量t，即基于时间戳的Ren-Harn方案[7]，使其满足可转化性。

在改进的过程中，我们继续沿用Ren-Harn方案中的一些概念。具体方案如下：

环签名算法：（m，e1，e2，…，en，ds，s）：m为将要被签名的信息，ds为签名者Bs的私钥，e1，e2，…，en为各个环成员的公钥，签名者按如下步骤计算环签名：

1.计算信息摘要值：k = h（m）;

2.随机选取胶值（初始化值）：签名者Bs随机选取初始化值v∈Zp。

3.为信息mi生成伪造签名（αi，βi）：真实的消息签名者任意选择ai∈Zp-1，bi∈Z*p-1（其中i = 1，2，...，n，i≠s），那么签名（αi，βi）可以从获得gi（ai，bi） = （mi，αi，βi）獲得。

4.求解m：签名者Bs随机选取初始化值r∈Zp，计算t = h（e1‖e2‖…‖es - 1‖es + 1‖…‖en，r）。假设真实的签名者所签名信息的下标为is。令

v= h（m‖t，v），

v= h（m‖t，vm），

v= h（m‖t，vm），

v= h（m‖t，vm），

上面所有式子里面出现的下标都属于Zn，有v= v。为了形成一个环，令vm = v，这样可以得到m= vv。

5.利用签名者的陷门信息对m签名：真实的签名者Bs随机选择x∈Z *p-1，计算l = h（x，es），要求gcd（l，p - 1） = 1，那么对m产生的签名为（αi，βi） = （glmodp（m- diαi）l-1mod（p-1）。

6.输出环签名：信息m的签名被定义为（4n+3）元组，即σ = （e1，e2，…，en;i0，v，m1，m2，…，mn;α1 β1，α2 β2，…，αn βn;t），其中i0∈Z n。

环验证算法（m，σ）：对于信息m的环签名σ =（e1，e2，…，en;i0，v，m1，m2，…，mn;α1 β1，α2 β2，…，αn βn;t），验证者可以按照如下步骤进行验证：

1.验证陷门置换：验证者首先验证等式gmi= eαi

i

eβi

i  modp（i = 1，2，...，n）是否成立。如果等式成立，继续下一步验证，否则退出验证。

2.验证环等式：验证者验证等式：

v= h是否成立。若成立，验证者认为环签名有效，否则拒绝。

提出的基于时间戳的Ren-Harn方案是满足可转化性的，具体验证过程如下：

环转化算法：有些时候，真实的签名者Bs需要向验证者证明自己的身份。因此，他必须通过公布自己的秘密信息（r，x）来把无条件匿名的环签名转化为普通签名。

1.验证者首先验证t = h（e1‖e2‖…‖es - 1‖es + 1‖…‖en，r）是否成立，若成立，验证者可以通过比较e1，e2，…，es - 1，es + 1，…，en和e1，e2，…，en在es没有参加运算的情况下来指出Bs是真实的签名者。

2.因为x∈Z *p-1，l = h（x，es），gcd（l，p - 1） = 1，Bs

能够通过秘密值x来证实自己是真实的签名者。其他的环成员Bi（i≠s）即使能够通过文献[8]中的攻击方法求得Ii，但由于哈希函数h的单向性，仍然无法获得秘密值x。

环转化验证算法[8]：知道了秘密信息（r，x），验证者可以按照以下步骤来验证环签名的有效性：

1.首先，验证者验证（e1，e2，…，es - 1，es + 1，…，en）∈σ = （e1，e2，…，en;i0，v，m1，m2，…，mn;α1 β1，α2 β2，…，αn βn;t），是否成立，若成立，则认为环签名有效，否则拒绝。

2.然后，验证者验证t = h（e1‖e2‖…‖es - 1‖es + 1‖…‖en，r）和l = h（x，es）是否成立，若成立。则接受签名，否则拒绝。

3.2   安全性分析

在Ren-Harn方案的基础上，通过引入时间戳变量，使Ren-Harn方案得到改进，进而满足可转化性的定义，因此我们的方案是安全的。

如果Bi是真实的签名者，即Bi = Bs，那么他可以通过公布自己的秘密信息（x，r）来实现从环签名向普通签名的转化，也就证实了自己的身份。但是如果他不愿意透露秘密信息，任何人都无法知道是他产生了签名。

如果Bi不是真实的签名者，即Bi≠Bs，他不能证明自己是真实的签名者。即使Bi知道了Bs的秘密信息（x，r），他会计算t′ =  h（e1‖e2‖…‖ei - 1‖

ei + 1‖…‖en，r）和l′ = h（x，ei），很明显t′≠t，并且αi= gl′modp，αi[∈] σ = （e1，e2，…，en;i0，v，m1，m2，…，mn;α1 β1，α2 β2，…，αn βn;t），故非签名者βi无法证实自己是真实的签名者。

經过以上分析，看到新方案满足对于可转化的环签名的三点安全要求。由于该方案是基于Ren-Harn方案进行改进的，因此改进后的方案同样满足该定理[9]：基于ElGamal签名方案的广义环签名对于随机预言模型（ROM）中的适应性选择消息攻击是安全的。

4   结   论

广义环签名是一种时新的并且非常实用的签名。文中主要针对Ren-Harn方案的不足进行了改进。经过验证，基于时间戳的Ren-Harn方案是可转化性的，也就是说新方案能够保障真实的签名者对于环签名的独创性，它严格拒绝任何非签名者来对环签名进行转化。

参考文献

[1]   BENDER A，KATZ J，MORSELLI R，et al.Ring signatures：stronger definitions，and constructions without random oracles[J]. Journal of Cryptology，2008，30（9）：114-138.

[2]   BOYEN X.Mesh signatures：how to leak a secret with unwitting and unwilling participants，Proceedings of the 26th International Conference on the Theory and Applications of Cryptographic Techniques[J]. Cryptology-Eurocrypt，2007，2013，13（2）： 210-217.

[3]   LEE K，WEN H，HANG T，et al. Convertible ring signature[J].IEEE Proceedings Communications，2003，19（4）： 251-260.

[4]   WANG C，LIU Y.A new ring signature scheme with signer-admission property[J]. Information Sciences，2007，78（6）： 747-754.

[5]   REN J，HARN L.Generalized ring signatures，IEEE Transactions on Dependable[J]. Secure Computing，2008，85（8）： 155-163.

[6]   RIVEST L，SHAMIR A，TAUMAN Y，et al.How to leak a secret，Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security[C]. Advances in Cryptology-Asiacrypt，2011，15（6）：552-565.

[7]   WANG H，ZHANG F，SUN Y，et al. Cryptanalysis of a generalized ring signature scheme，IEEE Transactions on Dependable[J]. Secure Computing，2009，26（2）：149-151.

[8]   ELGAMAL A.A public-key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory，2015，80（12）：469-472.

[9]   GOLDWASSER S，MICALI S，RIVEST L，et al. A digital signature scheme secure against adaptive chosen-message attacks[C].SIAM Journal on Computing Special Issue on Cryptography，2017，90（12）：125-140.