基于模m的n方根的前向安全數字簽名方案的分析與改進

劉亞麗，秦小麟，殷新春，李博涵

(1. 南京航空航天大學 信息科學與技術學院，江蘇 南京 210016；2. 徐州師范大學 計算機科學與技術學院，江蘇 徐州 221116；3. 揚州大學 信息工程學院，江蘇 揚州 225009)

1 引言

前向安全數字簽名是信息安全風險控制的措施之一，也是目前密碼學研究的熱點。1997 年，Ross Anderson首次提出前向安全的概念[1]，解決了通常數字簽名的一些缺陷：一旦密鑰丟失(或被竊取)，由這個密鑰生成的以前所有簽名都變得無效。Bellare和Miner第一次給出了前向安全簽名的正式定義，并基于A.Fiat和A.Shamir的簽名方案[2]給出了2個前向安全簽名方案[3,4]。前向安全方法的目標是如果在某一時間段簽名密鑰被盜取，攻擊者雖然可以偽造此時段后的簽名，但無法偽造密鑰被盜取時段前的簽名。其思想本質是數字簽名安全的風險控制，即將簽名密鑰被盜后對系統安全所造成的影響和損失盡可能減少到最小。

隨著前向安全特性的提出，前向安全數字簽名方案已成為信息安全領域的研究熱點。Tal M等提出具有無界時間段的前向安全數字簽名方案[5]，ANTON K等提出快速密鑰更新的前向安全數字簽名方案[6]；此外將前向安全特性和其他特殊的簽名方案結合，進一步設計具有前向安全特性的特殊數字簽名方案，如李如鵬等提出的高效撤銷成員的前向安全群簽名方案[7]，王曉明等提出的前向安全的多重數字簽名方案[8]，彭華熹等提出的基于雙線性映射的前向安全門限簽名方案[9]等。同時前向安全的概念在電子貨幣系統[10]、密鑰交換協議[11]等方面有著重要的應用。在特定的應用領域如何真正保證前向安全特性，從而提高整個方案的安全性是個亟待解決的問題。近年來眾多學者提出的前向安全數字簽名方案在密鑰的進化上使用最多的是使基于模m的n方根難題[8,9]作為單向函數，實際上具有因子分解難度。如何讓密鑰演進與簽名結合起來是個較難解決的問題，以及如何尋找更多單向密鑰更新算法來構造前向安全數字簽名方案，均將是今后前向安全數字簽名方案值得進一步研究的問題。

基于模m的n方根難題的前向安全數字簽名方案[12～18]的共同點是密鑰演進均采用求密鑰模m的n方根，試圖為簽名加上一個“時間戳”，防止簽名者對先前時間段簽名的抵賴。由于可以使用后繼密鑰的信息對當前時段的消息進行簽名，雖然密鑰是前向安全的，但是簽名卻不具備前向安全性，使得密鑰的進化沒有任何意義。雖然一些學者指出其中某些方案存在的安全漏洞不能抵抗攻擊者的攻擊，但均沒有系統地總結出此類簽名方案存在安全漏洞的本質原因。本文針對文獻[12～18]提出的一類基于模m的n方根難題的前向安全數字簽名方案中的代表方案[12～14]分別進行了詳細的安全性分析，發現攻擊者如果得到簽名者某一簽名時段的簽名密鑰,即可偽造任何簽名時段的有效簽名(包括此時段前的簽名)，得出這些方案[12～18]均不具備前向安全性的結論，進而總結出對于此類前向安全數字簽名方案攻擊者成功偽造有效簽名的本質原因。在實際中，設計前向安全數字簽名方案時應注意避免出現此類安全隱患。

本文在總結此類簽名方案密鑰泄漏根本原因的同時對簽名方案[12]進行了改進，采用將當前簽名密鑰隱藏且僅使用與當前密鑰有關的信息進行簽名的方式，構造了一種真正具備前向安全特性的新方案，其安全性基于求合數模平方根難度的密鑰演進與求離散對數難題簽名的結合。通過詳細的安全性分析和計算復雜度分析表明新方案不僅具有前向安全性，而且和已提出的改進方案[19]相比減少了求冪運算、乘法運算和加法運算的次數，有效地提高了簽名的速度，具有一定的理論意義、安全性和實用性。借鑒對文獻[12]的改進方法，根據有限域上數字簽名所基于的困難性問題和基于求模m的n方根難度的密鑰演進進行方案的設計，使用當前密鑰或與當前密鑰有關的信息進行簽名，將時段信息加入簽名（與后繼密鑰無關），可改進此類基于模m的n方根難題的其他簽名方案，真正實現整個簽名方案的前向安全性。利用此改進方法的基本思想可以設計前向安全代理簽名、前向安全群簽名、前向安全多重簽名等一些具有實際應用價值的簽名方案。

