具有強前向安全性的動態門限簽名方案

程亞歌，胡明生，公 備，王利朋，徐二鋒

1.鄭州師范學院 信息科學與技術學院，鄭州450044

2.北京工業大學 計算機學院，北京100124

1 引言

在如今互聯網處于爆炸式發展時期，它在給人們帶來便利的同時，也存在著隱私泄露、信息被篡改的事實。網絡的飛速發展促使了數字簽名技術的廣泛應用，然而數字簽名技術存在的最大挑戰來自于私鑰泄露帶來的簽名被篡改、偽造導致的信息失實的嚴重后果。在這樣的大背景下前向安全的思想應運而生。

1997 年Anderson[1]首次在歐洲的密碼學大會上提出前向安全的概念，其核心思想在于密鑰的更新。在此基礎上，Bellare和Miner[2]于1999年基于One-Schnorr和Fiat-Shamir 認證方案，提出了前向安全性理論，并首次通過算法實現了前向安全的數字簽名方案。1997 年Anderson 對前向安全方案進行總結提出了兩種安全性[3]：前向安全性和后向安全性。2001 年Mike Burmester 等人提出了強前向安全性的定義[4]，即一個簽名體制在當前密鑰泄露時，不會對在此之前和之后的簽名造成影響。它的提出極大地提升了簽名效率，不必因每次密鑰泄露就重新構建新的密鑰系統。強前向安全的這一特性極大地提高了簽名系統的安全性，因此在近20 年的簽名方案研究歷程中被眾多國內外研究者追捧。

鑒于強前向安全性對于數字簽名安全性的重要性，國內外學者致力于這一方面已做了大量的工作。文獻[5]提出了一種前向安全數字簽名方案的分析及改進，該方案借助單向散列鏈技術，對劉亞麗等人方案進行了改進，使方案滿足后向安全。文獻[6]引入反向安全監測，采用哈希鏈技術，使方案滿足了后向安全性，但并沒有對密鑰泄露之后采取措施，且方案耗時較長。文獻[7]提出一種強前向安全的數字簽名方案，該方案基于Guillou-Quisquater 簽名體制和Rabin 密碼體制，并引入雙密鑰，在簽名生成過程中需要計算雜湊函數、雙密鑰等其他信息，計算復雜。文獻[8]提出基于離散對數的雙向安全簽名方案，該方案引入正向和逆向的密鑰算法，同時利用哈希進行盲化，設計簡單，效率較高，但該方案不能抵抗共謀攻擊。文獻[9]利用哈希鏈和秘密共享技術相結合，提出前后向安全的群簽名方案，該方案需要群管理員對成員進行統一管理，權利過于集中，容易造成系統擁塞，效率低等問題。

文獻[10]提出一個前向和后向安全的數字簽名方案，該方案基于強RSA假設，在密鑰演化過程中加入后向元素，使方案滿足前后向安全，但該方案在密鑰生成和更新階段計算量較大處理速度較慢。文獻[11]基于雙線性對算法，將雙私鑰更新方法與環簽名有效地結合，提出了可驗證的強前向安全的環簽名方案，方案在簽名及驗證過程中均需雙線性對計算，使得簽名效率較低。文獻[12]提出一種前向后向安全的數字簽名方案，該方案利用多變量公鑰密碼理論和零知識證明技術構造了基于身份識別的改進模型的密鑰更新算法，方案需計算大量多項式，而多項式階數較高導致計算復雜度高、效率低。文獻[13]提出了一種基于WEB的數字簽名方案，該方案采用基于證據與證據相結合的檢測方法，保證了信息的安全性和完整性，但該方案構造復雜，算法執行效率低。以上方案均滿足前后向安全，但在執行效率方面有待提高。

