橢圓曲線密碼學

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

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

歷史

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

理論

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

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

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

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

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

密鑰交換

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

伽羅瓦域

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

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

在密碼的使用上，會選擇曲線 $E(q)$ 和其中一個特定的基點G，並且公開這些資料。會再選擇一個隨機整數k作為私鑰；公布值為 $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之間的報文進行加密的實際方法是適應以前的，最初是在其他組中描述使用的離散對數密碼系統。這些系統包括：

對於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萬億個托佛利門。因此，橢圓曲線會更先遭到量子計算機的破解。目前還不存在建造如此大型量子計算機的科學技術，因此橢圓曲線密碼學至少在未來十年（或更久）依然是安全的。但是密碼學家已經積極展開了後量子密碼學的研究。其中，超奇異橢圓曲線同源密鑰交換（英語：Supersingular isogeny key exchange）（SIDH）有望取代當前的常規橢圓曲線密鑰交換（ECDH）。

無效曲線攻擊

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

參考文獻

^ Elliptic Curve Cryptography - OpenSSLWiki. wiki.openssl.org. [2020-05-02]. （原始內容存檔於2020-12-04）.
^ Koblitz, N. Elliptic curve cryptosystems. Mathematics of Computation. 1987, 48 (177): 203–209. JSTOR 2007884. doi:10.2307/2007884 .
^ Miller, V. Use of elliptic curves in cryptography. Advances in Cryptology — CRYPTO '85 Proceedings. Lecture Notes in Computer Science 85. 1985: 417–426. ISBN 978-3-540-16463-0. doi:10.1007/3-540-39799-X_31. |journal=被忽略 (幫助)
^ Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-06]. （原始內容存檔於2020-04-04）.
^ Hedabou, M.; Pinel, P.; Beneteau, L. A comb method to render ECC resistant against Side Channel Attacks (PDF). 2004 [2021-12-17]. （原始內容存檔 (PDF)於2021-12-17）.
^ Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system. [2021-12-17]. （原始內容存檔於2014-03-23）.
^ See, for example, Biehl, Ingrid; Meyer, Bernd; Müller, Volker. Differential Fault Attacks on Elliptic Curve Cryptosystems (PDF). Lecture Notes in Computer Science 1880. 2000: 131–146 [2021-12-17]. ISBN 978-3-540-67907-3. doi:10.1007/3-540-44598-6_8. （原始內容存檔 (PDF)於2021-12-17）. |journal=被忽略 (幫助)
^ "Did NSA Put a Secret Backdoor in New Encryption Standard?" （頁面存檔備份，存於網際網路檔案館）. www.schneier.com.
^ Government Announces Steps to Restore Confidence on Encryption Standards. NY Times – Bits Blog. 2013-09-10 [2015-11-06]. （原始內容存檔於2014-07-12）.
^ 存档副本 (PDF). [2021-12-17]. （原始內容存檔 (PDF)於2014-02-26）.
^ Bernstein, Daniel J.; Lange, Tanja. SafeCurves: choosing safe curves for elliptic-curve cryptography. [2016-10-01]. （原始內容存檔於2021-11-09）.
^ Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin. Quantum resource estimates for computing elliptic curve discrete logarithms. 2017. arXiv:1706.06752  [quant-ph].
^ Cohen, Cfir. AMD-SEV: Platform DH key recovery via invalid curve attack (CVE-2019-9836). Seclist Org. 2019-06-25 [2019-07-04]. （原始內容存檔於2019-07-02）. The SEV elliptic-curve (ECC) implementation was found to be vulnerable to an invalid curve attack. At launch-start command, an attacker can send small order ECC points not on the official NIST curves, and force the SEV firmware to multiply a small order point by the firmware’s private DH scalar.

Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation 48, 1987, pp203–209
V. Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.
Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999
Hankerson, Menezes, Vanstone, "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004
L. Washington, "Elliptic Curves: Number Theory and Cryptography", Chapman & Hall/CRC, 2003
Standards for Efficient Cryptography Group (SECG), SEC 1: Elliptic Curve Cryptography, Version 1.0, September 20, 2000. (archived as if Nov 11, 2014)
D. Hankerson, A. Menezes, and S.A. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004.
I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, London Mathematical Society 265, Cambridge University Press, 1999.
I. Blake, G. Seroussi, and N. Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society 317, Cambridge University Press, 2005.
L. Washington, Elliptic Curves: Number Theory and Cryptography, Chapman & Hall / CRC, 2003.
The Case for Elliptic Curve Cryptography, National Security Agency (archived January 17, 2009)
Online Elliptic Curve Cryptography Tutorial, Certicom Corp. (archived here as of March 3, 2016)
K. Malhotra, S. Gardner, and R. Patz, Implementation of Elliptic-Curve Cryptography on Mobile Healthcare Devices, Networking, Sensing and Control, 2007 IEEE International Conference on, London, 15–17 April 2007 Page(s):239–244
Saikat Basu, A New Parallel Window-Based Implementation of the Elliptic Curve Point Multiplication in Multi-Core Architectures, International Journal of Network Security, Vol. 13, No. 3, 2011, Page(s):234–241 (archived here as of March 4, 2016)
Christof Paar, Jan Pelzl, "Elliptic Curve Cryptosystems", Chapter 9 of "Understanding Cryptography, A Textbook for Students and Practitioners". (companion web site contains online cryptography course that covers elliptic curve cryptography), Springer, 2009. (archived here as of April 20, 2016)
Luca De Feo, David Jao, Jerome Plut, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Springer 2011. (archived here as of May 7, 2012)
Jacques Vélu, Courbes elliptiques (...), Société Mathématique de France, 57, 1-152, Paris, 1978. （頁面存檔備份，存於網際網路檔案館）

