基于橢圓曲線的 ELGamal數字簽名方案

伍紅梅

(西南交通大學數學學院,四川 成都 610031)

基于橢圓曲線的 ELGamal數字簽名方案

伍紅梅

(西南交通大學數學學院,四川 成都 610031)

首先介紹了有限域上的橢圓曲線,把 ELGamal數字簽名體制成功的遷移到基于橢圓曲線的體制上,并在此基礎上,給出了兩個新的橢圓曲線 ELGamal數字簽名方案,提高了簽名的安全性,及其簽名的效率。

橢圓曲線;數字簽名;加密算法

1 引言

20世紀 80年代中期,Miller[1]和 Koblitz[2]將橢圓曲線引進了密碼學中,人們對其做了大量的研究工作后,建立了橢圓曲線公鑰密碼體制。它是一種基于橢圓曲線離散對數問題的公鑰密碼,并且具有很好的安全性。

橢圓曲線數字簽名技術在現代網絡數據通信處理過程中扮演著非常重要的角色,在網絡資源非常有限的情況下,如何提高網絡數據通訊效率及安全,提高簽名效率,就顯得尤為重要。文獻 [3]提出了橢圓曲線數字簽名算法,文獻 [4]給出了著名的橢圓曲線的數字簽名方案,文獻 [5]提出了 ELGamal數字簽名體制。本文把 ELGamal數字簽名體制成功的遷移到基于橢圓曲線的體制上,并在此基礎上,給出了兩個新的橢圓曲線 ELGamal數字簽名方案,提高了簽名的安全性及其效率。

2 有限域上的橢圓曲線[6]

(1)GF(p)上的橢圓曲線

GF(p)是一個特征為 p的有限域。p≠2,3。a,b∈GF(p)滿足 4a3+27b2≠0。橢圓曲線E(a,b)定義為滿足方程 y2=x3+ax+b的點 (x,y)∈GF(p)×GF(p)和無窮遠點O的集合。這些點在如下定義的加法下構成一個阿貝爾群,其恒等元為O。P和Q是 E(a,b)上的兩點,如果 P=O,則 -P=O,且P+Q=Q+P=Q;令P=(x1,y1),Q=(x2,y2)則 -P=(x1,-y1),P+(-P)=O如果Q≠-P,則 P+Q=(x3,y3),且

(2)GF(2m)上的橢圓曲線

非超奇異橢圓曲線 E(a,b)(GF(2m))定義為滿足方程 y2+xy=x3+ax2+b的點(x,y)∈GF(P)×GF(P)和無窮遠點O的集合,a,b∈GF(2m)且 b≠0,這些點在如下定義的加法下構成一個阿貝爾群,恒等元為O。P和Q是 E(a,b)(GF(2m))上的兩點,如果 P=O則 -P =O,且 P+Q=Q+P=Q;令 P=(x1,y1),Q=(x2,y2)則 -P=(x1,y1+x1),P+(-P) =O;如果Q≠-P,則 P+Q=(x3,y3),且

3 橢圓曲線數字簽名體制

3.1 橢圓曲線的 ELGam al數字簽名算法的參數

構造橢圓曲線 E(a,b)(GF(q)),選取一個基點G,階是 g,即 gG=O(其中 nG表示為 n個G相加,即 gG=G+G+G+…+G相加,O表示橢圓曲線方程的無窮遠點),n為素數,且 n> 3,在區間[1,n-1]中選擇一個隨機整數 d是簽名私鑰,Q=dG是簽名驗證公鑰,H是一個安全的 hash函數,公開 q,a,b,g,G,Q,H保密 d。

3.2 簽名生成

簽名者A lice利用上面的參數和公私鑰對消息m簽名:

(1)A lice隨機選擇一個整數 k使得 gcd(k,g)=1;

(2)計算 R=kG=(x1,y1),r=x1modn,如果 r=0則返回到第 (1)步;

(3)計算 k-1modn;

(4)計算 e=H(m);

(5)計算 s =k-1(e-dr)(m odn),如果 s =0則返回到第 (1)步;

(6)將數字簽名 s=(e,r,s)傳送給 B ob。

3.3 驗證過程

(1)B ob收到數字簽名 s=(e,r,s),并取得 A lice的公鑰 (E/Fq,G,Q);

(2)計算 e=H(m);

