一種復(fù)合問題的多重數(shù)字簽名方案

曹 陽

（陜西理工學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，陜西 漢中723000）

數(shù)字簽名是實現(xiàn)網(wǎng)絡(luò)身份認(rèn)證、不可否認(rèn)性、數(shù)據(jù)完整性等信息服務(wù)的基礎(chǔ)，也是實現(xiàn)電子商務(wù)、電子金融等的重要技術(shù)保證。所謂數(shù)字簽名就是接收方能夠向第三方證明其收到的消息的真?zhèn)涡远扇〉囊环N加密措施。多重數(shù)字簽名［1］就是多個簽名者對同一份文件進(jìn)行簽名。Harn在1994年首次提出了一種基于離散對數(shù)難題的多重數(shù)字簽名方案［2］，但該方案不能用于多重數(shù)字簽名。隨后大量的學(xué)者提出了基于公鑰密碼［3］系統(tǒng)的多重數(shù)字簽名方案，如：Lyu Wanli、盧鵬菲、胡越梅等提出了基于橢圓曲線多重數(shù)字簽名方案［4－7］；焦陽等提出基于ELGamal型的有序多重數(shù)字簽名方案［8］；羅麗平等提出了基于RSA的多重數(shù)字簽名方案［9］。無論多重數(shù)字簽名方案基于ECC、RSA，還是離散對數(shù)問題，最終的目的都是為了提高簽名的安全性及效率［10－12］。鑒于此問題，本文通過參數(shù)替換避免求逆運(yùn)算對橢圓曲線數(shù)字簽名算法（ECDSA）進(jìn)行改進(jìn)，結(jié)合橢圓曲線密鑰短、存儲開銷小等特點(diǎn)，提出一種復(fù)合問題的多重數(shù)字簽名方案。

1 ECDSA快速簽名方案

ECDSA的簽名方程一般為xk＝y(tǒng)＋dz（modq），對系數(shù)（x，y，z）進(jìn)行轉(zhuǎn)換可以得到不同的簽名算法，由簽名方程求出v，形成簽名信息（u，v）。G是橢圓曲線的基點(diǎn)，l是私鑰，L是公鑰，用（1，Mu＋v，1）置換（x，y，z）則得到的簽名方程和驗證方程如下

使用轉(zhuǎn)換后的簽名方程得到的方案如下：

（1）簽名者Q在橢圓曲線上選擇私鑰l，G為基點(diǎn)，L＝lG，M＝hash（m），并將M轉(zhuǎn)換為整數(shù)。

（2）Q隨機(jī)選取整數(shù)k∈［1，q－1］，并計算U＝kG＝（x1，y1），并將x1轉(zhuǎn)換為整數(shù)，u＝x1（modq），如果u＝0則轉(zhuǎn)第（2）步。

（3）計算v＝k－Mu－lmodq，如果v＝0則轉(zhuǎn)第（2）步，（u，v）作為對消息m的簽名，將（u，v，m）傳送給驗證者。

（4）驗證者獲取公鑰L，驗證u和v是［1，q－1］間的整數(shù)，計算M＝hash（m），R＝v＋Mu（modq），如果R＝0，則簽名無效，否則計算U＝（R＋l）G＝RG＋L＝kG＝（x2，y2），u＇＝x2（modq），如果u′＝u則簽名驗證成功。

簽名過程中避免了求逆運(yùn)算，所以簽名的效率比較高。

2 復(fù)合問題的多重數(shù)字簽名方案

2.1 系統(tǒng)初始化

設(shè)有n個簽名者 ｛Q1，Q2，…，Qn｝對同一個消息m進(jìn)行簽名，可信秘鑰生成中心KGC生成系統(tǒng)參數(shù)（Fp，E，G，q，a，b，hash（），N），其中Fp為有限域，E是Fp上的橢圓曲線，G是E上的基點(diǎn)，q是E的階，a和b是曲線E的系數(shù)，hash（）為單向哈唏函數(shù)，N是簽名重發(fā)的次數(shù)。

2.2 秘鑰生成和分配

為了防止組內(nèi)成員內(nèi)部的欺詐行為，簽名者的私鑰由簽名者自己生成，用戶的身份以密文的形式傳送給KGC，并利用離散對數(shù)難解性證明來驗證用戶身份的安全性。KGC為每一個簽名者生成一個秘密數(shù)，將該秘密數(shù)與用戶的身份簡單復(fù)合后傳送給每一個簽名者，簽名者收到后利用自己的私鑰和身份解出秘密數(shù)。

（1）KGC隨機(jī)選擇一個整數(shù)s作為自己的私鑰，計算S＝sG，并公布S和G。

（2）簽名者Qi（i＝1，2，…，n）計算Di＝Sdi，di為簽名者的身份，將Di發(fā)送給KGC，KGC利用私鑰解密用戶身份，并為用戶建立檔案，將其定為合法的簽名者，簽名者Qi隨機(jī)選擇一個整數(shù)li作為自己的私鑰，Li＝liG為公鑰，公開Li。

