改進(jìn)的橢圓曲線數(shù)字簽名方案及實(shí)例分析

楊 青 王昊軒 梁 磊 黃林飛

(西安航空學(xué)院理學(xué)院 陜西 西安 710077)

0 引 言

如今計(jì)算機(jī)科技的進(jìn)步相當(dāng)快，同時(shí)互聯(lián)網(wǎng)得到大量運(yùn)用，全球邁向信息化階段，人們借助公共網(wǎng)絡(luò)與信息平臺(tái)進(jìn)行交流，因此電子政務(wù)與電商，還有互聯(lián)網(wǎng)平臺(tái)同樣飛速進(jìn)步，逐步構(gòu)建信息分享平臺(tái)。然而個(gè)人與公司、國(guó)家等各方信息均需保密，例如銀行交易與公司財(cái)會(huì)，還有國(guó)家政治與軍事等信息。在信息安全系統(tǒng)的性能相對(duì)來說較低時(shí)，就很容易遇到侵略者，借助資源分享平臺(tái)來盜取關(guān)聯(lián)信息，以此獲取巨大的經(jīng)濟(jì)利益，對(duì)網(wǎng)絡(luò)安全形成不小的損害。因而由個(gè)人入手，保證信息的安全，已然變成如今工作的要點(diǎn)，也受到整個(gè)社會(huì)以及國(guó)家的高度重視。

數(shù)字簽名技術(shù)是網(wǎng)絡(luò)環(huán)境下的認(rèn)證技術(shù)，該簽名技術(shù)最早是由Diffie等[1]于1976年提出。在此之后，各類數(shù)字簽名方案相繼被提出，并得到了很大的發(fā)展和廣泛的應(yīng)用。然而，基于橢圓曲線的簽名算法相對(duì)于離散對(duì)數(shù)簽名算法擁有更高的安全性和高效性。Zhao等[2]給出了橢圓曲線認(rèn)證加密方案的構(gòu)造方法，方案具有消息恢復(fù)的功能。2017年， Chandrasekhar等[3]提出了使用代理簽名進(jìn)行基于云健康信息交換的訪問控制。Kumar等[4]提出了可證明安全的基于證書的代理盲簽名方案，該方案運(yùn)用了雙線性對(duì)。Kumar等[5]提出了一個(gè)無證書聚合簽名方案，并在隨機(jī)預(yù)言模型下證明方案的安全性。Xuan等[6]提出了一種新的數(shù)字簽名方案，該方案是基于求解根問題和一些擴(kuò)展根問題的困難性。根據(jù)不同的密碼體制，Shuai等[7]提出的方案采用Rabin密碼體制，避免了口令驗(yàn)證表的存在。Seo[8]提出的簽名方案是基于RSA密碼體制的，并在準(zhǔn)模型下驗(yàn)證該方案。根據(jù)不同的實(shí)際需求，學(xué)者們分別提出了各種數(shù)字簽名方案。比如，歐海文等[9]提出群簽名方案，李亞紅等[10]提出門限簽名，楊小東等[11]提出無證書簽名方案。本文仔細(xì)研讀并分析文獻(xiàn)[2,5,8-9]后提出改進(jìn)的基于橢圓曲線密碼體制的數(shù)字簽名方案，改進(jìn)的方案能夠防御生日攻擊，提高數(shù)字簽名的安全性能，而且運(yùn)算量不大。

1 數(shù)字簽名的模型

數(shù)字簽名方案的組成部分可以分為三個(gè)環(huán)節(jié)，分為系統(tǒng)初始化過程、簽名產(chǎn)生過程、簽名驗(yàn)證過程，下面就數(shù)字簽名的形式加以說明：

(1) 初始化過程。數(shù)字簽名產(chǎn)生過程中，涉及到基本參數(shù)的問題，為(M,S,K,Sig,Ver)其含義各不相同，按順序分別為消息集合、簽名集合、密鑰集合(PK為公鑰集合，SK為私鑰集合)。Sig代表的是簽名產(chǎn)生算法集合，Ver代表的是簽名驗(yàn)證算法集合。

