橢圓曲線加密體制的構建與應用

摘 要:采用Java提供的大數操作，對素數域上橢圓曲線進行深入分析，以國際上相關的研究和算法實現工作為基礎，采用數學建模和面向對象的思想，根據橢圓曲線密碼體制，實現素數域橢圓曲線加密系統，給出詳細的設計，并分析了其中的關鍵算法。針對Java在網絡上的廣泛應用，將其應用于網絡驗證，保護網絡應用系統的安全。關鍵詞:橢圓曲線; 密碼體制; 倍點; 數字簽名; 面向對象

中圖分類號:TN919-34; TP3097文獻標識碼:A

文章編號:1004-373X(2010)17-0117-04

Research and Application of Elliptic Curve Cryptosystem

LI Ming-xin， ZENG Xiao-ping， KANG Feng

(Department of Computer Engineering， Chengdu Aeronautic Vocational and Technical College， Chengdu 610021， China)

Abstract: The elliptic curve over prime finite field is analyzed deeply by using big integer provided by Java. Using mathematics modeling and object oriented method， according to EC public key encrypt theme， the elliptic curve encrypt system over prime finite field is achieved based on international relevant research and algorithms. Some important algorithms and detailed design of the system is proposed. In view of the wide application of Java in network， this cryptosystem is applied to network authentication for protecting the security of the system information.Keywords: elliptic curve; cryptosystem; point multiplying; digital signature; object-oriented

0 引 言

橢圓曲線密碼系統是由Neal Koblitz和Victor Miller在1985年分別獨立提出的，橢圓曲線密碼系統在同等的安全級別下密鑰最短，特別適用于計算能力較弱，存儲空間較小，帶寬較小的環境。同時，橢圓曲線資源豐富，同一個有限域上存在著大量不同的橢圓曲線，這為安全性增加了額外的保證，也為軟、硬件實現帶來方便。由于受美國安全出口限制，與Java開發包中橢圓曲線相關的API中提供的密鑰長度達不到保障數據的安全，Java語言具有很好的跨平臺性，所以本系統采用Java開發，并將其應用到網絡傳輸中。

1 橢圓曲線及相關定義

定義1 韋爾斯特拉斯(Weierstrass)方程:

y2+axy+by=x3+cx2+dx+e(1)

所確定光滑平面曲線稱為橢圓曲線，記為E，其中a，b，c，d，e∈Fp;Fp為有限域。滿足式(1) 的(x，y) 稱為Fp域上的點。此外，橢圓曲線還定義一個特殊的無窮點O。

設p是一個大于3的奇素數，參數a，b滿足4a3+27b2≠0(mod p)，那么有限素數域Fp上的橢圓曲線可以定義為:

E: y2≡x3+ax+b(mod p)(2)

素數域上Fp的橢圓曲線參數是一個六元組，它們是T={p，a，b，G，n，h}，其中p，a，b用來確定一條橢圓曲線;G=(xG，yG)為橢圓曲線的基點;素數n為G的階，n即為#E(Ep)，可以利用Hasse[1]定理來計算橢圓曲線的階:

p+1-2p≤#E(Fp)≤p+1+2p(3)

h是n關于#E(Ep)的協因子，即h=#E(Ep)/n。素數域Fp的橢圓曲線參數準確指定了橢圓曲線及其基點，這對于基于EC公鑰加密體制是必須的。

定義2 對滿足式(2)的橢圓曲線，無窮遠點為O，任取EC兩點P(x1，y1)，Q(x2，y2)，P+Q=R(x3，y3)是PQ連線交于EC的第三點相對于x軸的對稱點，且滿足以下性質:

(1) O+P=P+O=P;

(2) P+Q=Q+P;

(3) P+Q+R=O;

(4) λ為PQ連線的斜率，若P和Q為橢圓曲線E上同一點時，取E上經過P點切線的斜率:

x3=λ2-x1-x2(mod p)

y3=λ(x1-x3)-y1(mod p)

當P=Q時:

λ=3x21+a2y1(mod p)

當P≠Q時:

λ=y2-y1x2-x1(mod p)

2 橢圓曲線加密體制實現

橢圓曲線加密體制是基于橢圓曲線離散對數問題(Elliptic Curve Discrete Logarithm Problem，ECDLP)，即:假設基于E(Fp)上橢圓曲線E上有兩點G和Q，其中G為基點，Q=kG，則由G和Q要計算出k是一個數學難題。根據對橢圓曲線的數學建模，對橢圓曲線加密體制進行抽象，并按照面向對象的程序設計方法，先給出橢圓曲線相關變量的定義，然后給出關鍵算法的實現。本系統大致分為以下4個主要類。

(1) class EllipticCurve:基于有限素域的橢圓曲線類。

(2) class ECPoint:基于有限素域的橢圓曲線點類。

(3) class ECKey:橢圓曲線密鑰對類。

(4) class ECCryptoSystem:橢圓曲線加密體制類。