（3）KGC為每個簽名者Qi選擇隨機(jī)數(shù)ki，保密，計算計算u＝KG＝（x0，y0），并將x0和y0轉(zhuǎn)換為整數(shù)，M＝hash（m＋x0＋y0），w＝c0G，用Qi的公鑰加密w得w′，根據(jù)簽名者的身份將w′和ri發(fā)送給簽名者Qi，公開u和M。

（4）簽名者Qi利用自己的私鑰li解密w，利用身份di求出ki，ci＝w＋Li。

2.3 簽名生成

簽名中心對簽名者設(shè)計一種簽名順序（Q1，Q2，Q3，…，Qn，Q），最終簽名由Qn提交給驗證者Q，順序發(fā)送給每一位簽名者，簽名中心確定發(fā)送的消息m，計算M＝hash（m＋x0＋y0，T），公開M，然后用Q1的公鑰L1加密m得m′發(fā)送給Q1，并把時間標(biāo)志T發(fā)送給每一個簽名者和驗證者，要求簽名者Qi在給定的時間ΔTi內(nèi)簽名，以防止簽名重播。

（1）簽名者Q1首先利用自己的私鑰l1解密消息m′得m，計算T1＝T＋ΔT1，若消息m在T1時刻之前到達(dá)，M＝hash（m＋x0＋y0，T）。若等式不成立，則Q1請求簽名中心重發(fā)消息，若消息m在T1時刻還沒有到達(dá)或重發(fā)的次數(shù)＞N，向簽名中心發(fā)送一個簽名失敗消息；若等式成立，則進(jìn)行以下操作

公開u1和v1，利用Q2的公鑰L2加密m得m′，將簽名的消息（m′，c1，u1′，v1′）發(fā)送給下一個簽名者Q2。

（2）簽名者Qi（i≥2）接收到簽名者Qi－1發(fā)來的（m′，ci－1，ui－1′，vi－1′），利用自己的私鑰li解密消息m′得m。計算Ti＝T＋ΔTi，若Qi－1的簽名在Ti時刻之前還末到達(dá)，Qi要求Qi－1重新發(fā)送消息且發(fā)送次數(shù)≤N；若Qi－1消息在Ti之前還是沒有到達(dá)，或消息重發(fā)次數(shù)＞N，則Qi向簽名中心發(fā)送簽名失敗消息。

（3）驗證ci＝w＋Li－1，M＝hash（m＋x0＋y0，T）是否成立，若不成立拒絕簽名，并要求Qi－1重新發(fā)送消息；若成立則執(zhí)行第（4）步。

（4）計算ui＝kiG＝（xi，yi），vi＝ki－Mui－li（modq），ui′＝ui－1＋ui，vi′＝vi－1＋vi，ci＝w＋Li，顯然由第（1）步可得出：ui′＝u1＋u2＋…＋ui，vi′＝v1＋v2＋ … ＋vi，公開（ui，vi）。

（5）若1≤i＜n，則Qi利用Qi＋1的公鑰加密m得m′，將（m′，ci，ui′，vi′）發(fā) 送 給Qi＋1，執(zhí) 行 第（2）、第（3）步；若i＝n，執(zhí)行第（6）步。

（6）Qn將（M，cn，un′，vn′）發(fā)送給簽名驗證者Q完成簽名驗證。

2.4 簽名驗證

驗證者Q收到最終簽名執(zhí)行以下操作：

（1）判斷un和vn是［1，q－1］的素數(shù)，計算Ri＝vi＋Mui（modq）。

（2）查詢簽名者Qi（i＝1，2，…，n）公鑰Li和部分 簽 名（ui，vi），驗 證li）G（modq）。

2.5 簽名驗證過程的正確性證明

證明：

所以，上述簽名驗證過程是正確的。

3 安全性分析

（1）方案的安全性基于離散對數(shù)求解的困難性及簽名者的身份。方案中合法簽名者秘鑰的生成是由自己生成，簽名者向KGC提供的身份di是由KGC的公鑰進(jìn)行加密Di＝Sdi。由Di＝Sdi，S＝sG知，攻擊者無法知道KGC的私鑰s，也就無法知道簽名者的身份di，難解性基于橢圓曲線離散對數(shù)問題。若攻擊者要想從簽名者Qi的公鑰Li解出私鑰li，且想從公開的u解出K和ki，由知，要求出ki就必須知道用戶的身份di，難解性仍然是基于橢圓曲線離散對數(shù)問題。

（2）本方案中消息m的傳遞及w的傳遞都是以密文的形式傳遞，秘密數(shù)ki與簽名者Qi的身份di進(jìn)行簡單復(fù)合，保證了消息和ki的機(jī)密性。簽名過程中，攻擊者無法從vi＝ki－Muili（modq）中求出vi，因為簽名方程中有ki和li兩個未知數(shù)，無法求解，從而保證了簽名的機(jī)密性。

