橢圓曲線密碼學

橢圓曲線密碼學（英語：Elliptic Curve Cryptography，縮寫：ECC）是一種基於橢圓曲線數學的公開密鑰加密演算法。

ECC的主要優勢是它相比RSA加密演算法使用較小的密鑰長度並提供相當等級的安全性^[1]。ECC的另一個優勢是可以定義群之間的雙線性映射，基於Weil對或是Tate對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。

歷史

橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz（英語：Neal Koblitz）^[2]和Victor Miller（英語：Victor Miller）^[3]分別獨立提出的。橢圓曲線密碼學的演算法是在2004年至2005年開始廣泛應用。

理論

針對密碼學應用上的橢圓曲線是在有限域（不是實數域）的平面曲線，其方程式如下：

${\displaystyle y^{2}=x^{3}+ax+b,\,}$

有一個特別的無窮遠點（標示為∞）。座標會選定為特定的有限域，其特徵不等於2或是3，也有可能是更複雜的曲線方程。

由橢圓曲線產生的集合是阿貝爾群，以無窮遠點為單位元。此群的結構會繼承以下代數簇中除子的結構：

${\displaystyle \mathrm {Div} ^{0}(E)\to \mathrm {Pic} ^{0}(E)\simeq E,\,}$

密鑰交換

主條目：橢圓曲線迪菲-赫爾曼密鑰交換

橢圓曲線密碼學的許多形式有稍微的不同，所有的都依賴於被廣泛承認的解決「橢圓曲線離散對數」問題的困難性上，對應有限域上橢圓曲線的群。

伽羅瓦域

對橢圓曲線來說最流行的有限域是以素數為模的整數域（參見模運算）${\displaystyle GF(p)}$，或是特徵為2的伽羅瓦域 GF（2^m）。後者在專門的硬件實現上計算更為有效，而前者通常在通用處理器上更為有效。專利的問題也是相關的。一些其他素數的伽羅瓦域的大小和能力也已經提出了，但被密碼專家認為有一點問題。

給定一條橢圓曲線E以及一個域${\displaystyle GF(q)}$，考慮具有${\displaystyle (x,y)}$形式有理數點${\displaystyle E(q)}$的阿貝爾群，其中x和y都在${\displaystyle GF(q)}$中並且定義在這條曲線上的群運算"+"（運算"+"在條目橢圓曲線中描述）。然後定義第二個運算"*" | Z×${\displaystyle E(q)->E(q)}$：如果P是${\displaystyle E(q)}$上的某個點，那麼定義${\displaystyle 2*P=P+P,3*P=2*P+P=P+P+P}$等等。針對給定整數j和k，${\displaystyle j*(k*P)=(jk)*P=k*(j*P)}$。橢圓曲線離散對數問題（ECDLP）就是給定點P和Q，確定整數k使${\displaystyle k*P=Q}$。 -- 一般認為在一個有限域乘法群上的離散對數問題（DLP）和橢圓曲線上的離散對數問題（ECDLP）並不等價；ECDLP比DLP要困難的多。

在密碼的使用上，會選擇曲線${\displaystyle E(q)}$和其中一個特定的基點G，並且公開這些資料。會再選擇一個隨機整數k作為私鑰；公布值為${\displaystyle P=k*G}$的公鑰（注意假設的ECDLP困難性意味着k很難從P中確定）。如果Alice和Bob有私鑰k_A和k_B，公鑰是P_A和P_B，那麼Alice能計算k_A*P_B=(k_A*k_B)*G；Bob能計算同樣的值k_B*P_A=(k_B*k_A)*G。

這允許一個「秘密」值的建立，這樣Alice和Bob能很容易地計算出，但任何的第三方卻很難得到。另外，Bob在處理期間不會獲得任何關於k_A的新知識，因此Alice的私鑰仍然是私有的。

加密

基於這個秘密值，用來對Alice和Bob之間的報文進行加密的實際方法是適應以前的，最初是在其他組中描述使用的離散對數密碼系統。這些系統包括：

• 橢圓曲線迪菲-赫爾曼密鑰交換（ECDH）
• MQV（英語：Menezes–Qu–Vanstone）（ECMQV）
• ElGamal離散對數密碼體制（ECElGamal）
• 橢圓曲線數字簽名算法（ECDSA）

對於ECC系統來說，完成運行系統所必須的群操作比同樣大小的因數分解系統或模整數離散對數系統要慢。不過，ECC系統的擁護者相信ECDLP問題比DLP或因數分解問題要難的多，並且因此使用ECC能用小的多的密鑰長度來提供同等的安全，在這方面來說它確實比例如RSA之類的更快。到目前為止已經公布的結果趨於支持這個結論，不過一些專家表示懷疑。

