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

◆韓英帥 崔新春

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

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

◆韓英帥 崔新春

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

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

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

0 引言

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

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

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

對比于環(huán)簽名，可轉(zhuǎn)換的環(huán)簽名具有兩大優(yōu)勢：（1）真實的簽名者能夠提供不可否認(rèn)的證據(jù)來證實環(huán)簽名由自己生成；（2）給定一個環(huán)簽名和一個公鑰集合，驗證者能夠證實該簽名是否是某個環(huán)成員產(chǎ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算法是可轉(zhuǎn)換的，即它允許真實的簽名者通過透露不可否認(rèn)的秘密信息來證實自己的身份。

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

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

1.1 RH方案概述

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

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

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

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

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

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

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

圖1 RH算法中的函數(shù)拓?fù)潢P(guān)系

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

Step3：為Bs設(shè)定下標(biāo)簽is，然后計算

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

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

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

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

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

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

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

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

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

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

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

進一步就可以計算：

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

通過以上分析得出，RH算法既缺乏安全性，又不能滿足可轉(zhuǎn)換性?？梢?，RH算法存在嚴(yán)重的漏洞。

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

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

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

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

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

為Bs設(shè)定下標(biāo)簽is，并計算

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

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

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

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

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

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

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

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

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

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

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

Step1：驗證者首先驗證：

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

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

3 算法分析

3.1 可轉(zhuǎn)換性分析

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

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

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

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

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

3.2 安全性分析

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

圖3 l和ds的關(guān)系

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

4 結(jié)束語

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

[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]．信息安全與技術(shù)，2014．

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

[5]張春生，蘇本躍，姚紹文．無雙線性配對的無證書代理環(huán)簽名方案[J]．計算機應(yīng)用研究，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）；山東省自然科學(xué)基金面上項目（NO．ZR2016FM45）。