基于公鑰密碼體制的Ｅｌｌｉｐｓｅ曲線加密算法

摘 要: 基于Ellipse曲線的密碼體制是最近發(fā)展起來的安全性能較好的一種體制，在一定程度上代表著公鑰密碼體制的發(fā)展方向。本文闡述了Ellipse曲線的基礎，密鑰對的生成，ECIES加解密方案，以及ECDSA簽名驗證方案。

關鍵詞: Ellipse曲線公鑰密碼 密鑰對 ECIES加密方案 ECDSA簽名

前言

目前影響最大的三類公鑰密碼是RSA公鑰密碼、ElGamal公鑰密碼和Ellipse曲線公鑰密碼，前者是在20世紀70年代中期提出的，其安全性依賴于大整數(shù)的因子分解的困難性，而后兩者的安全性分別依賴于有限域和橢圓曲線離散對數(shù)的難度。Ellipse曲線公鑰密碼是1985年由Koblitz(美國華盛頓大學)和Victor Miller(IBM)提出來的，它具有一些其它公鑰密碼無法比擬的優(yōu)勢，如密鑰短、占用帶寬、存儲空間少，單位密鑰安全性高等，越來越受到人們的關注，有著廣闊的應用前景。

1.Ellipse曲線基礎

Ellipse曲線指的是由威爾斯特拉斯(Weierstrass)方程:

y+axy+ay=x+ax+ax+a(1)

所確定的平面曲線。

常用于密碼系統(tǒng)的基于有限域GF(p)上的橢圓曲線是由方程:

y≡x+ax+b(mod p)(2)

所確定的，外加一個無窮遠點o，它并不在Ellipse曲線上，表示為o=(x，+∞)。其中a、b、x、y均在GF(p)上取值，且有4a+27b≠0，p是大于3的素數(shù)。

在等式

mp=p+p+…+p=Q(3)

中，已知m和點P求Q比較容易，反之已知Q和點p求m卻是很難的，這個問題稱為橢圓曲線上點群的離散對數(shù)問題。橢圓曲線密碼體制正是利用這個困難問題設計出來的。

2.密鑰對的生成

Ellipse曲線密鑰對與參數(shù)組D=(q，F(xiàn)R，S，a，b，P，n，h)中的一系列參數(shù)相關。在由P生成的群{P}上隨機選擇點Q作為公鑰。相應的私鑰是d=logQ。要生成密鑰對的實體A必須保證參數(shù)組是合法的。參數(shù)組和公鑰間的關系必須能被所有隨后可能用到A的公鑰的通信實體所檢驗。

輸入:參數(shù)組D=(q，F(xiàn)R，S，a，b，P，n，h)。

輸出:公鑰Q，私鑰d。

1)選擇d∈[1，n-1]。

2)計算Q=dp。

3)返回(Q，d)。

從公鑰Q計算私鑰d的問題顯然就是橢圓曲線離散對數(shù)問題。至關重要的是參數(shù)組D的選擇要使得橢圓曲線離散對數(shù)問題不可求解。

3.ECIES加密方案

橢圓曲線加密方案(ECIES)由Bellare和Rogaway提出，是ElGamal公鑰加密方案的一種變體。在ECIEC中，使用Diffie-Hellman共享秘密來產(chǎn)生兩個對稱密鑰k和k。密鑰k用于對稱密鑰密碼中加密明文，而用于對得出的密文進行認證。

3.1 ECIES加密

輸入:參數(shù)組D=(q，F(xiàn)R，S，a，b，P，n，h)，公鑰Q，明文m。

輸出:密文(R，C，t)。

1)計算k∈[1，n-1]。

2)計算R=kP和Z=hkQ。若Z=+∞則跳至第一步。

3)(k，k)←KDF(x，R)，其中x是Z的x坐標。

4)計算C=E(m)和t=MACC。

5)返回(R，C，t)。

其中KDF是由雜湊函數(shù)H構成的密鑰導出函數(shù)。若需要生成一個長度為l比特的密鑰，則將KDF(S)定義為雜湊值H(S，i)的級聯(lián)，其中i是計數(shù)器，當每個雜湊函數(shù)得出結果后增一，直到產(chǎn)生l比特的雜湊值為止。E是對稱密鑰加密方案中的加密函數(shù)，而AES、D則是解密函數(shù)。MAC是消息認證碼算法。

3.2 ECIES解密

輸入:參數(shù)組D=(q，F(xiàn)R，S，a，b，P，n，h)，私鑰d，密文(R，C，t)。

輸出:明文m或者拒絕該密文。

1)對R進行嵌入的公鑰確認。若確認失敗，則返回(“拒絕該密文”)。