（3）引入時間戳防止重放攻擊。M＝hash（m＋x0＋y0，T），T為簽名時間，即使攻擊者獲取了（M，T，ci，ui′，vi′），并將T改為當(dāng)前時間，但vi－1中的M無法修改，因此不會成功。

（4）方案中設(shè)定常數(shù)N作為簽名不正確時重發(fā)簽名的次數(shù)，簽名生成的第（3）步不成立，在時間ΔTi內(nèi)，Qi要求Qi－1重新發(fā)送簽名消息且發(fā)送次數(shù)≤N。從而限制攻擊者嘗試的次數(shù)，增強(qiáng)了系統(tǒng)的安全性。

（5）方案簡化了簽名驗證的過程，Qi并沒有將（m′，ci，ui′，vi′）廣播給其后的所有簽名者，只是將簽名發(fā)送給其后的一個簽名者，所以Qi只需驗證Qi－1的簽名并簽名，提高了簽名效率，降低了通信成本。簽名時只有n個簽名者的簽名才是有效的，驗證者驗證簽名時使用了簽名者部分簽名和公鑰，有效防止中間人的攻擊及惡意攻擊。

4 結(jié)論

本文對橢圓曲線簽名方案進(jìn)行改進(jìn)，避免了求逆運(yùn)算，在此基礎(chǔ)上結(jié)合橢圓曲線密碼體制密鑰短、安全性高等優(yōu)點(diǎn)，提出了一種復(fù)合問題的多重數(shù)字簽名方案，并分析了該方案的安全性。實現(xiàn)中，如果橢圓曲線上點(diǎn)的運(yùn)算采用多標(biāo)量乘運(yùn)算，效率可以提高10%～20%。因而本方案在實際生活中具有一定的實用價值。

［1］Wu Z C，Chou S L.Two-base multi-signature protocols for sequential and broadcasting architectures［J］.Computer Communications，1996，19（9/10）：851－856.

［2］Harn L.Group-oriented（t，n）threshold digital signature scheme and digital multi-signature［J］.IEEE Proceedings on Computers and Digital Techniques，1994，141（5）：307－313.

［3］Harn L.Public-key cryptosystem design based on factoring and discrete logarithms［J］.IEEE Proceedings on Computers and Digital Techniques，1994，141（3）：193－195.

［4］Lyu W L，Zhong C.A robust elliptic curve digital multi-signature scheme［J］.Computer Engineering，2004，30（5）：30－32.

［5］盧鵬菲，詹雄泉，洪景新.基于橢圓曲線的有序多重數(shù)字簽名方案［J］.廈門大學(xué)學(xué)報：自然科學(xué)版，2005，44（3）：341－343.Lu P F，Zhan X Q，Hong J X.The elliptic curve sequential multi-signature digital scheme［J］.Journal of Xiamen University（Natural Science），2005，44（3）：341－343.（In Chinese）

［6］胡越梅，朱艷琴.一個基于ECC的多重數(shù)字簽名方案［J］.微電子學(xué)與計算機(jī)，2007，24（1）：180－182.Hu Y M，Zhu Y Q.An elliptic curve digital multisignature scheme［J］.Micro-electronics ＆Computer，2007，24（1）：180－182.（In Chinese）

［7］Koblitz N.Elliptic curve cryptosystems［J］.Mathematics of Computation，1987，48（177）：203－209.

［8］焦陽，傅德勝.基于ELGamal型的有序多重數(shù)字簽名方案［J］.四川大學(xué)學(xué)報：自然科學(xué)版，2013，50（4）：757－759.Jiao Y，F(xiàn)u D S.A sequential multi-signature scheme based on ELGamal［J］.Journal of Sichuan University（Natural Science Edition），2013，50（4）：757－759.（In Chinese）

［9］羅麗平，施榮華，劉宇.基于RSA的ELGamal型有序多重數(shù)字簽名方案［J］.計算機(jī)工程與應(yīng)用，2006，42（1）：120－121.Luo L P，Shi R H，Liu Y.ELGamal type sequential digital multi-signature scheme based on RSA［J］.Computer Engineering and Applications，2006，42（1）：120－121.（In Chinese）

［10］曹素珍，王彩芬.基于離散對數(shù)問題的可截取簽名方案［J］.計算機(jī)工程，2013，39（4）：132－136.Cao S Z，Wang C F.Content extraction signature scheme based on DLP［J］.Computer Engineering，2013，39（4）：132－136.（In Chinese）

［11］王澤成.基于身份數(shù)字簽名方案的通用可組合安全性［J］.計算機(jī)應(yīng)用，2011，31（1）：118－122.Wang Z C.Universally composable security of identity-based signature schemes［J］.Journal of Computer Applications，2011，31（1）：118－122.（In Chinese）

［12］劉曉川，陳恩紅.基于橢圓曲線的結(jié)構(gòu)化多重數(shù)字簽名方案［J］.計算機(jī)應(yīng)用與軟件，2010，28（8）：295－297.Liu X C，Chen E H.A structured multi-signature scheme based on elliptic curve cryptosystem［J］.Computer Applications and Software，2010，28（8）：295－297.（In Chinese）