商艷紅，侯金鳳

（唐山師范學(xué)院 計(jì)算機(jī)科學(xué)系，河北 唐山 063000）

計(jì)算機(jī)科學(xué)與技術(shù)研究

橢圓曲線密碼體制的分析和展望

商艷紅，侯金鳳

（唐山師范學(xué)院 計(jì)算機(jī)科學(xué)系，河北 唐山 063000）

橢圓曲線密碼體制（ECC）已成為密碼學(xué)的研究熱點(diǎn)之一。相對(duì)于其他的公鑰密碼體制，橢圓曲線密碼體制具有密鑰短和計(jì)算效率高等優(yōu)點(diǎn)。從橢圓曲線密碼體制的各優(yōu)點(diǎn)出發(fā)，介紹并分析橢圓曲線密碼體制的發(fā)展前景。

橢圓曲線密碼體制；移動(dòng)辦公；智能卡；無(wú)線網(wǎng)絡(luò)

1 ECC的背景

隨著計(jì)算機(jī)速度的迅速提高人們給出了多種加密方案及其改進(jìn)[1,p384;2]，但仍舊不能滿足Internet分布式計(jì)算能力的日益強(qiáng)大，而經(jīng)典的公鑰密碼體制如RSA等，在密鑰長(zhǎng)度為512 bit下已經(jīng)越來(lái)越不安全，增加密鑰長(zhǎng)度雖然能增強(qiáng)其安全性，但是加解密的效率越來(lái)越低，同時(shí)對(duì)系統(tǒng)要求越來(lái)越高，唯一的辦法就是使用新的有效的密碼體制。

橢圓曲線密碼體制（ECC）是一種基于橢圓曲線數(shù)學(xué)的公鑰密碼體制。橢圓曲線在密碼學(xué)中的使用是在 1985年由Neal Koblitz和Victor Miller分別獨(dú)立提出的。在公鑰密碼體制中，相比較其他算法而言，ECC具有密鑰短和計(jì)算效率高等優(yōu)點(diǎn)，且ECC本身算法的數(shù)學(xué)理論非常復(fù)雜深?yuàn)W。其原理[1,p190]在于：給定素?cái)?shù)p和橢圓曲線E，對(duì)Q=kP，在已知P，Q的情況下求出小于p的正整數(shù)k，已知k和P計(jì)算Q比較容易，而已知Q和P計(jì)算k則比較困難，至今沒有有效的方法來(lái)解決此問題。

一個(gè)利用橢圓曲線進(jìn)行加解密通信的過程如下：

（1）用戶A選定一條橢圓曲線E，并取橢圓曲線上一點(diǎn)作為基點(diǎn)G；

（2）用戶A選擇一個(gè)私鑰k，并生成公鑰K=kG；

（3）用戶A將E和點(diǎn)K、G傳給用戶B；

（4）用戶B接到信息后，將待傳輸?shù)拿魑木幋a到E上一點(diǎn)M，并產(chǎn)生一個(gè)隨機(jī)整數(shù)r（r＜n）；

（5）用戶B計(jì)算點(diǎn)C1=M+rK和C2=rG；

（6）用戶B將C1、C2傳給用戶A；

（7）用戶A接到信息后，計(jì)算C1-kC2，結(jié)果就是點(diǎn)M，再對(duì)其進(jìn)行解碼即可得到明文。

橢圓密碼體制的安全性是基于求解橢圓曲線離散對(duì)數(shù)問題的最有效算法的時(shí)間復(fù)雜度，與一般的有限乘法群上的離散對(duì)數(shù)問題不同，有限域上的橢圓曲線離散對(duì)數(shù)問題的求解更難，不能被所有已知算法在多項(xiàng)式時(shí)間內(nèi)求解。從數(shù)學(xué)理論的角度，ECC具有每比特最高安全強(qiáng)度，而且，ECC被公認(rèn)為目前已知的公鑰密碼體制中每比特提供加密強(qiáng)度最高的一種體制。

2 ECC的優(yōu)勢(shì)分析及應(yīng)用前景

