伍紅梅

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

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

伍紅梅

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

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

橢圓曲線;數(shù)字簽名;加密算法

1 引言

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

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

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

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

GF(p)是一個(gè)特征為 p的有限域。p≠2,3。a,b∈GF(p)滿足 4a3+27b2≠0。橢圓曲線E(a,b)定義為滿足方程 y2=x3+ax+b的點(diǎn) (x,y)∈GF(p)×GF(p)和無窮遠(yuǎn)點(diǎn)O的集合。這些點(diǎn)在如下定義的加法下構(gòu)成一個(gè)阿貝爾群,其恒等元為O。P和Q是 E(a,b)上的兩點(diǎn),如果 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的點(diǎn)(x,y)∈GF(P)×GF(P)和無窮遠(yuǎn)點(diǎn)O的集合,a,b∈GF(2m)且 b≠0,這些點(diǎn)在如下定義的加法下構(gòu)成一個(gè)阿貝爾群,恒等元為O。P和Q是 E(a,b)(GF(2m))上的兩點(diǎn),如果 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 橢圓曲線數(shù)字簽名體制

3.1 橢圓曲線的 ELGam al數(shù)字簽名算法的參數(shù)

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

3.2 簽名生成

簽名者A lice利用上面的參數(shù)和公私鑰對(duì)消息m簽名:

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

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

(3)計(jì)算 k-1modn;

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

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

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

3.3 驗(yàn)證過程

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

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

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

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

證明:V1=V2:

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

4 改進(jìn)的橢圓曲線的 ELGam al數(shù)字簽名

4.1 方案一

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

簽名者A lice利用上面的參數(shù)和公私鑰對(duì)消息m簽名:

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

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

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

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

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

驗(yàn)證過程

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

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

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

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

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

4.2 方案二

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

簽名者A lice利用上面的參數(shù)和公私鑰對(duì)消息m簽名:

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

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

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

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

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

驗(yàn)證過程

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

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

(3)計(jì)算 e=C2-dC1。

簽名驗(yàn)證的證明:e=C2-dC1=e+kQ-dkG=e+kQ-kQ=e

5 結(jié)果分析

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

改進(jìn)的兩個(gè)新方案,簽名和驗(yàn)證過程中都不含有求逆運(yùn)算,相對(duì)原來的方案提高了簽名的速度。顯然,該方案的安全性與原方案的安全性相同,都是基于橢圓曲線上的離散對(duì)數(shù)問題求解,但速度提高了很多。因?yàn)闄E圓曲線密碼體制有著獨(dú)特的優(yōu)越性,所以可被應(yīng)用在需要較短密鑰的應(yīng)用中。

[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.

(責(zé)任編輯 劉洪基)

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—),女,籍貫四川,研究方向密碼學(xué)。