其中，EllipticCurve提供參數并構造橢圓曲線操作;ECPoint類提供橢圓曲線上的點運算;ECKey提供生成密鑰對;ECCryptoSystem類抽象ElGamal加密體制，提供加密解密功能。接下來將會詳細介紹各個類的定義和關鍵算法的實現。

2.1 橢圓曲線域參數

利用上面介紹的橢圓曲線域參數，用Elliptic Curve類抽象橢圓曲線，其中BigInteger為Java語言所提供的實現大數運算類。下面是橢圓曲線的抽象定義，接下來介紹橢圓曲線域參數生成算法。

class EllipticCurve

{

private BigInteger a，b，p;

private BigInteger n;//橢圓曲線的階

private ECPoint G;//橢圓曲線的基點

private BigInteger h;//協因子

…

EllipticCurve(){}//構造EC參數

…

}

素數域Fp上橢圓曲線參數的產生，算法如下:

算法1[1]:輸入:橢圓曲線參數所要求大概的安全級別t必須是一個整數。

t∈{56，64，80，96，112，128，192，256}

輸出:素數域Fp上橢圓曲線參數T=(p，a，b，G，n，h)，算法大概需要2t次操作。

操作:素數域Fp上橢圓曲線參數產生如下步驟:

(1) 選擇一個素數p，t≠256，滿足log2p

=2t，并且t=256，滿足log2p=521來決定有限域Fp。

(2) 在素數域Fp上選擇a，b，并且滿足方程(2)。橢圓曲線E(Fp)基點G=(xG，yG)，階n，余因子h=#E(Fp)/n，這些參數必須滿足下列限制條件:



4a3+27b2≠0(mod p)

#E(Fp)≠p

PB≠1(mod n)(1≤B<20)

h≤4



(3) 輸出橢圓曲線域參數六元組T=(p，a，b，G，n，h)

2.2 素數域橢圓曲線的點運算

橢圓曲線加密系統要實現的本質是橢圓曲線上的點構成的Abel群上的點乘運算，而Abel群是一個加法群，根據加法群的運算特點，橢圓曲線上的點乘運算又需要轉化成橢圓曲線上的點加運算來實現，當兩個加數相同的時候，點加運算又變成了倍點運算，所以橢圓曲線上的點乘運算需要轉化成橢圓曲線上的點加和倍點運算實現。使用ECCPoint類，抽象橢圓曲線上的點，并實現倍點運算規則，下面是橢圓曲線點的抽象類，定義如下:

class ECCPoint

{

private EllipticCurve e;

private BigInteger x，y;

private boolean iszero;//判斷是否為0點

…

public ECPoint multiply(BigInteger k){}

//橢圓曲線倍點運算

…

}

在橢圓曲線加密系統中最重要和耗費時間的操作是倍點。倍點的定義如下:

Q=kP=∑ki=1P(4)

式中:P代表橢圓曲線上的點;k為隨機的整數。下面給出Double-and-add算法，為二進制法。

算法2:Double-and-add算法如下[2]:

(1) k=∑m-1i=1bi2i，bi∈(0，1)

(2) P:=P(x1，x2)

(3) Q:=P

(4) for i from m-1 down to 0 do

Q=Q+Q

if bi=1， then Q=Q+P

(5) return Q

對于常規的算法，需要k次點加法，在Double-and-add算法中，平均只需3/2[log2 n]次運算，最多需要2[log2 n]次運算[3]。

2.3 橢圓曲線密鑰對

給定橢圓曲線的域參數T=(p，a，b，G，n，h)，可以產生橢圓曲線密鑰對(d，Q)，其中d為一個整數，為秘鑰;d∈[1，n-1];公鑰Q=(xQ，yQ)，并且Q=dG。

下面的類用來抽象橢圓曲線的密鑰對:

class ECCKey

{

protected boolean secret;

protected BigInteger d;

protected ECCPoint G，Q;

protected EllipticCurve e;

…

public ECCKey(EllipticCurve e){};//產生密鑰

public Key getPublicKey() {}//產生公鑰

…

}

算法3:橢圓曲線的密鑰對產生如下:

輸入:正確的橢圓曲線域參數T=(p，a，b，G，n，h)。

輸出:一條和T相關的橢圓曲線密鑰對(d，Q)。

操作:橢圓曲線的密鑰對產生如下:

(1) 在區間[1，n-1]隨機地選擇一個整數d;

(2) 計算Q=dG;

(3) 輸出(d，Q);

有了密鑰對，接下來就可以介紹基于ElGamal橢圓曲線公鑰加密體制。

2.4 橢圓曲線密碼體制

在本系統中，使用橢圓曲線ElGamal加密體制(ECES)，用ECCryptoSystem抽象，在這個類中，提供加密解密函數，接下來將會描述加密解密過程，類的定義如下:

class ECCryptoSystem

{

MessageDigest hash;

private EllipticCurve e;

…

/*解密函數*

byte[] decrypt(byte[] input， int num，ECKey key){}

/*解密函數*/

byte[]encrypt(byte[] input，int num，ECKey key){}

/*簽名函數*/

byte[] sign(byte[] input，int num，ECKey key){}

/*驗證函數*/

bool verify(byte[] message，int num，ECKey key){}

…

}

