張彩娟，游林，2

（1. 杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2. 杭州電子科技大學(xué)通信學(xué)院，浙江 杭州 310018）

基于雙線性對(duì)的多重?cái)?shù)字簽名方案

張彩娟1，游林1，2

（1. 杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2. 杭州電子科技大學(xué)通信學(xué)院，浙江 杭州 310018）

基于雙線性對(duì)及3個(gè)困難性問(wèn)題（IFP、DLP、CDHP）提出了新的多重?cái)?shù)字簽名方案。新方案將廣播多重?cái)?shù)字簽名中簽名快速的優(yōu)點(diǎn)應(yīng)用到按序多重?cái)?shù)字簽名，改變簽名的一般機(jī)制，使簽名者同時(shí)進(jìn)行簽名；然后，由可信任第三方驗(yàn)證簽名，驗(yàn)證通過(guò)后發(fā)送給驗(yàn)證者；最后，由驗(yàn)證者將簽名轉(zhuǎn)變?yōu)榘葱虻?。同時(shí)，分析了方案在3個(gè)困難問(wèn)題、防偽攻擊和抗部分成員合謀攻擊方面的安全性能。新方案具有計(jì)算量少、算法簡(jiǎn)單、獲取簽名速度快、安全性強(qiáng)等優(yōu)點(diǎn)。

多重?cái)?shù)字簽名；按序簽名；廣播簽名；安全性

1　引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，人們希望通過(guò)電子設(shè)備就能實(shí)現(xiàn)遠(yuǎn)距離的、快速的交易。自 1976 年Diffie和Hellman［1］首次提出公鑰密碼體制的概念后，數(shù)字簽名隨之產(chǎn)生，并開(kāi)始在商業(yè)通信系統(tǒng)中得到廣泛應(yīng)用。實(shí)際情況中，有時(shí)需要多個(gè)用戶對(duì)同一消息進(jìn)行簽名，這類需要多個(gè)實(shí)體對(duì)同一份合同進(jìn)行簽名的電子對(duì)應(yīng)物就是多重?cái)?shù)字簽名。

自引入多重?cái)?shù)字簽名［2］的概念后，不同的多重?cái)?shù)字簽名方案相繼被提出。文獻(xiàn)［3～5］提出基于離散對(duì)數(shù)困難性問(wèn)題的多重?cái)?shù)字簽名；文獻(xiàn)［5］在離散對(duì)數(shù)困難性的基礎(chǔ)上把整數(shù)分解問(wèn)題也應(yīng)用到簽名里，使簽名方案更安全、可靠；文獻(xiàn)［6～8］給出關(guān)于散列函數(shù)的發(fā)展和其在多重簽名中的應(yīng)用；文獻(xiàn)［9］把盲簽名以及代理簽名運(yùn)用到多重簽名中形成新的方案；文獻(xiàn)［10，11］中對(duì)橢圓曲線密碼體制的運(yùn)用和改進(jìn)，使多重簽名方案更加多樣化；文獻(xiàn)［12］中提出的針對(duì)基于離散對(duì)數(shù)多重簽名方案的攻擊和文獻(xiàn)［13］提出的基于橢圓密碼體制的簽名方案的攻擊，使多重簽名方案更加完善、安全。以上文獻(xiàn)各有優(yōu)缺點(diǎn)，但其設(shè)計(jì)思想值得借鑒。

根據(jù)多重簽名順序和過(guò)程的不同，可分為按序多重簽名和廣播多重簽名。文獻(xiàn)［6，14］給出基于同樣問(wèn)題的按序和廣播2種多重簽名方案，通過(guò)比較可以發(fā)現(xiàn)，按序多重簽名方案耗時(shí)更久些，對(duì)重大性和緊急性事件有較大影響。例如，在按序多重?cái)?shù)字簽名體系中，當(dāng)消息發(fā)送給簽名者時(shí)，若簽名者未及時(shí)簽名，則后面的簽名者也無(wú)法對(duì)消息進(jìn)行簽名。依此下去，每個(gè)簽名者都耽誤一點(diǎn)時(shí)間，則最后驗(yàn)證者收到簽名的時(shí)間就會(huì)延長(zhǎng)很久。針對(duì)按序多重簽名方案這一缺點(diǎn)，本文將按序和廣播 2種多重簽名在某種程度上結(jié)合起來(lái)，同時(shí)又結(jié)合離散對(duì)數(shù)困難性問(wèn)題、整數(shù)分解問(wèn)題以及Diffie-Hellman計(jì)算問(wèn)題來(lái)構(gòu)造新方案。與文獻(xiàn)［5］的按序多重?cái)?shù)字簽名方案相比，本方案獲取簽名速度更快、運(yùn)算量更少、安全性更高。

