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

1.鄭州師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院，鄭州450044

2.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京100124

1 引言

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

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

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

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

文獻(xiàn)[14]提出了基于可驗(yàn)證隨機(jī)數(shù)的前后向安全群簽名方案，方案需可信管理中心，缺乏成員對(duì)群管理中心的反向監(jiān)督機(jī)制，管理中心很容易成為整個(gè)簽名系統(tǒng)的安全隱患。文獻(xiàn)[15]提出了一種具有雙向安全性的基于身份的短簽名方案，該方案算法簡(jiǎn)單，但沒有考慮成員加入和退出問題。文獻(xiàn)[16]提出了基于中國(guó)剩余定理的簽名方案，該方案無需可信中心，解決了成員撤銷問題，但該方案不滿足后向安全。為解決以上問題，本文在已有研究的基礎(chǔ)上，提出一種具有強(qiáng)前向安全性的動(dòng)態(tài)門限簽名方案。方案基于中國(guó)剩余定理，無需可信中心，避免了可信中心權(quán)威欺詐等行為，定期更新成員私鑰，使方案滿足強(qiáng)前向安全性，同時(shí)解決了成員加入和退出等問題。

2 背景知識(shí)

2.1 前向安全性介紹

前向安全性理論[2]是指將整個(gè)簽名時(shí)間劃分為T個(gè)周期，在整個(gè)簽名時(shí)間內(nèi)公鑰持續(xù)保持不變，成員私鑰則隨著簽名周期的遞進(jìn)不斷更新，在每個(gè)周期內(nèi)使用成員當(dāng)前周期的私鑰產(chǎn)生簽名。當(dāng)某個(gè)周期內(nèi)某成員私鑰泄露時(shí)，由于私鑰的動(dòng)態(tài)更新，惡意攻擊者無法利用當(dāng)前周期的私鑰修改該周期之前的簽名信息，即當(dāng)前周期私鑰對(duì)前期簽名無效，因此在當(dāng)前周期之前產(chǎn)生的簽名是安全有效的。前向安全性保證了前期簽名信息的安全。

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

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

（2）在整個(gè)簽名時(shí)間內(nèi)公鑰PK 不變，私鑰SK 隨著時(shí)間周期的遞進(jìn)而動(dòng)態(tài)更新。

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

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

圖1 私鑰更新示意圖

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

2.2 Asmuth-Bloom秘密共享方案

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

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

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

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

z ≡zimod di

根據(jù)中國(guó)剩余定理，該方程組有且只有唯一解：

這里：

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

2.3 離散對(duì)數(shù)難題

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

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

3 本文方案

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

具有強(qiáng)前向安全性的門限簽名方案架構(gòu)圖如圖2所示。

如圖2所示，具有強(qiáng)前向安全的動(dòng)態(tài)門限簽名包括：產(chǎn)生簽名、私鑰更新、成員加入和撤銷三個(gè)方面的內(nèi)容。

3.1 產(chǎn)生簽名

為方便理解，對(duì)本文定義符號(hào)解釋如表1所示。

圖2 強(qiáng)前向安全門限簽名方案架構(gòu)圖

表1 符號(hào)說明

（1）系統(tǒng)初始化。Q={ }

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

（2）產(chǎn)生秘密份額。成員Qi隨機(jī)選取子秘密α0i和整數(shù)，滿足如下條件：

成員Qi為其他成員計(jì)算秘密份額：

（3）Qi計(jì)算驗(yàn)證信息。

（4）產(chǎn)生成員私鑰及組密鑰。Qj收到其他t-1 個(gè)成員發(fā)送來的秘密份額，根據(jù)其廣播的消息驗(yàn)證收到消息的正確性，以確保信息未被篡改：

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

則成員Qj的個(gè)人公鑰為：

根據(jù)每個(gè)成員選取的子秘密α0

i ，產(chǎn)生組私鑰：

則組公鑰為：

（5）產(chǎn)生簽名。任意t 個(gè)成員協(xié)作產(chǎn)生簽名。首先由每個(gè)成員產(chǎn)生部分簽名，然后由t 個(gè)部分簽名合成消息M 的簽名。每個(gè)成員Qi選取隨機(jī)數(shù)xi∈Zp，計(jì)算：

廣播信息gxi，Qj收到zi后，計(jì)算：

Qi計(jì)算部分簽名R0i：

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

