一個改進的前向安全的多重簽名方案

摘 要：對羅等人提出的前向安全的ElGamal型多重數字簽名方案進行了安全性分析，指出該方案不具有前向安全性。當某個簽名人的簽名密鑰泄露后，該方案存在偽造攻擊。最后，改進了這個方案，并分析了新方案的安全性。新方案能夠抵抗偽造攻擊和聯合攻擊，是一個安全、高效、實用的前向安全的多重簽名方案。

關鍵詞：前向安全；多重簽名；偽造攻擊；安全分析

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695(2009)06-2125-03

doi:10.3969/j.issn.1001-3695.2009.06.038

Improved forward secure multi-signature scheme

XIA Xiang-sheng1，2，HONG Fan1，CUI Guo-hua1

(1.Dept. of Information Security， College of Computer Science， Huazhong University of Science Technology， Wuhan 430074， China; 2.Dept.of Computer， Wuhan Polytechnic University， Wuhan 430023， China)

Abstract:This paper gave security analysis of the multisignature schemes——Luo et al.’s forward-secure multisignature scheme based on ElGamal type.The scheme didn’t meet property of forward security whilesome signer’s key was compromised.LUO’s scheme could’t resist forge attack.And finally，proposed the new improved scheme，analysed its security.The scheme can effectively resist forge attack and coordinate attacks.It’s a safe，efficient，practical and forward secure multisignature scheme.

Key words:forward security; multisignature; forgery attack; security analysis

在現實生活中，有時需要多個人合作簽署同一份消息，由此導致了多重簽名的產生。多重簽名的概念最早是由Itakura等人^[1]提出的，Ohta等人^[2]將多重簽名體制分為有序多重簽名和廣播多重簽名，Hardjono等人^[3]提出了基于離散對數困難性假設的多重數字簽名。人們對多重簽名的研究十分關注，目前已經提出若干多重數字簽名方案^[1~4]。然而，當簽名人的簽名密鑰泄露后，這些方案均不能提供任何保護，之前所產生的多重簽名將變成無效。如何減少由于密鑰泄露所帶來的對系統安全的影響，一直是人們十分關注的研究課題。1997年，Anderson^[5]首次提出了前向安全的概念，前向安全就是將整個有效時間分成若干個周期，在每個周期內使用不同的簽名密鑰產生簽名，而驗證簽名的公鑰在整個有效時間內不變，即使當前周期的簽名密鑰被泄露，也不影響此周期之前簽名的有效性，從而大大減少了由于密鑰泄露所帶來的對系統安全的影響。文獻[6]首次將前向安全概念引入多重數字簽名體制，之后將前向安全機制引入數字簽名方案成為研究熱點和研究者關注的課題^[7~9]。羅麗平等人^[10]提出了一個具有前向安全的ElGamal型多重數字簽名方案，他們聲稱該方案不僅具有前向安全性，而且比文獻[6]所提方案計算代價小、簡單、實用。本文對羅方案的前向安全的有序多重簽名方案進行了安全性分析。

1 羅的前向安全的有序多重簽名方案的安全性分析

1.1 羅的前向安全的有序多重簽名方案

1）系統初始化 簽名中心（SC）首先選擇一個p，g是GF(p)的生成元，SC選擇安全的單向函數H和時間周期T，然后為每個簽名人ui選擇不同的SKi0∈(0，p)，計算Yi=gSK2T+1i0 mod p(1≤i≤n)作為驗證公鑰。ui(1≤i≤n)選擇一對整數ei，di作為公鑰和私鑰，滿足gcd(ei，(p))=1且eidi=1 mod(p-1)將ei發給SC，SC計算SKi=SKeii0 mod p，并將SKi通過安全信道送給ui，ui用私鑰di解密得到SKi0=SKdi，SC公布PK={p，g，T，H，Yi，i∈[1，n]}。

2）密鑰的更新 在周期j的開始，每個簽名人ui根據前一周期j-1的密鑰SKij-1利用SKij=SK2ij-1 mod p-1計算此周期的密鑰SKij，將周期號由j-1更新為j，并刪除SKij-1。

3）前向安全的有序多重數字簽名 在周期j，設有n個簽名人按簽名順序u1，u2，…，un簽署同一份信息m，t為SC發送簽名的時間標志，要求ui在給定的時間Δti內完成簽名，SC廣播(m，t，Δti，i=1，2，…，n)，有序簽名操作如下:

a)u1收到信息m后，隨機選取k1j∈[1，p-1]，并計算r1j=gk1jmod p，s1j=H(m，t)SK2T+1-j1j-r1jk1j mod(p-1)，將簽名消息(m，(s1j，r1j))發給下一位簽名人u2并將r1j發給SC。b)每一位簽名人ui(i≥2)收到(m，(si-1j，ri-1j))后，先驗證簽名的有效性。首先計算ti=Δti+t，若(m，(si-1，j，ri-1j))在ti之后到達，則向SC發送一個超時信息，表示對m的簽名失敗；否則繼續驗證式(1)是否成立。

gSi-1jrri-1ji-1j=YH(m，t)i mod p(1)

若式(1)不成立，則認為ui-1的簽名無效，要求ui-1重發消息簽名；否則ui繼續執行協議，隨機選取kij∈[1，p-1]，并計算:rij=gkijmod p，sij=si-1j+H(m，t)SK2T+1-jij-rijkij mod (p-1)， 將簽名消息(m，(sij，rij)）發給下一位簽名人ui+1并將rij發給SC。當第n個簽名人un的簽名完成后，形成的有序多重數字簽名消息為(m，(snj，rnj))，并將rnj發給SC。

4）前向安全的有序多重數字簽名的驗證 簽名中心首先計算tn=Δtn+t，若un的消息（m，(snj，rnj))在tn之后到達，則認為簽名無效；否則驗證式(2)是否成立。

gsnjni=1rrijij=(ni=1Yi)H(m，t) mod p(2)

1.2 羅的前向安全的有序多重簽名方案安全性分析

1）驗證式（1）是錯誤的

證明 當i=2時，由s1j=H(m，t)SK2T+1-j1j-r1jk1j mod(p-1)顯然有gs1jrr1j1j=(gSK2T+1-j1j)H(m，t)=(gSK2T+110)H(m，t)=YH(m，t)1 mod p≠YH(m，t)2 mod p。故當i=2時，gsi-1jrri-1ji-1j≠YH(m，t)i mod p，即驗證式（1）是錯誤的。驗證式（1）應改為

gsi-1ji-1h=1rrhjhj=(i-1h=1Yh)H(m，t) mod p(1′)

下面用數學歸納法證明改動是正確的。

證明 對i(i≥2)使用數學歸納法。

a）當i=2時結論顯然成立；

b）假定當i=β(β≥3)時結論成立，即有

gsβ-1jβ-1h=1rrhjhj=(β-1h=1Yh)H(m，t) mod p

那么當i=β+1時，因為

sβj=sβ-1j+H(m，t)SK2T+1-jβj-rβjkβj mod(p-1)

所以，gsβjβh=1rrhjhj=gsβ-1j(gSK2T+1-jβj)H(m，t)g-rβjkβjβh=1rrhjhj=gsβ-1j(gSK2T+1-jβ0)H(m，t)r-rβjβjh=1rrhjhj=gsβ-1jYH(m，t)βr-rβjβj×

（rrβjβj

β-1h=1rrhjhj）=(gsβ-1jβh=1rrhjhj)YH(m，t)β=(β-1h=1Yh)YH(m，t)β=(β-1h=1Yh)H（m，t） mod p

綜合式(1)（2），所以驗證式（1）應改為

gsi-1ji-1h=1rrhjhj=(i-1h=1Yh)H(m，t) mod p 

2）存在偽造攻擊

羅的方案即使驗證式（1）改為驗證式（1′）：gsi-1ji-1h=1rrhjhj=(i-1h=1Yh)H(m，t) mod p，仍然存在偽造攻擊。若某簽名人ui(1≤i≤n)在第j周期的簽名密鑰SKij泄露后，則簽名人ui-1能夠偽造ui任意周期(1≤≤j≤T)的簽名，從而使該方案不具有前向安全性質。證明如下：

證明 令a=SK2T+1-jij，因為簽名人ui在第j周期的簽名密鑰SKij已泄露，故對簽名人ui-1來說a是可計算的。另一方面，SK2T+1-jij=SK2T+1i0，所以有結論a=SK2T+1i0。在周期，簽名人ui-1按正常簽名順序計算出自己的簽名(m，(si-1，，ri-1))，顯然ui之前的簽名能夠通過驗證式(1′)，即有gsi-1i-1h=1