2 前向安全數字簽名方案分析

2.1 模m的n方根問題

設n≥2，同余方程xn≡a(modm)稱為模m的二項同余方程。當(a, m)=1且m≥2時，若二項同余方程xn≡a(modm)有解，則稱a為模m的n次剩余；若無解，則稱a為模m的n次非剩余。

特殊地，當n=2且m≥2時，若二項同余方程xn≡a(mod m)有解，則稱a為模m的二次剩余；若無解，則稱a為模m的二次非剩余。

模m的n次剩余問題也被稱為模m的n方根問題。

2.2 基于ElGamal體制前向安全簽名方案的安全性分析

具體簽名方案請參見文獻[12]。此簽名方案不具備前向安全性：即若攻擊者得到簽名者第j(1≤j≤T) 時段的簽名密鑰SKj，即可偽造任一時段 j' (1≤j'≤T) 的有效簽名( j', r, δ )。

若攻擊者獲得了第j(1≤j≤T)時段的簽名密鑰SKj，由于( j, r, δ )可以從公用信道獲取，所以攻擊者可以獲知r和δ。簽名方通過δ=(H(m)-計算第 j(1≤j≤T) 時段的簽名δ 時，根據第 j(1≤j≤T) 時段的密鑰更新算法，由SKj+1=mod(p-1)可以得到，因此為一個和時段 j 無關的常數。又由于H(m), r, k, p均和時段 j 無關，所以每一個不同j(1≤j≤T)時段求出的簽名δ 也和時段 j 無關，故最終的簽名( j, r, δ )中只有表示時段 j 的不同。因此攻擊者一旦獲得簽名者某一簽名時段 j(1≤j≤T) 的簽名密鑰SKj，就可以根據且將簽名時段標記換為 j'，即可成功地偽造出任一簽名時段 j' (1≤j' ≤T) 的簽名( j', r, δ )，這樣j(1≤j≤T)時段前的簽名也可以通過這種方法偽造出來，所以此簽名方案不具備前向安全性。

根據以上分析可得，攻擊者一旦獲得簽名者第j(1≤j≤T) 時段的簽名密鑰SKj，就可以成功偽造任一時段 j' (1≤j'≤T)的有效簽名( j', r, δ )，所以此簽名方案不具備前向安全性。

2.3 前向安全可證實簽名方案的安全性分析

具體簽名方案請參見文獻[13]。此簽名方案不具備前向安全性：即若攻擊者得到簽名者第i(1≤i≤T) 時段的簽名密鑰xsi，即可偽造任一時段 j(1≤j≤T) 的有效簽名＜j, SGN( M , xsi), yT＞ = ＜ j,( c, s), yT＞。

基于該方案的攻擊和文獻[12]的攻擊類似。在有效簽名＜i, SGN( M , xsi), yT＞ = ＜ i, ( c, s), yT＞中，簽名公鑰yT=是一個和時段i無關的不變量，簽名方計算第 i(1≤i≤T) 時段的簽名＜ i, ( c, s),yT＞時，根據第 i(1≤i≤T) 時段的密鑰更新算法，由xi=mod N 可以得到又因為進化私鑰xsi=xi ，所以為一個和時段i無關的常數，根據進行的驗證肯定是正確的。基于以上所述可以得知，若攻擊者一旦獲得第i(1≤i≤T) 時段的簽名密鑰xsi，根據可以做出第j (1≤j≤i≤T) 時段的簽名，只需計算c= H( M‖g‖yT‖j‖gk)，s=(k-xs2iT-ic)mod N ，其中k從ZN中隨機選取，將簽名時段標記換為j，j為[1, T]中的任一時段，此時仍然成立，故通過ζ= H(M‖g‖yT‖j‖gsyTc)驗證此偽造簽名成立。i(1j≤i≤T)時段前的簽名也可以偽造，所以此簽名方案不具備前向安全性。

在文獻[13]中注意到以下特點：簽名公鑰為PK={g, N, yT}，其中，最終簽名為 ＜i,SGN( M, xsi), yT＞ = ＜ i,(c, s), yT＞，其中c = H( M‖g‖yT‖i‖gk)，根據第 i(1≤i≤T) 時段的密鑰更新算法mod N，可得，又因為xsi=xi，所以簽名中的為一個常數，因此實際簽名私鑰和時段i無關，驗證等式H( M‖g‖yT‖i‖gsyTc)= H(M‖g‖yT‖i‖gk)也和時段i無關。

根據以上分析可得，攻擊者一旦獲得簽名者第i(1≤i≤T) 時段的簽名密鑰xsi，就可以成功偽造任一時段j(1≤j≤T) 的有效簽名＜j, ( c, s), yT＞，所以此簽名方案也不具備前向安全性。

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

具體簽名方案請參見文獻[14]。此簽名方案不具備前向安全性：即若攻擊者得到原始簽名者A的私鑰kA或者代理簽名者B的私鑰kB，即可偽造任一時段j(1≤j≤T)的有效代理簽名[j, (m, s, u,t～)]。

若攻擊者獲得了原始簽名者A的私鑰kA或者代理簽名者B的私鑰kB，由于yA和yB分別為原始簽名者A和代理簽名者B的公鑰，可以從公用信道獲取，根據或者，攻擊者可以獲得初始時段的代理簽名密鑰σ0，進而通過代理密鑰進化算法，即可獲得任一時段j(1≤j≤T)的代理簽名密鑰σj。在有效簽名[j,(m,s,u,)]中，，其中，αj,jβ由代理簽名者B隨機選取，原始簽名者A選擇一對整數(e,d)使得ed=1modφ(n)，并公布(IDA,yA,e)，代理簽名者 B 公布(yB,IDB)。根據可得，因此簽名重要參數r,z可以通過上式計算得到，進而簽名中u通過散列函數即可得到，攻擊者再通過獲取的代理簽名者B私鑰kB可以直接計算出簽名s。在驗證過程中，根據r'和r的公式，可得

根據以上分析可得，不論攻擊者獲取原始簽名者A的私鑰kA還是得到代理簽名者B的私鑰kB，都可以成功偽造任一時段j(1≤j≤T)的有效代理簽名[j,(m,s,u,)]，所以此簽名方案也不具備前向安全性。

由于篇幅有限，文獻[15～18]安全性分析與2.2～2.4節分析類似，此處不再贅述。

3 密鑰泄漏的根本原因分析

綜上所述，此類基于模m的n方根難題的前向安全數字簽名方案均存在安全隱患，密鑰泄露的主要原因如下：

1)密鑰演進本質上均為基于求模m的n方根的難題作為單向函數，具有因子分解難度，保證密鑰的前向安全性；

2)在最終的簽名中均采用私鑰 n次方冪的形式進行簽名，根據密鑰進化算法，使得實際簽名的私鑰變為一個和具體時段無關的常數，導致私鑰的進化對于整個簽名方案而言沒有任何意義；

