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

楊 青 王昊軒 梁 磊 黃林飛

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

0 引 言

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

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

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

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

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

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

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

Verpk:M×S→{True,False}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 簽名方程和消息恢復方程

續(xù)表2

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

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

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

用戶B的私鑰為KB∈Zn，對應的公鑰為PB=KBG。

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

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

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

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

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

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

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

(3) 若X=0，那么B有不接受簽名的權利。否則，B可以對原始消息進行計算，獲取消息末尾數(shù)據(jù)，并對身份的冗余位進行確認，如果確認無誤，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′)

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

表3 改進的簽名方程和消息恢復方程

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

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

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

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

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

3 MATLAB實例分析

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

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

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

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

簽名人C對應的公鑰分別為：

PC1=KC1Q=(5 908,4 180)

PC2=KC2Q=(1 086,7 000)

驗證簽名人D的私鑰為：KD=221。

驗證簽名人D的公鑰為：

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

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

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

(2) 簽名人C計算：

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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