文獻[14]提出了基于可驗證隨機數的前后向安全群簽名方案，方案需可信管理中心，缺乏成員對群管理中心的反向監督機制，管理中心很容易成為整個簽名系統的安全隱患。文獻[15]提出了一種具有雙向安全性的基于身份的短簽名方案，該方案算法簡單，但沒有考慮成員加入和退出問題。文獻[16]提出了基于中國剩余定理的簽名方案，該方案無需可信中心，解決了成員撤銷問題，但該方案不滿足后向安全。為解決以上問題，本文在已有研究的基礎上，提出一種具有強前向安全性的動態門限簽名方案。方案基于中國剩余定理，無需可信中心，避免了可信中心權威欺詐等行為，定期更新成員私鑰，使方案滿足強前向安全性，同時解決了成員加入和退出等問題。

2 背景知識

2.1 前向安全性介紹

前向安全性理論[2]是指將整個簽名時間劃分為T個周期，在整個簽名時間內公鑰持續保持不變，成員私鑰則隨著簽名周期的遞進不斷更新，在每個周期內使用成員當前周期的私鑰產生簽名。當某個周期內某成員私鑰泄露時，由于私鑰的動態更新，惡意攻擊者無法利用當前周期的私鑰修改該周期之前的簽名信息，即當前周期私鑰對前期簽名無效，因此在當前周期之前產生的簽名是安全有效的。前向安全性保證了前期簽名信息的安全。

前向安全性理論具體實施過程如下：

（1）Pi( )i=1,2,…,n 將整個簽名的有效期劃分為T 個周期[ 0,T ]。

（2）在整個簽名時間內公鑰PK 不變，私鑰SK 隨著時間周期的遞進而動態更新。

（3）在第j 個周期時，成員Pi( )i=1,2,…,n 計算SKij=h( S Ki(j-1))，其中h 是一個單向函數。

（4）Pi計算出SKij后立即刪除SKi(j-1)。這樣即使有某攻擊者獲得了成員Pi第j 個周期的私鑰SKi(j-1)，也不能獲得該周期之前的私鑰SKi0,SKi1,…,SKi(j-1)的任何信息。私鑰更新示意圖如圖1所示。

圖1 私鑰更新示意圖

強前向安全性[4]是指一個簽名體制當前密鑰的泄露不會對之前和之后的簽名產生影響。主要包含兩方面的安全[3]：（1）前向安全，是指當前周期的密鑰泄露，對在此周期之前完成的簽名信息不會產生威脅，即保證前期簽名信息的安全。（2）后向安全，是指當前周期的密鑰泄露，對在此周期之后即將生成的密鑰信息沒有影響，他人無法根據當前密鑰偽造之后周期的密鑰信息，也無法偽造簽名，即保證未來周期的成員密鑰及簽名信息安全。

2.2 Asmuth-Bloom秘密共享方案

Asmuth-Bloom 秘 密 共 享 方 案[17]，是 由Asmuth 和Bloom 在1983 年時提出，方案主要包含以下三個步驟：初始化、秘密分發及秘密恢復。具體執行過程如下：

（1）初始化。假設DC 是秘密分發者，P={P1,P2,…,Pn}是n 個成員組成的集合，門限值為t ，需要共享的秘密為S。秘密分發者DC 選擇大素數q( )q ＞S ，以及嚴格遞增正整數序列d={ }d1,d2,…,dn，且q、d必須滿足如下條件：

（2）秘密分發。秘密分發者DC 隨機選擇整數A，使 其 滿 足：；并計算：z=S+Aq，zi=z mod di(i=1,2,…,n) ，然后將( )zi，di發送給Pi(i=1,2,…,n)，作為Pi的秘密份額。

（3）秘密恢復。任意成員可以通過相互之間交換秘密份額恢復秘密S。任意選取t 個成員作為恢復秘密的一組成員，成員之間通過相互交換秘密后，任意成員Qi都可以建立如下同余方程組來恢復秘密：

z ≡zimod di

根據中國剩余定理，該方程組有且只有唯一解：

這里：

因此，可求出S=z-Aq，也即S=z mod q。

2.3 離散對數難題

本文所涉及的難題為離散對數難題，是指給定有限域GF( p )，當模p 有原根時，設g 為模的一個原根（即有限循環群的生成元），任給元素y ∈，求解唯一的x，滿足1 ≤x ＜p-1，使得：稱為以p 為模，以g 為底y 的離散對數。

