一種橢圓曲線消息恢復數(shù)字簽名方案的分析與改進

周克元

(宿遷學院二系，江蘇宿遷　223800)

?

一種橢圓曲線消息恢復數(shù)字簽名方案的分析與改進

周克元

(宿遷學院二系，江蘇宿遷223800)

對Zhang等提出的橢圓曲線消息恢復數(shù)字簽名方案進行了分析,指出其驗證方程存在錯誤,且方案無前向安全性,同時任意第三方可恢復消息.給出了一種改進方案,證明了改進方案具有抗偽造簽名攻擊、前向安全性、公開驗證性和指定接收者消息恢復等性質(zhì)，并對復雜度進行了分析.

橢圓曲線;數(shù)字簽名;消息恢復;前向安全;消息替換攻擊

Diffie等[1]于1976年提出數(shù)字簽名后,數(shù)字簽名得到了很大的發(fā)展和廣泛的應用,各類數(shù)字簽名方案相繼被提出.橢圓曲線簽名算法相對于離散對數(shù)簽名算法擁有更高的安全性,對于基于身份的橢圓曲線數(shù)字簽名方案,為進一步提高安全性,有的簽名方案在使用雙密鑰的同時又使用了雙參數(shù)設(shè)計簽名方案.Zhang等[2]給出了一種基于橢圓曲線的消息恢復數(shù)字簽名方案,但該方案存在錯誤,且可被攻擊,文中指出了方案的錯誤并給出一個改進方案.

1　Zhang方案

1.1參數(shù)設(shè)置

設(shè)橢圓曲線參數(shù)D=(q,FR,a,b,G,n,h),其中,q為某個素數(shù)冪;FR指出Fq中元素的表示方法;a,b∈Fq為橢圓曲線系數(shù);G為橢圓曲線的基點;n為點G的階,即nG=0，要求n為素數(shù);h為n關(guān)于#E(Fq)(橢圓曲線的階)的協(xié)因子,即h=#E(Fq)/n.用戶A選取私鑰cA1,cA2∈{1,2,…,n-1},且cA1≠cA2,公鑰DA1=cA1P,DA2=cA2P.用戶B選取私鑰cB∈{1,2,…,n-1},公鑰DB=cBP.待簽名消息為m(m

1.2簽名過程

1)用戶A任取k1,k2∈{1,2,…,n-1}；

2)計算R=(x1,y1)=(k1+k2)DB, r=mh-1(x1)modn;

3)計算s1=(k1+rcA1)modn, s2=(k2+rcA2)modn.

消息m的簽名為(r,s1,s2).

1.3消息恢復及驗證

1)接收者B下載發(fā)送者A的公鑰DA1,DA2；

2)檢查r,s1,s2是否屬于{1,2,…,n-1},錯誤則拒絕簽名；

3)計算X=(x2,y2)=s1P+s2P-rDA1-rDA2,m′=rh(cBx2) modn；

4)若X=0，則簽名錯誤；否則，B恢復出消息明文m并檢查附在m后的冗余信息,如果冗余信息正確，則B接受簽名,否則拒絕.

2　Zhang方案安全性分析

2.1驗證方程的錯誤分析

Zhang方案驗證中m′=rh(cBx2)modn有誤.方案希望cBx2=x1,但cB(x2,y2)=(x1,y1)不等價于cBx2=x1, cBy2=y1.可將上述1.3節(jié)中步驟3)更改為：計算X=(x2,y2)=s1P+s2P-rDA1-rDA2, cBX=(x3,y3), m′=rh(x3)modn.

2.2前向安全性分析

前向安全概念由Anderson于1997年首次提出[3],其思想是:如果簽名者的私鑰泄露，不會對之前的簽名造成影響,即根據(jù)私鑰無法恢復出消息明文.具有前向安全的橢圓曲線數(shù)字簽名見文獻[4-13].

Zhang方案中,若簽名者的私鑰cA1,cA2被泄露,攻擊者截取簽名(r,s1,s2)后,可由s1=(k1+rcA1) modn,s2=(k2+rcA2) modn計算出隨機數(shù)k1,k2,則可計算出(k1+k2)DB=(x1,y1),進而可計算出消息m=rh(x1) modn,即此方案無前向安全性.

