王春玲，武淑敏

(西安工程大學計算機科學學院，陜西西安710048)

密鑰可更新的ElGamal有序多重數字簽名方案

王春玲，武淑敏

(西安工程大學計算機科學學院，陜西西安710048)

分析了Li和Yang提出的基于ElGamal的有序多重數字簽名方案，發(fā)現該方案無法抵抗內部成員的偽造攻擊.因此提出了一個密鑰可更新的ElGamal有序多重數字簽名方案.通過使用可信秘密分發(fā)中心SDC為各個簽名者分發(fā)密鑰的方法，解決原方案中無法抵抗內部成員攻擊的漏洞.同時方案還添加了密鑰更新算法，不僅提高了安全性，而且實用性更廣.

ElGamal數字簽名;有序多重數字簽名;內部攻擊;密鑰更新

0 引言

多重數字簽名技術用于同一文檔需經過多人簽名才能生效的情形，在日常生活工作中具有廣泛的應用.多重數字簽名主要分為有序多重數字簽名(Sequential Multi-Digital Signature)和廣播多重數字簽名(Broadcasting Multi-Digital Signature).有序多重數字簽名是按照一定順序將電子文件依次發(fā)送給簽名者進行簽名，最后由驗證者驗證簽名的正確性.

自從1983年Itakura和Nakamura提出了第一個多重數字簽名方案［1］以后，各種多重數字簽名算法相繼提出，同時基于ElGamal型的數字簽名方案的研究和應用也越來越廣泛.Harn和Xu提出了一種ElGamal型數字簽名，并根據這種簽名方案設計了一種多重數字簽名方案［2］，但該方案不能用于有序多重數字簽名;1999年李子辰、楊義先設計出一種基于ElGamal型有序和廣播多重數字簽名［3］，后續(xù)的學者們對于ElGamal方案的優(yōu)化改進也是層出不窮［4-7］.本文在分析研究了Li和Yang的ElGamal有序多重數字簽名方案的基礎上，根據秘密分發(fā)機制，提出了一個密鑰可更新的有序多重數字簽名算法.該方案不僅提高了安全性，而且具有更廣泛的實用性.

1 Li方案的描述

該方案是根據ElGamal簽名方案設計的一個有序多重簽名方案，包括系統初始化階段，簽名產生階段，簽名驗證階段等3個階段.

1.1 系統初始化

US為消息發(fā)送者，UV為簽名驗證者，U1，U2，…，Un為消息簽名者，選取一個大的素數p，G是GF(p)的本原元，H(.)是一個單向的哈希函數.每個簽名者Ui隨機選取自己的私鑰xi，計算yi=gxi(modp)作為自己的公鑰，然后公開p，g，h.

1.2 簽名產生階段

UI確定簽名順序后將要簽名的消息發(fā)送給第一個簽名者U1，U1收到m后，隨機選取k1∈［1，p-1］，計算r1=gk1modp，S1=H(m)x1-r1k1modφ(p);將(m，(r1，s1))發(fā)送給下一個簽名者，將ri發(fā)送給后續(xù)的每一個簽名者.簽名者Ui(i≥2)收到(m，(ri-1，si-1))，對其進行驗證，驗證通過后進行如下操作：

隨機選取ki∈［1，p-1］，計算ri=gkimodp，Si=Si-1+H(m)xi-rikimodφ(p);然后將(m，(ri，si))發(fā)送給下一個簽名者，將ri發(fā)送給后續(xù)的gk1每一個簽名者.

1.3 簽名驗證階段

2 原方案漏洞分析

該方案具有內部成員偽造攻擊的漏洞，因為在簽名驗證階段，系統沒有驗證每個簽名者的公鑰，則存在以下可能：不誠實簽名者可以隨意公布一個假的公鑰yi′，然后偽造一個假的簽名從而達到破壞多重簽名的目的.假設不誠實簽名者U′企圖偽造合法簽名者Ui-1對消息m的簽名(m，(ri-1，si-1))，他按如下步驟即可完成偽造簽名：

3 新的ElGamal多重數字簽名方案

基于以上分析，提出改進方案，在系統初始化階段，通過采用可信秘密分發(fā)中心SDC給每個簽名者分發(fā)密鑰的方法，去掉了原方案中簽名者可以隨機選取自己私鑰的過程，從而能夠克服內部成員偽造攻擊的漏洞，提高了安全性.同時方案還添加了密鑰更新算法和時間戳機制，具有更廣的實用價值.

