橢圓曲線密碼學（英語：Elliptic curve cryptography，縮寫為 ECC），一種建立公開密鑰加密的算法，基於橢圓曲線數學。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。
基本介紹
- 中文名：橢圓曲線密碼學
- 外文名：Elliptic curve cryptography
- 英文簡稱：ECC
- 提出時間：1985年
- 提出者：Neal Koblitz和Victor Miller
- 學科：密碼學
介紹,密鑰交換,加密,建議,另見,
介紹
橢圓曲線密碼學（英語：Elliptic curve cryptography，縮寫為ECC），一種建立公開密鑰加密的算法，基於橢圓曲線數學。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。
ECC的主要優勢是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密算法——提供相當的或更高等級的安全。ECC的另一個優勢是可以定義群之間的雙線性映射，基於Weil對或是Tate對；雙線性映射已經在密碼學中發現了大量的套用，例如基於身份的加密。其缺點是同長度密鑰下加密和解密操作的實現比其他機制花費的時間長，但由於可以使用更短的密鑰達到同級的安全程度，所以同級安全程度下速度相對更快。一般認為160比特的橢圓曲線密鑰提供的安全強度與1024比特RSA密鑰相當。
密鑰交換
伽羅瓦域
對橢圓曲線來說最流行的有限域是以素數為模的整數域（參見模運算) GF(p)，或是特徵為2的伽羅瓦域。後者在專門的硬體實現上計算更為有效，而前者通常在通用處理器上更為有效。專利的問題也是相關的。一些其他素數的伽羅瓦域的大小和能力也已經提出了，但被密碼專家認為有一點問題。
一般認為在一個有限域乘法群上的離散對數問題（DLP）和橢圓曲線上的離散對數問題（ECDLP）並不等價；ECDLP比DLP要困難的多。
在密碼的使用上，曲線E(q)和其中一個特定的基點G一起被選擇和公布。一個私鑰k被作為隨機整數來選擇；公鑰來公布（注意假設的ECDLP困難性意味著k很難從P中確定）。
這允許一個“秘密”值的建立，這樣Alice和Bob能很容易地計算出，但任何的第三方卻很難得到。另外，Bob在處理期間不會獲得任何關於kA的新知識，因此Alice的私鑰仍然是私有的。
加密
基於這個秘密值，用來對Alice和Bob之間的報文進行加密的實際方法是適應以前的，最初是在其他組中描述使用的離散對數密碼系統。這些系統包括：
- Diffie-Hellman—ECDH；
- MQV— ECMQV；
- ElGamal離散對數密碼體制— ECElGamal；
- 數字簽名算法 —ECDSA。
對於ECC系統來說，完成運行系統所必須的群操作比同樣大小的因數分解系統或模整數離散對數系統要慢。不過，ECC系統的擁護者相信ECDLP問題比DLP或因數分解問題要難的多，並且因此使用ECC能用小的多的密鑰長度來提供同等的安全，在這方面來說它確實比例如RSA之類的更快。到目前為止已經公布的結果趨於支持這個結論，不過一些專家表示懷疑。
ECC被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱算法，因此在對頻寬要求十分緊的連線中會十分有用。
建議
美國國家標準與技術局和ANSI X9已經設定了最小密鑰長度的要求，RSA和DSA是1024位，ECC是160位，相應的對稱分組密碼的密鑰長度是80位。NIST已經公布了一列推薦的橢圓曲線用來保護5個不同的對稱密鑰大小（80, 112, 128, 192, 256）。一般而言，二進制域上的ECC需要的非對稱密鑰的大小是相應的對稱密鑰大小的兩倍。
Certicom是ECC的主要商業支持者，擁有超過130項專利，並且已經以2千5百萬美元的交易獲得了美國國家安全局（NSA）的技術許可。他們也已經發起了許多對ECC算法的挑戰。已經被解決的最複雜的是109位的密鑰，是在2003年初由一個研究團隊破解的。破解密鑰的這個團隊使用了基於生日攻擊的大塊並行攻擊，用超過10,000台奔騰級的PC機連續運行了540天以上。對於ECC推薦的最小密鑰長度163位來說，當前估計需要的計算資源是109位問題的10倍。
在2005年2月16日，NSA宣布決定採用橢圓曲線密碼的戰略作為美國政府標準的一部分，用來保護敏感但不保密的信息。NSA推薦了一組被稱為Suit B的算法，包括用來密鑰交換的Menezes-Qu-Vanstone橢圓曲線和Diffie-Hellman橢圓曲線，用來數字簽名的橢圓曲線數字簽名算法。這一組中也包括AES和SHA。
另見
- SECG（Standards for Efficient Cryptography Group (SECG)）
- 密鑰合意協定