rrhh=(i-1h=1Yh)H(m，t) mod p，ui-1盡管不知道簽名人ui在周期的簽名密鑰SKi，但ui-1仍可計算SK2T+1-i，因為SK2T+1-i=SK2T+1i0=a。ui-1偽造ui的簽名(m，(si，ri))過程如下：

ui-1隨機選取ki∈[1，p-1]，并計算:

ri=gkimod p（3）

si =si-1+aH(m，t)-riki mod (p-1)（4）

ui-1將簽名消息(m，(si，ri))發給下一位簽名人ui+1并將ri發給SC。因為：

gsiih=1

rrhh=gsi-1gaH(m，t)g-kiriih=1rrhh=

gsi-1(gSK2T+1-i)H(m，t)r-riiih=1rrhh=gsi-1(gSK2T+1i0)H(m，t)i-1h=1rrhh(gsi-1

i-1h=1rrhh)YH(m，t)i=(i-1h=1YhH(m，t)YH(m，t)i=(ih=1Yh)H(m，t) mod p

所以，gsiih=1rrhh=(ih=1Yh)H(m，t) mod p，即(m，(si，ri))能通過驗證式(1′)。因此，簽名人ui-1偽造ui的簽名(m，(si，ri))能夠通過簽名人ui+1的驗證。又簽名人ui+1到簽名人un按既定協議完成簽名，顯然簽名人un在周期的簽名(m，(si，ri))能夠通過驗證式（2），即式gsnni=1

riir=(ni=1Yi)H(m，t) mod p

的驗證。所以簽名人ui-1的偽造攻擊成功。

2 改進的前向安全的多重簽名方案

2.1 系統初始化

簽名中心(SC)首先選擇安全的大素數p1、p2、p′1、p′2、q，且滿足p1≡p2≡3 mod 4，選擇p=p1p2=(2qp′1+1)(2qp′2+1)和一個階為q的g∈QRp(即gq=1 mod p)，SC選擇安全的單向函數h和時間周期T；然后為每個簽名人ui選擇不同的SKi0∈(0，q)，計算Yi=SK-2T+1i0 mod p(1≤i≤n)作為驗證公鑰。SC隨機選擇參數K∈[1，p]，選擇一對整數e、d作為公鑰和私鑰，并滿足gcd(e，Φ(p))=1，ed=1 mod Φ(p)。其中Φ（p）=(p1-1)(p2-1)為歐拉函數。公開參數p、q、g、h、T、Yi(1≤i≤n)、e、K，保密SKi0(1≤i≤n)，d。

2.2 密鑰更新

在周期j的開始，每個簽名人ui根據前一周期j-1的密鑰SKij-1利用SKij=SK2ij-1 mod p計算此周期的密鑰SKij，將周期號由j-1更新為j，并刪除SKij-1。

2.3 前向安全的有序多重數字簽名

在周期j，設有n個簽名人按簽名順序u1，u2，…，un簽署同一份信息m，t為SC發送簽名的時間標志，要求ui在給定的時間Δti內完成簽名，SC廣播(m，t，Δti，i=1，2，…，n)，有序簽名操作如下:

a）u1收到m后，隨機選取k1j，w1j∈(0，q]，并計算R1j=gk1j2T+1-jmod p，Z1j=SK1jgw1jmod p，u=h(m‖j‖t‖K)，S1j=k1j-w1ju mod q，將簽名信息(R1j，Z1j，S1j)傳給簽名人u2。

b）每一位簽名人ui(i≥2)收到(Ri-1j，Zi-1j，Si-1j)后，先驗證簽名的有效性。首先計算ti=Δti+t，若(Ri-1j，Zi-1j，Si-1j)在ti之后到達，則向SC發送一個超時信息，表示對m的簽名失敗；否則計算u=h(m‖j‖t‖K)，并驗證式(5)是否成立。

Ri-1j=gSi-1j2T+1-j(Z2T+1-ji-1ji-1h=1Yh)u mod p(5)

若式(5)不成立，則認為ui-1的簽名無效，要求ui-1重發消息簽名，否則ui繼續執行協議，隨機選取kij，wij∈(0，q)，計算

Rij=Ri-1jgkij2T+1-jmod p（6）

Zij=Zi-1jSKijgwij mod p（7）

Sij=Si-1j+kij-wiju mod q（8）

將簽名信息（Rij，Zij，Sij）傳給簽名人ui+1。當第n個簽名人un的簽名完成后，形成的有序多重數字簽名消息為(Rnj，Znj，Snj)，并將(Rnj，Znj，Snj)發給SC。SC首先計算tn=Δtn+t，若(Rnj，Znj，Snj)在tn之后到達，則向un發送一個超時信息，表示對m的簽名失敗，請求un重發消息(Rnj，Znj，Snj)；否則計算u=h(m‖j‖t‖K)，并驗證式(9)是否成立。

Rnj=gSnj2T+1-j(Z2T+1-jnjnh=1Yh)u mod p(9)

若式（9）成立，令Z=Zdnj，S=Snjd，U=h(m‖j‖t‖Z‖Rnj‖K)，則前向安全的有序多重簽名為[j，(m，S，Z，U，t)]；否則SC要求un重發簽名消息(Rnj，Znj，Snj)。

2.4 前向安全的有序多重數字簽名的驗證

簽名驗證人收到[j，(m，S，Z，U，t)]后，計算

u=h(m‖j‖t‖K)，Y=nh=1Yh mod p

R=geS2T+1-j(Ze2T+1-jY)u mod p(10)



驗證式(11)是否成立。

U=h(j‖m‖t‖R‖Z‖K)(11)

如式（11）成立，則多重簽名有效；否則多重簽名無效。

3 改進方案的正確性證明

定理1 若式(5)成立，則ui-1(i≥2)的簽名(Ri-1j，Zi-1j，Si-1j)是有效的。

證明 對i(i≥2)使用數學歸納法。

a）當i=2時結論顯然成立。

b）假定當i=β(β∈N，β≥3)結論成立，即有

Rβ-1j=gSβ-1j2T+1-j(Z2T+1-jβ-1jβ-1h=1Yh)u mod p

那么，當i=β+1時，根據式（6）~（8）有

Rβj=Rβ-1jgkβj2T+1-j=

gSβ-1j2T+1-j(Z2T+1-jβ-1jβ-1h=1Yh)u gkβj2T+1-j=

g(Sβ-1j+kβj)2T+1-j((

Zβ-1jSKβj)2T+1-j

SK-2T+1-jβjβ-1h=1Yh)u=

g(Sβ-1j+kβj)2T+1-j((

Zβ-1jSKβj)2T+1-j

所以，當i=β+1時，結論也成立。

綜上所述，若式(5)成立，則ui-1(i≥2)的簽名(Ri-1j，Zi-1j，Si-1j)是有效的。如果un的簽名(Rnj，Znj，Snj)是有效的，由定理1的結論則式（9）顯然成立。

定理2 [j，(m，S，Z，U，t)]是有效的前向安全的多重數字簽名。

證明 由已知，則需要證明式（11）成立。

由式（9）（10）有

R=geS2T+1-j(Ze2T+1-jY)u mod p=gedSnj2T+1-j(Zed2T+1-jnjnh=1Yh)u mod p=gSnj2T+1-j(Z2T+1-jnjnh=1Yh)u mod p=Rnj

所以，U=h(j‖m‖t‖Rnj‖Z‖K)=h(j‖m‖t‖R‖Z‖K)。[j，(m，S，Z，U，t)]是有效的前向安全的多重數字簽名。

4 改進方案的安全性分析

1）改進方案具有前向安全的特性 本方案的前向安全性是基于強RSA假定^[9]和模合數平方剩余難題。當p為合數時，企圖通過SKij=SK2i-1j mod p求SKi-1j是一個困難問題。因此，即使攻擊者已獲得簽名人ui當前周期j的簽名密鑰SKij，他也無法求出ui當前周期j之前的簽名密鑰SKik(k＜j)，新方案具有前向安全的特性。

2）改進方案能夠抵抗偽造攻擊 假定知道(j，m，Rnj，Z，t，Yi(i=1，2，…，n))，攻擊者企圖通過驗證式（見式（9）（10））Rnj=R=geS2T+1-j(Ze2T+1-jY）u mod p求S，這相當于求解離散對數問題。若假定他已知(j，m，S，Rnj，t，Yi(i=1，2，…，n))，通過上式求Z，他必須至少求出e-1(mod φ(p))。其中：φ(p)為歐拉函數，在大合數p分解未知的情況下，求解e-1(mod φ(p))是一個十分困難的問題。如果攻擊者企圖偽造部分多重簽名，使得全體多重簽名通過驗證式，那么本方案要對部分簽名驗證，所以偽造的部分簽名無法通過式（5）和（9）的驗證。如果攻擊者在已知部分參數的情況下通過式（5）和（9）求解某些參數，以達到偽造部分簽名的目的，這也是不可能的。因此，本方案能抵制偽造攻擊。

3）改進方案能夠抵抗內部攻擊 如果攻擊者是不誠實的內部簽名人ui-1，他向ui或SC提供偽造的簽名，ui或SC可以通過驗證式（5）或（9）發現ui-1欺詐行為，并要求ui-1的簽名，因此，本方案能抵抗內部攻擊。如果ui-1通過偽造簽名有意延誤時間，則SC能夠根據ui提供的失敗信息進行分析并及時處理。

4）改進方案能夠抵抗聯合攻擊

如果攻擊者是不誠實的部分內部簽名人集合，企圖聯合偽造簽名實施攻擊，則無法通過驗證式（5）或（9）。因此，本方案能抵抗聯合攻擊。

5）改進方案能夠抵抗重播攻擊

在本方案中引入了時間標志，每次都要對時間進行驗證，所以能夠抵抗重播攻擊。

5 改進方案的性能分析

與王曉明等人所提出的文獻[6]相比，本方案也引入了預計算，在每個周期開始時，簽名人可以預先計算g2T+1-j；在每次簽名前，可以預先計算gkij2T+1-jmod p和SKijgwij mod p。文獻[7]經過兩輪循環才完成有序多重簽名，第一輪計算每個簽名人的Rij和Zij（包括最后一個簽名人的Rlj和Zlj）；第二輪將Rlj和Zlj廣播給每個簽名人以便每個簽名人能計算u=h(j‖m‖Rlj‖Zlj‖t)，進而計算出Sij。本文在保證安全性質不變的前提下改進了文獻[6]的簽名過程，只用一輪循環完成簽名，大大提高了簽名的效率，且簽名的驗證過程比文獻[6]簡單方便。改進方案也比羅的方案簡潔、高效，可進行類似分析。此處不再贅述。

6 結束語

在多重簽名過程中，如何減少由于簽名者簽名密鑰泄露所造成的損失是一個亟待解決的問題，但是目前所提出的方案大多數不具有真的前向安全性質。本文給出的新方案在強RSA假定、模合數平方剩余等難解問題假設下是安全有效的。對羅的前向安全的廣播多重簽名方案可采用類似的方法進行分析與改進。

參考文獻：

［1］ITAKURA K，NAKAMURA K.A public-key cryptosystem suitable for digital multisignature[J].NEC Research and Development，1983，71(10):1-8.

［2］OHTA K，OKAMOTO T.A digital multi-signature scheme based on the Fiat-Shamir scheme[C]//Proc of Advances in Cryptology ASIACRYPT’91.Berlin:Springer-Verlag，1991:139-148.

［3］HARDJONO T，ZHENG Y.A practical digital multi-signature scheme based on discrete logarithms[C]//Proc of Advanced in Cryptology-Auscrypt’92.Berlin:Springer-Verlag，1992:16-21.

［4］YI L J，BAI G Q，XIAO G Z.Proxy multi-signature scheme:a new type of proxy signature scheme[J].Electronics Letters，2000，36(6):527-528.

［5］ANDERSON R.Two remarks on public key cryptology[C]//Proc of the 4th ACM Conference on Computer and Communications Security.Zurich:[s.n.]，1997:1-7.

［6］王曉明，符方偉，張震.前向安全的多重數字簽名方案[J].計算機學報，2004，27(9):1177-1181.

［7］KOZLOV A，REYZIN L.Forward-secure signature with fast key update[C]//Proc of Security in Communication Network.Berlin:Springer，2002:241-256.

［8］CANETTI R，HALEVI S，KATZ J.A forward-secure signature public-key encryption scheme G[C]//Proc of Advances in Cryptology-Eurocrypt’03.Berlin:Springer-Verlag，2003:255-271.

［9］王曉明，陳火炎，符方偉.前向安全的代理簽名方案[J].通信學報，2005，26(11):38-42.

［10］羅麗平，農亮勤.具有前向安全的ElGamal型多重數字簽名方案[J].信息安全與通信保密，2007，10:95-97.