基於橢圓曲線的數字簽名方案，也稱為橢圓曲線數字簽名算法。橢圓曲線數字簽名方案是DSA算法在橢圓曲線上的模擬，只是群元素由素域中的元素數換位有限域上橢圓曲線上的點。

橢圓曲線數字簽名算法的安全性

橢圓曲線密碼體制的安全性是基於橢圓曲線離散對數難題的。與整數因子分解問題和模P的離散對數問題一樣,现在還沒有對橢圓曲線離散對數問題的有效解法,所以本方案是安全的。橢圓曲線公鑰密碼體制(ECC)的安全性依賴於橢圓曲線離散對數問題的困難性。

橢圓曲線數字簽名算法的應用

橢圓曲線數字簽名算法具有計算參數更小、密鑰更短、安全強度更高、運算速度更快、簽名也更加短小、軟硬件實現節省資源等特點,尤其適用於處理能力、存儲空間、帶寬及功耗受限的場合。

橢圓曲線數字簽名算法的不足之處

(1)在 橢圓曲線數字簽名算法的簽名和驗證算法中,都含有求逆運算,這種運算複雜而費時。一般對一個大整數求逆,若是採用擴展歐幾里德算法來求逆,平均需完成0.8413log2n+1.47次除法,運算是很慢的。

 (2)由簽名算法中s=k-1(e+rx)mod q可以知道,在生成簽名時必須要求k的逆,所以,在這裏對進行秘密分享,即密鑰分割和合成都是很困難的,也就很難直接運用於群簽名和門限簽名方案中。

2)改進的橢圓曲線數字簽名算法

鑒於 橢圓曲線數字簽名算法存在的上述不足之處,提出了一種改進的去逆的橢圓曲線數字簽名方案,下面將這個方案完整地敘述如下:

設橢圓曲線公鑰密碼系統參數為(Fq,E,G,P,q,a,b,h),其中, Fq是有限域;E是Fq上的橢圓曲線;G是E上的q階生成元(q為一大素數),稱為基點;a、b是橢圓曲線E的係數;P為橢圓曲線上的點;h是一個單向安全的哈希函數。

假設用戶A要對信息m作數字簽名發送給B(Bob),則簽名過程如下:

1)簽名者密鑰對的生成

(1)簽名方A隨機選擇一個整數x(1≤x≤q-1)作為私鑰,即簽名者的密鑰為SK={x}。

(2)計算簽名方A的公鑰y=xG,即簽名者的初始公鑰PK={y}。

(3)由以上兩步可以得到簽名方A的簽名密鑰和公鑰對為(SK,PK),其中SK={x}，PK={y}。

2)簽名過程

簽名方A隨機選取一個整數k(1≤k≤q-1),計算:P=KG=(u, v), r=u mod q

(2)m為消息,計算e=h(m)

(3)計算s=k-erx

(4)以(r,s)作為簽名方A對消息m的簽名發送給驗證方B

3)驗證過程

(1)驗證方B計算e=h(m)。

(2)P’=(u’,v’)=sG+ery

(3)如果P’=0則驗證方B拒絕這個簽名;否則計算r’= u’ mod q,若r’=r,則接收這個簽名。

只有簽名方A才知道他的私鑰x,對於任何第三者要假冒簽名方A的簽名,或更改經簽名方A簽名後的消息,都是難以顺利获得驗證的。同樣簽名方A對消息簽名後,也是不能否認的。

4)該方案的有效性證明

因為

P’=(u’, v’)

=sG+ery

=sG+erxG

=(s+erx)G

=(k-erx+erx)G

又因為:

P=kG=(u, v)

所以

P’=P, u’=u,r’=r

故該方案是正確的、有效的。

5)方案的分析及安全性證明顯然,該方案的安全性與 ECDSA的安全性相同,都依賴於由G和kG求解k的難度。它基於橢圓曲線離散對數難題。由於现在還沒有對橢圓曲線離散對數問題的有效解法,所以本方案是安全的。