[科普中國(guó)]-橢圓加密算法

橢圓加密算法（ECC）是一種公鑰加密體制，最初由Koblitz和Miller兩人于1985年提出，其數(shù)學(xué)基礎(chǔ)是利用橢圓曲線上的有理點(diǎn)構(gòu)成Abel加法群上橢圓離散對(duì)數(shù)的計(jì)算困難性。公鑰密碼體制根據(jù)其所依據(jù)的難題一般分為三類：大整數(shù)分解問(wèn)題類、離散對(duì)數(shù)問(wèn)題類、橢圓曲線類。有時(shí)也把橢圓曲線類歸為離散對(duì)數(shù)類。

橢圓曲線密碼學(xué)橢圓曲線密碼學(xué)（英語(yǔ)：Elliptic curve cryptography，縮寫為ECC），一種建立公開(kāi)密鑰加密的演算法，基于橢圓曲線數(shù)學(xué)。橢圓曲線在密碼學(xué)中的使用是在1985年由Neal Koblitz和Victor Miller分別獨(dú)立提出的。

ECC的主要優(yōu)勢(shì)是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密算法——提供相當(dāng)?shù)幕蚋叩燃?jí)的安全。ECC的另一個(gè)優(yōu)勢(shì)是可以定義群之間的雙線性映射，基于Weil對(duì)或是Tate對(duì)；雙線性映射已經(jīng)在密碼學(xué)中發(fā)現(xiàn)了大量的應(yīng)用，例如基于身份的加密。不過(guò)一個(gè)缺點(diǎn)是加密和解密操作的實(shí)現(xiàn)比其他機(jī)制花費(fèi)的時(shí)間長(zhǎng)。1

加密基于這個(gè)秘密值，用來(lái)對(duì)Alice和Bob之間的報(bào)文進(jìn)行加密的實(shí)際方法是適應(yīng)以前的，最初是在其他組中描述使用的離散對(duì)數(shù)密碼系統(tǒng)。這些系統(tǒng)包括：

Diffie-Hellman—ECDH

MQV—ECMQV

ElGamal discrete log cryptosystem—ECElGamal

數(shù)字簽名算法—ECDSA

對(duì)于ECC系統(tǒng)來(lái)說(shuō)，完成運(yùn)行系統(tǒng)所必須的群操作比同樣大小的因數(shù)分解系統(tǒng)或模整數(shù)離散對(duì)數(shù)系統(tǒng)要慢。不過(guò)，ECC系統(tǒng)的擁護(hù)者相信ECDLP問(wèn)題比DLP或因數(shù)分解問(wèn)題要難的多，并且因此使用ECC能用小的多的密鑰長(zhǎng)度來(lái)提供同等的安全，在這方面來(lái)說(shuō)它確實(shí)比例如RSA之類的更快。到目前為止已經(jīng)公布的結(jié)果趨于支持這個(gè)結(jié)論，不過(guò)一些專家表示懷疑。

ECC被廣泛認(rèn)為是在給定密鑰長(zhǎng)度的情況下，最強(qiáng)大的非對(duì)稱算法，因此在對(duì)帶寬要求十分緊的連接中會(huì)十分有用。1

優(yōu)點(diǎn)安全性高有研究表示160位的橢圓密鑰與1024位的RSA密鑰安全性相同。

處理速度快在私鑰的加密解密速度上，ecc算法比RSA、DSA速度更快。

存儲(chǔ)空間占用小。

帶寬要求低。1

公鑰密碼系統(tǒng)的加密算法ECC與RSA的對(duì)比第六屆國(guó)際密碼學(xué)會(huì)議對(duì)應(yīng)用于公鑰密碼系統(tǒng)的加密算法推薦了兩種：基于大整數(shù)因子分解問(wèn)題（IFP）的RSA算法和基于橢圓曲線上離散對(duì)數(shù)計(jì)算問(wèn)題（ECDLP）的ECC算法。RSA算法的特點(diǎn)之一是數(shù)學(xué)原理簡(jiǎn)單、在工程應(yīng)用中比較易于實(shí)現(xiàn)，但它的單位安全強(qiáng)度相對(duì)較低。目前用國(guó)際上公認(rèn)的對(duì)于RSA算法最有效的攻擊方法--一般數(shù)域篩(NFS)方法去破譯和攻擊RSA算法，它的破譯或求解難度是亞指數(shù)級(jí)的。ECC算法的數(shù)學(xué)理論非常深?yuàn)W和復(fù)雜，在工程應(yīng)用中比較難于實(shí)現(xiàn)，但它的單位安全強(qiáng)度相對(duì)較高。用國(guó)際上公認(rèn)的對(duì)于ECC算法最有效的攻擊方法--Pollard rho方法去破譯和攻擊ECC算法，它的破譯或求解難度基本上是指數(shù)級(jí)的。正是由于RSA算法和ECC算法這一明顯不同，使得ECC算法的單位安全強(qiáng)度高于RSA算法，也就是說(shuō)，要達(dá)到同樣的安全強(qiáng)度，ECC算法所需的密鑰長(zhǎng)度遠(yuǎn)比RSA算法低。這就有效地解決了為了提高安全強(qiáng)度必須增加密鑰長(zhǎng)度所帶來(lái)的工程實(shí)現(xiàn)難度的問(wèn)題。2

建議美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)局和ANSI X9已經(jīng)設(shè)定了最小密鑰長(zhǎng)度的要求，RSA和DSA是1024位，ECC是160位，相應(yīng)的對(duì)稱分組密碼的密鑰長(zhǎng)度是80位。NIST已經(jīng)公布了一列推薦的橢圓曲線用來(lái)保護(hù)5個(gè)不同的對(duì)稱密鑰大小（80, 112, 128, 192, 256）。一般而言，二進(jìn)制域上的ECC需要的非對(duì)稱密鑰的大小是相應(yīng)的對(duì)稱密鑰大小的兩倍。

Certicom是ECC的主要商業(yè)支持者，擁有超過(guò)130項(xiàng)專利，并且已經(jīng)以2千5百萬(wàn)美元的交易獲得了美國(guó)國(guó)家安全局（NSA）的技術(shù)許可。他們也已經(jīng)發(fā)起了許多對(duì)ECC算法的挑戰(zhàn)。已經(jīng)被解決的最復(fù)雜的是109位的密鑰，是在2003年初由一個(gè)研究團(tuán)隊(duì)破解的。破解密鑰的這個(gè)團(tuán)隊(duì)使用了基于生日攻擊的大塊并行攻擊，用超過(guò)10,000臺(tái)奔騰級(jí)的PC機(jī)連續(xù)運(yùn)行了540天以上。對(duì)于ECC推薦的最小密鑰長(zhǎng)度163位來(lái)說(shuō)，當(dāng)前估計(jì)需要的計(jì)算資源是109位問(wèn)題的10倍。

在2005年2月16日，NSA宣布決定采用橢圓曲線密碼的戰(zhàn)略作為美國(guó)政府標(biāo)準(zhǔn)的一部分，用來(lái)保護(hù)敏感但不保密的信息。NSA推薦了一組被稱為Suit B的算法，包括用來(lái)密鑰交換的Menezes-Qu-Vanstone橢圓曲線和Diffie-Hellman橢圓曲線，用來(lái)數(shù)字簽名的橢圓曲線數(shù)字簽名算法。這一組中也包括AES和SHA。3

另見(jiàn)SECG（Standards for Efficient Cryptography Group (SECG)）

抽象代數(shù)

奇幻熊

密鑰合意協(xié)議

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)