◆韓英帥 崔新春

（曲阜師范大學信息科學與工程學院 山東276826）

基于離散對數(shù)的廣義環(huán)簽名算法

◆韓英帥 崔新春

（曲阜師范大學信息科學與工程學院 山東276826）

廣義環(huán)簽名是一種具有可轉換性質的特殊環(huán)簽名。在必要的條件下，它允許真實的簽名者通過透露關于環(huán)簽名的一些秘密信息來把環(huán)簽名轉換為普通簽名，從而撤銷了簽名的匿名性，證明自己就是簽名者。2008年，Ren和Harn首次提出了基于ElGamal算法的廣義環(huán)簽名，并聲稱該簽名方案是可轉換的。后來，王化群等人通過論證分析證實了上述方案并不滿足可轉換性。通過進一步分析，本文還發(fā)現(xiàn)原廣義環(huán)簽名存在安全漏洞。為此，本文在原廣義環(huán)簽名的基礎上加以改進，提出一種基于離散對數(shù)的廣義環(huán)簽名算法。改進后的新方案可以嚴格滿足可轉換性，并且安全性也得到了保障。

環(huán)簽名；可轉換性；合成函數(shù)；廣義環(huán)簽名

0 引言

目前，飛速發(fā)展的計算機技術和網(wǎng)絡通信技術使人們的工作和生活發(fā)生了質的改變，電子商務、電子政務等信息化活動蓬勃發(fā)展。人們在暢享便利的同時，對信息安全技術的要求也越來越高。作為傳統(tǒng)手工簽名的替代品，數(shù)字簽名已成為信息安全技術中一種重要的認證技術，在信息化活動中得到了廣泛的應用。普通的數(shù)字簽名僅用于保障信息傳輸中的數(shù)據(jù)認證性、完整性和不可否認性，這遠遠不能滿足實際應用中的需求。針對特定的應用環(huán)境，催生了許多具有特殊性質的簽名方案，如盲簽名、代理簽名、群簽名、環(huán)簽名[1-5]等。

2001年，Rivest等人[6]首次提出了基于RSA算法[7]的環(huán)簽名。環(huán)簽名因簽名中的某些參數(shù)可以首尾連接形成環(huán)而得名。環(huán)簽名允許一個成員代表一群成員進行匿名簽名，在生成簽名時，真實的簽名者利用自己的私鑰和其他環(huán)成員的公鑰進行簽名，但卻不需要獲得其他環(huán)成員的同意。對于任何一個驗證者，他們都會相信信息已經被簽名了，但是無法獲知誰是真實的簽名者。實質上，環(huán)簽名是一類帶有隱私考慮的類群簽名，它可以被很好地用來保護真實簽名者的身份，并克服了群簽名[8]方案中群管理員權利過大的缺點。作為一項匿名泄密技術，環(huán)簽名可以為需要長期保護的信息提供無條件的匿名性。目前，環(huán)簽名技術己經廣泛用于電子郵件、數(shù)據(jù)交換、電子交易和電子貨幣等領域[9-11]。

考慮到某些特定場景，尤其是在利益的誘使下，真實的簽名者可能需要公布自己的身份。比如在匿名檢舉中，檢舉人想要檢舉某人但又不想讓別人知道是自己所為，這時候他可以利用環(huán)簽名來完成這一操作。一旦檢舉成功，檢舉人可能會獲得豐厚報酬，那么他需要拿出不可否認的證據(jù)來證實自己的身份。為此，Lee等人提出了可轉換的環(huán)簽名[12]。

對比于環(huán)簽名，可轉換的環(huán)簽名具有兩大優(yōu)勢：（1）真實的簽名者能夠提供不可否認的證據(jù)來證實環(huán)簽名由自己生成；（2）給定一個環(huán)簽名和一個公鑰集合，驗證者能夠證實該簽名是否是某個環(huán)成員產生的有效環(huán)簽名。