ECC被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱算法，因此在對帶寬要求十分緊的連接中會十分有用。

建議

美國國家標準與技術局和ANSI X9已經設定了最小密鑰長度的要求，RSA和DSA是最小2048位，ECC是最小224位，相應的對稱密鑰加密的密鑰長度是最小128位，這樣的組合在2030年以前是安全的^[4]。

在2005年2月16日，NSA宣布決定採用橢圓曲線密碼的戰略作為美國政府標準的一部分，用來保護敏感但不保密的信息。NSA推薦了一組被稱為Suit B的算法，包括用來密鑰交換的橢圓曲線Menezes-Qu-Vanstone（ECMQV）和橢圓曲線Diffie-Hellman（ECDH），用來數字簽名的橢圓曲線數字簽名算法。這一組中也包括AES和SHA。

安全性

旁路攻擊

橢圓曲線密碼學和其他的離散對數不同，在離散對數中可以用相同的程序處理平方以及乘法，但橢圓曲線上的加法在加倍（P = Q）和一般加法（P ≠ Q）上會因為使用的座標系統而有顯著的不同。因此有關旁路攻擊（例如時間或能量分析）的防治就格外的重要。例如用固定模式窗口（fixed pattern window，也稱為comb）的方式^{[需要解釋][5]}（這不會增加運算時間）。另外也可以使用愛德華曲線（英語：Edwards curve），這是一類特別的橢圓曲線，其中的加倍和加法可以用同一個運算完成^[6]。另一個ECC系統的疑慮是差別錯誤分析的風險，特別是在智能卡上的應用^[7]。

後門

密碼學專家擔心，美國國家安全局（NSA）可能已在至少一個以橢圓曲線為基礎的偽亂數產生器中置入kleptographic（英語：kleptographic）後門^[8]。前美國中央情報局（CIA）職員愛德華·斯諾登所洩漏的內部摘要暗示，NSA在雙橢圓曲線確定性隨機比特生成器標準中加入後門^[9]。微軟公司的研究人員針對此標準中一個的疑似後門進行分析，並得出結論：擁有此演算法私鑰的攻擊者，可以只根據32位元組的PRNG輸出，找到加密的密鑰^[10]。

密碼學家發起了「SafeCurves」計劃，整理並列出安全性易實現且設計過程完全公開可驗證的曲線，以減少曲線被植入後門的可能性^[11]。

量子計算攻擊

如果攻擊者擁有大型量子計算機，那麼他可以使用秀爾算法解決離散對數問題，從而破解私鑰和共享秘密。目前的估算認為：破解256位素數域上的橢圓曲線，需要2330個量子比特與1260億個托佛利門。^[12]相比之下，使用秀爾算法破解2048位的RSA則需要4098個量子比特與5.2萬億個托佛利門。因此，橢圓曲線會更先遭到量子計算機的破解。目前還不存在建造如此大型量子計算機的科學技術，因此橢圓曲線密碼學至少在未來十年（或更久）依然是安全的。但是密碼學家已經積極展開了後量子密碼學的研究。

無效曲線攻擊

若ECC是在虛擬機器運作，攻擊者可以用無效的曲線來取得完整的PDH私鑰^[13]。

相關條目

• SECG（英語：SECG）（高效密碼學標準組）
• 橢圓曲線數字簽名算法
• 橢圓曲線迪菲-赫爾曼金鑰交換
• 公開金鑰加密
• 抽象代數
• 奇幻熊
• 密鑰合意協議（英語：Key-agreement protocol）
• ECMQC（英語：ECMQC）
• 加密貨幣
• Curve25519
• FourQ（英語：FourQ）
• DNSCurve
• RSA加密演算法
• 橢圓曲線密碼學專利（英語：ECC patents）
• 橢圓曲線迪菲-赫爾曼金鑰交換 (ECDH)
• 橢圓曲線數字簽名算法 (ECDSA)
• EdDSA
• ECMQV（英語：ECMQV）
• 橢圓曲線的純量乘法
• 網絡編碼的同態簽名（英語：Homomorphic Signatures for Network Coding）
• 超橢圓曲線密碼學（英語：Hyperelliptic curve cryptography）
• 基於配對的密碼學（英語：Pairing-based cryptography）
• 公開密鑰加密
• 量子密碼學
• 超奇異同基因密鑰交換（英語：Supersingular isogeny key exchange）