一種基于橢圓曲線的Schnorr型多重?cái)?shù)字簽名

周 敏，張秉儒

（青海師范大學(xué)數(shù)學(xué)系，青海西寧 810008）

1 引言

數(shù)字簽名在密碼學(xué)中就是用私有密鑰進(jìn)行加密，接受方用公開(kāi)密鑰進(jìn)行解密.數(shù)字簽名技術(shù)首先最早是應(yīng)用于用戶登錄過(guò)程，其次相關(guān)的數(shù)字證書(shū)應(yīng)用在網(wǎng)上報(bào)關(guān)，網(wǎng)上采購(gòu)，電子商務(wù)交易，現(xiàn)在還廣泛應(yīng)用于電子郵件，數(shù)據(jù)交換，電子交易［1］.1983年Boyd提出多重?cái)?shù)字簽名［2］的概念以來(lái)，多重?cái)?shù)字簽名發(fā)展的很快，對(duì)于不同的數(shù)學(xué)難題的多重?cái)?shù)字簽名應(yīng)運(yùn)而生.多重?cái)?shù)字簽名即多個(gè)用戶對(duì)同一消息進(jìn)行的數(shù)字簽名，從而實(shí)現(xiàn)多個(gè)用戶對(duì)同一消息進(jìn)行簽名方案.根據(jù)簽名的順序不同分為有序多重?cái)?shù)字簽名和廣播多重?cái)?shù)字簽名.有序多重簽名是所有簽名者按照一定的次序進(jìn)行簽名，每一位簽名者在收到前一位簽名者簽名先對(duì)其驗(yàn)證，若驗(yàn)證沒(méi)通過(guò)，則拒絕后面的工作并終止整個(gè)簽名，若驗(yàn)證通過(guò)，則進(jìn)行接下來(lái)的簽名.廣播多重簽名是指在簽名過(guò)程中簽名組成人員之間沒(méi)有先后順序，但在每個(gè)簽名成員簽完名后有一個(gè)簽名收集者來(lái)最終完成這個(gè)簽名.基于橢圓曲線的多重簽名是指在橢圓曲線的離散對(duì)數(shù)問(wèn)題下的多重?cái)?shù)字簽名，它比一般基于離散對(duì)數(shù)問(wèn)題更加困難.2006年閻希光提出了一種基于橢圓曲線的多重簽名［2］，2007年李斌等又提出另一種基于橢圓曲線的多重?cái)?shù)字簽名［3］，在同一年他們又提出Schnorr型多重簽名［4］，而本文基于前人基礎(chǔ)上提出了基于橢圓曲線的Schnorr型多重簽名它不僅提高安全性，還利用Schnorr簽名的特點(diǎn)即密文短，運(yùn)算速度快.

2 Schnorr型廣播多重?cái)?shù)字簽名

2.1 方案描述

此方案包括系統(tǒng)參數(shù)的選取，簽名過(guò)程和驗(yàn)證過(guò)程，方案的參與者即消息發(fā)送者U1，若干簽名者Ui（i=1，2…n），簽名收集者Uc和簽名驗(yàn)證者Uv.

2.2 系統(tǒng)參數(shù)的選取

選取大素?cái)?shù)p，q滿足q整除p－1，q和p是整數(shù)，g∈Z*p且滿足gq=1modp，g≠1，h為單向哈希函數(shù)，選取的私鑰為x，1＜x＜q，公鑰為y，y=gxmodp，（p，q，g，y，h） 公開(kāi).

2.3 簽名過(guò)程

Step1:每一位簽名者Ui（i=1，2…n）任意選取xi∈Z*q，作為Ui的私鑰，并計(jì)算ri=gkimodp，將其發(fā)送給其他簽名者Uj（j≠i）.

Step2:Uj收到ri后計(jì)算R=rimodp和e=h（R，m），然后再計(jì)算si=ki－xi（e+R）modq.

Step3:將簽名（m，（si，ri））作為用戶對(duì)m的簽名發(fā)送到Uc.

Step4:Uc收到（m，（si，ri）） 后，其中i=1，2…，n，按照R=rimodp計(jì)算R和e，然后驗(yàn)證方程g－siri=gki=y（e+r）modp

Step5:Uc計(jì)算s=s1+s2+…+sn，則多重簽名是（m，（s，R））.

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

消息接收者Uv收到消息（m，（s，R））后，驗(yàn)證（y1y2…yn）（e+R）=Rg－smodp是否成立，若成立則簽名有效，否則拒絕簽名.

3 基于橢圓曲線的Schnorr型廣播多重簽名