橢圓曲線離散對(duì)數(shù)的計(jì)算難度是完全指數(shù)級(jí)的，相對(duì)于其他密碼體制，ECC具有諸多優(yōu)勢(shì)。下面就從ECC的優(yōu)勢(shì)切入，對(duì)其優(yōu)勢(shì)進(jìn)行分析并探討它的應(yīng)用展望。

2.1 安全性高

在所有密碼體制中，安全性無(wú)疑是最核心的問題。由上給出的ECC算法數(shù)學(xué)原理可得出，有限域上的離散對(duì)數(shù)問題是ECC的核心，而次離散對(duì)數(shù)問題不能被所有已知算法在多項(xiàng)式時(shí)間內(nèi)求解，可見ECC的抗攻擊性占據(jù)絕對(duì)優(yōu)勢(shì)。由表1可以看出，同等安全條件下，ECC的安全性遠(yuǎn)遠(yuǎn)優(yōu)于RSA，如采用160位的ECC和1 024位的RSA算法的安全強(qiáng)度相當(dāng)；而且，在同等安全條件下，安全要求越高，其短密鑰的優(yōu)勢(shì)會(huì)越明顯?？梢姡鄬?duì)于RSA，ECC每比特具有較高安全強(qiáng)度。

表1 ECC與RSA密鑰長(zhǎng)度及安全性的比較

基于這一特點(diǎn)，ECC在移動(dòng)電子商務(wù)、電子政務(wù)和計(jì)算機(jī)網(wǎng)絡(luò)安全以及軟件的注冊(cè)等領(lǐng)域具有廣闊的應(yīng)用前景[3]。

2.2 計(jì)算量小，處理速度快

公鑰的生成速度主要是由其中的大數(shù)算術(shù)運(yùn)算決定，而大數(shù)算術(shù)運(yùn)算的速度跟大數(shù)的規(guī)模密切相關(guān)，在相同計(jì)算條件下，ECC的實(shí)現(xiàn)可以選取比RSA小得多的大數(shù)，ECC的實(shí)現(xiàn)速度比RSA快得多。如表2所示，在相同安全強(qiáng)度下，ECC在密鑰對(duì)的生成、簽名以及認(rèn)證方面，實(shí)現(xiàn)速度均比RSA快得多。如在密鑰對(duì)生成上，ECC僅需3.8 ms，而RSA需要4 708.3 ms，此外，對(duì)于ECC來(lái)說，所有應(yīng)用于離散對(duì)數(shù)加密系統(tǒng)的計(jì)算技巧可以同樣應(yīng)用于基于橢圓曲線的系統(tǒng)中，對(duì)于基于ECC的密碼系統(tǒng)的運(yùn)算還可以采用快速冗余算法來(lái)降低計(jì)算開銷。這使得ECC在私鑰處理速度上快得多。

ECC的計(jì)算開銷小以及速度快，尤其在存儲(chǔ)容量有限且運(yùn)算能力較低等方面，具有顯著優(yōu)勢(shì)。實(shí)際應(yīng)用中，在VPN安全隧道方面，考慮到嵌入式應(yīng)用在計(jì)算機(jī)資源和存儲(chǔ)資源方面的局限性，根據(jù)ECC加解密速度快、節(jié)省帶寬、節(jié)省存儲(chǔ)資源，可選擇ECC來(lái)設(shè)計(jì)和實(shí)現(xiàn)身份鑒別[4]；在移動(dòng)通信以及網(wǎng)絡(luò)通信方面，需要高效地對(duì)數(shù)據(jù)進(jìn)行加密，ECC處理速度快的特點(diǎn)使得移動(dòng)通信的發(fā)展不再受存儲(chǔ)容量及低計(jì)算能力的限制。此外，ECC在集成電路卡、數(shù)字簽名等加密速度要求高的地方能夠?qū)崿F(xiàn)快速、安全的加密和簽名。

表2 ECC密碼與RSA密碼軟件實(shí)現(xiàn)速度的比較

2.3 存儲(chǔ)空間小

ECC的密鑰長(zhǎng)度和系統(tǒng)參數(shù)與RSA相比要小得多，由表1可知，RSA算法需要512位，而僅需106位即可保證其安全性，這就意味著ECC所需的存儲(chǔ)空間小得多。在計(jì)算上，所選素?cái)?shù)小，計(jì)算開銷小，這也使得ECC在存儲(chǔ)空間有限制的設(shè)備上有更好的應(yīng)用。