2)計算Z=hkR。若Z=+∞則返回(“拒絕該密文”)。

3)(k，k)←KDF(x，R)，其中x是Z的x坐標。

4)計算t′=MAC(C)。若t′≠t，則返回(“拒絕該密文”)。

5)計算m=D(c)。

6)返回(m)。

解密工作的證明:若密文(R，C，t)確實是由合法的加密者加密明文m產(chǎn)生的，則

hkR=hd(kP)=hk(dP)=hkQ，

于是解密者同加密者計算出同樣的密鑰(R，R)，接受該密文并解密出m。

4.ECDSA簽名

橢圓曲線簽名算法(ECDSA)是數(shù)字簽名算法(DSA)的橢圓曲線版本。

4.1 ECDSA簽名的生成

輸入:參數(shù)組D=(q，F(xiàn)R，S，a，b，P，n，h)，私鑰d，消息m。

輸出:簽名(r，s)。

1)選擇k∈[1，n-1]。

2)計算kP=(x，y)并將x轉換為整數(shù)。

3)計算r=mod n。若r=0，則跳至第一步。

4)計算e=H(m)。

5)計算s=k(e+dr)mod n。若s=0，則跳至第一步。

6)返回(r，s)。

其中H表示一個密碼雜湊函數(shù)，其輸出長度不超過n比特。

4.2 ECDSA簽名的驗證

輸入:參數(shù)組D=(q，F(xiàn)R，S，a，b，P，n，h)，公鑰Q，消息m，簽名(r，s)。

輸出:判斷簽名是否合法。

1)檢驗r和s是否是區(qū)間[1，n-1]內(nèi)的整數(shù)。若任何一個檢驗失敗，則返回(“拒絕該簽名”)。

2)計算e=H(m)。

3)計算w=smod n。

4)計算u=ew mod n和u=rw mod n。

5)計算X=uP+uQ。

6)若X=+∞，則返回(“拒絕該簽名”)。

7)將X的x坐標x轉換為整數(shù);計算v=mod n。

8)若v=r，則返回(“接受該簽名”);否則，返回(“拒絕該簽名”)。

簽名驗證工作的證明:若一條消息的簽名(r，s)確實是由合法的簽名者生成的，則s≡k(e+dr)(mod n)，

重新整理可得k≡s(e+dr)≡se+srd≡we+wrd≡u+ud(mod n)，

于是X=uP+uQ=(u+ud)P=kP，因此v=r即為所需。

數(shù)字簽名的加密解密過程和秘密密鑰的加密解密過程都使用公開密鑰體系。數(shù)字簽名使用的是發(fā)送方的密鑰對，發(fā)送方用自己的私有密鑰進行加密，接收方用發(fā)送方的公開密鑰進行解密。在實用過程中，通常一個用戶擁有兩個密鑰對，一個密鑰對用來對數(shù)字簽名進行加密解密，一個密鑰對用來對秘密密鑰進行加密解密。這種方式提供了更高的安全性。加密鑰匙是公開的，密鑰的分配和管理就很簡單，而且能夠很容易地實現(xiàn)數(shù)字簽名。

5.結語

Ellipse加密算法作為一種密碼系統(tǒng)，它比RSA，DSA具有更高的安全強度，Ellipse加密算法只有亞指數(shù)時間算法。其由于所需要的密鑰較短、計算量小、處理速度快及占用存儲空間小等優(yōu)點，正廣泛應用于電子商務、電子政務等領域之中，Ellipse加密算法取代RSA和DSA是個必然的趨勢。如何高效地實現(xiàn)橢圓曲線密碼系統(tǒng)是當前密碼學研究的熱點，它必將有著廣闊而實際的應用前景。

參考文獻:

[1][加]Darrel Hankerson著.張煥國等譯.橢圓曲線密碼學導論[M].北京:電子工業(yè)出版社，2005.

[2][德]Andreas Enge著.吳鋌，董軍武等譯.橢圓曲線及其在密碼學中的應用——導引[M].北京:科學出版社，2007.

[3]滕艷平.基于非對稱密鑰體制Ellipse曲線加密算法的應用研究[D].吉林大學，2007.

[4]宋金秀，楊秋翔.橢圓曲線密碼體制的研究與探討[J].山西農(nóng)業(yè)大學學報，2008，28，(2).

[5]宋國琴.橢圓曲線密碼體制ECC[J].電腦開發(fā)與應用，2008，21，(8).

[6]張楠，張建華，吳兵，陳建英，傅春常.基于橢圓曲線密碼體制的數(shù)字簽名[J].西安民族大學學報，2007，33，(1).