3.1 系統初始化

本方案涉及可信秘密分發(fā)中心，消息發(fā)送者，消息簽名者和簽名驗證者三方，設US為消息發(fā)送者，UV為簽名驗證者，U1，U2，…，Un為消息簽名者，SDC為可信秘密分發(fā)中心，初始化過程如下：設p是一個素數，p=mq+1，其中q也是素數，m是整數，g是Zp中階為q的元素.

步驟一：SDC選擇Zq上的k-1次多項式f(x)=a0+a1x+…ak-1xk-1，公開ga0，ga1，…，gak-1，秘密地將xi=f(i)(modq)傳送給每個簽名者Ui，Ui根據式(1)來驗證所收到的密鑰xi是否正確：

如果正確，則將xi作為自己的私鑰，然后計算yi=gxi(modp)作為公鑰.

3.2 簽名過程

消息發(fā)送者US預先設計簽名順序為(U1，U2，…，Un)，并且確定要發(fā)送的消息m，計算H(m，T)，然后將這種簽名順序和時間標志T發(fā)送到每一個簽名者Ui和驗證者UV;要求Ui在給定時間t內完成簽名.

步驟一：U1收到需要簽名的消息后，隨機選取k1∈［1，p-1］，按式(2)計算

然后將簽名消息(m，(r1，S1))發(fā)送給下一個簽名者U2，將k1發(fā)送給后續(xù)的簽名者和驗證者.

步驟二：U2收到U1的簽名消息后，首先計算T′=T+Δt，如果U1的簽名消息在T′之前到達，則按式(3)驗證簽名的正確性，否則拒絕接受簽名.

如果式(3)成立，則U1的簽名正確，U2按步驟三繼續(xù)簽名;否則拒絕對消息簽名，簽名失敗.

步驟三：U2隨機選取k2∈［1，p-1］，按式(4)計算

然后將簽名消息(m，(r2，S2))發(fā)送給下一個簽名者U3，將r2發(fā)送給后續(xù)的簽名者和驗證者，以此類推.

步驟四：簽名者Ui(2＜i＜n)傳遞消息m的部分簽名(ri，Si)給Ui+1后，Ui+1首先計算

T′=T+Δt*i，如果簽名消息在T′之前到達，則按式(5)驗證部分簽名的正確性

如果等式成立，則簽名正確，Ui+1繼續(xù)對m進行簽名，簽名如下：ri+1=gki+1modp.

3.3 驗證過程

驗證者UV收到最后一個簽名者發(fā)來的簽名(rn，Sn)后，同樣計算T′=T+nΔt.若簽名結果在T′之前到達，則按式(7)驗證，

如果等式成立，則說明簽名正確，否則簽名失敗.

3.4 密鑰更新過程

如果某個簽名者Ui的密鑰xi被盜或者丟失，則向可信秘密分發(fā)中心SDC請求密鑰的重發(fā)，SDC按照如下過程對所有簽名者的密鑰進行更新.

(1)SDC隨機選擇Zq中的k-1個隨機數δ1，δ2，…，δk-1，定義多項式：δ(x)=δ1x+δ2x2+…δk-1xk-1，并計算εi=gδi(modp)，i=1，2，…，k-1;Δxi=δ(i)，將xi發(fā)給對應的每個簽名者Ui;

(2)Ui收到xi后，根據式(3)驗證xi是否正確：

若xi滿足上式，則接收到的xi正確.

(3)Ui按下式更新自己的密鑰.并銷毀xi.

4 新方案的分析

4.1 外部攻擊

該方案是基于離散對數問題的，即每一位簽名者都有自己的私鑰xi和公鑰yi=gxi，外部攻擊者要想偽造簽名者Ui對消息m的簽名，就必須知道簽名者Ui的私鑰xi和簽名者選擇的隨機數ki，而從公鑰yi求解簽名者的私鑰xi相當于求解離散對數難題;而且在簽名過程中，ri=gkimodp，攻擊者欲從公開的ri求出隨機數ki也相當于求解離散對數問題.

外部攻擊者要想偽造最終的簽名(rn，Sn)，并通過Uc的驗證，就必須知道每個簽名者的私鑰xi，而每個簽名者的私鑰xi是可信秘密分發(fā)中心SDC惟一分配的，外部攻擊者欲從公開的ga0，ga1，…，gak-1獲取a0，a1，…，ak-1等同于求解離散對數難題，所以攻擊不成功.