橢圓曲線加密解密的過程描述如下: 假想Alice想使用ElGamal橢圓曲線加密體制，其中橢圓曲線E(Fp)給定，他將執行下面的步驟:

(1) 選擇一個隨機整數d，并且滿足2≤d≤(#E-1);

(2) 計算Q=dG=(xQ，yQ);

(3) 公開(G，Q，p，#E)為公鑰，d為密匙，由算法3生成。

接下來，假設Bob想要發送一條消息(x1，x2)給Alice，他將執行下面的步驟:

(1) 選擇一個隨機數k，滿足2≤k≤(#E-1);

(2) 執行下面的計算:

R=kG;

(c1，c2)=kQ;

(y1，y2)=(c2x1，c2x2)(mod p)

(3) 發送(R，y1，y2)給Alice，接收到密文，Alice按照下面的步驟恢復密文(x1，x2):

(c1，c2)=dR;

(x1，x2)=(c-11y1，c-12y2)(mod p)

2.5 橢圓曲線數字簽名

假設Bob發送的信息為m，由上面生成的密鑰對為(d，Q)，簽名的過程如下:

(1) 計算信息m的消息摘要e=SHA1(m);

(2) 選擇一個隨機數k，1≤k≤n-1;

(3) 計算kG=(x，y);

(4) 計算r=x mod n

(5) s=k-1(e+dr)mod n

則簽名的信息為(r，s);發送簽名消息(r，s)給Alice，Alice按照下面的步驟驗證:

(1) 計算c=s-1mod n;

(2) 計算u1=ec mod n;u2=rc mod n;

(3) 計算X=u1G+u2Q=(x，y);

(4) 計算v=x mod n，如果v=r，簽名有效，否則無效。

3 應 用

利用橢圓曲線的數學構建和面向對象程序設計思想，實現了素數域上的橢圓曲線密碼體制。本系統基于Java語言實現，由于Java在網絡中的廣泛應用，而網絡中的用戶名密碼消息一般是明文傳送的，所以很容易被截獲下來，造成重要資料的損失。本試驗根據前面介紹的算法，采用160 b長度的橢圓曲線參數，客戶端傳輸加密數據，數據在非安全信道上傳輸，然后服務器端解密。可以安全地傳輸數據，但是這種方式也有其自身的缺點，不能解決中間人攻擊。所以本應用是采用基于橢圓曲線的簽名機制來避免中間人攻擊的問題，圖1是基于橢圓曲線簽名驗證的流程圖。

客戶端將用戶名密碼的Hash值傳遞給服務端，由于Hash值是不可逆的，這樣能避免中間人攻擊。由于數據庫中存放是用戶名和密碼的Hash值，也可以避免由于服務器的數據泄露帶來的危害。采用基于簽名驗證的方式，采用簽名驗證的方式登陸性能和安全更好。

圖1 基于ECDSA登陸的流程圖

根據RSA實驗室破解不同加密算法所耗的時間來看，采用160 b橢圓曲線加密的安全性和1 024 b的RSA加密安全性相當，需要花費600個月的時間[4]，因此，在160 b的情況下，其安全性系數適合在網絡中應用。

4 結 語

ECC算法的數學背景比較深奧，本文在橢圓曲線

的數學建模和面向對象的程序實現上還有待加強。借

助Java提供的大數操作，實現了橢圓曲線加密系統，能夠直接應用于網絡上數據加密傳輸和簽名驗證，本系統功能比較簡單，執行效率性有待提高，下一步的主要工作是實現并完善本系統，進一步完善橢圓曲線的數學模型和改進執行效率，規范系統調用接口，供其他程序調用。

參考文獻

[1]US EPA. SEC1: SECG released standards[S/OL]. [2000-02-10]. http://www.secg.org.

[2]MOON Sangook. Elliptic curve scalar point multiplication using radix-4 booth′s algorithm[J]. Computer and Information，2005，1(1):1-8.

[3]侯整風，李嵐.橢圓曲線密碼系統(ECC)整體算法設計及優化研究[J].電子學報，2004，32(11):1904-1906.

[4]QIU Qi-zhi， XIONG Qian-xing. Research on elliptic curve cryptography[J/OL]. [2004-05-26]. http://ieeexplore.ieee.org/.

[5]IEEE Computer Society. IEEE standard specifications for public-key cryptography[J/OL]. [2004-10-11]. http://standards.ieee.org/.

[6]IEEE Computer Society. IEEE standard specifications for public-keycryptography-amendment 1: additional techniques[J/OL]. [2004-11-10]. Http://ieeexplore.ieee.org/.

[7]ECKEL Bruce.Java編程思想[M].陳昊鵬，譯.北京:機械工業出版社，2002.

[8]DOUGLAS Stinson R.密碼學原理與實踐[M].馮登國，譯.北京:電子工業出版社，2003.

[9]Tom St Denis.程序員密碼學[M].沈斌，譯.北京:機械工業出版社，2007.

[10]KNUTH Donald E. The art of computer programming[M]. 3rd ed. [S.l.]: Addison Wesley， 1997.