兩個前向安全的代理簽名方案的安全性分析

（1.華中科技大學(xué)計(jì)算機(jī)學(xué)院信息安全系， 武漢 430074； 2. 武漢工業(yè)學(xué)院計(jì)算機(jī)系， 武漢 430023）



摘 要：

針對最近一些學(xué)者提出的前向安全的代理簽名方案和改進(jìn)的前向安全的代理簽名方案，給出了這兩種代理簽名方案的安全性分析，并指出它們是不安全的，均不具備前向安全性質(zhì)。當(dāng)代理人的私鑰泄露后，前向安全的代理簽名方案不能抵抗偽造攻擊;而改進(jìn)的前向安全的代理簽名方案對攻擊者來說僅利用公開的信息就可以實(shí)施偽造攻擊。

關(guān)鍵詞：前向安全; 代理簽名； 偽造攻擊； 安全分析

中圖分類號：TP309 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)02-0709-02





Security analysis of two forward secure proxy signature schemes



XIA Xiang-sheng1，2，HONG Fan1， CUI Guo-hua1

 (1.Dept.of Information Security， College of Computer Science， Huazhong University of Science Technology， Wuhan 430074，China; 2.Dept.of Computer， Wuhan Polytechnic University， Wuhan 430023，China)



Abstract:Recently， some researchers proposed a forward secure proxy signature scheme and an improved forward-secure proxy signature scheme. This paper analyzed the security of the two proxy signature schemes and pointed out they were insecure and had not the characteristic of forward security at all. The first scheme couldn’t resist forgery attack while the secret key of the proxy signer was lost. If adversary knew some public information of the second scheme， he/she could forge proxy signature.

Key words：forward security;proxy signature;forgery attack; security analysis



代理簽名是指原始簽名人將自己的簽名權(quán)利委托給代理簽名人，由代理簽名人代表原始簽名人產(chǎn)生代理簽名，其有效性由驗(yàn)證人驗(yàn)證和確認(rèn)。自Mambo等人于1996年首次提出代理簽名方案[1，2]以來，人們對代理簽名的研究非常關(guān)注，取得了豐富的成果，已提出了許多代理簽名方案，如代理環(huán)簽名[3]、代理多重簽名[4]、門限代理簽名[5]等。一個代理簽名至少應(yīng)滿足可驗(yàn)證性、不可偽造性、可區(qū)分性、不可否認(rèn)性等安全性質(zhì)。代理簽名在電子現(xiàn)金、電子投票、移動代理及電子商務(wù)等方面有廣泛的應(yīng)用。

但是，代理簽名密鑰或私鑰的泄露，將會給系統(tǒng)帶來災(zāi)難性的后果。為了將損失降低到最小，人們提出前向安全的簽名機(jī)制來解決此類問題，其本質(zhì)是數(shù)字簽名的風(fēng)險控制。 1997年，Anderson首次提出前向安全的概念[6]，前向安全數(shù)字簽名的基本方法是把簽名密鑰的有效期（如一年）分成T個周期，在每個周期內(nèi)使用不同的簽名密鑰產(chǎn)生簽名，而驗(yàn)證簽名的公鑰在整個有效期內(nèi)保持不變。即使當(dāng)前周期的簽名密鑰被泄露，此周期之前所產(chǎn)生的簽名依然有效。從而大大減輕了由于簽名密鑰泄露而給系統(tǒng)帶來的損失。2005年，王曉明等人首次將前向安全的概念引入代理簽名體制[7]，提出了一個前向安全的代理簽名方案；2007年，張曉敏等人提出了一個改進(jìn)的前向安全的代理簽名方案[8]。引入前向安全機(jī)制構(gòu)造前向安全的簽名方案成為研究熱點(diǎn)之一[9，10]。

本文詳細(xì)分析了文獻(xiàn)[7，8]的方案，發(fā)現(xiàn)它們都不具有真正的前向安全特性。王的方案雖然實(shí)現(xiàn)了授權(quán)密鑰的前向安全，但當(dāng)代理人的私鑰泄露后，任何人均可以實(shí)施偽造攻擊，從而不具有真的前向安全性質(zhì)。張的方案企圖對代理人的私鑰進(jìn)行進(jìn)化，以彌補(bǔ)王的方案只對代理簽名密鑰進(jìn)化的不足，但仍然不具備前向安全的性質(zhì)，是不安全的；攻擊者甚至不用知曉代理簽名人的私鑰，亦可成功實(shí)施偽造攻擊。

1 前向安全數(shù)字簽名相關(guān)知識 

