李順波，黃光球，彭家龍

(1.西安建筑科技大學(xué) 管理學(xué)院，陜西 西安 710055；2.西安建筑科技大學(xué) 理學(xué)院，陜西 西安 710055)

一種前向安全數(shù)字簽名方案的分析及改進(jìn)

李順波1,2，黃光球1，彭家龍2

(1.西安建筑科技大學(xué) 管理學(xué)院，陜西 西安 710055；2.西安建筑科技大學(xué) 理學(xué)院，陜西 西安 710055)

前向安全在實(shí)際應(yīng)用中能有效減少私鑰泄露對(duì)過(guò)去時(shí)間段簽名帶來(lái)的損失，但會(huì)影響未來(lái)時(shí)段簽名的安全性。針對(duì)未來(lái)時(shí)間段的私鑰泄露問(wèn)題，提出了一種強(qiáng)前向安全的數(shù)字簽名方案。先是對(duì)劉亞麗(2010)等提出的基于模m的n方根難題的ElGamal前向安全數(shù)字簽名方案進(jìn)行了分析，發(fā)現(xiàn)該方案并不能保證未來(lái)時(shí)間段簽名的安全性，即不具備后向安全。于是借助單向散列鏈技術(shù)對(duì)該方案的私鑰更新和簽名算法進(jìn)行了有效改進(jìn)，在劉亞麗所提方案的基礎(chǔ)上構(gòu)造了一種基于ElGamal體制的數(shù)字簽名方案，并對(duì)該方案進(jìn)行了分析。分析結(jié)果表明，新方案是正確有效的，同時(shí)具有前向安全性和后向安全性。

前向安全；后向安全；數(shù)字簽名；ElGamal；單向散列鏈

0 引 言

數(shù)字簽名是公鑰加密技術(shù)和數(shù)字摘要技術(shù)的應(yīng)用，是保證數(shù)據(jù)機(jī)密性、完整性、真實(shí)性、不可否認(rèn)性的有效手段，已廣泛應(yīng)用于電子商務(wù)、金融等領(lǐng)域。根據(jù)Kerckhof假設(shè)密碼算法是公開(kāi)的，其安全性完全依賴于私鑰的安全性。一旦私鑰被泄露，不僅當(dāng)前的數(shù)字簽名安全性受到威脅，而且過(guò)去時(shí)段簽名的安全性也不能保證,勢(shì)必導(dǎo)致原來(lái)簽署的所有簽名都作廢。針對(duì)這個(gè)問(wèn)題，Anderson[1]于1997年首次提出前向安全簽名(Forword-secure signature)的思想，即當(dāng)前私鑰的暴露不會(huì)影響過(guò)去簽名的安全性。1999年，Bellare和Miner[2]具體給出了前向安全簽名的正式定義，并構(gòu)造了一種前向安全簽名方案。2001年，Burmester等[3]提出了強(qiáng)前向安全的概念，即同時(shí)保證前向安全和后向安全。隨著電子商務(wù)和網(wǎng)絡(luò)的發(fā)展，前向安全已成為信息安全領(lǐng)域的研究熱點(diǎn)，提出了基于屬性的前向安全[4]、基于雙線性對(duì)的前向安全[5]、基于格的前向安全[6]、強(qiáng)前向安全[7-10]、前向安全代理[11]等數(shù)字簽名方案。

2003年，吳克力等[12]給出了基于ElGamal體制的前向安全數(shù)字簽名方案。接著夏峰等[13]指出吳克力提出的方案并不具備前向安全性，并提出了一種新的基于ElGamal體制的前向安全簽名方案，可以將當(dāng)前私鑰隱藏在簽名中，確保簽名具有前向安全性。2009年，郭遠(yuǎn)等[14]改進(jìn)初始參數(shù)和私鑰更新算法，設(shè)計(jì)了一種基于ElGamal體制的前向安全簽名方案，但該方案無(wú)法保證其后向安全性。隨后廖小平[15]引入單向散列鏈對(duì)郭遠(yuǎn)的方案進(jìn)行了改進(jìn)，給出的方案既是前向安全又是后向安全的。2010年，劉亞麗等[16]構(gòu)造了新的密鑰生成算法，利用離散對(duì)數(shù)和合數(shù)模平方根困難問(wèn)題，提出了一種基于ElGamal的前向安全簽名方案，該方案具有前向安全性且優(yōu)于夏峰的簽名方案。

