橢圓曲線數(shù)字簽名的兩種改進(jìn)算法

李明株，劉瑞芹

(華北科技學(xué)院 理學(xué)院，北京 東燕郊 065201)

0 引言

上世紀(jì)九十年代，通用的是 RSA 公鑰密碼體制，密鑰長度一般為512bit。1999年RSA-512被破解，之后只能用加長密鑰保證信息的安全性，導(dǎo)致運(yùn)行速度更加緩慢。1985年，Koblitz[1]和Miller[2]提出將橢圓曲線用于公鑰密碼學(xué)的思想，標(biāo)志著橢圓曲線密碼體制(ECC，Elliptic Curve Cryptography)的誕生。ECC是建立在基于橢圓曲線上的點(diǎn)構(gòu)成的Abelian加法群的離散對數(shù)問題上的密碼體制。研究表明：基于有限域上橢圓曲線的離散對數(shù)問題運(yùn)算位數(shù)遠(yuǎn)小于傳統(tǒng)離散對數(shù)的運(yùn)算位數(shù)，它可以使用較短的密鑰達(dá)到較高的安全性，且計算速度快、存儲量小、帶寬要求低[3]。

數(shù)字簽名在網(wǎng)絡(luò)環(huán)境中可以代替?zhèn)鹘y(tǒng)手寫簽名或印章，是實(shí)體簽名的信息化實(shí)現(xiàn)。使用數(shù)字簽名技術(shù)能夠使得發(fā)送者事后不能否認(rèn)發(fā)送的簽名信息、接收者能夠核實(shí)但不能偽造或篡改發(fā)送者的簽名信息。數(shù)字簽名是提供身份認(rèn)證、確保信息完整性、不可偽造性、不可否認(rèn)性的重要信息技術(shù)。Jonhson和Menezes于1999年提出了基于橢圓曲線的數(shù)字簽名算法(ECDSA)。橢圓曲線數(shù)字簽名算法也成為目前研究的熱門問題[4-6]。

1 橢圓曲線密碼體制

1.1 有限域上的橢圓曲線

橢圓曲線密碼體制[7，8]的有效實(shí)現(xiàn)主要用到兩種類型的有限域，它們是素數(shù)域GF(p)和二元域GF(2)上的擴(kuò)域GF(2m)。

素數(shù)域GF(p)：設(shè)p是一個大素數(shù)，GF(p)={0，1，2…，p-1}。

二進(jìn)制擴(kuò)域GF(2m)：由二元域GF(2)上所有次數(shù)小于m的多項(xiàng)式組成，即：

GF(2m)={am-1xm-1+am-2xm-2+…a1x+a0}，ai={0,1}。

域元素(am-1xm-1+am-2xm-2+…+a1x+a0)通常用長度為m的二進(jìn)制串(am-1，am-2，…，a1，a0)表示，則GF(2m)={(am-1，am-2，…，a1，a0)},ai={0,1}。擴(kuò)域GF(2m)中包含2m個元素。

(1) 有限域GF(p)上的橢圓曲線是對于給定a,b(4a3+27b2)modp≠0，滿足方程：

y2=x3+ax+bmodp

的所有解(x,y)構(gòu)成的點(diǎn)集，外加無窮遠(yuǎn)點(diǎn)O構(gòu)成的一個群E(Fp)。其中a,b,x,y均在有限域GF(p)={0，1，2…，p-1}中取值，E(Fp)稱為橢圓曲線群。

(2) 有限域GF(2m)上的橢圓曲線滿足方程：y2+xy=x3+ax2+b

的所有解(x,y)構(gòu)成的點(diǎn)集，外加無窮遠(yuǎn)點(diǎn)O構(gòu)成一個橢圓曲線群E(F(2m))。

其中a,b,x,y均在有限域GF(2m)中取值。

在橢圓曲線群中，使nG=0的最小正整數(shù)n稱為點(diǎn)G的階數(shù)。

橢圓曲線上的離散對數(shù)問題：在曲線上兩個點(diǎn)P和Q滿足Q=kP，其中k為常數(shù)。已知k和P求Q容易，已知P和Q求k的問題是離散對數(shù)問題，求解卻很困難，是建立橢圓曲線密碼體制的數(shù)學(xué)依據(jù)。

1.2 橢圓曲線加解密算法

橢圓曲線密碼體制是將加密問題轉(zhuǎn)換為橢圓曲線群中元素的計算問題，采取非對稱的公、私雙秘鑰方式進(jìn)行加解密運(yùn)算。下面以素數(shù)域上的橢圓曲線為例介紹一種利用橢圓曲線群實(shí)現(xiàn)加、解密的方法。

首先選定橢圓曲線y2=x3+ax+bmodp。尋找一個階數(shù)為n的點(diǎn)G，要求n為一個大素數(shù)，稱為基點(diǎn)。把要發(fā)送的明文m嵌入到群E(Fp)上的點(diǎn)Pm[9，10]，然后對消息Pm進(jìn)行加、解密：

用戶A，選取一個整數(shù)dA作為私鑰，對應(yīng)的公鑰為pA=dAG。