3)驗證等式均和具體時段無關，使得時段參數不是一個有效的參數。

以上導致前向安全失敗的原因中，密鑰泄漏最關鍵的是第2個原因。此類方案的密鑰進化算法相同，均為基于求模m的n方根的難題作為單向函數，使得私鑰進化是前向安全的；但是在簽名過程中采用私鑰n次方冪的形式進行簽名，根據密鑰進化算法，使得整個實際簽名的私鑰變為一個和時段i(1≤i≤T)無關的常數，導致私鑰進化沒有任何意義。只要恰當地在實際簽名中加入當前時段i (1≤i≤T)的信息，使得進化的私鑰真正用于簽名，并且驗證等式和簽名公鑰的形式隨之改變，就可以實現整個簽名方案的前向安全性。

下面從導致前向安全失敗最關鍵的第2個原因入手對基于ElGamal體制的前向安全簽名方案[12]進行改進，設計一種真正具備前向安全特性的新方案。

4 基于ElGamal體制的前向安全簽名方案的改進

方案定義新的密鑰生成算法、密鑰進化算法、簽名算法與驗證算法對原方案[12]進行改進。通過詳細的安全性分析可知，改進的新方案真正具備前向安全性，且和夏等人提出的改進方案[19]相比減少了求冪運算、乘法運算和加法運算的次數，從整體上有效地提高了簽名的速度。