2　基礎(chǔ)知識(shí)

2.1 對(duì)稱雙線性對(duì)

2.2 困難問(wèn)題假設(shè)

定義1 大整數(shù)分解問(wèn)題（IFP）。已知2個(gè)大素?cái)?shù)p， q，求n=pq是容易的，但若由n來(lái)求p 和q是困難的，這就是大整數(shù)分解困難問(wèn)題。

定義3 Diffie-Hellman計(jì)算問(wèn)題（CDHP）。對(duì)于任意的給出，計(jì)算出abP且滿足

2.3 基于SDLP和IFP的多重?cái)?shù)字簽名方案

文獻(xiàn)［5］提出基于SDLP和IFP的按序多重?cái)?shù)字簽名方案。簡(jiǎn)述如下。

2） 簽名算法。

3）簽名的驗(yàn)證

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

3.1系統(tǒng)的建立

3.2簽名算法

3.3簽名的驗(yàn)證

這樣形成的最終簽名長(zhǎng)度是固定的，與簽名者的個(gè)數(shù)無(wú)關(guān)。

上述按序簽名方案是在文獻(xiàn)［5］的基礎(chǔ)上進(jìn)行改進(jìn)的，與文獻(xiàn)［5］相比，本文引入了雙線性對(duì)并選取了不同的ni，使方案的安全性更高；同時(shí)，又改變了按序簽名的體制，使簽名經(jīng)過(guò)了可信任第三方和驗(yàn)證者雙重的驗(yàn)證，更加真實(shí)可靠；且新方案中可信任第三方產(chǎn)生的私鑰量較小，節(jié)省了密鑰存儲(chǔ)空間；此外，新方案在整個(gè)簽名生成的過(guò)程中運(yùn)算量較小、獲取簽名速度快，簽名的長(zhǎng)度也是固定的，不隨簽名者的變化而改變。

4　效率及安全性分析

4.1效率分析

本文提出的新方案與文獻(xiàn)［5］在運(yùn)算量和簽名時(shí)間上的比較如表1所示。

Ui開(kāi)始到簽名結(jié)束所消耗的時(shí)間， T△表示從消息發(fā)出后到所有簽名結(jié)束需要的總時(shí)間。

由表1可知，本文方案在簽名所需總時(shí)間和簽名生成過(guò)程中所需運(yùn)算量上都占有極大優(yōu)勢(shì)。顯然，新方案獲取簽名的速度更快、運(yùn)算量更少、效率更高。

4.2安全性分析

4.2.1困難問(wèn)題

表1　2個(gè)方案運(yùn)算效率對(duì)比

DLP：因?yàn)?e（ g， g）是可以由公共參數(shù)求得的，同時(shí)是公開(kāi)的，所以，任何人想要通過(guò) e（ g， g）和）來(lái)找到，使成立是不可能的，因?yàn)閷ふ业倪^(guò)程實(shí)際就是解決離散對(duì)數(shù)問(wèn)題的過(guò)程。

4.2.2防偽攻擊

4.2.3抗部分成員合謀攻擊

本文方案在一定程度上將按序多重簽名與廣播多重簽名結(jié)合起來(lái)，先由每個(gè)簽名者立地進(jìn)行簽名，然后，將交給可信任第三方C進(jìn)行驗(yàn)證，驗(yàn)證通過(guò)后由C將簽名直接發(fā)送給驗(yàn)證者。驗(yàn)證者接收到所有簽名后，按照預(yù)定的順序?qū)灻M(jìn)行逐一驗(yàn)證，驗(yàn)證成功后再統(tǒng)一形成總的簽名正是由于該算法中簽名者進(jìn)行簽名時(shí)是各自獨(dú)立的，且每個(gè)簽名要經(jīng)過(guò)C的驗(yàn)證才能發(fā)送給驗(yàn)證者，所以，整個(gè)方案中沒(méi)有通過(guò)簽名者相互合作而形成的公私鑰，即部分成員之間是無(wú)法通過(guò)合謀來(lái)偽造任何東西的。

從上面安全性的分析可以看出，雙線性對(duì)的引入、不同ni的選取以及新結(jié)構(gòu)的構(gòu)造使新方案更安全，防攻擊能力更強(qiáng)。

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

針對(duì)按序多重?cái)?shù)字簽名方案獲取簽名速度慢的特點(diǎn)，本文改變了傳統(tǒng)按序簽名的體制，將按序和廣播簽名在一定程度上結(jié)合起來(lái)，形成新的按序多重簽名體制。新方案具有運(yùn)算量少、算法簡(jiǎn)單、獲取簽名速度快、安全性強(qiáng)等優(yōu)點(diǎn)，同時(shí)，方案中新的構(gòu)造方法為簽名節(jié)省了大量時(shí)間，極具推廣性，是具有發(fā)展?jié)摿Φ亩嘀財(cái)?shù)字簽名方案。

