基于Weil對的橢圓曲線數(shù)字簽名方案

田潤芙，楊 旭

(1.張家口職業(yè)技術(shù)學院，河北張家口 075051；2.河北宣化縣交通局，河北張家口 075100)

0 引言

數(shù)字簽名是一種重要的信息安全技術(shù)，隨著橢圓曲線在密碼學中的應用，人們對其進行了大量研究，發(fā)現(xiàn)作為一種公鑰密碼，橢圓曲線密碼不僅有比較高的安全性，而且利用橢圓曲線離散對數(shù)問題可以構(gòu)造三種基本形式的公鑰體制，即數(shù)字簽名體制、公鑰加密體制和密鑰交換協(xié)議等。1985年ElGamal提出了基于離散對數(shù)問題的數(shù)字簽名方案，隨后對ElGamal方案的變形和改進方案相繼被提出，這些方案統(tǒng)稱為ElGamal型數(shù)字簽名方案。1994年Harn.L.和Xu.Y.提出了設(shè)計ElGamal型數(shù)字簽名的規(guī)則，并列出了18種安全的ElGamal型數(shù)字簽名方案。[1]本文在遵循這些規(guī)則的前提下，給出了另外一種簽名方案。這種數(shù)字簽名體制是通過基于ElGamal的橢圓曲線數(shù)字簽名實現(xiàn)，通過Weil對來驗證的。

1 基本知識與相關(guān)概念

1.1 Weil對及其相關(guān)概念

1.1.1 相關(guān)概念

定義1：設(shè)φ：E→E是橢圓曲線E上的一個非常數(shù)有理映射，P是E上一點，有理函數(shù)u是E在φ(P)點上的一致參數(shù)，稱u°φ在P點的階數(shù)為φ在P點的分歧指數(shù)(RamificationIndex)，記作eφ(P)=OrdP(u°φ) 。

eφ(P)與u的選取無關(guān)。因為u是E在eφ(P)點的一致參數(shù)，所以P是u°φ的零點，故eφ(P)≥1。特別地，如果φ是一個自同態(tài)，那么每一點的分歧指數(shù)都相同，故可以記作eφ。

定義2：設(shè)φ：E→E是橢圓曲線E上的一個非常數(shù)有理映射，可如下定義除子群Div(E)上的自同態(tài)：

φ*：Div(E)→Div(E)

對任意的非零有理函數(shù)r，下式成立，

div(r°φ)=φ*(div(r))

Weil對的定義：Weil對em是如下定義的一個二元函數(shù)：

em:E[m]×E[m]→μm

1.1.2Weil對具有的性質(zhì)：

(1)雙線性：(i)對任意的S1,S2,T∈E[m]，em(S1+S2,T)=em(S1,T)em(S2,T)

(ii)對任意的S,H1,H2∈E[m]，em(S,H1+H2)=em(S,H1)em(S,H2)，

(2)恒等性：對任意的S∈E[m]，em(S,S)=1

(3)對稱性：對任意的P，Q∈E[m]，em(nP,Q)=em(P,Q)n,em(P,nQ)=em(P,Q)n

(4)非退化性：如果任意的S∈E[m]，那么em(S,O)=1；如果em(S,T)=1對于所有的T∈E[m]，那么S=O。

(5)對于所有的S1，S2∈E[m],如果E[m]?E(Fqk)，那么em(S1,S2)∈Fqk。

1.2 橢圓曲線上的ElGamal公鑰體制

1.2.1 橢圓曲線離散對數(shù)問題

令E(F)為有限域F上的一條橢圓曲線，點P∈E(F)，對于隨機生成一個整數(shù)d，容易計算Q=d×P，但給定Q和P計算d就相對困難，即為橢圓曲線離散對數(shù)問題(ECDLP)。橢圓曲線密碼體制的依據(jù)就是利用定義在曲線群上的離散對數(shù)問題的難解性。

設(shè)P是橢圓曲線E上的一點，若存在最小的正整數(shù)n，使得nP=O，其中O是無群遠點，則稱n是點P的階。

1.2.2 橢圓曲線上的ElGamal公鑰體制