3.2 私鑰更新

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

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

設(shè)更新周期為T ，則詳細(xì)的更新算法步驟如下：

（1）成員Qi隨機(jī)選取整數(shù)，滿足初始條件。

（2）成員Qi計(jì)算更新因子：

（3）成員Qi計(jì)算驗(yàn)證信息

（4）成員Qj收到Qi發(fā)送的信息，以及，根據(jù)廣播信息，由以下兩個(gè)等式驗(yàn)證ωTi和的正確性：

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

更新產(chǎn)生的新私鑰，仍然可以按照簽名過程進(jìn)行簽名和驗(yàn)證。更新過程中組公鑰不變，因此更新前的簽名依然有效。

3.3 成員加入和撤銷

3.3.1 成員加入

當(dāng)有新成員加入時(shí)，任意t 個(gè)老成員相互協(xié)作產(chǎn)生偽私鑰，并發(fā)送給新成員，新成員收到t 份偽私鑰后計(jì)算自己的私鑰。假設(shè)某一時(shí)刻有新成員Qn+1加入，其加入過程的算法如下：

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

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

然后由每個(gè)老成員Qj計(jì)算偽私鑰：

并將H'j發(fā)送給Qn+1。

（3）新成員計(jì)算自己的私鑰。當(dāng)Qn+1收到來自其他t 個(gè)老成員的偽私鑰H'i后，計(jì)算自己的私鑰：

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

3.3.2 成員撤銷

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

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

（2）Qi計(jì)算并驗(yàn)證信息。根據(jù)收到的其他成員發(fā)送的秘密份額和廣播信息，Qi計(jì)算驗(yàn)證收到的來自其他成員發(fā)送的信息的正確性。

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

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

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

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

4 方案分析

4.1 正確性分析

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

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

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

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

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

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

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

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

令：

則：

根據(jù)中國(guó)剩余定理，解如下同余方程組：

可得唯一解：

因此：

令：

則：

當(dāng)t ＞2 時(shí)，根據(jù)文獻(xiàn)[18]可知：

由式（11）、（12）有：

因此：

則有：

故有：

經(jīng)驗(yàn)證，等式（13）成立，則證明簽名信息真實(shí)有效，由部分簽名合成的最終簽名為有效簽名，接受該簽名。

定理4 私鑰動(dòng)態(tài)更新后，新私鑰可以通過3.1 節(jié)產(chǎn)生簽名過程產(chǎn)生簽名，且該簽名依然能夠通過簽名驗(yàn)證等式（13）的驗(yàn)證，即證明由新私鑰產(chǎn)生的簽名有效。

證明

令：

則：

根據(jù)中國(guó)剩余定理解同余式方程組：

得唯一解：

令：

則：

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

由文獻(xiàn)[18]可知，當(dāng)t ＞2 時(shí)有：

根據(jù)式（12）、（13）有：

由式（21）有：

所以，有：

經(jīng)驗(yàn)證等式（13）成立，故由更新后的新私鑰產(chǎn)生的簽名有效。

定理5 在新成員加入時(shí)，由老成員協(xié)作為新加入成員產(chǎn)生的新私鑰式（17），需由原私鑰式（15）驗(yàn)證新成員私鑰的有效性。

證明

定理6 當(dāng)有成員退出時(shí)，其他成員更新自己的私鑰，更新后的新私鑰式（19）依然有效，即驗(yàn)證公式（19）成立。

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

4.2 安全性分析

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

4.2.1 前向安全性分析

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

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

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

4.2.2 后向安全性分析

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

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

4.2.3 不可偽造性分析

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

若惡意攻擊者Q'i 想替代合法成員Qi偽造成員秘密選取的秘密數(shù)。則惡意攻擊者Q'i隨機(jī)選取秘密數(shù)并保存，由于所以，在計(jì)算組私鑰的過程中必然會(huì)有=SKT，由于每個(gè)成員均保存了一份，當(dāng)組成員發(fā)現(xiàn)成員Q'

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

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

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

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

5 性能分析

5.1 效率分析

本文設(shè)計(jì)的具有強(qiáng)前向安全性的動(dòng)態(tài)門限簽名方案，其計(jì)算難度等價(jià)于求解離散對(duì)數(shù)難題。

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