(3)計算V1=r Q+sR,V2=eG。

(4)若 V1=V2則驗收,否則拒絕。

證明:V1=V2:

V1=r Q+sR=rdG+k-1(e-dr)kG=(rd+e-dr)G=eG=V2 證畢

4 改進的橢圓曲線的 ELGam al數字簽名

4.1 方案一

橢圓曲線域參數跟前面介紹的相同,簽名過程:

簽名者A lice利用上面的參數和公私鑰對消息m簽名:

(1)A lice隨機選擇一個整數 k使得 gcd(k,g)=1;

(2)計算 R=kG=(x1,y1),r=x1m odn,如果 r=0則返回到第 (1)步;

(3)計算 e=H(m);

(4)計算 s =k+edr(m odn),如果 s =0則返回到第 (1)步;

(5)將數字簽名 s=(e,r,s)傳送給 B ob。

驗證過程

(1)B ob收到數字簽名 s=(e,r,s),并取得 A lice的公鑰 (E/Fq,G,Q);

(2)計算 e=H(m);

(3)計算V1=sG-R,V2=er Q。

(4)若 V1=V2則驗收,否則拒絕。

證明:V1=V2:V1=sG-R=(k+edr)G-R=kG+er Q-R=er Q=V2 證畢

4.2 方案二

橢圓曲線域參數跟前面介紹的相同,簽名過程:

簽名者A lice利用上面的參數和公私鑰對消息m簽名:

(1)A lice隨機選擇一個整數 k使得 gcd(k,g)=1;

(2)計算 e=H(m);

(3)計算 C1=kG=(x1,y1),r=x1m odn,如果 r=o則返回到第 (1)步;

(4)計算 kQ =(x2,y2),t=x2m odn,如果 t=0則返回到第 (1)步,C1=e+t;

(5)將數字簽名 s=(C1,C2),傳送給 B ob。

驗證過程

(1)B ob收到數字簽名;

(2)計算 e=H(m);

(3)計算 e=C2-dC1。

簽名驗證的證明:e=C2-dC1=e+kQ-dkG=e+kQ-kQ=e

5 結果分析

ELGam al算法其安全性是依賴計算有限域上離散對數問題的困難性,而把 ELGam al數字簽名體制遷移到基于橢圓曲線的體制上,其安全性是依賴橢圓曲線離散對數問題。攻擊者試圖通過分析(e,r,s)來取得簽名者的私鑰 d,是橢圓曲線上的離散對數問題求解,是困難的。

改進的兩個新方案,簽名和驗證過程中都不含有求逆運算,相對原來的方案提高了簽名的速度。顯然,該方案的安全性與原方案的安全性相同,都是基于橢圓曲線上的離散對數問題求解,但速度提高了很多。因為橢圓曲線密碼體制有著獨特的優越性,所以可被應用在需要較短密鑰的應用中。

[1]N Koblitz.Elliptic Curves Cryptosystems[J].M ath Comp.1987,48(177):203～209.

[2]V Miller.Usesof Elliptic Curves in Cryptography[A].Advance in Cryptology-CRYPTO,Lecture Notes in Computer Science[M]Springer-Vedag,1986:417～427.

[3]ANSI X9.62.Public Key Cryptography for the Financial Services Industry:The Elliptic CurvesDigital Signature Algorithm(ECDSA)[S].

[4]Johson D Menezes A.The elliptic curve digital signature algorithm [J].Technical Report,CORR99-31,Canada:Department of Combinatorics and Optim ization,University of W aterloo,1999.

[5]ELGamal L.A Public Key Cryptosystem and a Signture Scheme Base on Discrete Logarithm [J],IEEE Transactions on Infor m ation theory,1996,31:469—472.

(責任編輯 劉洪基)

ELGamalD igital Signature Scheme Based on the Elliptic Curves

W U Hong-mei
(School of M athematics,Southwest Jiaotong University,Chengdu610031,China)

The author introduced the elliptic curves over finite fields,put ELGamal digital signature scheme into a successfulmove to a system based on elliptic curve,And on this basis,ELGamal digital signature scheme of two new elliptic curves had been given to improve the security of the signature and the signature efficiency.

elliptic curve;digital signature;encryption

TP309

A

1671-7406(2010)03-0044-04

2010-01-05

伍紅梅 (1983—),女,籍貫四川,研究方向密碼學。