1) 密鑰生成

① 選擇一個大素數p和隨機數SK0(小于p)，g是GF(p)的生成元；

③ 公開p，g，T和PK。

2) 密鑰進化

若j=T+1，則SKj為空串；若1≤j≤T，則。其中j表示第j個時間段。

3) 簽名算法

① 簽名方選擇隨機數k∈Zp，計算r = gkmod p；

②簽名方選擇隨機數μ∈Zp，計算ω=SKjgμmodp；

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

④ 發送 ( j, r,ω, δ ) 給驗證方。

4) 驗證算法

驗證者驗證：(PKω-2T-j)rrδmodp=gH(m)mod p。若等式成立，則認可簽名( j, r,ω, δ )有效；否則，認為( j, r,ω, δ )是無效簽名。

5) 安全性分析

① 有效性

根據方案中相關等式考察簽名驗證中的等式：

由上式可以得出驗證等式

成立，因此本簽名方案是正確的，( j, r,ω, δ )為有效的前向安全簽名。

② 前向安全性

本方案中簽名私鑰SKj在簽名過程中根據時間段 j(1≤j≤T) 的不同進行更新，而簽名公鑰PK在整個簽名過程中不變。由于采用的密鑰進化算法是單向函數，若想通過此密鑰進化算法求出j時段之前的私鑰是基于求模合數平方根問題的難解性，其困難性等價于因子分解問題，因此私鑰SKj的進化具有前向安全性。

在本方案中將簽名私鑰SKj在簽名之初轉換為隨機的實際簽名私鑰μ，由信息ω傳到驗證者證實，傳給驗證者的信息ω是直接與 j時段密鑰相關的信息，即使攻擊者盜取了第 j(1≤j≤T) 時段的簽名密鑰SKj，也最多只能通過密鑰進化算法求出j+1時段的密鑰SKj+1，再通過δ=(H( m)+2T-jμr) k-1mod(p -1)進而可以偽造j+1時段的簽名，但是一定不能偽造密鑰被盜取時段j(1≤j≤T) 前的簽名，即時段j前的簽名仍然有效。

假設j時段的私鑰SKj泄露，攻擊者偽造 i (i ＜j) 時段的最終簽名記為(i, r',ω',δ ')，其中ω'由攻擊者隨機選取的實際簽名私鑰μ' ∈Zp，通過mod p 計算得出(SKi'為攻擊者偽造的i時段私鑰)。由于≠SKi=，故驗證過程無法通過，詳細過程見③抗偽造性分析。

因此，本方案私鑰SKj的進化和 j 時段的簽名( j, r,ω, δ )均具有真正的前向安全性。

③ 抗偽造性

信息ω作為簽名的重要組成部分在j時段公開，由ω=SKjgμmod p 可知，若想通過ω得到實際簽名私鑰μ(即隱藏的私鑰)是基于離散對數的難題，根本不可行。由ω和δ的公式可知，如果無法知道私鑰SKj和μ，則顯然也無法構造j時段的有效簽名( j, r,ω, δ)；且由驗證公式可知，在不知道私鑰SKj和μ的情況下，想用一個偽造的私鑰SKji'進行簽名，則驗證無法通過。

假設攻擊者偽造i時段私鑰SKi'，隨機選取實際簽名私鑰μ'∈Zp構造，進而偽造i 時段的最終簽名記為(i, r',ω',δ ')，但是在驗證過程中，由于，因此有

因此驗證無法通過，本方案具有較強的抗偽造性。

6) 方案特點