前向安全簽名在當(dāng)前私鑰泄露時(shí)不會(huì)對(duì)過(guò)去時(shí)間段的簽名造成危害，而后向安全能保證當(dāng)前私鑰的泄露不會(huì)對(duì)未來(lái)時(shí)段的私鑰造成影響，即不必每次檢測(cè)出私鑰泄露就撤銷當(dāng)前的私鑰系統(tǒng)而重建新的密鑰系統(tǒng)。通過(guò)分析劉亞麗提出的方案，發(fā)現(xiàn)其無(wú)法保證后向安全性，文中借助單向散列鏈技術(shù)，改進(jìn)方案的私鑰進(jìn)化和簽名算法，給出了基于ElGamal體制的強(qiáng)前向安全數(shù)字簽名方案。該方案可在滿足前向安全性的基礎(chǔ)上獲得后向安全性。

1 前向安全數(shù)字簽名

前向安全的基本思想是如果用戶當(dāng)前時(shí)間段的私鑰泄露了，攻擊者雖然可以偽造此時(shí)段后的簽名，但無(wú)法偽造過(guò)去時(shí)間段的簽名；其本質(zhì)是將簽名私鑰泄露所帶來(lái)的影響和損失盡可能減少到最小。前向安全數(shù)字簽名方案主要由四部分組成：公鑰和初始私鑰生成、私鑰更新、簽名算法、驗(yàn)證算法。其關(guān)鍵是簽名私鑰的更新和簽名算法。

用戶先注冊(cè)得到公鑰PK和相應(yīng)的初始私鑰SK0，將私鑰的有效期分成T個(gè)時(shí)段，分別記為1,2,…,T。在有效時(shí)段內(nèi)，公鑰PK是固定不變的，私鑰隨著時(shí)段的變化進(jìn)行更新，記i時(shí)段的私鑰為SKi，更新公式為SKi=h(SKi-1)，h是一個(gè)單向函數(shù)，求出SKi后立即刪除SKi-1。這樣當(dāng)攻擊者在i時(shí)段截獲私鑰SKi，但無(wú)法獲得前時(shí)段的私鑰SKi-1,SKi-2,…,SK0，因此前向的私鑰是安全的，稱之為前向安全，其私鑰更新過(guò)程如圖1所示。

圖1 前向安全數(shù)字簽名的私鑰更新過(guò)程

2 劉亞麗方案及其安全性分析

2.1 劉亞麗的簽名方案

(1)初始參數(shù)。

(2)私鑰更新算法。

(3)簽名算法。

①選擇隨機(jī)數(shù)k∈Zp，計(jì)算r=gkmodp；

②選擇隨機(jī)數(shù)μ∈Zp，計(jì)算ω=SKigμmodp；

③計(jì)算δ=(H(m)+2T-iμr)k-1mod(p-1)，其中m為簽名消息；

④發(fā)送簽名(i,r,ω,δ)給驗(yàn)證方。

(4)驗(yàn)證算法。

如果(PKω-2T-i)rrδ=gH(m)modp為真，則認(rèn)為簽名有效；否則，認(rèn)為無(wú)效。

2.2 劉亞麗方案的安全性分析

(1)劉亞麗方案基于求合數(shù)模平方根和離散對(duì)數(shù)困難問(wèn)題，將當(dāng)前時(shí)段簽名密鑰隱藏且僅使用密鑰有關(guān)信息進(jìn)行簽名，從而無(wú)法獲得過(guò)去時(shí)段的私鑰和簽名，具有前向安全性和抗偽造性。

(2)方案不具備后向安全性。

①簽名方選擇隨機(jī)數(shù)k'，計(jì)算r'=gk'modp；

②簽名方選擇隨機(jī)數(shù)μ'，計(jì)算ω'=SKi+3gμ'modp；

