具有可追查的基于橢圓曲線的門限簽名方案

梅偉鋒，沈忠華

(杭州師范大學理學院，浙江 杭州 310036)

隨著信息化技術(shù)不斷深入和互聯(lián)網(wǎng)的迅速發(fā)展，信息安全也越來越重要.數(shù)字簽名技術(shù)是信息安全理論與技術(shù)的基礎(chǔ)和重要保證之一.然而，在數(shù)字簽名中，有時候需要由集體而非個人進行簽名.門限密碼由Shamir[1]于1979年首次提出，目前主要涉及門限秘密共享、門限簽名、 門限加/解密、門限密鑰托管等研究方向[2].1987年，Desmedt[3]提出了基于群組與群組之間的安全通信的面向群組的密碼系統(tǒng)，該系統(tǒng)能夠被用于門限簽名.1992年，Desmedt等[4]提出了基于RSA和秘密共享的面向群組的(t，n)門限數(shù)字簽名方案，之后，Li等[5]指出t個或者更多的惡意參與者能形成合謀攻擊,從而得到系統(tǒng)的密鑰進而偽造簽名.

現(xiàn)如今，如何設計具有合謀攻擊免疫性的門限簽名方案成為一個研究熱點.文獻[6]中的門限簽名方案存在不能抗合謀攻擊的缺陷，而文獻[7-9]中的方案則不滿足身份可追查性.對于以上問題，考慮到橢圓曲線離散對數(shù)的難解性，本文提出一個基于橢圓曲線的門限簽名方案，它具有抗合謀攻擊和可追查性.接下來描述此方案，然后對方案的安全性和可行性進行分析，最后給出一個結(jié)論.

1 門限簽名方案

假設系統(tǒng)有一個可信任的秘密分發(fā)中心(shared distribution center,SDC)，本方案的安全性是基于橢圓曲線的難解性.SDC負責群私鑰、群公鑰以及其他系統(tǒng)參數(shù)的選取.

1.1 系統(tǒng)初始化

不失一般性，假設一個群體中有w個成員，用集合U=(P1,P2,…,Pw)來表示該群體進行簽名.B?U表示集合U中參與簽名的t個成員的子集，不失一般性可假定B=(P1,P2,…Pt)(若有多于t個人想簽名，只需要其中的t個人簽名即可). 另外選出一個主要負責人Pm，其中Pm不一定是簽名參與者.

(2)取E上階為n的生成元G=(xG,yG)作為基點,即有nG=o，o表示一個無窮原點，基點G公開.

(3)選取兩個安全的公開的Hash函數(shù)h()，h1().

(4)SDC公開橢圓曲線相關(guān)參數(shù)(a，b，q，G,h()，h1(),n) .

1.2 密鑰生成

(1)SDC為每個成員Pi分別構(gòu)造其對應的t-1階秘密多項式

每個成員Pi選擇自己唯一的標識號IDi并公開.根據(jù)事先確定的門限值t，SDC把每一個成員的一個t-1次多項式fi(x) 通過秘密通道發(fā)送給Pi,然后每個成員均向其余成員公開廣播aikG,并為集合U中每一位成員Pi(包括自己)計算λij=fi(IDj)(modn)), 并通過廣播的形式將λij(j≠i)發(fā)給Pj,Pi自己保留λii.

(2)每個成員Pi對接收到其他的w-1個用戶發(fā)來λij進行驗證

(5)通過上面的步驟可知，由于門限值為t，所以在這個系統(tǒng)中任意t個成員聯(lián)合，就可以利用拉格朗日多項式插值法恢復共享多項式：

這樣則有下式成立：

1.3 部分簽名的的生成

(1)當要對消息m進行簽名時，設參與簽名的t個人為B=(P1,P2,…,Pt).主要負責人Pm把要簽名的集合B的各個成員身份IDv(v∈(1,t)) 發(fā)送給SDC，SDC計算SID=h1(ID1‖ID2‖…‖IDt)并且把SID秘密發(fā)送給Pm，SDC保存(SID,(ID1,ID2,…,IDt)).

