基于橢圓曲線的數(shù)字簽名加解密技術(shù)的研究

[摘要] 本文在分析了現(xiàn)行數(shù)字簽名（PKI）的缺陷的基礎(chǔ)上，提出基于橢圓曲線的數(shù)字簽名加解密技術(shù)的數(shù)字簽名體制。該方案是基于橢圓曲線離散對(duì)數(shù)問(wèn)題的難解性，大大增強(qiáng)了攻擊難度和提高了簽名的效率，極大地提高了數(shù)字簽名體制的安全性。

[關(guān)鍵詞] 數(shù)字簽名用戶密鑰橢圓曲線公鑰密碼離散對(duì)數(shù)

一、引言

數(shù)字簽名用于鑒定簽名人的身份以及對(duì)一項(xiàng)電子數(shù)據(jù)內(nèi)容的認(rèn)可。它還能驗(yàn)證出文件的原文在傳輸過(guò)程中有無(wú)變動(dòng)，確保傳輸電子文件的完整性、真實(shí)性和不可抵賴性。隨著計(jì)算機(jī)網(wǎng)絡(luò)的飛速發(fā)展和迅速普及，數(shù)字簽名系統(tǒng)密鑰的安全性和數(shù)字簽名的有效性，一直是國(guó)內(nèi)外研究人員的研究熱點(diǎn)?，F(xiàn)行數(shù)字簽名的加解密技術(shù)絕大多數(shù)采用的是20世紀(jì)80年代由美國(guó)學(xué)者提出的公鑰基礎(chǔ)設(shè)施（PKI）。PKI是一種利用非對(duì)稱密碼算法(RSA算法，即公開密鑰算法)原理和技術(shù)來(lái)實(shí)現(xiàn)的。然而近年來(lái)的研究表明，512位模長(zhǎng)的RSA已經(jīng)被攻破，為了保證安全性。RSA不得不采用更長(zhǎng)的密鑰，這將降低RSA系統(tǒng)的運(yùn)行速度。橢圓曲線密碼系統(tǒng)(ECC)比RSA等其他公鑰加密系統(tǒng)能提供更好的加密強(qiáng)度、更快的執(zhí)行速度和更小的密鑰長(zhǎng)度。這些性能使得橢圓曲線密碼系統(tǒng)能用較小的開銷和時(shí)延實(shí)現(xiàn)較高的安全性，特別能滿足在帶寬、計(jì)算能力或存儲(chǔ)能力等受限的各種特殊應(yīng)用場(chǎng)合。基于橢圓曲線的數(shù)字簽名已成為目前數(shù)字簽名技術(shù)的研究熱點(diǎn)。本文對(duì)基于橢圓曲線的數(shù)字簽名加解密實(shí)現(xiàn)技術(shù)進(jìn)行研究。

二、基于橢圓曲線的數(shù)字簽名加解密技術(shù)簡(jiǎn)介

基于橢圓曲線的數(shù)字簽名加解密技術(shù)是建立在有限域上的橢圓曲線基礎(chǔ)上。所謂有限域Fq上的橢圓曲線是在仿射平面A2k上滿足Weierastrass方程的平滑曲線:y2+a1xy+a3y=x3+a2x2+a4x+a6

也就是該方程的解及無(wú)窮遠(yuǎn)點(diǎn)O的集合，其中ai∈Fq(i=1，2，3，…，6)。把該橢圓曲線表示為E，橢圓曲線上的所有點(diǎn)組成一個(gè) Abel群，用#E(Fq)來(lái)表示。橢圓曲線密碼系統(tǒng)就建立在這個(gè)有限群上。有限域Fq上的橢圓曲線的點(diǎn)的加法法則是:

已知橢圓曲線E上的兩點(diǎn)P、Q，其中P=(xP，yP)，Q=(xQ，yQ)，且P≠-Q，設(shè)λ是P、Q所確定的直線的斜率，當(dāng)P≠Q(mào)時(shí)，有;當(dāng) P=Q時(shí)，有，令R=P+Q=(xP+Q，yP+Q)，可知R也是橢圓曲線E上的點(diǎn)，其中有

這時(shí)點(diǎn)P的逆-P=(xP，-yP)。

三、橢圓曲線的數(shù)字簽名加解密算法實(shí)現(xiàn)

1.系統(tǒng)的建立和密鑰生成

（1)系統(tǒng)的建立

選取一個(gè)基域Fq，在Fq上隨機(jī)尋找一條階含有大素?cái)?shù)因子的隨機(jī)橢圓曲線E及E上階為素?cái)?shù)n的基點(diǎn)G=(xG，yG)，a，b是橢圓曲線E的參數(shù)。則我們已經(jīng)建立了橢圓曲線公鑰密碼系統(tǒng)，系統(tǒng)參數(shù)為(Fq，G，n，a，b)。