［1］DIFFIE W， HELLMAN M E. New directions in cryptography［J］. IEEE Transactions on Information Theory， 1976， 22（6）： 644-654.

［2］ITAKURA K. A public-key cryptosystem suitable for digital multi-signatures［J］. Nec Research & Development， 1983， 71（1）：474-480.

［3］LU L R， ZENG J J， KUANG Y H， et al. A new multi-signature scheme based on discrete logarithm problem and its distributed computation［J］. Chinese Journal of Computers， 2002， 25（12）：1417-1420.

［4］BURMESTER M， DESMEDT Y， DOI H， et al. A structured elgamal-type multi-signature scheme［C］//The 3rd International Workshop on Practice and Theory in Public Key Cryptography. c2000：466-483.

［5］DíAZ R D， ENCINAS L H， MASQUé J M. A multi-signature scheme based on the SDLP and on the IFP［C］// International Conference on Computational Intelligence in Security for Information Systems. c2011：135-142.

［6］ZHANG J H， WEI Y Z， WANG Y M. Digital multi-signatures scheme based on RSA［J］. Journal of China Institute of Communications， 2003， 24（8）： 150-154.

［7］U.S. Department of Commerce. Secure Hash standard-SHS： federal information processing standards publication 180-4［M］. Create Space Independent Publishing Platform， 2012.

［8］NOROOZI E， DAND S M， SABOUHI A， et al. A new dynamic hash algorithm in digital signature［J］. Advanced Machine Learning Technologies and Applications， 2012， 322（12）： 583-589.

［9］GUO W， ZHANG J Z， LI Y P， et al. Multi-proxy strong blind quantum signature scheme［J］. International Journal of Theoretical Physics， 2016， 55（3）： 1-13.

［10］LI F， XUE Q. Two improved proxy multi-sigvcdnature schemes based on the elliptic curve cryptosystem［M］//Computing and Intelligent Systems. Berlin Heidelberg： Springer， 2011： 101-109.

［11］CHOUKSEY R， SIVASHANKARI R， SINGHAI P. ECDLP based proxy multi-signature scheme［M］//Advances in Computing and Information Technology. Berlin Heidelberg： Springer， 2012： 71-79.

［12］HAN X X， WANG G P， BAO F， et al. An attack to multi-signature schemes based on discrete logarithm［J］. Chinese Journal of Computers， 2004， 27（8）： 1147-1152.

［13］LIU Y， LUO P， DAI Y Q. Attack on digital multi-signature scheme based on elliptic curve cryptosystem［J］. Journal of Computer Science & Technology， 2007， 22（1）： 92-94.

［14］WANG X F， ZHANG J， WANG S P. Digital multi-signature scheme and its security roof［J］. Chinese Journal of Computer， 2008， 31（1）：176-183.

Digital multi-signature scheme based on bilinear pairing

ZHANG Cai-juan1， YOU Lin1，2

（1. College of Science， Hangzhou Dianzi University， Hangzhou 310018， China；2. College of Communication， Hangzhou Dianzi University， Hangzhou 310018， China）

Based on bilinear pairing and three complicated problems， a new digital multi-signature scheme was proposed. In the new scheme， the advantage of fast signature in broadcasting digital multi-signature was applied to sequential digital multi-signature. By changing the general mechanism of signature， signing could be done simultaneously by the signers. Then， the signature was sent to verifier after it was verified by trusted third party. The transformation from concurrent signature to sequential signature was finally realized by the verifier. The security capabilities in three complicated problems， anti-fake attack and anti-conspiracy attack from some members of the new scheme were analyzed. Proposed scheme has many advantages over the old ones， such as fewer calculation， simpler algorithm， faster signing， higher security.

digital multi-signature， sequential signature， broadcasting signature， security

Zhejiang Province Science and Technology Innovation Program （No.2013TD03）

TP309

A

10.11959/j.issn.2096-109x.2016.00061

2016-05-13；

2016-06-04。通信作者：張彩娟，908332087@qq.com

浙江省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)基金資助項(xiàng)目（No.2013TD03）

張彩娟（1993-），女，山西大同人，杭州電子科技大學(xué)碩士生，主要研究方向?yàn)樾畔踩c密碼學(xué)。

游林（1966-），男，江西臨川人，杭州電子科技大學(xué)教授，主要研究方向?yàn)樾畔踩c密碼學(xué)。