一種基于橢圓曲線的Schnorr型多重數(shù)字簽名

周 敏，張秉儒

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

1 引言

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

2 Schnorr型廣播多重數(shù)字簽名

2.1 方案描述

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

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

選取大素數(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） 公開.

2.3 簽名過程

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

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

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

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

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

2.4 驗證過程

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

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

3.1 參數(shù)選取

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

3.2 簽名生成

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

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

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

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

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

3.3 驗證過程

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

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

4 安全性分析

4.1 體制上的安全

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

4.2 防完全攻破

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

4.3 防一般偽造

對于每個簽名者Ui簽名si=ki－di（e+R1）modn，其驗證方程為:vi=rimodn和對于收到簽名消息（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é)束語

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

:

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

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

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

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