這里對于已知的g 和y 要求解出唯一的x 屬于離散對數難題。

3 本文方案

本文基于中國剩余定理提出了一種具有強前向安全性的動態門限簽名方案。本文方案無需可信中心，在保持組公鑰和組私鑰不變的前提下，定期更新成員私鑰，使其具有強前向安全性，且允許成員加入和退出。

具有強前向安全性的門限簽名方案架構圖如圖2所示。

如圖2所示，具有強前向安全的動態門限簽名包括：產生簽名、私鑰更新、成員加入和撤銷三個方面的內容。

3.1 產生簽名

為方便理解，對本文定義符號解釋如表1所示。

圖2 強前向安全門限簽名方案架構圖

表1 符號說明

（1）系統初始化。Q={ }

Q1,Q2,…,Qn是n 個成員的集合，p 和q 是兩個大素數，滿足,d={d1,d2,…,dn}是一組嚴格單調遞增的正整數序列，q 和d 滿足Asmuth-Bloom 秘密共享方案，t 為門限值，有限域GF( p )上的生成元為g ，待簽名消息為M ，為最小的t 個di之積，公開n,t,g,p,q,d 以及N 。

（2）產生秘密份額。成員Qi隨機選取子秘密α0i和整數，滿足如下條件：

成員Qi為其他成員計算秘密份額：

（3）Qi計算驗證信息。

（4）產生成員私鑰及組密鑰。Qj收到其他t-1 個成員發送來的秘密份額，根據其廣播的消息驗證收到消息的正確性，以確保信息未被篡改：

如果上述兩個等式成立，則證明收到的消息正確未被篡改，此時Qj計算個人私鑰：

則成員Qj的個人公鑰為：

根據每個成員選取的子秘密α0

i ，產生組私鑰：

則組公鑰為：

（5）產生簽名。任意t 個成員協作產生簽名。首先由每個成員產生部分簽名，然后由t 個部分簽名合成消息M 的簽名。每個成員Qi選取隨機數xi∈Zp，計算：

廣播信息gxi，Qj收到zi后，計算：

Qi計算部分簽名R0i：

（6）合成簽名。簽名合成者收到t 個成員的部分簽名后，合成簽名R：

3.2 私鑰更新

成員私鑰生成后，攻擊者只要有足夠時間便可竊取該成員私鑰信息，進而獲得t 個成員私鑰，并偽造簽名，這種攻擊機制稱為移動攻擊。為了防止移動攻擊，成員需要定期更新自己的私鑰。私鑰的更新必須確保之前的簽名仍然有效，因此必須保證更新過程不更改組公鑰信息。

私鑰更新確保即使攻擊者獲得了T 時刻的成員私鑰，也無法獲得T-1 時刻的私鑰，而且也不能偽造T+1時刻的私鑰，使得攻擊者即使知曉了T 時刻的成員私鑰，也無法修改之前的簽名，更不能偽造之后的簽名。本文方案提出的私鑰更新機制具有強前向安全性，能夠有效抵御移動攻擊，具有較高的安全性。

設更新周期為T ，則詳細的更新算法步驟如下：

（1）成員Qi隨機選取整數，滿足初始條件。

（2）成員Qi計算更新因子：

（3）成員Qi計算驗證信息

（4）成員Qj收到Qi發送的信息，以及，根據廣播信息，由以下兩個等式驗證ωTi和的正確性：

（5）Qj在T-2 時段的私鑰為，則T 時段的私鑰為：

更新產生的新私鑰，仍然可以按照簽名過程進行簽名和驗證。更新過程中組公鑰不變，因此更新前的簽名依然有效。

3.3 成員加入和撤銷

3.3.1 成員加入

當有新成員加入時，任意t 個老成員相互協作產生偽私鑰，并發送給新成員，新成員收到t 份偽私鑰后計算自己的私鑰。假設某一時刻有新成員Qn+1加入，其加入過程的算法如下：