1. 1 文獻(xiàn)[7]給出了前向安全的形式化定義

定義 若存在一個單向簽名密鑰更新算法KeyUd，使得簽名人可以在第i時間段將簽名密鑰由σi-1更新為σi=KeyUd(σi-1)，并在不同的時間段內(nèi)使用不同的簽名密鑰σi生成簽名sign(σi，m)(m是消息)，而任何驗(yàn)證人均可用固定的公鑰y及時間段的編號i驗(yàn)證等式ver[y，i，sign(σi，m)，m]=true成立，則簽名sign(σi，m)為一個前向安全數(shù)字簽名。

1. 2 前向安全數(shù)字簽名的密鑰進(jìn)化過程

前向安全數(shù)字簽名實(shí)現(xiàn)的一個關(guān)鍵問題是密鑰進(jìn)化，即尋找一個單向簽名密鑰更新算法KeyUd，使得簽名人可在第i時間段將簽名密鑰由σi-1更新為σi=KeyUd(σi-1)。但目前構(gòu)造方法單一，大多數(shù)基于

模合數(shù)平方剩余難題[11，12]，利用式σi=σ2i-1mod n（其中n為合數(shù)）將第i-1時間段簽名密鑰σi-1更新為第i時間段簽名密鑰σi。由于模合數(shù)平方剩余難題，即使σi泄露，也很難推出σi-1，從而保證簽名的前向安全性。如何尋找更多單向密鑰更新算法KeyUd來構(gòu)造前向安全數(shù)字簽名方案，仍將是一個值得研究的問題。

2 對王曉明等人所提方案的安全性分析 

2. 1 王曉明等人的前向安全代理簽名方案 

1）初始化階段 系統(tǒng)選擇一個安全的單向散列函數(shù)h(#8226;)和安全的大素?cái)?shù)p1、p2、p′1、p′2、q滿足：p1=2qp′1+1， p2=2qp′2+1， p1=p2=3 mod 4；令n=p1p2，在模n的平方剩余集合中選擇一個q階生成元g，公布(n，q，g，h)。原始簽名人A的身份標(biāo)志為IDA， A隨機(jī)選擇kA∈[1，n]作為私鑰，計(jì)算yA=gkAmod n作為公鑰，選擇(e，d)滿足gcd(e，Φ(n))=1， ed≡1(modΦ(n))，公布(IDA，YA，e)。代理簽名人B的身份標(biāo)志為IDB， B隨機(jī)選擇kB∈[1，n]作為私鑰，計(jì)算yB=gkBmod n作為公鑰，公布(IDB，yB)。

2）授權(quán)過程 A選擇時間周期1，2，…，T和代理終止時間t，計(jì)算σ0=ykAB mod n以及

Y=(σ2T+10yIDBA)-emod n，公布B為其代理簽名人及參數(shù)(T，Y，t， IDB)。B計(jì)算σ0=ykBA mod n并驗(yàn)證等式Y(jié)=(σ2T+10yIDBA)-emod n是否成立，如果等式成立，則σ0為代理簽名密鑰。

3)前向安全的代理簽名產(chǎn)生過程 在第j個簽名周期開始時，B計(jì)算σj=σ2j-1作為該時段的簽名密鑰，并刪除前一個時段的簽名密鑰σj-1，1≤j≤T。設(shè)待簽名消息為m，B隨機(jī)選擇αj，βj∈[1，n]，計(jì)算r=gαj2T-j+1mod n，z=σjgβjmod n， u=h(j‖m‖r2‖t)， s=αj-βje-kBu mod q，則前向安全的代理簽名為[j，(m，s，u，z，t)]。

4)前向安全的代理簽名的驗(yàn)證 驗(yàn)證人收到[j，(m，s，u，z，t)]后，首先驗(yàn)證t是否超過代理終止時間t如果超過，則認(rèn)為簽名無效；否則計(jì)算

r′=(gszeyuB)2T-j+1Y(yIDBA)emod n，然后驗(yàn)證等式u=h(j‖m‖r′‖z‖t)是否成立，若成立則代理簽名有效。

2. 2 對王曉明等人的前向安全代理簽名方案的分析 

該方案對σ0進(jìn)行進(jìn)化是沒有意義的。因?yàn)榇砣薆的私鑰kB在整個簽名過程中并沒有被刪除，一旦泄露，任何人都可以像B一樣計(jì)算σ0=ykBA mod n，進(jìn)而可以偽造任意時段j′的代理簽名。分析如下：