本文將在簽名生成、簽名驗(yàn)證和密鑰更新三個(gè)階段展開，對(duì)本文方案和文獻(xiàn)[7，10-11]在時(shí)間計(jì)算復(fù)雜度上進(jìn)行對(duì)比分析。其對(duì)比結(jié)果如表3所示。

表3是本文基于中國(guó)剩余定理的強(qiáng)前向簽名算法，與其他具有強(qiáng)前向安全的簽名算法時(shí)間計(jì)算復(fù)雜度對(duì)比結(jié)果。以上方案都具有強(qiáng)前向安全性，通過對(duì)比發(fā)現(xiàn)，本文方案的時(shí)間計(jì)算復(fù)雜度明顯低于其他幾個(gè)方案。

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

文獻(xiàn)[10]基于強(qiáng)RSA假設(shè)，在方案中引入偽隨機(jī)函數(shù)：種子seed和Hash函數(shù)來生成素?cái)?shù)，在私鑰演化過程中私鑰由兩部分的乘積組成，需要分別計(jì)算部分私鑰然后合成私鑰，這個(gè)過程大大增加了時(shí)間開銷，計(jì)算復(fù)雜度較高。

文獻(xiàn)[11]利用雙線性對(duì)性質(zhì)構(gòu)造了前后向安全的簽名算法，方案在產(chǎn)生簽名算法時(shí)引入雙線性對(duì)運(yùn)算和哈希計(jì)算，在驗(yàn)證過程需經(jīng)兩次雙線性運(yùn)算進(jìn)行驗(yàn)證，大大增加了系統(tǒng)計(jì)算量，執(zhí)行效率較低。

上述幾個(gè)方案中涉及的算法為：e、m、u、r 、h，在相同操作系統(tǒng)下運(yùn)行一萬次得到這四個(gè)算法的時(shí)間計(jì)算復(fù)雜度大小順序?yàn)椋篹 ＞m ＞u ＞h ＞r，也即雙線性對(duì)計(jì)算復(fù)雜度最高，接下來依次為模冪計(jì)算、模逆計(jì)算、哈希計(jì)算和模乘運(yùn)算。本文方案主要涉及模冪、模逆和模乘運(yùn)算。

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

由以上分析，顯然本文方案所涉及的運(yùn)算較其他幾個(gè)方案算法更簡(jiǎn)單，計(jì)算復(fù)雜度更低、效率更高。

5.2 仿真實(shí)驗(yàn)

該仿真實(shí)驗(yàn)的環(huán)境為：64位Window 10操作系統(tǒng)，MyEclipse2015 系統(tǒng)，CPU 為英特爾酷睿i5-8300H 處理器，主頻2.3 GHz，內(nèi)存8 GB。將本文方案與文獻(xiàn)[11]在簽名生成和驗(yàn)證階段的時(shí)間開銷進(jìn)行仿真實(shí)驗(yàn)。結(jié)果顯示如圖3。

由圖3 可知，本文方案和文獻(xiàn)[11]隨著成員數(shù)n 的增加耗時(shí)均成上升趨勢(shì)，這是因?yàn)檎麄€(gè)簽名過程與成員n 成正相關(guān)的關(guān)系。從實(shí)驗(yàn)數(shù)據(jù)看，文獻(xiàn)[11]較本文方案耗時(shí)更多，這是由于文獻(xiàn)[11]在簽名生成和驗(yàn)證階段均需進(jìn)行雙線性對(duì)運(yùn)算，該運(yùn)算計(jì)算復(fù)雜度相對(duì)較高。

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

表2 時(shí)間復(fù)雜度表示符號(hào)

表3 簽名方案計(jì)算復(fù)雜度對(duì)比

圖3 成員數(shù)n 與時(shí)間開銷關(guān)系圖

圖4 驗(yàn)證效率與成員數(shù)n 的關(guān)系圖

6 結(jié)語

本文設(shè)計(jì)的具有強(qiáng)前向安全的動(dòng)態(tài)門限簽名方案，無可信中心，由集合內(nèi)部成員相互協(xié)作產(chǎn)生部分簽名并合成簽名，同時(shí)實(shí)現(xiàn)了成員之間相互驗(yàn)證功能。在組公鑰不變的前提下解決了成員加入和退出問題。周期性更新成員私鑰，使其具有強(qiáng)前向安全性。方案基于中國(guó)剩余定理與其他方案相比具有計(jì)算量小、效率高的優(yōu)點(diǎn)。