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

周 敏，張秉儒

（青海師范大學數學系，青海西寧 810008）

1 引言

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

2 Schnorr型廣播多重數字簽名

2.1 方案描述

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

2.2 系統參數的選取

選取大素數p，q滿足q整除p－1，q和p是整數，g∈Z*p且滿足gq=1modp，g≠1，h為單向哈希函數，選取的私鑰為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，將其發送給其他簽名者Uj（j≠i）.

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

Step3:將簽名（m，（si，ri））作為用戶對m的簽名發送到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 參數選取

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

3.2 簽名生成

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

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

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

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

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

3.3 驗證過程

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

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

4 安全性分析

4.1 體制上的安全

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

4.2 防完全攻破

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

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 結束語

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

:

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

［2］閻希光.基于橢圓曲線的多重簽名［J］.網絡安全技術與應用，2006，35（3）.

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

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