如果代理人B的私鑰kB泄露，那么攻擊者C就可以計(jì)算σ0=ykBA mod n，因?yàn)棣要﹋′=σ2j′0所以攻擊者C就可以偽造任意時段j′的代理簽名密鑰。在周期j′，C隨機(jī)選

因此，一旦代理簽名人B的私鑰kB泄露，任何人都可以偽造代理簽名，不誠實(shí)的代理人也可以否認(rèn)他的真實(shí)簽名，聲稱是其他人偽造他的簽名，從而使代理簽名不再具有不可偽造性、可區(qū)分性、不可否認(rèn)性等安全性質(zhì)。另外，即使像原始簽名人一樣知道σ0，不知道kB也無法偽造代理簽名，因此對σ0進(jìn)化是沒有意義的。

3 對張曉敏等人所提方案的安全性分析 

張方案是對王方案的改進(jìn)，張曉敏等人認(rèn)為王方案沒有對代理簽名者的私鑰作進(jìn)化，導(dǎo)致當(dāng)代理簽名者的私鑰泄露后不具有前向安全性；但沒有給出詳細(xì)的證明，并提出了一個對代理簽名者的私鑰作進(jìn)化的改進(jìn)方案。張曉敏等人聲稱他們的方案具有真的前向安全性質(zhì)，本文的分析顯示張方案也不具有前向安全性。

3. 1 張曉敏等人的改進(jìn)的前向安全代理簽名方案 

