一種前向安全數字簽名方案的分析及改進

李順波，黃光球，彭家龍

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

一種前向安全數字簽名方案的分析及改進

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

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

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

前向安全；后向安全；數字簽名；ElGamal；單向散列鏈

0 引 言

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

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

前向安全簽名在當前私鑰泄露時不會對過去時間段的簽名造成危害，而后向安全能保證當前私鑰的泄露不會對未來時段的私鑰造成影響，即不必每次檢測出私鑰泄露就撤銷當前的私鑰系統而重建新的密鑰系統。通過分析劉亞麗提出的方案，發現其無法保證后向安全性，文中借助單向散列鏈技術，改進方案的私鑰進化和簽名算法，給出了基于ElGamal體制的強前向安全數字簽名方案。該方案可在滿足前向安全性的基礎上獲得后向安全性。

1 前向安全數字簽名

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

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

圖1 前向安全數字簽名的私鑰更新過程

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

2.1 劉亞麗的簽名方案

(1)初始參數。

(2)私鑰更新算法。

(3)簽名算法。

①選擇隨機數k∈Zp，計算r=gkmodp；

②選擇隨機數μ∈Zp，計算ω=SKigμmodp；

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

④發送簽名(i,r,ω,δ)給驗證方。

(4)驗證算法。

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

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

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

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

①簽名方選擇隨機數k'，計算r'=gk'modp；

②簽名方選擇隨機數μ'，計算ω'=SKi+3gμ'modp；

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

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

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

因為：

(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時段的私鑰SKi后，可以偽造出i時段以后的所有簽名并通過驗證算法，即該方案不滿足后向安全性。

3 基于ElGamal體制的強前向安全數字簽名方案

新方案將借助單向散列鏈技術，改進初始參數、簽名算法和驗證算法。使得構造的方案既有前向安全性，又有后向安全性，即強前向安全的，從整體上有效地提高了數字簽名的安全性。

3.1 單向散列鏈

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

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

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

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

對于隨機選取的種子值a(個人密碼)，用單向散列函數h通過遞歸散列運算hi(a)=h(hi-1(a))(i=1,2,…,T且h0(a)=a)構造長度為T的一串散列值a,h(a),h2(a),…,hi(a),…,hT-1(a)稱為時段T的單向散列鏈。

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

表1 時段T對應的散列鏈

3.2 強前向安全簽名方案

(1)初始參數。

②選擇隨機數a，并計算x0=hT(a)。

③公開p，g，x0，T和PK。

(2)私鑰更新算法。

(3)簽名算法。

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

②簽名方選擇隨機數μ∈Zp，計算ω=SKigμmodp,ri=gximodp。

④發送(i,ri,ω,δ)給驗證方。

(4)驗證算法。

(5)安全性分析。

①有效性。

考察驗證算法中的等式：

(gxi)modp=

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

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

②抗偽造性。

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

③前向安全性。

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

④后向安全性。

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

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

4 結束語

前向安全簽名方案能有效降低因私鑰泄露而造成的損失，但其普遍存在的缺陷就是無法保證私鑰泄露后未來時段簽名的安全性和及時發現機制。文中借助單向散列鏈技術，對劉亞麗的前向安全簽名方案進行了改進，新方案彌補了其后向安全性，構造了基于ElGamal體制的強前向安全數字簽名方案，該方案既具有前向安全性又有后向安全性。

[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] 魏江宏，劉文芬，胡學先.前向安全的密文策略基于屬性加密方案[J].通信學報，2014,35(7):38-45.

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

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

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

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

[9] 廖小平，蔡光興.一類具有強前向安全性的數字簽名方案[J].湖北工業大學學報，2011，26(2):126-130.

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

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

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

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

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

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

[16] 劉亞麗，秦小麟，殷新春，等.基于模m的n方根的前向安全數字簽名方案的分析與改進[J].通信學報，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

時間：2016-10-24

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

李順波(1979-)，男，副教授，博士，CCF會員，研究方向為密碼學與信息安全。

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