（1）選擇模數dn+1。新成員Qn+1選取模數dn+1并公開，使其滿足Asmuth-Bloom秘密共享方案。

（2）計算偽私鑰。任意t 個老成員協助新加入成員Qn+1計算偽私鑰。 Qi隨機選取t 個隨機數λij∈Zp，并將λij發送給Qj，Qj收到λij后由以下等式計算λ'j：

然后由每個老成員Qj計算偽私鑰：

并將H'j發送給Qn+1。

（3）新成員計算自己的私鑰。當Qn+1收到來自其他t 個老成員的偽私鑰H'i后，計算自己的私鑰：

在這個過程中組公鑰、組私鑰以及其他成員的私鑰均未發生變化，因此，對整個簽名過程沒有任何影響。

3.3.2 成員撤銷

成員的撤銷必須遵循在保持組公鑰和組私鑰不變的前提下，重新構建其余成員的秘密份額，并更新其私鑰，使被刪除成員的秘密份額及私鑰無效，從而無法參與后期的簽名過程。在后期的更新以及簽名階段，其他成員不再接受被刪除成員分發的信息，也不再為被刪除成員分發信息。假設在第T 個周期有成員Qk決定離開，其他n-1 個成員重新構建自己的秘密份額：

（1）成員Qi( i ≠k )隨機選取，并為其他n-2 個成員計算秘密份額：

（2）Qi計算并驗證信息。根據收到的其他成員發送的秘密份額和廣播信息，Qi計算驗證收到的來自其他成員發送的信息的正確性。

（3）其他成員計算自己的新私鑰。Qj收到ωT′i和φT′ij后，由以下驗證信息其正確性：

若等式成立，則Qj重新計算自己的新私鑰：

至此，其他n-1 個成員的私鑰已重新構建，對于要撤銷的成員Qk不再執行此過程，其秘密份額失效，成員Qk被刪除。

在現有的大多數門限簽名方案中，只考慮了成員加入，沒有考慮成員退出問題，允許成員退出的算法，大都依賴可信中心，由可信中心直接刪除，不能排除可信中心權威欺詐的可能性。本文方案在沒有可信中心的前提下，確保成員退出時組公鑰、組私鑰保持不變，仍可用于簽名及驗證，降低了系統更新代價。

4 方案分析

4.1 正確性分析

定理1 成員Qj收到其他成員Qi( i=1,2,…,n,i ≠j )發送的子秘密和整數時，鑒別信息來源的真實性，確保信息未被篡改，即證明驗證等式（7）成立。

證明等式（7）成立，則證明該信息真實可信，其他成員接受Qi發送的信息。

定理2 成員Qj收到其他n-1 個成員發來的秘密份額后，鑒別秘密份額的真實性，確保秘密份額來源可信且未被篡改，即證明驗證等式（8）成立。

證明 由式（5）、（6），可得：

原式得證，等式（8）成立，則證明成員Qj收到的其他成員發送的秘密份額真實可信，接受此信息。

如果成員Qi提供了真實的信息，則式（7）、（8）一定成立。反之，如果驗證結果表明等式不成立，則說明成員沒有提供真實的信息，則該成員不可信，不接受此成員發送的信息。

定理3 由部分簽名式（11）合成的最終簽名式（12），需由簽名驗證公式（13）驗證簽名是否成立，即證明等式（13）成立。

證明 由式（3）和（9），成員私鑰為：

令：

則：

根據中國剩余定理，解如下同余方程組：

可得唯一解：

因此：

令：

則：

當t ＞2 時，根據文獻[18]可知：

由式（11）、（12）有：

因此：

則有：

故有：

經驗證，等式（13）成立，則證明簽名信息真實有效，由部分簽名合成的最終簽名為有效簽名，接受該簽名。

定理4 私鑰動態更新后，新私鑰可以通過3.1 節產生簽名過程產生簽名，且該簽名依然能夠通過簽名驗證等式（13）的驗證，即證明由新私鑰產生的簽名有效。

證明

令：

則：

根據中國剩余定理解同余式方程組：