設(shè)m|Pm是明文空間到橢圓曲線的嵌入，G∈E為橢圓曲線上的基點，G的階為q。用戶B欲向A發(fā)送信息m，則A選取dA(0

2 基于Weil對的橢圓曲線數(shù)字簽名方案

設(shè)p,Fq,q,l,μl均和前面1.1中Weil配對定義的意義相同(為了和明文m區(qū)別，把下標m改為l)，P∈μl是E(Fq)上階數(shù)為l的點?；陔x散對數(shù)的難解性，用戶A和B利用橢圓曲線的ElGamal公鑰體制和Weil對進行簽名以及驗證。

⑴用戶A和B都將自己的公鑰公開登記，用來作為雙方和第三方(如：仲裁者)驗證簽名的依據(jù)。

⑵將密碼信息m用哈希算法求得數(shù)字摘要e，e=h(m)，將e嵌入到橢圓曲線上，記為點Pe。

(i) 由Weil對的對稱性可知：em(nP,Q)=em(P,Q)n=em(P,nQ)。

(ii)據(jù)雙線性和對稱性二性質(zhì)，可得，對em(Y,G)的驗證如下：

em(Y,G)=em(dA(Pe+X),G)=em(Pe+X,dAG)=em(Pe+X,PA)=em(PePA)em(XPA)即Verk(Pe,X,Y)=true?em(Y,G)=em(PePA)em(XPA)。若等式成立，則接受(X,Y)是A的簽名，否則拒絕。同理，B也可以采用同樣的方式進行簽名。A收到后，同樣進行驗證簽名。

3 安全性分析

本數(shù)字簽名方案是基于橢圓曲線離散對數(shù)問題，同時結(jié)合BDH問題，以及ElGamal類加密體制和簽名方案而構(gòu)造的。就其安全性分析如下：

(1)由橢圓曲線密碼的基礎(chǔ)知識可知：在橢圓曲線中，當設(shè)Q=nP，P、Q∈E(F)，從n、P求Q存在有效的算法，而從P、Q求n沒有有效的算法，這個問題就稱為橢圓曲線離散對數(shù)問題。從而，增強了方案的安全性。另外，由于本簽名方案是基于橢圓曲線數(shù)字簽名體制的簽名方案，因此，具有橢圓曲線的特點：(i)安全性高，(ii)密鑰量小，(iii)存儲量小、傳輸時間短，(iv)靈活性好，只要有限域已定，其上的循環(huán)群就確定了等優(yōu)點。

(2)本簽名方案的安全性同時又基于雙線性Diffie-Hellman(BDH)問題：已知P、Q、R∈E(Fq)，求點S∈E(Fq)，使得等式em(S,P)=em(R,Q)成立。攻擊者想偽造簽名，相當于求解BDH問題，該問題目前還沒有有效的算法。因此，相信該問題是難以計算的。

(3)本簽名方案為了增強安全性沒有直接把明文m嵌入到橢圓曲線上，即點Pm，而是使用較為安全的Hash函數(shù)h(m)，然后嵌入到橢圓曲線上后再進行簽名。這樣把Hash函數(shù)應用于數(shù)字簽名中，從而也可以提高簽名的速度。

(4)另外，本方案沒有完全按照一般的ElGamal公鑰體制進行簽名。若簽名按照一般的ElGamal公鑰體制，其形式為：Sigk(Pm,k,dA)=(X,Y)，其中X=kG，Y=Pm+dAX。但是攻擊者可以用Y-Pm計算出dAX，然后用其他的消息得到P'm進行簽名：

X'←X，Y' ←P'm+(Y-Pm)

顯然，這樣的簽名可以通過驗證，于是簽名很容易被偽造了。本方案由于dA很難計算，也就很難偽造Y，從而增強了方案的安全性。

結(jié)束語

本文提出了基于Weil對的橢圓曲線數(shù)字簽名方案，并利用了ElGamal 型數(shù)字簽名規(guī)則，使其安全性基于離散對數(shù)的難解性和BDH問題的難解性，具有較高的安全性。同時，也為解決橢圓曲線上數(shù)字簽名的驗證提供了一種新的方法。

參考文獻：

[1]Harn . L. and Xu . Y. ,Design of generalized ElGamal type digital signature schemes based on discrete logarithm , Electron Lettt ,1994 ,30(24):2025 - 2026.

[2]趙云峰 等.一個基于Weil對的基于身份的群簽名方案[J]. 計算機應用研究，2005，(5):124-125.

[3]D JOHNSON,A MENEZES VANSTONE. The elliptic curve digital signature algorithm (ECDSA)[J].International Journal on Information Security,2001;(1):36-63.

[4]Dr Tsuyoshi Takagi. Efficient Algorithms for Pairing-Based Cryptosystems. Marcus Stogbauer, 2004-01.