用戶B，選取一個整數(shù)dB作為私鑰，對應(yīng)的公鑰為pB=dBG。

用戶A向用戶B發(fā)送信息Pm，進(jìn)行秘密傳輸。

1.2.1 加密過程

(1) 用戶A隨機(jī)選取一個正整數(shù)k∈[1,n-1]；

(2) 計算點(diǎn)Pk=kG；

(3) 利用用戶B的公鑰pB，計算點(diǎn)kpB；

(4) 計算點(diǎn)Pm+kpB；

(5) 形成密文C=(Pk,Pm+kpB)，由一對橢圓曲線群E(Fp)中的點(diǎn)組成。

1.2.2 解密過程

(1) 用戶B接收到密文C=(Pk,Pm+kpB)；

(2) 用私鑰dB計算點(diǎn)dBPk；

(3) 計算點(diǎn)(Pm+kpB)-dBPk，得到消息Pm=(Pm+kpB)-dBPk。

事實(shí)上，(Pm+kpB)-dBPk=(Pm+kdBG)-dBkG=Pm。

上述過程表明，用戶A通過將kpB與Pm相加來偽裝消息Pm，實(shí)現(xiàn)加密。因?yàn)閗是用戶A隨機(jī)選取的，只有用戶A知道，加解密過程中的主要計算是點(diǎn)的倍乘運(yùn)算，其他人無法從Pk=kG中解出k，就無法消除偽裝，提高了加密的安全性。

2 橢圓曲線密碼數(shù)字簽名的算法

數(shù)字簽名算法包括兩個部分，即簽名算法和驗(yàn)證算法。發(fā)送者簽名時用私鑰對明文或消息摘要實(shí)施加密運(yùn)算，然后把加密的數(shù)據(jù)傳給接受者，因他人無法知道私鑰，故不能偽造簽名。接收者驗(yàn)證簽名時利用發(fā)送者的公鑰進(jìn)行驗(yàn)證，將結(jié)果與消息或者摘要進(jìn)行比較，當(dāng)且僅當(dāng)兩者相同，就接收簽名。

在SEC(Standards for Efficient Cryptography)制定的ECC工作草案中[11]，定義橢圓曲線參數(shù)的形式是一個六元偶，記作：R={q,a,b,G,n,h}

其中：

(1) 整數(shù)q表示橢圓曲線基域F(pm)中域元素的個數(shù)；

(2)a,b表示橢圓曲線方程的系數(shù)；

(3)G是橢圓曲線點(diǎn)群的一個基點(diǎn)；

(4)n是橢圓曲線基點(diǎn)G的階；

(5)h是余因子，利用h可以較快地找到基點(diǎn)G。

橢圓曲線數(shù)字簽名ECDSA(Elliptic Curve Digital Signature Algorithm)是不帶有消息恢復(fù)功能簽名方案[12]，需要使用的參數(shù)有：橢圓曲線參數(shù)六元偶；待簽名消息m；簽名者A的密鑰對(d,Q)，其中Q=dG，d是私鑰、Q是公鑰。

簽名生成過程：

輸入：R={q,a,b,G,n,h}，私鑰d、消息m

輸出：(r,s)

(1) 隨機(jī)地選取一個整數(shù)k∈[1,n-1]

(2) 計算kG=(x1,y1)，r=x1modn，如果r=0則返回到1；

(3) 計算e=SHA-1(m)；

(4) 利用簽名者A的私鑰計算s=k-1(e+dr)modn，如果s=0則返回1；

(5) (r,s)是A對消息m的簽名。A發(fā)送給接收者B消息m及簽名(r,s)。

簽名驗(yàn)證：

輸入：R={q,a,b,G,n,h}，公鑰Q、消息m

輸出：驗(yàn)證(r,s)是對消息m的簽名是否正確。

(1) 驗(yàn)證(r,s)是[1,n-1]中的整數(shù)；

(2) 計算e=SHA-1(m)；

(3) 計算w=s-1modn；

(4) 計算u1=ewmodn,u2=rwmodn；

(5) 利用簽名者A的公鑰計算X=u1G+u2Q=(x2,y2)；

(6) 判定：如果X=O則拒絕簽名，否則計算v=x2modn，當(dāng)v=r時接受這個簽名。

簽名驗(yàn)證的證明：

因?yàn)?r,s)是簽名者A對消息m的簽名，

則s=k-1(e+dr)modn，

從而

k=s-1(e+dr)=s-1e+s-1dr=we+wdr=u1+u2d

所以X=u1G+u2dG=(u1+u2d)G=kG即v=r。

從上述算法知道，A是利用隨機(jī)數(shù)k和私鑰d，對消息m進(jìn)行的簽名，B是利用r和公鑰Q對簽名進(jìn)行驗(yàn)證。這個過程中無法通過r和公鑰Q來計算k和私鑰d，這就使得ECDSA算法非常安全。

3 兩種改進(jìn)的數(shù)字簽名算法