得唯一解：

令：

則：

由式（1）、（2）和（14）可知：

由文獻[18]可知，當t ＞2 時有：

根據式（12）、（13）有：

由式（21）有：

所以，有：

經驗證等式（13）成立，故由更新后的新私鑰產生的簽名有效。

定理5 在新成員加入時，由老成員協作為新加入成員產生的新私鑰式（17），需由原私鑰式（15）驗證新成員私鑰的有效性。

證明

定理6 當有成員退出時，其他成員更新自己的私鑰，更新后的新私鑰式（19）依然有效，即驗證公式（19）成立。

成員退出時，其他成員更新自己的私鑰，即將退出成員不再執行此過程，整個過程類似于更新過程。證明過程同定理4，在此不再展開。

4.2 安全性分析

本文設計的具有強前向安全性的( )t,n 動態門限簽名方案，攻擊者即使竊取了某一周期的私鑰也無法偽造在此之前和之后的所有簽名。根據中國剩余定理，至少需要t 個同余方程組才能求解方程組，因此只有達到門限值即t 個成員聯合才能完成簽名，少于t 個成員的聯合攻擊屬于無效攻擊。

4.2.1 前向安全性分析

假設某攻擊者竊取了第T 周期成員Qj的私鑰HTj=試圖計算，則攻擊者必須先計算，而：

所以有：則攻擊者需要在有限時間內，即第T 周期內同時獲得所有成員前T 個周期的隨機數以及所有成員的初始秘密份額，而是有成員秘密選取的攻擊者不可能獲得，成員初始秘密份額中的隨機數由成員秘密選取并保存攻擊者也不可能知曉。

因此，攻擊者無法根據T 時段的私鑰計算得到T周期之前的成員私鑰，方案具有前向安全性。

4.2.2 后向安全性分析

若攻擊者想由T 時段的私鑰偽造T 時間段之后的成員私鑰也是不能實現的。由成員私鑰可知，攻擊者若要由當前私鑰偽造T周期之后的私鑰，假設攻擊者要偽造第T+1 周期的私鑰則攻擊者必須先計算和，而由上一段的分析可知，攻擊者不可能在有效時間內計算得到T 周期之前的私鑰，因此攻擊者無法獲得，同時由上一段的分析，攻擊者也無法通過計算得到成員T+1 周期的秘密份額

因此，攻擊者不可能獲得第T+1 周期的私鑰，不可能偽造T+1 周期之后的所有成員私鑰。故攻擊者不能在有限的周期內獲得當前周期之后的成員私鑰，即方案具有后向安全性。

4.2.3 不可偽造性分析

不可偽造性是指任意惡意攻擊者以及合法成員均不能偽造其他成員生成簽名信息。本文方案具有強前向安全性的門限簽名，無需可信中心，成員協作產生簽名，可以有效地避免可信中心的權威欺詐等問題。為方便下文描述，假設惡意攻擊者為Q'i，合法成員為Qi。

若惡意攻擊者Q'i 想替代合法成員Qi偽造成員秘密選取的秘密數。則惡意攻擊者Q'i隨機選取秘密數并保存，由于所以，在計算組私鑰的過程中必然會有=SKT，由于每個成員均保存了一份，當組成員發現成員Q'

i 發送的信息有誤，則不接受其發送的信息，Q'i無法參與到簽名算法系統中，因此攻擊者Q'i 無法偽造成員Qi的秘密信息。

若惡意攻擊者想通過偽造秘密份額從而偽造成員私鑰，由于秘密份額q mod dj，在驗證階段當其他成員收到Q'

另外，惡意攻擊者Q'i 可能截獲其他n-1 個成員發送的信息，想通過計算成員私鑰，由于每個成員各自保留了攻擊者無法獲得。而攻擊者可能截獲和，試圖通過和計算出和從而得到，然而通過和求解和是離散對數難題，攻擊者無法通過求解得到。

由以上分析可知，本文方案具有不可偽造性。

5 性能分析

5.1 效率分析