4.2 內部攻擊

該方案在原方案的基礎上加入了密鑰分發(fā)機制，使得每個簽名者的私鑰不再由簽名者隨機選取，而是由可信秘密分發(fā)中心SDC分配，而且每個簽名者可以根據式(1)驗證SDC分發(fā)給自己的私鑰，從而避免了Li方案的內部成員之間攻擊，提高了方案的安全性.

假設某個不誠實的簽名者Ui想偽造簽名者Ut對消息m的簽名，他可以隨機選擇kt，計算rt=gkt，但是他不能獲得簽名者Ut的私鑰xt.假設他自己隨機選擇xt，然后計算偽造簽名st，由式(4)可知，st是不能通過st+1的驗證的，因為隨機選擇的私鑰xt不能滿足已知的簽名者Ut的公鑰，使得yt=gxt.同理，部分簽名者(ui，ui+1，…，ut)合謀偽造前i-1個簽名者的簽名，通過最終的驗證者的驗證也是行不通的.

4.3 性能分析

該方案雖然抵抗了內部成員之間的攻擊，提高了算法的安全性，但是和原方案比較起來，也有不足之處.首先，新方案增加了系統開銷，因為在系統初始化時，原方案是每個簽名者隨機選取自己的私鑰，而新方案SDC則需要計算每個簽名者的私鑰xi，并且要通過安全信道傳送給每個簽名者，所以增加了方案的通信量.

5 結束語

多重數字簽名在電子合同、文件簽署、遺囑簽署、電子商務和網絡安全等方面有著廣泛的應用前景.本文在學習了ElGamal有序多重數字簽名的基礎上提出了一種密鑰可更新的ElGamal有序多重數字簽名方案，不僅解決了原方案的內部成員偽造攻擊的漏洞，而且在簽名成員密鑰丟失的情況下可以重新進行密鑰分配，大大提高了簽名的安全性和實用性，同時方案還引入了hash函數和時間戳機制，有效地提高了簽名效率.

［1］ITAKURA K，NAKAMURA K.A public-key cryptosystem suitable for digital multisigature［J］.NEC Research＆Development，1983，71：1-8.

［2］L Harn.New digital signature scheme based on discrete logarithm［J］.Electronics Letters，1994，30(5)：396-398.

［3］李子辰，楊義先.ElGamal多重數字簽名方案［J］.北京郵電大學學報，1999，22(2)：30-34.

［4］盧建朱，陳火炎，林飛.ELGamal型多重數字簽名算法及其安全性［J］.計算機研究與發(fā)展，1999，37(11)：1335-1339.

［5］鞠宏偉，李鳳銀.基于ElGamal的多重數字簽名方案［J］.山東科學，2005，18(3A)：69-72.

［6］柳毅，郝彥君.基于ElGamal密碼體制的可驗證秘密共享方案［J］.計算機科學，2010，37(3)：80-82.

［7］李佳佳，謝冬，沈忠華.基于變形的ElGamal的(t，n)門限秘密共享方案［J］.杭州師范大學學報，2013(2)：135-139.

［8］許春香，魏仕民，肖國鎮(zhèn).定期更新防欺詐的秘密共享方案［J］.計算機學報，2002，25：657-660.

(School of Computer Science，Xi'an Polytechnic University，Xi'an 710048，China)

A key renewable ElGamal sequential multi-digital signature scheme

WANG Chun-ling，WU Shu-min

Li and Yang's sequential multi-digital signature scheme is analyzed based on ElGamal，which couldn' t resist the masquerading attack of internal members.So a key renewable ElGamal sequential multi-digital signature scheme is presented，which can solve the problem in the original scheme by using the method of trusted SDC (Secret Distribution Center)distribute keys for each signer.Morever，a key update algorithm is added to the secheme，so it is highly secure and practical.

ElGamal digital signature;sequential multi-digital signature;internal attack;key-update

TP 393

A

1674-649X(2014)01-0102-04

編輯、校對：武暉

2013-06-08

王春玲(1968-)，女，陜西省西安市人，西安工程大學副教授，主要從事網絡信息安全等方面的研究.E-mail： wangcl1968@yahoo.com.cn