(2) 簽名產(chǎn)生過程。K為密鑰集合，在對(duì)簽名進(jìn)行計(jì)算時(shí)，其算法為Sigsk∈Sig，Sigsk:M→S，m∈M作為任意消息，s=Sigsk，s∈S為消息m的簽名，將(m,s)發(fā)送給簽名驗(yàn)證者進(jìn)行驗(yàn)證。

(3) 簽名驗(yàn)證過程。以密鑰集合K為例，下式為相應(yīng)的簽名驗(yàn)證算法。

Verpk:M×S→{True,False}

Verpk(m,s)=True,s=Sigsk(m)

Verpk(m,s)=False,s≠Sigsk(m)

當(dāng)(m,s)被簽名驗(yàn)證者接收到后進(jìn)行計(jì)算，如果Verpk(m,s)=True，說明簽名是具有效力的，反之無效。

2 橢圓曲線數(shù)字簽名方案

橢圓曲線參數(shù)的含義如表1所示。

表1 橢圓曲線參數(shù)的含義

2.1 Zhao等[2]的數(shù)字簽名方案

Zhao等[2]給出了一個(gè)基于橢圓曲線密碼體制的具有消息恢復(fù)功能的認(rèn)證加密方案，該方案由以下幾個(gè)過程組成，分別為初始化過程、簽名的產(chǎn)生過程、驗(yàn)證簽名和消息恢復(fù)。

1) 初始化過程。用戶A的私鑰為KA，對(duì)應(yīng)公鑰為PA=KAG；用戶B的私鑰為KB，對(duì)應(yīng)公鑰為PB=KBG。

2) 簽名的產(chǎn)生。

(2)A計(jì)算R=KPB=(x,y),r=h(x)-1m(modn)，若r=0則返回(1)。

(3) 計(jì)算s=K+rKA(modn)，若s=0，則返回(1)。

(4) 消息m的簽名：(r,s)。

3) 驗(yàn)證簽名和消息恢復(fù)。B接收到簽名(r,s)，下載域參數(shù)及A的公鑰，并進(jìn)行計(jì)算。

(1) 檢驗(yàn)r、s是否在區(qū)間[1,n-1]上，如果不在此區(qū)間則拒絕簽名。

(2) 計(jì)算X=sG-rPA=(x′,y′)和m=h(KBx′)r(modn)為消息恢復(fù)方程。

(3) 若X=0，B拒絕接受簽名，否則B計(jì)算原始消息m,并對(duì)消息進(jìn)行檢驗(yàn)，如果正確，則接受簽名，反之拒絕。

在消息末尾加中冗余位被廣泛采用，其方法有多種，可以把參與者的身份進(jìn)行認(rèn)證，或采用被通信雙方指定的字符串，B擁有的私鑰是保密的，沒有人能夠?qū)ο⑦M(jìn)行恢復(fù)操作，也不可能知道消息是由誰發(fā)出的，但是B有此權(quán)限，能夠?qū)υ枷⑦M(jìn)行計(jì)算，掌握與之通信人的資料。

文獻(xiàn)[2]給出的簽名方程ak=b+ckAmodn，未知向量(a,b,c)是向量(±r,±s,±1)、(±1,±1,±sr)、(±1,±s,±sr)和(±1,±r,±sr)的任何一個(gè)排列，分別有24、12、24和24種。文獻(xiàn)[2]給出了其中主要的6種基本簽名方程和對(duì)應(yīng)消息恢復(fù)方程，如表2所示。

表2 簽名方程和消息恢復(fù)方程

續(xù)表2

2.2 改進(jìn)的基于橢圓曲線的數(shù)字簽名方案

橢圓曲線參數(shù)定義如表1所示，以下為改進(jìn)方案的具體算法：

1) 初始化過程。用戶A的兩個(gè)不同私鑰分別為KA1,KA2，其中KA1,KA2∈Zn,KA1≠KA2；用戶A的兩個(gè)對(duì)應(yīng)公鑰分別為PA1=KA1G,PA2=KA2G。

