摘 要:采用Java提供的大數(shù)操作，對素數(shù)域上橢圓曲線進行深入分析，以國際上相關(guān)的研究和算法實現(xiàn)工作為基礎(chǔ)，采用數(shù)學(xué)建模和面向?qū)ο蟮乃枷?，根?jù)橢圓曲線密碼體制，實現(xiàn)素數(shù)域橢圓曲線加密系統(tǒng)，給出詳細的設(shè)計，并分析了其中的關(guān)鍵算法。針對Java在網(wǎng)絡(luò)上的廣泛應(yīng)用，將其應(yīng)用于網(wǎng)絡(luò)驗證，保護網(wǎng)絡(luò)應(yīng)用系統(tǒng)的安全。關(guān)鍵詞:橢圓曲線; 密碼體制; 倍點; 數(shù)字簽名; 面向?qū)ο?/p>

中圖分類號: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 引 言

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

1 橢圓曲線及相關(guān)定義

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

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

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

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

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

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

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

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

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

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

(2) P+Q=Q+P;

(3) P+Q+R=O;

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

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

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

當(dāng)P=Q時:

λ=3x21+a2y1(mod p)

當(dāng)P≠Q(mào)時:

λ=y2-y1x2-x1(mod p)

2 橢圓曲線加密體制實現(xiàn)

橢圓曲線加密體制是基于橢圓曲線離散對數(shù)問題(Elliptic Curve Discrete Logarithm Problem，ECDLP)，即:假設(shè)基于E(Fp)上橢圓曲線E上有兩點G和Q，其中G為基點，Q=kG，則由G和Q要計算出k是一個數(shù)學(xué)難題。根據(jù)對橢圓曲線的數(shù)學(xué)建模，對橢圓曲線加密體制進行抽象，并按照面向?qū)ο蟮某绦蛟O(shè)計方法，先給出橢圓曲線相關(guān)變量的定義，然后給出關(guān)鍵算法的實現(xiàn)。本系統(tǒng)大致分為以下4個主要類。

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

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

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

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

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

2.1 橢圓曲線域參數(shù)

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

class EllipticCurve

{

private BigInteger a，b，p;

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

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

private BigInteger h;//協(xié)因子

…

EllipticCurve(){}//構(gòu)造EC參數(shù)

…

}

素數(shù)域Fp上橢圓曲線參數(shù)的產(chǎn)生，算法如下:

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

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

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

操作:素數(shù)域Fp上橢圓曲線參數(shù)產(chǎn)生如下步驟:

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

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

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



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

#E(Fp)≠p

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

h≤4



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

2.2 素數(shù)域橢圓曲線的點運算

橢圓曲線加密系統(tǒng)要實現(xiàn)的本質(zhì)是橢圓曲線上的點構(gòu)成的Abel群上的點乘運算，而Abel群是一個加法群，根據(jù)加法群的運算特點，橢圓曲線上的點乘運算又需要轉(zhuǎn)化成橢圓曲線上的點加運算來實現(xiàn)，當(dāng)兩個加數(shù)相同的時候，點加運算又變成了倍點運算，所以橢圓曲線上的點乘運算需要轉(zhuǎn)化成橢圓曲線上的點加和倍點運算實現(xiàn)。使用ECCPoint類，抽象橢圓曲線上的點，并實現(xiàn)倍點運算規(guī)則，下面是橢圓曲線點的抽象類，定義如下:

class ECCPoint

{

private EllipticCurve e;

private BigInteger x，y;

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

…

public ECPoint multiply(BigInteger k){}

//橢圓曲線倍點運算

…

}

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

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

式中:P代表橢圓曲線上的點;k為隨機的整數(shù)。下面給出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

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

2.3 橢圓曲線密鑰對

給定橢圓曲線的域參數(shù)T=(p，a，b，G，n，h)，可以產(chǎn)生橢圓曲線密鑰對(d，Q)，其中d為一個整數(shù)，為秘鑰;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){};//產(chǎn)生密鑰

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

…

}

算法3:橢圓曲線的密鑰對產(chǎn)生如下:

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

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

操作:橢圓曲線的密鑰對產(chǎn)生如下:

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

(2) 計算Q=dG;

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

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

2.4 橢圓曲線密碼體制

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

class ECCryptoSystem

{

MessageDigest hash;

private EllipticCurve e;

…

/*解密函數(shù)*

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

/*解密函數(shù)*/

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

/*簽名函數(shù)*/

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

/*驗證函數(shù)*/

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

…

}

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

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

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

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

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

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

(2) 執(zhí)行下面的計算:

R=kG;

(c1，c2)=kQ;

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

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

(c1，c2)=dR;

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

2.5 橢圓曲線數(shù)字簽名

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

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

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

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

(4) 計算r=x mod n

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

則簽名的信息為(r，s);發(fā)送簽名消息(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 應(yīng) 用

利用橢圓曲線的數(shù)學(xué)構(gòu)建和面向?qū)ο蟪绦蛟O(shè)計思想，實現(xiàn)了素數(shù)域上的橢圓曲線密碼體制。本系統(tǒng)基于Java語言實現(xiàn)，由于Java在網(wǎng)絡(luò)中的廣泛應(yīng)用，而網(wǎng)絡(luò)中的用戶名密碼消息一般是明文傳送的，所以很容易被截獲下來，造成重要資料的損失。本試驗根據(jù)前面介紹的算法，采用160 b長度的橢圓曲線參數(shù)，客戶端傳輸加密數(shù)據(jù)，數(shù)據(jù)在非安全信道上傳輸，然后服務(wù)器端解密?？梢园踩貍鬏敂?shù)據(jù)，但是這種方式也有其自身的缺點，不能解決中間人攻擊。所以本應(yīng)用是采用基于橢圓曲線的簽名機制來避免中間人攻擊的問題，圖1是基于橢圓曲線簽名驗證的流程圖。

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

圖1 基于ECDSA登陸的流程圖

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

4 結(jié) 語

ECC算法的數(shù)學(xué)背景比較深奧，本文在橢圓曲線

的數(shù)學(xué)建模和面向?qū)ο蟮某绦驅(qū)崿F(xiàn)上還有待加強。借

助Java提供的大數(shù)操作，實現(xiàn)了橢圓曲線加密系統(tǒng)，能夠直接應(yīng)用于網(wǎng)絡(luò)上數(shù)據(jù)加密傳輸和簽名驗證，本系統(tǒng)功能比較簡單，執(zhí)行效率性有待提高，下一步的主要工作是實現(xiàn)并完善本系統(tǒng)，進一步完善橢圓曲線的數(shù)學(xué)模型和改進執(zhí)行效率，規(guī)范系統(tǒng)調(diào)用接口，供其他程序調(diào)用。

參考文獻

[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]侯整風(fēng)，李嵐.橢圓曲線密碼系統(tǒng)(ECC)整體算法設(shè)計及優(yōu)化研究[J].電子學(xué)報，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].陳昊鵬，譯.北京:機械工業(yè)出版社，2002.

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

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

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