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

商艷紅，侯金鳳

（唐山師范學院 計算機科學系，河北 唐山 063000）

計算機科學與技術研究

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

商艷紅，侯金鳳

（唐山師范學院 計算機科學系，河北 唐山 063000）

橢圓曲線密碼體制（ECC）已成為密碼學的研究熱點之一。相對于其他的公鑰密碼體制，橢圓曲線密碼體制具有密鑰短和計算效率高等優點。從橢圓曲線密碼體制的各優點出發，介紹并分析橢圓曲線密碼體制的發展前景。

橢圓曲線密碼體制；移動辦公；智能卡；無線網絡

1 ECC的背景

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

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

一個利用橢圓曲線進行加解密通信的過程如下：

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

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

（3）用戶A將E和點K、G傳給用戶B；

（4）用戶B接到信息后，將待傳輸的明文編碼到E上一點M，并產生一個隨機整數r（r＜n）；

（5）用戶B計算點C1=M+rK和C2=rG；

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

（7）用戶A接到信息后，計算C1-kC2，結果就是點M，再對其進行解碼即可得到明文。

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

2 ECC的優勢分析及應用前景

橢圓曲線離散對數的計算難度是完全指數級的，相對于其他密碼體制，ECC具有諸多優勢。下面就從ECC的優勢切入，對其優勢進行分析并探討它的應用展望。

2.1 安全性高

在所有密碼體制中，安全性無疑是最核心的問題。由上給出的ECC算法數學原理可得出，有限域上的離散對數問題是ECC的核心，而次離散對數問題不能被所有已知算法在多項式時間內求解，可見ECC的抗攻擊性占據絕對優勢。由表1可以看出，同等安全條件下，ECC的安全性遠遠優于RSA，如采用160位的ECC和1 024位的RSA算法的安全強度相當；而且，在同等安全條件下，安全要求越高，其短密鑰的優勢會越明顯?？梢姡鄬τ赗SA，ECC每比特具有較高安全強度。

表1 ECC與RSA密鑰長度及安全性的比較

基于這一特點，ECC在移動電子商務、電子政務和計算機網絡安全以及軟件的注冊等領域具有廣闊的應用前景[3]。

2.2 計算量小，處理速度快

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

ECC的計算開銷小以及速度快，尤其在存儲容量有限且運算能力較低等方面，具有顯著優勢。實際應用中，在VPN安全隧道方面，考慮到嵌入式應用在計算機資源和存儲資源方面的局限性，根據ECC加解密速度快、節省帶寬、節省存儲資源，可選擇ECC來設計和實現身份鑒別[4]；在移動通信以及網絡通信方面，需要高效地對數據進行加密，ECC處理速度快的特點使得移動通信的發展不再受存儲容量及低計算能力的限制。此外，ECC在集成電路卡、數字簽名等加密速度要求高的地方能夠實現快速、安全的加密和簽名。

表2 ECC密碼與RSA密碼軟件實現速度的比較

2.3 存儲空間小

ECC的密鑰長度和系統參數與RSA相比要小得多，由表1可知，RSA算法需要512位，而僅需106位即可保證其安全性，這就意味著ECC所需的存儲空間小得多。在計算上，所選素數小，計算開銷小，這也使得ECC在存儲空間有限制的設備上有更好的應用。

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

2.4 帶寬要求低

由于ECC比其他加密算法密鑰短，使得其在傳輸時帶寬要求更低。當對長信息進行加密時，ECC、RSA密碼系統有相同的帶寬要求，但應用于短信息時ECC的帶寬要求卻低得多，使得ECC在無線網絡中具有廣闊的應用前景[6]。

目前而言，在無線網絡方面，WLAN的安全問題一直是業界廣泛關注的問題，它一直制約著WLAN的大規模推廣及企業級應用?，F在使用的SSL標準安全套接層握手協議帶寬開銷大而使得網絡數據通信效率低，ECC可減少一定量的帶寬開銷，使得通信效率得到提高。同時，在Web服務器上的帶寬有限使得帶寬的費用高昂，而ECC恰恰解決了Web服務器的實現遇到的這種瓶頸，節省了計算時間和帶寬。在 3G網絡方面，針對計算資源和帶寬資源有限的弱點，基于ECC涉及安全的支付流程，可實現端對端的信息安全傳輸。

3 ECC的發展

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

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

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

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

（2）不是超奇異曲線；

（3）不是畸形曲線。

確定橢圓曲線的參數后，還必須找出一個基點以構造各種基于橢圓曲線的密碼體制。

3.2 對于運算效率而言，如何產生合適的符合安全條件的橢圓曲線并快速實現的問題

有效地計算橢圓曲線的階是主要問題。因為安全的橢圓曲線的核心步驟是對橢圓曲線階的計算，對橢圓曲線階的有效算法的研究也是實現安全橢圓曲線密碼體制的一個極其重要的環節。

橢圓曲線密碼體制中，橢圓曲線群上的點的倍乘占了整個運算的很大比例，其效率關系到整個體制的執行效率，對于橢圓曲線中的 kP倍乘計算仍需研究更高效、快捷的方法。

4 結束語

ECC是一種能適應未來通信技術和信息安全技術發展的新型密碼體制。目前，在實際應用中，相關產品不是很多，主要集中在軟件實現上。相信在理論算法的突破以及實現技術的更新下，ECC的實現會越來越迅猛。隨著其標準的成型，相關的ECC產品，尤其是能體現ECC優勢的智能卡將很快問世和得到很好推廣。

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

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

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

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

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

[6] 曹陽,權雙燕.ECC在無線局域網安全中的研究與應用[J].樂山師范學院學報,2009(5)：76-78.

（責任編輯、校對：趙光峰）

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

唐山師范學院教育教學改革研究項目（2012001021）

2012-05-23

商艷紅（1979-），女，河北樂亭人，碩士，講師，研究方向為密碼學、信息安全。

TP309.7

A

1009-9115(2012)05-0044-03