本簽名方案的特點是將簽名密鑰 SKj轉換為隨機的實際簽名密鑰μ，利用求離散對數的難題隱藏了簽名密鑰SKj的信息，僅使用與當前密鑰有關的信息進行簽名，與后繼密鑰無關，不需要額外的存儲空間，使竊密者沒有任何可能由后繼密鑰偽造出前時段的簽名信息，且驗證等式在ElGamal原等式基礎上構造的同時，恰當地加入了時段 j的信息，簽名方案的前向安全性基于離散對數問題和模合數平方根問題的難解性。這是本方案和現有的眾多前向安全數字簽名方案的不同特色所在，從而真正實現了一種基于模 m的二次方根問題的新的數字簽名方案的前向安全性，具有一定的理論意義、安全性和實用性。本方案所采用的方法也同樣適用于此類基于模m的n方根難題的其他簽名方案，由于篇幅的限制，此處不再贅述。

由以上分析可知，設計一個真正具備前向安全特性簽名方案的關鍵在于需在實際簽名中加入當前時段 j (1≤j≤T) 的信息，使得進化的私鑰真正用于簽名，公鑰和驗證等式的形式隨進化的私鑰在原有的基礎上構造，從而保證當前私鑰和驗證過程中時段參數的有效性。

7) 計算效率分析

將夏等人提出的改進方案[19]和本文構造的新方案進行比較，并將2種方案的計算量列入表1中進行對比。其中E、M、A、I分別代表取模意義下的求冪運算、乘法運算、加法運算以及逆運算。在簽名過程中，這些運算占據大部分的計算時間。通過分析表明，新方案與改進方案[19]相比，除了密鑰進化階段運算量相同，簽名過程中的其他各階段均減少了計算量，所以新簽名方案的總運算量比改進方案[19]低，有效地提高了簽名的速度。

5 結束語

本文介紹了前向安全數字簽名的思想本質、目標和研究現狀，分析了近年來眾多學者提出的一類基于模m的n方根難題的前向安全數字簽名方案的安全性，進而總結出對于此類前向安全數字簽名方案攻擊者成功偽造簽名的本質原因。在實際應用中，設計前向安全數字簽名方案時應注意避免出現此安全隱患。同時根據有限域上數字簽名所基于的困難性問題，對其中一種簽名方案進行了改進，構造一種真正具備前向安全特性的新簽名方案，并進行詳細的安全性分析和計算復雜度分析。本文的改進方案和已提出的改進方案相比在簽名速度上有了明顯的提高。本文中改進方案所用的方法也同樣適用于此類基于模m的n方根難題的其他簽名方案，對于構造其他具有特殊性質的前向安全數字簽名方案具有借鑒意義，在實際中具有廣泛的應用價值。下一階段的研究是設計效率更高、安全性更強的、具有實用價值的新型前向安全數字簽名方案及其形式化安全性證明，并使得前向安全特性和特殊數字簽名技術恰當結合，從而在電子支付系統、移動安全計算、隱私保護等方面得以更加廣泛的應用。

[1] ROSS A. Two remarks on public key cryptology[A]. The Fourth Annual Conference on Computer and Communications Security[C]. New York, 1997. 151-160.

[2] AMOS F, ADI S. How to prove yourself: practical solutions to identification and signature problems[A]. Advances in Crytology- Crypto’86,Lecture Notes in Computer Science[C]. Santa Barbara, California,USA, 1987. 186-194.

[3] MIHIR B, SARA K M. A Forward-secure digital signature scheme[A].Advances in Cryptology-Crypto'99, Lecture Notes in Computer Science[C]. Springer-Verlag, Santa Barbara, California, USA, 1999.431-448.

[4] MICHEL A, LEONID R. A new forward-secure digital signature scheme[A]. Advances in Cryptology-Asiacrypt 2000, Lecture Notes in Computer Science[C]. Springer-Verlag, Kyoto, Japan, 2000. 116-129.

[5] TAL M, DANIELE M, SARA M. Efficient generic forward-secure signatures with an unbounded number of time periods[A]. Advances in Cryptology-EUROCRYPT 2002, Lecture Notes in Computer Science[C]. Springer-Verlag, Amsterdam, The Netherlands, 2002.400-417.

[6] ANTON K, LEONID R. Forward-secure signatures with fast key update[A]. Proc of the 3rd International Conference on Security in Communication Networks[C]. Springer-Verlag, Amalfi, Italy, 2003.241-256.