2.3第三方可恢復消息

簽名者若否認簽名,則接收者需要將解密后的簽名提供給第三方進行驗證,以揭示簽名者的抵賴.方案中驗證過程不需要使用接收者的私鑰,任何第三方都可以進行驗證,但由于消息恢復不需要接收者的私鑰,第三方也可以恢復消息m,從而知道消息m中的內(nèi)容,故方案公開驗證時不具有消息機密性.

3　改進的簽名方案

在保留Zhang方案使用雙私鑰、雙參數(shù)的情況下,給出一個改進的簽名方案,具有前向安全性、指定接收者消息恢復、第三方驗證功能等性質(zhì).

3.1參數(shù)設(shè)置

參數(shù)設(shè)置同Zhang方案.

3.2簽名過程

1)用戶A任取k1,k2∈{1,2,…,n-1};

2)計算(k1+k2)DB=(x1,y1),r1=mh-1(x1) modn, (k1+k2)P=R,h(m)R=(x2,y2),r2=x2modn;

3)計算s1=(h(m)k1+r1cA1) modn,s2=(h(m)k2+r2cA2) modn.

消息m的簽名為(r1,r2,s1,s2,R).

3.3消息恢復及驗證

1)接收者B下載發(fā)送者A的公鑰DA1,DA2;

2)檢查r1,r2,s1,s2∈{1,2,…,n-1},錯誤則拒絕簽名；

3)計算X=(x′,y′)=(s1+s2)P-r1(DA1+DA2),r′=x′modn,驗證r′=r2是否成立；

4)計算cBR=(x″,y″),消息恢復m′=r1h(x″)modn；

若r′=r2成立且消息恢復m′有意義,則接受簽名且m′=m,否則拒絕簽名.

3.4正確性證明

因為X=(x′,y′)=s1P+s2P-rDA1-rDA2=h(m)(k1+k2)P,所以x′=x2,r′=r2.

因為(x″,y″)=cBR=cB(k1+k2)P=(k1+k2)DB=(x1,y1),所以x″=x1,m′=r1h(x″) modn=r1h(x1) modn=m.

4　改進方案的安全性及復雜度分析

4.1抗私鑰攻擊

攻擊者截取簽名(r1,r2,s1,s2,R)后,攻擊者不知接收者的密鑰cB,無法求出cBR,則無法恢復消息m.而由DB=cBP求解私鑰cB需要求解橢圓曲線離散對數(shù)問題.

4.2前向安全性

改進方案中,若簽名者的私鑰cA1,cA2被泄露,攻擊者截取簽名(r1,r2,s1,s2,R)后,因無法通過計算私鑰cB方式恢復消息m,故無法求出h(m),則由s1=(h(m)k1+rcA1) modn,s2=(h(m)k2+rcA2) modn不能計算出隨機數(shù)k1,k2,從而無法由(k1+k2)DB=(x1,y1),r1=mh-1(x1) modn恢復出消息m.對文中改進方案而言，即使密鑰泄漏,已有的簽名也無法攻擊,所以改進方案的前向安全性為絕對前向安全,比前述定期更換密鑰具有的前向安全性更優(yōu).

4.3抗抵賴

簽名者如果想抵賴簽名,接收者可以把簽名(r1,r2,s1,s2,R)提供給第三方,第三方可通過驗證方程驗證簽名的正確性,防止簽名者抵賴.驗證過程不需要簽名者的協(xié)助,也不需要提供恢復的消息.另外,在驗證過程中,因不知接收者的私鑰cB,第三方無法恢復出消息m,方案具有保密性.如有必要,接收方可提供私鑰cB恢復消息m.

此外,驗證者要想更改密鑰cB以恢復出對自己有利的消息也是不可行的.設(shè)驗證者希望恢復出對自己有利的消息為m,由m=r1h(x″)modn求出x″需求解單向函數(shù)問題,由cBR=(x″,y″)求解cB需求解橢圓曲線離散對數(shù)問題.

4.4抗偽造簽名攻擊

攻擊者截取簽名(r1,r2,s1,s2,R)后,隨機選取橢圓曲線中點R′,組成(r1,r2,s1,s2,R′)發(fā)送給驗證者,由3.3節(jié)驗證過程,驗證者可以驗證r′=r2的正確性,進一步設(shè)cBR′=(x?,y?),驗證者計算m=r1h(x?) modn,則m為無意義的亂碼,由3.3節(jié)則接收者拒絕簽名.