（2)密鑰的生成

系統(tǒng)建成后，每個(gè)用戶各自產(chǎn)生自己的密鑰:

①用戶A隨機(jī)選取一個(gè)整數(shù)d，其中1≤d≤n-1；

②然后計(jì)算:Q=dG，如果Q是無(wú)窮遠(yuǎn)點(diǎn)或G，則需重新選擇d;

③將d作為私鑰保存，Q作為公開密鑰公開。

2.數(shù)字簽名的加密過(guò)程

假設(shè)用戶B要把數(shù)字簽名信息m發(fā)送給用戶A，則用戶B首先將信息原文用哈希算法求得數(shù)字摘要，然后進(jìn)行如下操作：

(1)用戶B找出A的公鑰Q，然后隨機(jī)選取一個(gè)整數(shù)k，其中1≤k≤n-1，計(jì)算P=kG=(x1，y1);

(2)計(jì)算:kQ=(x2，y2);

(3)計(jì)算:c=mx2;

(4)最后把生成的數(shù)字簽名(P，c)發(fā)送給用戶A。

3.數(shù)字簽名的解密過(guò)程

當(dāng)用戶A收到B發(fā)送來(lái)的數(shù)字簽名(P，c)后，用自己的私鑰d進(jìn)行如下解密操作：

(1)用戶A計(jì)算:dP=(x2，y2)，因?yàn)閐P=d(kG)=dkG=k(dG)=kQ=(x2，y2);

(2)然后計(jì)算:m=cx-12 ;從而恢復(fù)出數(shù)字簽名信息m。

四、橢圓曲線的數(shù)字簽名加解密算法分析

橢圓曲線公鑰密碼是基于橢圓曲線離散對(duì)數(shù)問(wèn)題的難解性，即在有限域Fq上，已知P、Q在橢圓曲線E上的有理點(diǎn)，要尋找一個(gè)d∈Fq，使得Q=dP，這是很難解的。從上面算法可知，在解密過(guò)程中，要求出x2-1，必須知道x2，而要知道x2，必須知道dP，或者必須知道kQ，而知道G、Q、P，要求出用戶A的私鑰d或隨機(jī)整數(shù)k，這相當(dāng)于求解橢圓曲線離散對(duì)數(shù)問(wèn)題，就現(xiàn)有的計(jì)算技術(shù)和能力來(lái)說(shuō)，如果橢圓曲線公鑰密碼系統(tǒng)中的橢圓曲線是隨機(jī)選取的，而且它的階包含有大素?cái)?shù)因子，那么這是一個(gè)很難的問(wèn)題。也就是必須求逆運(yùn)算，這是一個(gè)很費(fèi)時(shí)和復(fù)雜的過(guò)程。

五、結(jié)語(yǔ)

該方案的簽名過(guò)程比EC-DSA或EC-ElGamal少計(jì)算一次有限域元素的逆，而在Fq中求元素的逆需要使用EEA，該算法的執(zhí)行時(shí)間比模乘算法快80多倍，而簽名過(guò)程需要的時(shí)間比模乘快700多倍，因此該協(xié)議在簽名速度上將比EC-DSA或EC-ElGamal協(xié)議快大約10％，在密鑰生成部分該協(xié)議比EC-DSA和EC-Schnorr要簡(jiǎn)單。如果協(xié)議雙方用戶都嚴(yán)格履行協(xié)議，并且協(xié)議中隨機(jī)數(shù)和散列算法都是理想的，即使攻擊者獲得某個(gè)時(shí)期的密鑰并試圖偽造數(shù)字簽名信息m，由于C=mx2，攻擊者不知道x2，因此也不能計(jì)算出C。該方案較之文獻(xiàn)中的方案增強(qiáng)了安全性，在有效性方面也得到了進(jìn)一步保證，因此具有一定的理論價(jià)值和廣泛的應(yīng)用前景。

參考文獻(xiàn):

[1]J.Silverman. The Arithmetic of Ellipitc Curves[M].GTM106，Springer-Verlag，New York，1986

[2]周玉結(jié)馮登國(guó):公開密鑰密碼算法及其快速實(shí)現(xiàn)[M]. 國(guó)防工業(yè)出版社，2002

[3]白國(guó)強(qiáng)周濤陳宏毅:一類適合普通PC機(jī)實(shí)現(xiàn)的安全橢圓曲線[J].密碼學(xué)進(jìn)展2000，125-130

[4]D.Johnson， A.Menezes.The elliptic curve digital siguature algorithm ECDSA[R].Technical report CORR 99-31.Canada:Dept of CO，University of Waterloo，1999

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。