2008年，Ren和Harn[13]首次提出了基于ElGamal算法[14]的環(huán)簽名(簡稱RH算法)。與基于RSA算法的環(huán)簽名相比，RH算法做了如下改進：（1）全體環(huán)成員共享大素數(shù)p并且所有的計算都是在同一個域中進行的，因此可以避免擴展操作[6]；（2）通過聯(lián)合多用戶數(shù)字簽名，廣義多用戶環(huán)簽名可以用來實施跨組織參與的秘密信息泄露。這為信息的安全傳輸提供了更加強有力的保障；（3）RH算法是可轉換的，即它允許真實的簽名者通過透露不可否認的秘密信息來證實自己的身份。

但是，王化群等人[15]通過對RH算法的密碼學分析，發(fā)現(xiàn)RH算法并不能滿足可轉換性，因為任意環(huán)成員都可以宣稱對環(huán)簽名的所有權。通過進一步分析，本文證實RH算法也不具備安全性。為此，本文將對RH算法加以改進，得到一種安全的基于離散對數(shù)的廣義環(huán)簽名算法。

1 RH方案概述及其漏洞分析

1.1 RH方案概述

在ElGamal算法中，p是一個大素數(shù)，g是中的生成元，并且 p、g被公開。簽名者隨機選取私鑰 d ∈Zp-1，公鑰由計算獲得，私鑰d需要嚴格保密。

給定需要被保護的信息 m，簽名者隨機選取一次性私鑰

l∈ Zp-1，然后生成簽名：

(α,β)即為 m的有效簽名，其有效性可以通過等式（3）來驗證：

相較于基于RSA算法的環(huán)簽名，RH算法中的全體環(huán)成員共享大素數(shù)p，并且所有的計算都是在同一個域中進行的，因此RH算法不涉及擴展操作，這對應著RH算法的第一個改進之處。廣義環(huán)簽名的構建需要存在性偽造，而ElGamal算法正是一類帶有通用報文攻擊的存在性偽造算法[14，16]。在著名的雙參數(shù)偽造簽名過程中，真實的簽名者給其他的環(huán)成員隨機選取然后計算：

這樣就得到了信息mi的一個有效簽名

在RH算法中，假定存在一個抗碰撞的哈希函數(shù)h，即不存在兩個不同的信息經過哈希函數(shù)處理后而得到相同的哈希值。下面，給出RH算法中的環(huán)簽名算法和環(huán)驗證算法。

圖1 RH算法中的函數(shù)拓撲關系

Step1：Bs隨機均勻地選取一個膠值（即初始值）v∈Zp；

Step3：為Bs設定下標簽is，然后計算

上式中出現(xiàn)的下標簽都屬于Zn，因此有為了構成環(huán)，令則有該過程如圖2所示。

圖2 RH算法構成的環(huán)

Step5：生成環(huán)簽名：

容易看出，m的環(huán)簽名σ為一個(4n+2)元組。

環(huán)驗證算法(m,)σ：對于環(huán)簽名σ，驗證者可以進行如下驗證。

若成立，驗證者認為環(huán)簽名有效，否則拒絕。

1.2 RH環(huán)簽名方案的漏洞分析

在RH算法中，作者宣稱自己的環(huán)簽名算法是可轉換的。后來，王化群等人對 RH算法提出了一種攻擊方法[15]。通過密碼學分析，RH算法并不能滿足可轉換性，因為所有環(huán)成員都有能力宣稱對環(huán)簽名的所有權。本文通過進一步分析發(fā)現(xiàn)，RH算法缺乏安全性，這就說明RH算法不是安全可轉換的。

如果Bi是真實的簽名者，即Bi=Bs，不用通過計算，他就能知道sα的離散對數(shù)l，因為l是他自己隨機選取的。因此他可以向驗證者證實自己的身份，從而實現(xiàn)了環(huán)簽名向普通簽名的轉換。然而，一旦泄露了真實簽名者的秘密信息l，攻擊者就會通過β的生成式：

計算出簽名者的私鑰ds。由此看來，RH環(huán)簽名方案缺乏安全性。