本文設計的具有強前向安全性的動態門限簽名方案，其計算難度等價于求解離散對數難題。

為方便描述，本文定義符號表示不同運算的計算復雜度，如表2。表3 是本文方案與文獻[7，10-11]的計算復雜度對比表。計算復雜度分為時間復雜度和空間復雜度，本文主要從時間復雜度層面展開分析。以上方案中涉及的運算主要有雙線性對、Hash 運算、模冪運算、模逆運算、模乘運算、模加和模減等。鑒于模加、模減與模乘法運算與其他運算相比計算量較小可忽略不計，因此不予進行分析。

本文將在簽名生成、簽名驗證和密鑰更新三個階段展開，對本文方案和文獻[7，10-11]在時間計算復雜度上進行對比分析。其對比結果如表3所示。

表3是本文基于中國剩余定理的強前向簽名算法，與其他具有強前向安全的簽名算法時間計算復雜度對比結果。以上方案都具有強前向安全性，通過對比發現，本文方案的時間計算復雜度明顯低于其他幾個方案。

文獻[7]引入雙密鑰，在簽名生成過程中需要計算雜湊函數、雙密鑰等信息，從而增加了時間消耗，計算成本較高。

文獻[10]基于強RSA假設，在方案中引入偽隨機函數：種子seed和Hash函數來生成素數，在私鑰演化過程中私鑰由兩部分的乘積組成，需要分別計算部分私鑰然后合成私鑰，這個過程大大增加了時間開銷，計算復雜度較高。

文獻[11]利用雙線性對性質構造了前后向安全的簽名算法，方案在產生簽名算法時引入雙線性對運算和哈希計算，在驗證過程需經兩次雙線性運算進行驗證，大大增加了系統計算量，執行效率較低。

上述幾個方案中涉及的算法為：e、m、u、r 、h，在相同操作系統下運行一萬次得到這四個算法的時間計算復雜度大小順序為：e ＞m ＞u ＞h ＞r，也即雙線性對計算復雜度最高，接下來依次為模冪計算、模逆計算、哈希計算和模乘運算。本文方案主要涉及模冪、模逆和模乘運算。

由表3 可知，文獻[10]在這三個階段的計算復雜度都高于本文方案。文獻[7]和文獻[11]在更新階段優于本文，但是在簽名生成和驗證階段的計算復雜度均高于本文方案。文獻[7]需哈希運算和大量模冪運算，使得執行效率較低。文獻[11]基于雙線性對運算，而雙線性對運算的計算復雜度明顯高于模冪和模逆運算。

由以上分析，顯然本文方案所涉及的運算較其他幾個方案算法更簡單，計算復雜度更低、效率更高。

5.2 仿真實驗

該仿真實驗的環境為：64位Window 10操作系統，MyEclipse2015 系統，CPU 為英特爾酷睿i5-8300H 處理器，主頻2.3 GHz，內存8 GB。將本文方案與文獻[11]在簽名生成和驗證階段的時間開銷進行仿真實驗。結果顯示如圖3。

由圖3 可知，本文方案和文獻[11]隨著成員數n 的增加耗時均成上升趨勢，這是因為整個簽名過程與成員n 成正相關的關系。從實驗數據看，文獻[11]較本文方案耗時更多，這是由于文獻[11]在簽名生成和驗證階段均需進行雙線性對運算，該運算計算復雜度相對較高。

由圖4 可知，本文效率與方案[11]相比提升了80%左右，很大程度上降低了簽名系統時間開銷，執行效率較高。

表2 時間復雜度表示符號

表3 簽名方案計算復雜度對比

圖3 成員數n 與時間開銷關系圖

圖4 驗證效率與成員數n 的關系圖

6 結語

本文設計的具有強前向安全的動態門限簽名方案，無可信中心，由集合內部成員相互協作產生部分簽名并合成簽名，同時實現了成員之間相互驗證功能。在組公鑰不變的前提下解決了成員加入和退出問題。周期性更新成員私鑰，使其具有強前向安全性。方案基于中國剩余定理與其他方案相比具有計算量小、效率高的優點。