另外,若攻擊者事先選定某對其有利的消息m,若要滿足驗證條件需求出對應的x″,y″,R.由方程m=r1h(x″) modn求x″需求解Hash函數(shù);(x″,y″)滿足二次同余方程

y2=(x3+ax+b) modp,

由x″求解y″需求解該同余方程;由cBR=(x″,y″)求R需要求解出橢圓曲線離散對數(shù)雙數(shù)學難題.

綜上所述,該方案可抵抗攻擊者偽造簽名攻擊.

4.5復雜度與安全性分析

對于基于橢圓曲線設(shè)計消息恢復數(shù)字簽名,Yang等[14]于2011年提出了一個方案,但該方案沒有前向安全性.同時具有前向安全性和公開驗證消息機密性的方案,目前還沒查到相關(guān)的文獻.將文中方案與Yang方案進行復雜度對比,見表1.

表1　復雜度對比

[1]DIFFIEW,HELLMANM.Newdirectionincryptography[J].IEEE Transactions on Information Theory,1976,22(6):644.

[2]ZHANGYun-peng,CHENTong,ZHANGXian-wei,etal.Improveddigitalsignatureschemebasedonellipticcurve[J].Research Journal of Applied Sciences,Engineering and Technology,2012,4(18):3437.

[3]ANDERSONR.Tworemarksonpublickeycryptology[J].Computer and Communication Security,1997,19(9):128.

[4]張曉敏,張建中.基于橢圓曲線的前向安全代理簽名方案[J].濟南大學學報(自然科學版),2008,22(3):263.

[5]詹雄泉,洪景新.基于橢圓曲線密碼體制的一種具有前向安全的數(shù)字簽名方案[J].廈門大學學報(自然科學版),2005,44(2):189.

[6]付茂盛,任哲,侯整風.基于ECC的前向安全數(shù)字簽名的研究與改進[J].計算機工程,2006,32(14):109.

[7]龐倩倩,辛小龍.兩種具有前向安全的數(shù)字簽名的改進方案[J].計算機工程與應用,2008,44(30):102.

[8]褚晶晶,何琪芬,張慧.前向安全的由指定接收者恢復消息的簽名方案[J].杭州師范大學學報(自然科學版),2010,9(5): 335.

[9]徐光寶,姜東煥,梁向前.一種強前向安全的數(shù)字簽名方案[J].計算機工程,2013,39(9):167.

[10]胡江紅.一類前向安全簽名方案的安全性分析[J].電子設(shè)計工程,2015,23(14):23.

[11]曹欣,魏仕民,卓澤朋.三個前向安全代理簽名方案的安全性分析[J].計算機工程與應用,2015,51(7):98.

[12]戚明平,陳建華,何德彪.具有前向安全性的可公開驗證的簽密方案[J].計算機應用研究,31(10):3093.

[13]陳寧宇,樓俊剛.一個基于身份的前向安全代理簽名的安全分析與改進[J].計算機應用與軟件,2014,31(8):295.

[14]楊迎輝,任俊峰,袁喜鳳.改進的具有消息恢復簽名方案[J].計算機技術(shù)與發(fā)展,2011,21(4):168.

(責任編輯惠松騏)

Attack analysis and improvement on a digital signature algorithm with message recovery

ZHOU Ke-yuan

(The Second Department,Suqian College,Suqian 223800,Jiangsu,China)

The digital signature algorithm with message recovery proposed by Zhang Yun-peng et al is analyzed,two errors are pointed out,the algorithm didn’t have the forward security,and one can recover message.An improvement algorithm is proposed,the correctness,security are proved.

discrete logarithm;elliptic curve;digital signature;message recovery;replacement message attack

10.16783/j.cnki.nwnuz.2016.04.009

2015-06-06;修改稿收到日期:2015-09-29

宿遷市科研項目(Z201450)

周克元(1978—)，男，江蘇淮安人，講師，碩士.主要研究方向為密碼學.

E-mail:zhoukeyuan2001@163.com

TP 309.7；TN 918.1

A

1001-988Ⅹ(2016)04-0038-03