用戶B的私鑰為KB∈Zn，對(duì)應(yīng)的公鑰為PB=KBG。

2) 簽名的產(chǎn)生過程。

(2)A計(jì)算R=(K1+K2)PB=(x,y)，r=h(x)-1m(modn)若r=0，則返回(1)。

(3)A再計(jì)算s1=K1+rKA1(modn),s2=K2+rKA2(modn),若s1=0或s2=0，則返回(1)。

(4) 以(r,s1,s2)作為A對(duì)消息m的簽名。

3) 消息確認(rèn)和簽名驗(yàn)證過程。簽名(r,s1,s2)被傳給B，需要進(jìn)行驗(yàn)證簽名，B獲取橢圓曲線的各個(gè)參數(shù)及A的公鑰，并計(jì)算：

(1) 進(jìn)行檢驗(yàn)，確定r、s1、s2在 區(qū)間[1,n-1]上，如果沒有在此區(qū)間之上，B可以做出拒絕簽名的決定。

(2)B計(jì)算X=s1G+s2G-rPA1-rPA2=(x′,y′)和m=h(KBx′)r(modn)，KBx′為KBX的橫坐標(biāo)。

(3) 若X=0，那么B有不接受簽名的權(quán)利。否則，B可以對(duì)原始消息進(jìn)行計(jì)算，獲取消息末尾數(shù)據(jù)，并對(duì)身份的冗余位進(jìn)行確認(rèn)，如果確認(rèn)無誤，B可以接受簽名，反之拒絕。

此簽名體制是否具有正確性，需要下式來證明：

R=(K1+K2)PB=(K1+K2)KBG=

KB(K1+K2)G=

KB(s1G+s2G-rPA1-rPA2)=

KB(x′,y′)

m=h(KBx′)r(modn)

X=s1G+s2G-rPA1-rPA2=

K1G+rKA1G+K2G+rKA2G-r(KA1+KA2)G=

K1G+K2G=(K1+K2)G=(x′,y′)

類似地，針對(duì)表2本文還給出主要的6種改進(jìn)的算法，簽名方程和消息恢復(fù)方程如表3所示，其中KBx′為KB(x′,y′)的橫坐標(biāo)。

表3 改進(jìn)的簽名方程和消息恢復(fù)方程

2.3 數(shù)字簽名方案的安全性和復(fù)雜度分析

在此僅對(duì)第一種方案進(jìn)行分析，其他6種算法類似，具體分析如下：

1) 若攻擊者想對(duì)改進(jìn)的簽名方案攻擊，利用Fq上求解方程dG=Q(modq)或d=logGQ(modq)。與有限域上的DLP相比，ECDLP的難度更大。在目前所采用的方法中，目前有兩種方法能夠達(dá)到較為理想的效果，一種方法是Pohlig-Hellman方法，另一種方法是Pollard-ρ方法。需要探討兩類特殊的橢圓曲線，可利用有效的方法：(1) 運(yùn)用概率亞指數(shù)算法，選取超奇異橢圓曲線，由于其具有特殊性，采用Mov算法以及FR算法，那么能夠予以解決ECDLP的問題；(2) 可以選取異常橢圓曲線，需要運(yùn)用SSSA算法，那么能夠解決ECDLP的問題。

3) 攻擊者為了達(dá)到目的而企圖冒充A，對(duì)消息m行使簽名權(quán)，在實(shí)際操作時(shí)，要隨機(jī)選取K1、K2計(jì)算R=(K1+K2)PB=(xR,yR),r=h(xR)-1m(modn),s1=K1+rKA1,s2=K2+rKA2，這需要解決橢圓曲線離散對(duì)數(shù)問題(ECDLP問題)由此可知，攻擊者冒充A產(chǎn)生有效簽名是不可行的。