(2)Pi選擇一個隨機數(shù)ki，ki∈[1,n-1]，計算Qi=kiG，其中ri=xi(modn),如果ri=0，則重新選取隨機數(shù)ki.

(4)計算l=h(m)，si=(ki+ldi),如果si=0,那么重新選取隨機數(shù)ki.生成部分簽名(m,ri,si).并把部分簽名(m,ri,si)發(fā)送給Pm.

1.4 Pm對組密鑰的簽名

1.5 DC對簽名的驗證

(2) 計算l=h(m),Vi=siG-lTi,如果Vi=0 簽名無效.否則令ri為Vi的橫坐標.

證明由si=ki+ldi(modn)得

Vi=siG-lTi=(ki+ldi)G-lTi=kiG,即ri=ri′.

1.6 群簽名的生成

1.7 群簽名的驗證

2 方案的安全性和可行性

(1)方案具有門限特性.任何少于t個人成員組成的集合均不能產(chǎn)生一個有效的門限群簽名.根據(jù)拉格朗日插值定理，只有t個人或多于t個人的時候才能恢復出群私鑰f(0)，另外，當少于t個人簽名時也無法合成群簽名.

(2)根據(jù)群公鑰Y和各個成員的公鑰Ti來推導出群密鑰X和各個成員的xi，其困難等價于求解有限域上基于橢圓曲線的離散對數(shù)問題.

(3)方案具有匿名性.當簽名接收者接收到群簽名時，在沒有SDC的幫助下是無法知道哪些人參與了簽名.

(6)方案能抗合謀攻擊.在現(xiàn)有眾多門限方案中，t個或多于t個成員合作能夠恢復系統(tǒng)秘密多項式函數(shù)f(x)，因此t個或多于t個成員能夠算出λi=f(IDi)，從而偽造其他成員的份額簽名.但是在本方案中， 任何小組不能冒充其他小組生成簽名，因為他們不知道ci所以無法計算出其他成員的私鑰di.

3 結(jié) 論

基于橢圓曲線離散對數(shù)的難解性，提出一個有實際應用意義的基于橢圓曲線的門限簽名方案，并且討論了該方案的正確性、可行性和安全性.與經(jīng)典的ECDSA方案[10]相比，該方案提高了整體運算速度，具有抗合謀攻擊和可追查性.

[1]Shamir A. How to share a secret[J].Conlnlun ACM,1979，11:612-613.

[2]周由勝.門限密碼相關(guān)技術(shù)研究[D].北京：北京郵電大學,2011.

[3]Desmedt Y.Society and group oriented cryptography[C]//Advance in Cryptology-CRYPTO' 87. USA :California,1987:120-127.

[4]Desmedt Y, Frankel Y. Shared generation of authenticator and signatures[C]//Advances in Cryptology-CRYPTO′ 91.Berlin: Springer-Verlag,1992:457-469.

[5]LI C M, Lee N Y. Remark on the threshold RSA signature scheme[C]//Advances in CRPTO' 93.Berlin: Springer-Verlag,1994:413-420.

[6]李海峰,藍才會,左為,等.基于身份的無可信中心的門限群簽名方案[J].計算機工程應用,2012,48(32):89-93.

[7]陳洪海,王宏久,于存光.安全的(t,n)門限簽名方案[J].沈陽師范大學學報:自然科學版,2012，30(2):172-175.

[8]周敏,索南仁欠.基于橢圓曲線的DSA門限簽名[J].青海師范大學學報:自然科學版,2012,30(2):6-8.

[9]徐燕.一個改進的無可信中心的門限簽名方案[J].宣賓學院學報,2012,12(6):27-29.

[10]徐瑩,孫劍.一種改進的基于橢圓曲線的數(shù)字簽名方案[J].黑龍江科技學院學報,2012,25(6):66-69.