③計(jì)算δ'=(H(m)+2T-i-3μ'r')k'-1mod(p-1)，則用戶對(duì)消息m在i+3時(shí)段的簽名為(i+3,r',ω',δ')，并發(fā)給驗(yàn)證方；

④驗(yàn)證方利用簽名方的公鑰PK，驗(yàn)證下面等式是否成立：

(PKω'-2T-i-3)r'(r')δ'=gH(m)modp

因?yàn)椋?/p>

(gk')(H(m)+2T-i-3μ'r')k'-1=

(g-2T-i-3μ')r'g(H(m)+2T-i-3μ'r')=gH(m)modp

所以攻擊成功，即攻擊者獲得i時(shí)段的私鑰SKi后，可以偽造出i時(shí)段以后的所有簽名并通過(guò)驗(yàn)證算法，即該方案不滿足后向安全性。

3 基于ElGamal體制的強(qiáng)前向安全數(shù)字簽名方案

新方案將借助單向散列鏈技術(shù)，改進(jìn)初始參數(shù)、簽名算法和驗(yàn)證算法。使得構(gòu)造的方案既有前向安全性，又有后向安全性，即強(qiáng)前向安全的，從整體上有效地提高了數(shù)字簽名的安全性。

3.1 單向散列鏈

單向散列函數(shù)h(又稱哈希函數(shù)、雜湊函數(shù))是將任意長(zhǎng)度的消息x映射成一個(gè)固定長(zhǎng)度的函數(shù)。滿足3個(gè)性質(zhì)：

(1)給定x，容易計(jì)算h(x)。

(2)給定h(x)，求出x在計(jì)算上是不可行的；稱為單向性。

(3)找到兩個(gè)值x和y，且x≠y，使得h(x)=h(y)在計(jì)算上是不可行的，稱為抗弱碰撞性。

對(duì)于隨機(jī)選取的種子值a(個(gè)人密碼)，用單向散列函數(shù)h通過(guò)遞歸散列運(yùn)算hi(a)=h(hi-1(a))(i=1,2,…,T且h0(a)=a)構(gòu)造長(zhǎng)度為T(mén)的一串散列值a,h(a),h2(a),…,hi(a),…,hT-1(a)稱為時(shí)段T的單向散列鏈。

令xi=hT-i(a)，也就是說(shuō)xi是散列鏈中的第T-i個(gè)散列值，如表1所示。當(dāng)攻擊者截獲第i時(shí)段的xi，可由公式xi-1=hT-i+1(a)=h(hT-i(a))=h(xi)容易得到前一時(shí)段i-1的xi-1。但當(dāng)攻擊者竊取第i時(shí)段的xi時(shí)，由于h的單向性，無(wú)法用公式xi=h(xi+1)獲得后一時(shí)段的xi+1。因此表1構(gòu)造的散列鏈x1,x2,…,xi,…,xT能保證其后向安全性，為強(qiáng)前向安全的數(shù)字簽名提供了設(shè)計(jì)理念。

表1 時(shí)段T對(duì)應(yīng)的散列鏈

3.2 強(qiáng)前向安全簽名方案

(1)初始參數(shù)。

②選擇隨機(jī)數(shù)a，并計(jì)算x0=hT(a)。

③公開(kāi)p，g，x0，T和PK。

(2)私鑰更新算法。

(3)簽名算法。

①簽名方生成第i時(shí)段和i+1時(shí)段的散列值xi和xi+1，其中xi=hT-i(a)，xi+1=hT-i-1(a)。

②簽名方選擇隨機(jī)數(shù)μ∈Zp，計(jì)算ω=SKigμmodp,ri=gximodp。

④發(fā)送(i,ri,ω,δ)給驗(yàn)證方。

(4)驗(yàn)證算法。

(5)安全性分析。

①有效性。

考察驗(yàn)證算法中的等式：

(gxi)modp=

[(gμ)-2T-i]rigH(m)+2T-iμrimodp=gH(m)modp

因此待驗(yàn)證的等式成立，該簽名方案正確，且(i,ri,ω,δ)為有效的數(shù)字簽名方案。

②抗偽造性。

方案采用劉亞麗的方法。當(dāng)攻擊者截獲了第i時(shí)段的簽名(i,ri,ω,δ)，由ω=SKigμmodp，若想通過(guò)ω得到隱藏的私鑰μ是求解離散對(duì)數(shù)問(wèn)題，計(jì)算上是不可行的。

③前向安全性。

由于簽名算法ω=SKigμmodp中有私鑰SKi的參與，保證了其簽名算法也具有前向安全性。

④后向安全性。

若攻擊者截獲了第i時(shí)段的簽名(i,ri,ω,δ)，盡管知道了ri=gximodp，但xi,xi+1在單向散列鏈中且滿足xi=h(xi+1)，無(wú)法由xi得到xi+1。因此攻擊者無(wú)法獲得未來(lái)時(shí)段的簽名，也就是說(shuō)即使第i時(shí)段的密鑰泄露，也不會(huì)影響此后時(shí)段簽名的安全性。因此，該方案具有后向安全性。

綜上所述，新方案具有不可偽造性、前向安全性和后向安全性；借助單向散列鏈技術(shù)可以有效地提高簽名方案的安全性。

4 結(jié)束語(yǔ)

前向安全簽名方案能有效降低因私鑰泄露而造成的損失，但其普遍存在的缺陷就是無(wú)法保證私鑰泄露后未來(lái)時(shí)段簽名的安全性和及時(shí)發(fā)現(xiàn)機(jī)制。文中借助單向散列鏈技術(shù)，對(duì)劉亞麗的前向安全簽名方案進(jìn)行了改進(jìn)，新方案彌補(bǔ)了其后向安全性，構(gòu)造了基于ElGamal體制的強(qiáng)前向安全數(shù)字簽名方案，該方案既具有前向安全性又有后向安全性。

[1]AndersonR.Tworemarksonpublickeycryptology[C]//Thefourthannualconferenceoncomputerandcommunicationssecurity.NewYork:[s.n.],1997:151-160.

[2]BellareM,MinerSK.Aforward-securedigitalsignaturescheme[C]//AdvancesinCryptology-Crypto'99.Berlin:Springer-Verlag,1999:431-448.

[3]BurmesterM,ChrissikopoulosV,KotzanikolaouP,etal.Strongforwardsecurity[M]//Trustedinformation.US:Springer,2001:109-121.

[4] 魏江宏，劉文芬，胡學(xué)先.前向安全的密文策略基于屬性加密方案[J].通信學(xué)報(bào)，2014,35(7):38-45.

[5]YuJia,KongFanyu,ChengXiangguo,etal.Oneforward-securesignatureschemeusingbilinearmapsanditsapplications[J].InformationSciences,2014,279:60-76.

[6] 李明祥，安 妮.基于格的前向安全簽名方案[J].密碼學(xué)報(bào),2016,3(3):249-257.

[7] 阿力木江·艾沙，庫(kù)爾班·吾布力，艾斯卡爾·艾木都拉，等.一種強(qiáng)前向安全數(shù)字簽名方案[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(9)：107-108.

[8] 徐光寶,姜東煥,梁向前.一種強(qiáng)前向安全的數(shù)字簽名方案[J].計(jì)算機(jī)工程,2013,39(9):167-169.

[9] 廖小平，蔡光興.一類具有強(qiáng)前向安全性的數(shù)字簽名方案[J].湖北工業(yè)大學(xué)學(xué)報(bào)，2011，26(2):126-130.

[10] 王明偉，胡予濮.一種前向-后向安全的數(shù)字簽名方案[J].西安電子科技大學(xué)學(xué)報(bào)，2014，41(2):71-78.

[11] 曹 欣，魏仕民，卓澤朋.三個(gè)前向安全代理簽名方案的安全性分析[J].計(jì)算機(jī)工程與應(yīng)用，2015,51(7):98-100.

[12] 吳克力,王慶梅,劉鳳玉.一種具有前向安全的數(shù)字簽名方案[J].計(jì)算機(jī)工程,2003,29(8):122-123.

[13] 夏 峰,謝冬青,匡華清.一類前向安全數(shù)字簽名方案的分析與改進(jìn)[J].計(jì)算機(jī)工程,2006,32(16):146-147.

[14] 郭 遠(yuǎn)，徐賜文.基于ElGamal的前向安全簽名方案的分析與改進(jìn)[J].電腦知識(shí)與技術(shù)，2009，15(6):1459-1460.

[15] 廖小平.前向安全數(shù)字簽名方案的分析與改進(jìn)[J].計(jì)算機(jī)與信息技術(shù)，2012，20(1):45-47.

[16] 劉亞麗，秦小麟，殷新春，等.基于模m的n方根的前向安全數(shù)字簽名方案的分析與改進(jìn)[J].通信學(xué)報(bào)，2010，31(6):82-88.

Analysis and Improvement for a Digital Signature Scheme of Forward Security

LI Shun-bo1,2,HUANG Guang-qiu1,PENG Jia-long2

(1.School of Management,Xi’an University of Architecture and Technology,Xi’an 710055,China; 2.School of Science,Xi’an University of Architecture and Technology,Xi’an 710055,China)

Forward security can effectively reduce the damage caused by exposure of the secret key in the past time period,but may affect the signature in the future period.In order to solve this problem,a strong forward-secure signature is proposed.Firstly,Liu Yali’s ElGamal forward-secure signature scheme in 2010 based onnrootofmodulemisanalyzed,andthisschemeisnotbackwardsecurity,whichmeansitcan’tguaranteethesignaturesecurityinthefutureperiod.Then,byusingaone-wayhashchain,thekeyupdatingandsignaturealgorithmisimprovedeffectively.AnewdigitalsignatureschemebasedonElGamalispresentedonthebasisofLiu’sschemeandanalyzed.Theresultshowsthatthenewschemeiscorrectandfeasible,withforwardandbackwardsecurity.

forward-secure;backward-secure;digital signature;ElGamal;one-way hash chain

2015-09-11

2015-12-24

時(shí)間：2016-10-24

國(guó)家自然科學(xué)基金資助項(xiàng)目(11471255，11526161)；陜西省自然科學(xué)基金(2014JQ1027,2015JQ1014)；陜西省教育廳基金(2013JK0589)；西安建筑科技大學(xué)基金(RC1338,RC1438，JC1321,JC1416)

李順波(1979-)，男，副教授，博士，CCF會(huì)員，研究方向?yàn)槊艽a學(xué)與信息安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1105.004.html

TP

A

1673-629X(2016)11-0093-04

10.3969/j.issn.1673-629X.2016.11.021