在數(shù)字簽名前，對于待簽明文m的處理有兩種方法，一種方法用密碼雜湊函數(shù)即哈希函數(shù)計算e=H(m)，并轉(zhuǎn)化為一個整數(shù)。另一種方法是把明文m與橢圓曲線上的點(diǎn)建立對應(yīng)關(guān)系，利用嵌入算法把明文用橢圓曲線上的點(diǎn)Pm來表示[13，14]。對哈希函數(shù)值e和橢圓曲線上點(diǎn)pm的簽名就是對明文消息m的簽名。根據(jù)這兩種情況對數(shù)字簽名算法進(jìn)行了改進(jìn)。

3.1 明文m利用哈希函數(shù)處理的數(shù)字簽名改進(jìn)算法

3.1.1 簽名生成過程

輸入：R={q,a,b,G,n,h}，私鑰d、明文m

輸出：(r,s)

(1) 隨機(jī)地選取一個整數(shù)k∈[1,n-1]；

(2) 計算kG=(x1,y1)；

(3) 計算e=SHA-1(m)；

(4) 計算r=(x1+e)modn，如果r=0則返回1；

(5) 利用簽名者A的私鑰計算s=(k-dr)modn，如果s=0則返回到1；

(6) (r,s)是A對消息m的簽名。A發(fā)送給接收者B消息m及簽名(r,s)。

3.1.2 簽名驗(yàn)證

輸入：R={q,a,b,G,n,h}，公鑰Q、消息m

輸出：驗(yàn)證(r,s)是對消息m的簽名是否正確。

(1) 驗(yàn)證(r,s)是[1,n-1]中的整數(shù)；

(2) 計算e=SHA-1(m)；

(3) 利用簽名者A的公鑰計算：

X=sG+rQ=(x2,y2)

(4) 判定：如果X=O則拒絕簽名。否則計算v=(x2+e)modn，當(dāng)v=r時接受這個簽名。

3.1.3 簽名驗(yàn)證的證明

因?yàn)?r,s)是簽名者A對消息m的簽名，則s=(k-dr)modn，從而

X=sG+rQ=(k-dr)modnG+rdmodnG=kG

所以v=r。

3.2 明文m用橢圓曲線上的點(diǎn)Pm來表示的數(shù)字簽名改進(jìn)算法

3.2.1 簽名生成過程

輸入：R={q,a,b,G,n,h}，私鑰d、消息Pm

輸出：(r,s)

(1) 隨機(jī)地選取一個整數(shù)k∈[1,n-1]

(2) 計算Pm+kG=(x1,y1)；

(3) 計算r=x1modn，如果r=0則返回到1；

(4) 利用簽名者A的私鑰計算

s=(k-dr)modn，如果s=0則返回到1；

(5) (r,s)是A對消息m的簽名。A發(fā)送給接收者B消息m及簽名(r,s)。

3.2.2 簽名驗(yàn)證

輸入：R={q,a,b,G,n,h}，公鑰Q、消息Pm

輸出：驗(yàn)證(r,s)是對消息m的簽名是否正確。

(1) 驗(yàn)證(r,s)是[1,n-1]中的整數(shù)；

(2) 利用簽名者A的公鑰計算：

X=Pm+sG+rQ=(x2,y2)

(3) 判定：如果X=O則拒絕簽名，否則計算v=x2modn，當(dāng)v=r時接受這個簽名。

3.2.3 簽名驗(yàn)證的證明

因?yàn)?r,s)是簽名者A對消息m的簽名，則s=(k-dr)modn，從而

X=Pm+sG+rQ=Pm+[(k-dr)modn]G+[rdmodn]G

=Pm+kG

所以v=r。

3.3 改進(jìn)的ECDSA算法安全性分析及其特點(diǎn)

安全性分析：

(1) 簽名算法中s=(k-dr)modn，一個方程中包含隨機(jī)數(shù)k和私鑰d兩個量，攻擊者無法求解；

(2) 從驗(yàn)證方程X=sG+rQ和X=Pm+sG+rQ中無法求得私鑰，保證了消息的真實(shí)性；

(3) 如果簽名是偽造的，驗(yàn)證方程不能通過，簽名不能否認(rèn)。

改進(jìn)的數(shù)字簽名方案對Hash值e應(yīng)用模n做了約簡，具有以下幾方面的特點(diǎn)：

(1) 簽名算法的生成和驗(yàn)證過程比較簡單；

(2) 避免了求模逆的運(yùn)算，提高了計算速度，對計算機(jī)硬軟件的要求更低；

(3) 算法能夠保證簽名文件的安全。

4 結(jié)論

(1) 本文對橢圓曲線密碼體制和數(shù)字簽名算法進(jìn)行了研究,給出了一種明文m利用哈希函數(shù)處理的數(shù)字簽名改進(jìn)算法；給出了一種明文m用橢圓曲線上的點(diǎn)Pm來表示的數(shù)字簽名改進(jìn)算法。

(2) 兩種改進(jìn)的數(shù)字簽名算法，能夠保證簽名的安全性，避免了求模逆的問題，減少了運(yùn)算量，對系統(tǒng)要求更低。研究具有一定的理論意義和實(shí)際應(yīng)用價值。

(3) 從安全性和算法有效性的角度來看，數(shù)字簽名算法有進(jìn)一步改進(jìn)的可能，下一階段將繼續(xù)研究。