如果Bi不是真實的簽名者，即Bi≠Bs，他仍然可以宣稱自己是真實的簽名者。因為通過（3）式可以求得：

進一步就可以計算：

這樣看來，其他環(huán)成員也可以通過提供li宣稱自己是真實的簽名者。

通過以上分析得出，RH算法既缺乏安全性，又不能滿足可轉換性?？梢姡琑H算法存在嚴重的漏洞。

2 一種新的可轉換的廣義環(huán)簽名算法

本文針對RH算法中出現(xiàn)的問題加以改進，得到一種新的可轉換的廣義環(huán)簽名算法。

在改進過程中，本文繼續(xù)沿用RH算法中的一些概念。具體步驟如下：

Step1：Bs隨機均勻地選取一個膠值（即初始值）v∈Zp；

Step3：Bs隨機選取r∈Zp，然后計算：

為Bs設定下標簽is，并計算

上式中出現(xiàn)的下標簽都屬于Zn，因此有為了構成環(huán)，令則有

利用（8）式生成 mis的簽名；

Step5：生成環(huán)簽名：

新算法生成的環(huán)簽名σ為一個(4n+3)元組。

環(huán)驗證算法(m,)σ：對于環(huán)簽名σ，驗證者可以進行如下驗證。

Step2：驗證環(huán)等式：

若成立，驗證者認為環(huán)簽名有效，否則拒絕。

改進后的算法是可轉換的，因為它可以滿足環(huán)轉環(huán)算法和環(huán)驗證算法。

環(huán)轉換算法：在需要公布自己隱匿身份的情況下，Bs可以通過透漏自己的秘密信息(r,x)把環(huán)簽名轉換為普通簽名。

Step1：驗證者首先驗證（14）式是否成立。若成立，驗證者可以通過比較和在es沒有參加運算的情況下來指出Bs是真實的簽名者。

環(huán)轉換驗證算法：獲知了秘密信息(r,x)，驗證者可以對環(huán)簽名的有效性做如下驗證：

Step1：驗證者首先驗證：

是否成立，若成立，則繼續(xù)下一步驗證，否則拒絕。

Step2：然后，驗證者驗證（14）和（16）是否成立，若成立，則接受環(huán)簽名，否則拒絕。

3 算法分析

3.1 可轉換性分析

本文基于RH算法加以改進，改進后的新算法嚴格滿足可轉換性，具體分析如下：

（1）無條件匿名性：新算法具有和 RH算法類似的功能，即能給真實的簽名者提供無條件的匿名性。對于新算法生成的環(huán)簽名σ，任意的都能滿足（3）式。因為所有環(huán)成員之間的關系呈環(huán)狀分布，所以能夠滿足環(huán)等式（18）。因此對于環(huán)外驗證者來說，能夠準確猜出真實簽名者的概率不超過1/n，而環(huán)內非真實簽名者能夠準確猜出的概率不大于1/(n-1)。

（2）不可偽造性：在隨機預言模型[13]（Random Oracle Model， ROM）中，任何偽造算法A（通過多項式次分析其他信息的環(huán)簽名就可以以不可忽略的概率產生對于m'的環(huán)簽名），都可以轉換為新的算法 B（可以以不可忽略的概率對于隨機的輸入m'來求 fi的逆）。但是，本文設計的 fi是基于雙線性映射對的。而對于雙線性對的求逆，至今還沒有找到切實可行的計算方法。因此，新方案滿足不可偽造性。

（3）對于非真實簽名者的不可轉換性：如果Bi不是真實的簽名者，即Bi≠Bs，他將不能證明自己是真實的簽名者。即使Bi獲知了Bs的秘密信息(r,x)，他會做如下計算：

通過以上分析，新算法滿足了對于可轉換的環(huán)簽名的三條約束：無條件匿名性、不可偽造性和對于非真實簽名者的不可轉換性，故新算法是可轉換的。

3.2 安全性分析