4) 改進(jìn)方案與原方案的復(fù)雜度進(jìn)行比較，改進(jìn)方案初始化過程和簽名過程中遵循兩個(gè)密鑰的思想，改進(jìn)方案需要增加兩次橢圓曲線標(biāo)量乘運(yùn)算和一次模運(yùn)算，與橢圓曲線倍點(diǎn)乘運(yùn)算比較，大整數(shù)模運(yùn)算可以忽略，運(yùn)算量增加不大，但是改進(jìn)方案提高了安全性能。

3 MATLAB實(shí)例分析

實(shí)例如果簽名人C要對(duì)摘要N=1 234進(jìn)行簽名，設(shè)N的前三位所代表的是消息，最后一位是消息冗余位。系統(tǒng)所選定的橢圓曲線為v2=u3+3u+45(mod 8 831)(如圖1所示)，基點(diǎn)Q=(4,11)，其階p=4 427。

圖1 橢圓曲線：v2=u3+3u+45

對(duì)數(shù)字簽名算法進(jìn)行實(shí)例分析，根據(jù)已知條件，計(jì)算如下：

1) 系統(tǒng)的初始化。簽名人C的私鑰為：KC1=113,KC2=225。

簽名人C對(duì)應(yīng)的公鑰分別為：

PC1=KC1Q=(5 908,4 180)

PC2=KC2Q=(1 086,7 000)

驗(yàn)證簽名人D的私鑰為：KD=221。

驗(yàn)證簽名人D的公鑰為：

PD=KDQ=(3 829,4 859)。

2) 簽名人C對(duì)消息摘要N產(chǎn)生簽名過程。

(1) 簽名人C選擇兩個(gè)隨機(jī)數(shù)，分別為：t1=152,t2=284,然后計(jì)算M′=t1Q+t2Q=(459,7 517)。

(2) 簽名人C計(jì)算：

M=(t1PD+t2PD)=(974,7 560)=(u,v)

e=H(u)-1N(mod4 427)=

H(974)-1×1 234=1 383

(3) 簽名人C接著計(jì)算：

sig1=t1+eKC1(mod 4 427)=1 486

sig2=t2+eKC2(mod 4 427)=1 569

(4) 可得到簽名人C對(duì)消息摘要N的簽名為(e,sig1,sig2)=(1 383,1 486,1 569)，然后簽名人C將簽名(e,sig1,sig2)=(1 383,1 486,1 569)發(fā)送給驗(yàn)證人D。

3)D作為簽名驗(yàn)證人，對(duì)消息摘要N的恢復(fù)和驗(yàn)證。首先,D收到簽名(e,sig1,sig2)=(1 383,1 486,1 569)，需要進(jìn)行下載操作，獲取域參數(shù)和C的公鑰，并進(jìn)行如下計(jì)算：

(1) 簽名人D首先對(duì)簽名進(jìn)行檢驗(yàn)，驗(yàn)證(e,sig1,sig2)=(1 383,1 486,1 569) 的每個(gè)分量值是否在區(qū)間[1,4 426]上。若否，則該簽名無效；若是，則進(jìn)行步驟(2)的運(yùn)算。

(2) 簽名人D接著計(jì)算U=sig1Q+sig2Q-ePC1-ePC2=(u′,v′)=(8 811,6 607)和N=H(KDu′)e(mod 4 427)=1 234。其中KDu′為KDU的橫向坐標(biāo)值。

(3) 簽名人D經(jīng)過計(jì)算可得，原始消息摘要N=1 234，并檢驗(yàn)消息N的最后一位冗余位值為4。結(jié)果正確，所以簽名人D驗(yàn)證簽名有效。

4 結(jié) 語

本文對(duì)已有文獻(xiàn)的數(shù)字簽名方案的安全性和復(fù)雜度進(jìn)行分析，提出改進(jìn)的基于橢圓曲線的數(shù)字簽名方案，

該方案可以有效抵抗生日攻擊，并對(duì)方案進(jìn)行安全性分析和運(yùn)算量分析，最后通過MATLAB實(shí)例進(jìn)行仿真驗(yàn)證，改進(jìn)方案運(yùn)算量低，并易于實(shí)現(xiàn)。