王春玲，武淑敏

(西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安710048)

密鑰可更新的ElGamal有序多重?cái)?shù)字簽名方案

王春玲，武淑敏

(西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安710048)

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

ElGamal數(shù)字簽名;有序多重?cái)?shù)字簽名;內(nèi)部攻擊;密鑰更新

0 引言

多重?cái)?shù)字簽名技術(shù)用于同一文檔需經(jīng)過(guò)多人簽名才能生效的情形，在日常生活工作中具有廣泛的應(yīng)用.多重?cái)?shù)字簽名主要分為有序多重?cái)?shù)字簽名(Sequential Multi-Digital Signature)和廣播多重?cái)?shù)字簽名(Broadcasting Multi-Digital Signature).有序多重?cái)?shù)字簽名是按照一定順序?qū)㈦娮游募来伟l(fā)送給簽名者進(jìn)行簽名，最后由驗(yàn)證者驗(yàn)證簽名的正確性.

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

1 Li方案的描述

該方案是根據(jù)ElGamal簽名方案設(shè)計(jì)的一個(gè)有序多重簽名方案，包括系統(tǒng)初始化階段，簽名產(chǎn)生階段，簽名驗(yàn)證階段等3個(gè)階段.

1.1 系統(tǒng)初始化

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

1.2 簽名產(chǎn)生階段

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

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

1.3 簽名驗(yàn)證階段

2 原方案漏洞分析

該方案具有內(nèi)部成員偽造攻擊的漏洞，因?yàn)樵诤灻?yàn)證階段，系統(tǒng)沒(méi)有驗(yàn)證每個(gè)簽名者的公鑰，則存在以下可能：不誠(chéng)實(shí)簽名者可以隨意公布一個(gè)假的公鑰yi′，然后偽造一個(gè)假的簽名從而達(dá)到破壞多重簽名的目的.假設(shè)不誠(chéng)實(shí)簽名者U′企圖偽造合法簽名者Ui-1對(duì)消息m的簽名(m，(ri-1，si-1))，他按如下步驟即可完成偽造簽名：

3 新的ElGamal多重?cái)?shù)字簽名方案

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

3.1 系統(tǒng)初始化

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

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

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

3.2 簽名過(guò)程

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

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

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

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

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

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

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

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

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

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

3.3 驗(yàn)證過(guò)程

驗(yàn)證者UV收到最后一個(gè)簽名者發(fā)來(lái)的簽名(rn，Sn)后，同樣計(jì)算T′=T+nΔt.若簽名結(jié)果在T′之前到達(dá)，則按式(7)驗(yàn)證，

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

3.4 密鑰更新過(guò)程

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

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

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

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

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

4 新方案的分析

4.1 外部攻擊

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

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

4.2 內(nèi)部攻擊

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

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

4.3 性能分析

該方案雖然抵抗了內(nèi)部成員之間的攻擊，提高了算法的安全性，但是和原方案比較起來(lái)，也有不足之處.首先，新方案增加了系統(tǒng)開(kāi)銷，因?yàn)樵谙到y(tǒng)初始化時(shí)，原方案是每個(gè)簽名者隨機(jī)選取自己的私鑰，而新方案SDC則需要計(jì)算每個(gè)簽名者的私鑰xi，并且要通過(guò)安全信道傳送給每個(gè)簽名者，所以增加了方案的通信量.

5 結(jié)束語(yǔ)

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

［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多重?cái)?shù)字簽名方案［J］.北京郵電大學(xué)學(xué)報(bào)，1999，22(2)：30-34.

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

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

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

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

［8］許春香，魏仕民，肖國(guó)鎮(zhèn).定期更新防欺詐的秘密共享方案［J］.計(jì)算機(jī)學(xué)報(bào)，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

編輯、校對(duì)：武暉

2013-06-08

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