3.1 參數(shù)選取

設(shè)N是元素個(gè)數(shù)為q的有限域，全局參數(shù)表示為（q，F(xiàn)R，a，b，G，n，l），F(xiàn)R為GF（q） 中的一個(gè)元素，定義橢圓曲線E:y2=x3+ax+b，基點(diǎn)y2=x3+ax+b，xG，yG∈GF（q），G∈E，G的階為素?cái)?shù)n，n＞2160，n＞4，#E（GF（q））為橢圓曲線構(gòu)成群的階，l=#E（GF（q））/n.每一個(gè)簽名者Ui的私鑰為di，相應(yīng)的公鑰為Q=diG∈E（GF（q）），Ui的公鑰為Qi=diG.

3.2 簽名生成

UI將m發(fā)送到每一個(gè)簽名者Ui（i=1，2…，n），Ui和Uc收到消息后進(jìn)行如下操作:

Step1:Ui選擇一個(gè)隨機(jī)數(shù)ki，ki∈［1，n－1］計(jì)算kiG=（xi，yi），ri=ximodn，Ui將ri發(fā)送給簽名收集者Uc

Step2:Uc收到ri后，計(jì)算R1=rimodp和e=h（m，R1）將R1發(fā)送每一位簽名者Ui（即將R1廣播出去）.

Step3:對(duì)消息m，Ui計(jì)算si=ki－di（e+R1）modn，si作為用戶Ui對(duì)消息m的簽名，將（si，ri）發(fā)送到Uc.

Step4:Uc收到（si，ri） 后，計(jì)算R1=rimodp，s=s1+s2+…+…sn，然后將（si，ri，R1） 發(fā)送簽名收集者Uv.

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

Uv收到簽名后（si，ri，R1） 后，計(jì)算Xi=siG－（e+R1）Qi=（xi，y1），驗(yàn)證vi=rimodn是否成立，其中（i=1，2…n），如果等式成立則認(rèn)為Ui對(duì)消息的簽名有效，否則簽名無(wú)效.

由上述推論過(guò)程可得，Uv收到簽名（s，ri，R1）后驗(yàn)證vi=rimodn是否成立，才能確定所有簽名是否有效.

4 安全性分析

4.1 體制上的安全

首先，基于橢圓曲線體制上，且定義在GF（q）上，G是橢圓曲線上有理子群，設(shè)A，B滿足B=kA，k∈［0，n］，求出k是困難的，這是基于橢圓曲線的離散對(duì)數(shù)問(wèn)題，因此該方案基于橢圓曲線上就保證了其安全性.其次，Schnorr型的密文比ELGamal型的密文短，所以該簽名比基于橢圓曲線ELGamal型多重?cái)?shù)字簽名運(yùn)算速度快.

4.2 防完全攻破

它所依賴的主要是哈希函數(shù)，該簽名在簽名生成過(guò)程中引進(jìn)了哈希函數(shù)e=h（），偽造者偽造e＇，從而計(jì)算m是困難的，因?yàn)楣：瘮?shù)偽造者無(wú)法計(jì)算.

4.3 防一般偽造

對(duì)于每個(gè)簽名者Ui簽名si=ki－di（e+R1）modn，其驗(yàn)證方程為:vi=rimodn和對(duì)于收到簽名消息（si，ri）的簽名收集者Uc，有式子R1=rimodp和si=s1+s2+…+sn所得出的消息簽名（xi，ri，R1），若攻擊者欲以Uc的身份偽造所有簽名Ui的簽名即求解（si，ri，R1） 滿足Xi=siG－（e+R1）Qi=（xi，yi），得vi=rimodn它是困難的.

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

本文首先給出了一種Schnorr型的多重?cái)?shù)字簽名方案，并由前人的理論依據(jù)給出了一種基于橢圓曲線的Schnorr型的多重?cái)?shù)字簽名方案，并對(duì)其進(jìn)行驗(yàn)證，此外還對(duì)其的安全性進(jìn)行了分析.

:

［1］趙澤茂.數(shù)字簽名理論［M］.北京:科學(xué)出版社，2007:67－68.

［2］閻希光.基于橢圓曲線的多重簽名［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2006，35（3）.

［3］李斌，趙澤茂，李繼國(guó).基于橢圓曲線的多重?cái)?shù)字簽名方案［J］.計(jì)算及應(yīng)用與軟件，2007，24（4）.

［4］李斌，趙澤茂，龔少麟.Schnorr型多重?cái)?shù)字簽名方案［J］.河海大學(xué)常州分校學(xué)報(bào)，2005，19（3）.