[7] 李如鵬,于佳,李國文等. 高效撤銷成員的前向安全群簽名方案[J].計算機研究與發展, 2007, 44(7): 1219-1226.LI R P, YU J, LI G W, et al. Forward secure group signature schemes with efficient revocation[J]. Journal of Computer Research and Development, 2007, 44(7): 1219-1226.

[8] 王曉明, 符方偉, 張震. 前向安全的多重數字簽名方案[J].計算機學報, 2004, 27(9): 1177-1181.WANG X M, FU F W, ZHANG Z. A forward secure multisignature scheme[J]. China Journal of Computers, 2004, 27(9): 1177-1181.

[9] 彭華熹, 馮登國. 一個基于雙線性映射的前向安全門限簽名方案[J].計算機研究與發展, 2007, 44(4): 574-580.PENG H X, FENG D G. A forward secure threshold signature scheme from bilinear pairing[J]. Journal of Computer Research and Development, 2007, 44(4): 574-580.

[10] 蘇云學, 祝躍飛. 一個前向安全的電子貨幣系統[J]. 計算機學報,2004, 27(1): 136-139.SU Y X, ZHU Y F. A forward-secure e-cash system[J]. China Journal of Computers, 2004, 27(1): 136-139.

[11] 吳樹華, 祝躍飛. 一個前向安全的基于口令認證的三方密鑰交換協議[J]. 計算機學報, 2007, 30(10): 1833-1841.WU S H, ZHU Y F. Three-party password-based authenticated key exchange with forward-security[J]. China Journal of Computers, 2007,30(10): 1833-1841.

[12] 吳克力, 王慶梅, 劉鳳玉. 一種具有前向安全的數字簽名方案[J].計算機工程, 2003, 29(8): 122-123.WU K L, WANG Q M, LIU F Y. A forward security digital signature scheme[J]. Computer Engineering, 2003, 29(8): 122-123.

[13] 秦波, 王尚平, 王曉峰等. 一種新的前向安全可證實數字簽名方案[J]. 計算機研究與發展, 2003, 40(7): 1016-1020.QIN B, WANG S P, WANG X F, et al. A new forward-secure and confirmer digital signature scheme[J]. Journal of Computer Research and Development, 2003, 40(7): 1016-1020.

[14] 王曉明, 陳火炎, 符方偉. 前向安全的代理簽名方案[J]. 通信學報,2005, 26(11): 38-42.WANG X M, CHEN H Y, FU F W. Forward secure proxy signature scheme[J]. Journal on Communications, 2005, 26(11): 38-42.

[15] 譚作文, 劉卓軍. 一個前向安全的強代理簽名方案[J]. 信息與電子工程, 2003,1(4): 257-259.TAN Z W, LIU Z J. A forward secure strong proxy signature[J]. Information and Electronic Engineering, 2003, 1(4): 257-259.

[16] 夏祥勝, 耿永軍, 洪帆等. 前向安全的有代理的多重數字簽名方案[J]. 小型微型計算機系統, 2009, 30(5): 854-858.XIA X S, GENG Y J, HONG F, et al. Forward secure multisignature with proxy signers scheme[J]. Journal of Chinese Computer Systems,2009, 30(5): 854-858.

[17] 彭仁杰, 楊小東. 基于 Euler準測的前向安全的數字簽名方案[J].計算機應用與軟件, 2009, 26(4): 260-261.PENG R J, YANG X D. A forward secure digital signature scheme based on Euler’s criterion[J]. Computer Applications and Software,2009, 26(4): 260-261.

[18] 王玲玲, 張國印, 馬春光. 標準模型下基于雙線性對的前向安全環簽名方案[J]. 電子與信息學報, 2009, 31(2): 448-452.WANG L L, ZHANG G Y, MA C G. A forward-secure ring signature scheme based on bilinear pairing in standard model[J]. Journal of Electronics & Information Technology, 2009, 31(2): 448-452.

[19] 夏峰, 謝冬青, 匡華清. 一類前向安全數字簽名方案的分析與改進[J]. 計算機工程, 2006, 32(16): 146-147.XIA F, XIE D Q, KUANG H Q. Analysis and improvement for a class of forward security digital signature scheme[J]. Computer Engineering,2006, 32(16): 146-147.