隨著移動(dòng)互聯(lián)網(wǎng)時(shí)代的到來(lái)，ECC的這一優(yōu)勢(shì)決定了它在移動(dòng)通信設(shè)備、智能卡等存儲(chǔ)空間小、運(yùn)算能力差的設(shè)備上的發(fā)展地位[5]。智能卡作為電子媒介的主要形式具有體積小、便于攜帶、安全性高并具一定的數(shù)據(jù)存儲(chǔ)和處理能力、可進(jìn)行數(shù)據(jù)加密、解密和數(shù)字簽名等特點(diǎn)，從而在電子交易中得以廣泛的應(yīng)用。然而，由于其存儲(chǔ)容量和計(jì)算速度的限制，在對(duì)其進(jìn)行加密時(shí)所使用的密鑰應(yīng)盡可能的短，這樣才能為智能卡的實(shí)用化奠定基礎(chǔ)。智能卡的數(shù)據(jù)傳送相對(duì)較慢，為提高應(yīng)用效率，基本數(shù)據(jù)單元必須小，這樣可以減少智能卡與卡的終端之間的數(shù)據(jù)流量。將ECC應(yīng)用于智能卡的優(yōu)點(diǎn)是生成私鑰公鑰方便、節(jié)省存儲(chǔ)空間、節(jié)省帶寬、提高實(shí)用性、節(jié)省處理時(shí)間，而且不需要增加硬件的處理。ECC密鑰短所帶來(lái)的優(yōu)點(diǎn)彌補(bǔ)了智能卡硬件的局限，不僅有效降低了智能卡的生產(chǎn)成本，也提高了實(shí)用性。

2.4 帶寬要求低

由于ECC比其他加密算法密鑰短，使得其在傳輸時(shí)帶寬要求更低。當(dāng)對(duì)長(zhǎng)信息進(jìn)行加密時(shí)，ECC、RSA密碼系統(tǒng)有相同的帶寬要求，但應(yīng)用于短信息時(shí)ECC的帶寬要求卻低得多，使得ECC在無(wú)線網(wǎng)絡(luò)中具有廣闊的應(yīng)用前景[6]。

目前而言，在無(wú)線網(wǎng)絡(luò)方面，WLAN的安全問題一直是業(yè)界廣泛關(guān)注的問題，它一直制約著WLAN的大規(guī)模推廣及企業(yè)級(jí)應(yīng)用?，F(xiàn)在使用的SSL標(biāo)準(zhǔn)安全套接層握手協(xié)議帶寬開銷大而使得網(wǎng)絡(luò)數(shù)據(jù)通信效率低，ECC可減少一定量的帶寬開銷，使得通信效率得到提高。同時(shí)，在Web服務(wù)器上的帶寬有限使得帶寬的費(fèi)用高昂，而ECC恰恰解決了Web服務(wù)器的實(shí)現(xiàn)遇到的這種瓶頸，節(jié)省了計(jì)算時(shí)間和帶寬。在 3G網(wǎng)絡(luò)方面，針對(duì)計(jì)算資源和帶寬資源有限的弱點(diǎn)，基于ECC涉及安全的支付流程，可實(shí)現(xiàn)端對(duì)端的信息安全傳輸。

3 ECC的發(fā)展

橢圓曲線密碼體制是現(xiàn)有公鑰密碼體制中比特位強(qiáng)度最高的密碼體制，其發(fā)展前景相當(dāng)廣泛，且適應(yīng)于當(dāng)代社會(huì)的需求。但就目前而言，還面臨著很多理論以及技術(shù)上的問題，如何選取合適的有限域GF(Qm)的橢圓曲線E，如何選取基點(diǎn)P對(duì)于ECC的速度、效率、密鑰長(zhǎng)度以及安全性來(lái)說至關(guān)重要。

3.1 對(duì)于安全性而言，如何選取合適的適合安全條件的隨機(jī)橢圓曲線的問題

