李明株，劉瑞芹

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

0 引言

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

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

1 橢圓曲線密碼體制

1.1 有限域上的橢圓曲線

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

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

二進制擴域GF(2m)：由二元域GF(2)上所有次數(shù)小于m的多項式組成，即：

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

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

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

y2=x3+ax+bmodp

的所有解(x,y)構成的點集，外加無窮遠點O構成的一個群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)構成的點集，外加無窮遠點O構成一個橢圓曲線群E(F(2m))。

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

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

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

1.2 橢圓曲線加解密算法

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

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

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

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

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

1.2.1 加密過程

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

(2) 計算點Pk=kG；

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

(4) 計算點Pm+kpB；

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

1.2.2 解密過程

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

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

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

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

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

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

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

在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是橢圓曲線點群的一個基點；

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

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

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

簽名生成過程：

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

輸出：(r,s)

(1) 隨機地選取一個整數(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)。

簽名驗證：

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

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

(1) 驗證(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，當v=r時接受這個簽名。

簽名驗證的證明：

因為(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是利用隨機數(shù)k和私鑰d，對消息m進行的簽名，B是利用r和公鑰Q對簽名進行驗證。這個過程中無法通過r和公鑰Q來計算k和私鑰d，這就使得ECDSA算法非常安全。

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

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

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

3.1.1 簽名生成過程

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

輸出：(r,s)

(1) 隨機地選取一個整數(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 簽名驗證

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

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

(1) 驗證(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，當v=r時接受這個簽名。

3.1.3 簽名驗證的證明

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

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

所以v=r。

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

3.2.1 簽名生成過程

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

輸出：(r,s)

(1) 隨機地選取一個整數(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 簽名驗證

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

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

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

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

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

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

3.2.3 簽名驗證的證明

因為(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 改進的ECDSA算法安全性分析及其特點

安全性分析：

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

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

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

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

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

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

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

4 結論

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

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

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