在RH算法中，真實的簽名者一旦泄露了自己的秘密信息l，那么攻擊者就可以通過（11）式來獲得簽名者的私鑰ds。這一個環(huán)簽名算法來說，顯然是不允許的。本文對RH算法加以改進，以秘密信息(r,x)代替l。這樣即使攻擊者獲得了秘密信息(r,x)，但由于哈希函數(shù)的單向性，他也無法獲得簽名者的私鑰ds。由圖3可知，l和ds都需要嚴格保密，二者有一個被獲取，另一個也會被攻破。

圖3 l和ds的關系

基于以上分析可以看出新算法是安全的。由于新算法是基于RH算法進行改進的，因此同樣滿足定理[13]：基于ElGamal算法的廣義環(huán)簽名對于ROM中的適應性選擇消息攻擊是安全的。

4 結束語

廣義環(huán)簽名允許在必要的條件下能夠撤銷真實簽名者的匿名性，它是一種具有可轉換性質的環(huán)簽名。本文分析了RH算法，發(fā)現(xiàn)該算法不滿足可轉換性，而且存在安全漏洞。為此，本文對RH算法加以改進，改變真實簽名者的秘密信息值，使新算法真正達到安全可轉換的目的。最后，本文對新算法進行了可轉換性分析和安全性分析，二者均達到了預期的要求。

[1]Bender A,Katz J,Morselli R． Ring signatures： Stronger definitions,and constructions without random oracles[C]//TCC，2006．

[2]Boyen X． Mesh Signatures：How to Leak a Secret with Unwitting and Unwilling Participants[J]．Eurocrypt，2007．

[3]楊華杰， 繆祥華， 朱海韜．一種高效無證書可追蹤環(huán)簽名方案[J]．信息安全與技術，2014．

[4]Fujisaki E，Suzuki K． Traceable Ring Signature[J]． IEICE Transactions on Fundamentals of Electronics Communications &Computer Sciences，2007．

[5]張春生，蘇本躍，姚紹文．無雙線性配對的無證書代理環(huán)簽名方案[J]．計算機應用研究，2013．

[6]Rivest R L,Shamir A,Tauman Y．How to Leak a Secret[M]//Advances in Cryptology—ASIACRYPT，2001．

[7]Rivest R L．A method for obtaining digital signatures and public-keycryptosystems[J]．Communica tions of the Acm,1978．

[8]Harn L．Group-oriented (t,n) threshold digital signature scheme and digital multisignature[J]．IEE Proceedings - Computers and Digital Techniques，1994．

[9]Xiao J,Zeng G,Liao J,et al．Improved Threshold Ring Signature for Ad-Hoc Group[C]//International Conference on Wireless Communications, NETWORKIN G and Mobile Computing．IEEE,2006．

[10]Abe M,Ohkubo M,Suzuki K．1-out-of-n Signatures from a Variety of Keys[C]//International Conference on the Theory and Application of Cryptology and Information Security：Advances in Cryptology． Springer-Verlag,2002．

[11]Zhang F,Kim K．ID-Based Blind Signature and Ring Signature from Pairings[J]． Proc of Asiacrpt Lncs,2002．

[12]Lee,Wen,H-A,et al．Convertible ring signature[J]．Communications, IEE Proceedings,2005．

[13]Ren J,Harn L．Generalized Ring Signatures[J]．IEEE Transactions on Dependable & Secure Computing,2008．

[14]Elgamal T．A public key cryptosystem and a signature scheme based on discrete logarithms[J]．IEEE Transactions on Information Theory，2003．

[15]Wang H,Zhang F,Sun Y．Cryptanalysis of a Generalized Ring Signature Scheme[J]．IEEE Transactions on Dependable &Secure Computing，2009．

[16]Goldwasser S,Micali S,Rivest R L．A digital signature scheme secure against adaptive chosen-message attacks[M]．Society for Industrial and Applied Mathematics,1988．

教育部人文社科項目（No．11YJCZH021）；山東省自然科學基金面上項目（NO．ZR2016FM45）。