橢圓曲線密碼系統(tǒng)若沒有采用安全的橢圓曲線，那么整個(gè)系統(tǒng)就不安全。所謂安全橢圓曲線是指能夠抗各種已有攻擊的曲線，目前對(duì)橢圓曲攻擊比較有效的方式是Mov攻擊、Smart方法，大步小步法。為抵抗上述攻擊，有限域GF上的橢圓曲線必須滿足：

（1）階有最大的素因子；

（2）不是超奇異曲線；

（3）不是畸形曲線。

確定橢圓曲線的參數(shù)后，還必須找出一個(gè)基點(diǎn)以構(gòu)造各種基于橢圓曲線的密碼體制。

3.2 對(duì)于運(yùn)算效率而言，如何產(chǎn)生合適的符合安全條件的橢圓曲線并快速實(shí)現(xiàn)的問題

有效地計(jì)算橢圓曲線的階是主要問題。因?yàn)榘踩臋E圓曲線的核心步驟是對(duì)橢圓曲線階的計(jì)算，對(duì)橢圓曲線階的有效算法的研究也是實(shí)現(xiàn)安全橢圓曲線密碼體制的一個(gè)極其重要的環(huán)節(jié)。

橢圓曲線密碼體制中，橢圓曲線群上的點(diǎn)的倍乘占了整個(gè)運(yùn)算的很大比例，其效率關(guān)系到整個(gè)體制的執(zhí)行效率，對(duì)于橢圓曲線中的 kP倍乘計(jì)算仍需研究更高效、快捷的方法。

4 結(jié)束語(yǔ)

ECC是一種能適應(yīng)未來(lái)通信技術(shù)和信息安全技術(shù)發(fā)展的新型密碼體制。目前，在實(shí)際應(yīng)用中，相關(guān)產(chǎn)品不是很多，主要集中在軟件實(shí)現(xiàn)上。相信在理論算法的突破以及實(shí)現(xiàn)技術(shù)的更新下，ECC的實(shí)現(xiàn)會(huì)越來(lái)越迅猛。隨著其標(biāo)準(zhǔn)的成型，相關(guān)的ECC產(chǎn)品，尤其是能體現(xiàn)ECC優(yōu)勢(shì)的智能卡將很快問世和得到很好推廣。

[1] 張煥國(guó),王張宜.密碼學(xué)引論(第二版)[M].武漢：武漢大學(xué)出版社,2009：384.

[2] 商艷紅,張靜.一種基于 PlayFair密碼的改進(jìn)算法[J].光盤技術(shù),2009(3)：50.

[3] 麻勝海.基于橢圓曲線的數(shù)字簽名在移動(dòng)辦公中的應(yīng)用[J].科技信息,2010(5)：483-484.

[4] 叢清日,胡金初.基于橢圓曲線密碼體制的通信認(rèn)證[J].上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2010(3)：45-47.

[5] 項(xiàng)燦.ECC智能卡在電子交易中的安全應(yīng)用[J].科技信息,2008(20)：370-371.

[6] 曹陽(yáng),權(quán)雙燕.ECC在無(wú)線局域網(wǎng)安全中的研究與應(yīng)用[J].樂山師范學(xué)院學(xué)報(bào),2009(5)：76-78.

（責(zé)任編輯、校對(duì)：趙光峰）

Analysis and Forecast of Elliptic Curve Cryptosystem

SHANG Yan-hong, HOU Jin-feng

(Department of Computer Science, Tangshan Teachers College, Tangshan 063000, China)

Elliptic Curve Cryptosystem (ECC) has become one of the research hotspots in cryptography. Compared to other public-key cryptosystem, Elliptic Curve Cryptosystem has shorter key and calculation of high efficiency. Based the advantages of Elliptic Curve Cryptosystem this article introduces and analyzes the development prospect of elliptic curve cryptosystem.

ECC; mobile office; smart card; wireless network

唐山師范學(xué)院教育教學(xué)改革研究項(xiàng)目（2012001021）

2012-05-23

商艷紅（1979-），女，河北樂亭人，碩士，講師，研究方向?yàn)槊艽a學(xué)、信息安全。

TP309.7

A

1009-9115(2012)05-0044-03