1）系統(tǒng)初始化 n、p1、p2、p′1、p′2、q、g、h(#8226;)如王方案所述，v∈Z*n是一隨機(jī)數(shù)，xA、xB∈Z*n分別是原始簽名者和代理簽名者的私鑰； yA=x-vAmod n， yB=x-vB mod n分別是對應(yīng)的公鑰，系統(tǒng)將密鑰有效期劃分為T個時段，系統(tǒng)的公開參數(shù)是(n，yA，yB，v，q，g，h(#8226;)，T)。

2）授權(quán)過程 原始簽名者A選擇代理終止時間t，指定B為其代理簽名者，然后計(jì)算a=gxA mod n，公開(t， a， IDB)；如果代理簽名者B愿意接受代理則計(jì)算并公布b=gxBmod n。原始簽名者A計(jì)算σ=bxAmod n以及Y=σ-v2T+1y-1A mod n，并公布Y；代理簽名者B計(jì)算σ=axBmod n，并驗(yàn)證Y=σ-v2T+1Y-1A mod n是否成立，如果等式成立則接受A的授權(quán)。

3）前向安全的代理簽名產(chǎn)生過程 在第i個周期開始時，代理簽名者B首先進(jìn)行密鑰進(jìn)化，計(jì)算xBi=x2B

i-1mod n，并立即刪除xBi-1，其中xB0=xB。

設(shè)簽名消息為m，B選擇ki，αi，βi∈RZ*n，計(jì)算：r=gkiaimod n， w=g2T-i+1 mod n， z=xBiσ2igβimod n， u=h(i‖m‖w‖r‖z‖t)， s=αi-βiv-kiu mod q，消息m的前向安全的代理簽名為(i，m，r，s，z，u，t)。其中t是簽名時間。

4）前向安全的代理簽名的驗(yàn)證 驗(yàn)證人收到(i，m，r，s，z，u，t)后，首先驗(yàn)證t是否超過代理終止時間t，如果超過，則認(rèn)為簽名無效；否則計(jì)算w′=(gszvru)2T-i+1yAy2T+1B Y mond n，然后驗(yàn)證等式u=h(i‖m‖w′‖r‖z‖t)是否成立，如果成立，則認(rèn)為簽名有效。 

3. 2 對張曉敏等人的改進(jìn)前向安全代理簽名方案的分析

該方案存在安全隱患，攻擊者甚至在不知曉代理人私鑰的情況下也可假冒代理人實(shí)施偽造攻擊。由于Y，yA，yB，T公開，攻擊者可以偽造任意周期j的代理簽名，分析過程如下：

設(shè)簽名消息為m′，在周期j攻擊者選擇kj，αj∈RZ*n，計(jì)算

r=gkjmod n， w=g2T-j+1αjyAyB2T+1Y mod n，z=1（這里z取正整數(shù)1）u=h(j‖m′‖w‖r‖z‖t′)， s=αj-kj u mod q

其中t′是簽名時間。則(j，m′，r，s，z，u，t′)為有效的前向安全的代理簽名。下面證明(j，m′，r，s，z，u，t′)能夠通過驗(yàn)證人的驗(yàn)證。

驗(yàn)證人收到（j，m′，r，s，z，u，t′）后，首先驗(yàn)證t′是否超過代理終止時間t，如果超過，則認(rèn)為簽名無效，否則計(jì)算：

w′=(gszvru)2T-j+1yAyB2T+1Y mod n=

(gαjg-kju1vgkju)2T-j+1yAyB2T+1Y mod n=

g2T-j+1αjyAyB2T+1Y mod n=w



所以，等式u=h(j‖m′‖w′‖r‖z‖t′)成立，即(j，m′r，s，z，u，t′)能夠通過驗(yàn)證人的驗(yàn)證，攻擊者的偽造攻擊成功。

因此，對張方案不用知曉任何私有信息，任何人都可以直接偽造代理簽名，不誠實(shí)的代理人也可否認(rèn)他的真實(shí)簽名，聲稱是其他人偽造他的簽名，從而使代理簽名不再具有不可偽造性、可區(qū)分性、不可否認(rèn)性等安全性質(zhì)。張方案不僅不具有前向安全性質(zhì)，且已不具備一般代理簽名的安全性質(zhì)，存在非常嚴(yán)重的安全隱患。

4 結(jié)束語 

本文分別分析了由王曉明和張曉敏提出的兩個前向安全代理簽名方案的安全性，發(fā)現(xiàn)它們都不具有真的前向安全性質(zhì)，均不能抵抗偽造攻擊。張方案甚至已不具備一般代理簽名的安全性質(zhì)，攻擊者可以無條件地實(shí)施偽造攻擊。目前，大多數(shù)前向安全數(shù)字簽名方案[13，14]并不具備真的前向安全性質(zhì)，如何設(shè)計(jì)一個真的前向安全的簽名方案仍是一個值得研究的困難問題。

參考文獻(xiàn)：

[1]MAMBO M，USUDA K， OKAMOTO E. Proxy signature: delegation of the power to sign messages [J]. IEICE Trans on Fundamentals， 1996， E79-A(9): 1338-1354.

[2]MAMBO M，USUDA K， OKAMOTO E. Proxy signature for delegating signing operation[C]//Proc of the 3rd ACM Conference on Computer and Communications Security. New York: ACM Press， 1996: 48-57.

[3]ZHANG Fang-guo， SAFAVI-NAINI R， LIN C Y. New proxy signature， proxy blind signature and proxy ring signature schemes from bilinear pairings[J/OL].2003.http://eprint iacr.org/2003/104.

[4]YI Li-jiang， BAI Guo-qing， XIAO Guo-zhen. Proxy multi-signature scheme: a new type of proxy signature scheme[J].Electronics Letters， 2000， 36(6): 527-528.

[5]HSU C L， WU T S， WU T C. New nonrepudiable threshold proxy signature with known signers [J].Journal of Systems and Software， 2001，58(9): 119-124.

[6]ANDERSON R. Two remarks on public key cryptology[C]//Proc of the 4thACM Conference on Computer and Communications Security. New York: ACM Press， 1997: 151-160.

[7]王曉明，陳火炎，符方偉，等.前向安全的代理簽名方案[J].通信學(xué)報，2005，26(11): 38-42.

[8]張曉敏，張建中.一個改進(jìn)的前向安全的代理簽名方案[J]. 計(jì)算機(jī)工程， 2007， 33(21):140-141.

[9]KOZLOV A， REYZIN L. Forward-secure signature with fast key update[C]//Proc of the 3rd Interatinal Conference on Security in Communication Network. Berlin: Springer-Verlag， 2002:241-256.

[10]李如鵬，于佳，李國文，等.高效撤銷成員的前向安全群簽名方案[J]. 計(jì)算機(jī)研究與發(fā)展，2007，44(7):1219-1226.

[11]王曉明，符方偉，張震，等.前向安全的多重?cái)?shù)字簽名方案[J]. 計(jì)算機(jī)學(xué)報， 2004，27(9):1177-1181.

[12]馮華熹，馮登國.一個基于雙線性映射的前向安全門限簽名方案[J]. 計(jì)算機(jī)研究與發(fā)展，2007， 44(4): 574-580.

[13]譚作文，劉卓軍.一個前向安全的強(qiáng)代理簽名方案[J] .信息與電子工程，2003， 1(4): 257-259.

[14]秦波，王尚平，王曉峰，等.一種新的前向安全可證實(shí)數(shù)字簽名方案[J]. 計(jì)算機(jī)研究與發(fā)展，2003， 40(7): 1016-1020.