外部連結

橢圓曲線密碼學使用薦議書，NIST文件（PDF檔）（頁面存檔備份，存於網際網路檔案館）
Certicom press release regarding 109 bit ECC challenge （頁面存檔備份，存於網際網路檔案館）
Certicom線上橢圓曲線密碼學簡介（頁面存檔備份，存於網際網路檔案館）
數位簽章標準，含橢圓曲線密碼學數位簽章標準（ECDSA）（頁面存檔備份，存於網際網路檔案館）
參見Wikisource:Cryptography獲得曲線的算法程序和一些NIST曲線的測試向量
OpenSSL：開源SSL，已支援橢圓曲線密碼學（頁面存檔備份，存於網際網路檔案館）
Crypto++：開源C++橢圓曲線密碼學API
libecc: Open source ECC library （頁面存檔備份，存於網際網路檔案館）
Demo of elliptic curve point counting and domain parameter generation
Primer on elliptical curve cryptography
開源Java密碼學API
橢圓曲線密碼學問答集（頁面存檔備份，存於網際網路檔案館）
The Pairing-Based Crypto Lounge

[1] Elliptic Curve Cryptography - OpenSSLWiki. wiki.openssl.org. [2020-05-02]. （原始內容存檔於2020-12-04）.

[2] Koblitz, N. Elliptic curve cryptosystems. Mathematics of Computation. 1987, 48 (177): 203–209. JSTOR 2007884. doi:10.2307/2007884 .

[3] Miller, V. Use of elliptic curves in cryptography. Advances in Cryptology — CRYPTO '85 Proceedings. Lecture Notes in Computer Science 85. 1985: 417–426. ISBN 978-3-540-16463-0. doi:10.1007/3-540-39799-X_31. |journal=被忽略 (幫助)

[4] Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-06]. （原始內容存檔於2020-04-04）.

[5] Hedabou, M.; Pinel, P.; Beneteau, L. A comb method to render ECC resistant against Side Channel Attacks (PDF). 2004 [2021-12-17]. （原始內容存檔 (PDF)於2021-12-17）.

[6] Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system. [2021-12-17]. （原始內容存檔於2014-03-23）.

[7] See, for example, Biehl, Ingrid; Meyer, Bernd; Müller, Volker. Differential Fault Attacks on Elliptic Curve Cryptosystems (PDF). Lecture Notes in Computer Science 1880. 2000: 131–146 [2021-12-17]. ISBN 978-3-540-67907-3. doi:10.1007/3-540-44598-6_8. （原始內容存檔 (PDF)於2021-12-17）. |journal=被忽略 (幫助)

[8] "Did NSA Put a Secret Backdoor in New Encryption Standard?" （頁面存檔備份，存於網際網路檔案館）. www.schneier.com.

[9] Government Announces Steps to Restore Confidence on Encryption Standards. NY Times – Bits Blog. 2013-09-10 [2015-11-06]. （原始內容存檔於2014-07-12）.

[10] 存档副本 (PDF). [2021-12-17]. （原始內容存檔 (PDF)於2014-02-26）.

[11] Bernstein, Daniel J.; Lange, Tanja. SafeCurves: choosing safe curves for elliptic-curve cryptography. [2016-10-01]. （原始內容存檔於2021-11-09）.

[12] Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin. Quantum resource estimates for computing elliptic curve discrete logarithms. 2017. arXiv:1706.06752  [quant-ph].

[Cohen,_Seclist,_2019-13] Cohen, Cfir. AMD-SEV: Platform DH key recovery via invalid curve attack (CVE-2019-9836). Seclist Org. 2019-06-25 [2019-07-04]. （原始內容存檔於2019-07-02）. The SEV elliptic-curve (ECC) implementation was found to be vulnerable to an invalid curve attack. At launch-start command, an attacker can send small order ECC points not on the official NIST curves, and force the SEV firmware to multiply a small order point by the firmware’s private DH scalar.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

歷史

理論