橢圓曲線密碼學
橢圓曲線密碼學（英語：Elliptic Curve Cryptography，縮寫：ECC）是一種基於橢圓曲線數學的公開金鑰加密演算法。
ECC的主要優勢是它相比RSA加密演算法使用較小的金鑰長度並提供相當等級的安全性[1]。ECC的另一個優勢是可以定義群之間的雙線性對映，基於Weil對或是Tate對；雙線性對映已經在密碼學中發現了大量的應用，例如基於身份的加密。
歷史[編輯]
橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz[2]和Victor Miller[3]分別獨立提出的。橢圓曲線密碼學的演算法是在2004年至2005年開始廣泛應用。
理論[編輯]
針對密碼學應用上的橢圓曲線是在有限體（不是實數體）的平面曲線，其方程式如下：
- <math>y^2 = x^3 + ax + b, \, </math>
有一個特別的無窮遠點（標示為∞）。座標會選定為特定的有限體，其特徵不等於2或是3，也有可能是更複雜的曲線方程。
由橢圓曲線產生的集合是阿貝爾群，以無窮遠點為單位元素。此群的結構會繼承以下代數簇中除子的結構：
- <math>\mathrm{Div}^0 (E) \to \mathrm{Pic}^0 (E) \simeq E, \, </math>
金鑰交換[編輯]
橢圓曲線密碼學的許多形式有稍微的不同，所有的都依賴於被廣泛承認的解決「橢圓曲線離散對數」問題的困難性上，對應有限體上橢圓曲線的群。
伽羅瓦體[編輯]
對橢圓曲線來說最流行的有限體是以質數為模的整數體（參見模運算）<math>GF(p)</math>，或是特徵為2的伽羅瓦體 GF（2m）。後者在專門的硬件實現上計算更為有效，而前者通常在通用處理器上更為有效。專利的問題也是相關的。一些其他質數的伽羅瓦體的大小和能力也已經提出了，但被密碼專家認為有一點問題。
給定一條橢圓曲線E以及一個域<math>GF(q)</math>，考慮具有<math>(x, y)</math>形式有理數點<math>E(q)</math>的阿貝爾群，其中x和y都在<math>GF(q)</math>中並且定義在這條曲線上的群運算"+"（運算"+"在條目橢圓曲線中描述）。然後定義第二個運算"*" | Z×<math>E(q)->E(q)</math>：如果P是<math>E(q)</math>上的某個點，那麼定義<math>2*P=P+P, 3*P=2*P+P=P+P+P</math>等等。針對給定整數j和k，<math>j*(k*P)=(jk)*P=k*(j*P)</math>。橢圓曲線離散對數問題（ECDLP）就是給定點P和Q，確定整數k使<math>k*P=Q</math>。 -- 一般認為在一個有限體乘法群上的離散對數問題（DLP）和橢圓曲線上的離散對數問題（ECDLP）並不等價；ECDLP比DLP要困難的多。
在密碼的使用上，會選擇曲線<math>E(q)</math>和其中一個特定的基點G，並且公開這些資料。會再選擇一個隨機整數k作為私鑰；公佈值為<math>P=k*G</math>的公鑰（注意假設的ECDLP困難性意味着k很難從P中確定）。如果Alice和Bob有私鑰kA和kB，公鑰是PA和PB，那麼Alice能計算kA*PB=(kA*kB)*G；Bob能計算同樣的值kB*PA=(kB*kA)*G。
這允許一個「秘密」值的建立，這樣Alice和Bob能很容易地計算出，但任何的第三方卻很難得到。另外，Bob在處理期間不會獲得任何關於kA的新知識，因此Alice的私鑰仍然是私有的。
加密[編輯]
基於這個秘密值，用來對Alice和Bob之間的報文進行加密的實際方法是適應以前的，最初是在其他組中描述使用的離散對數密碼系統。這些系統包括：
- 橢圓曲線迪菲-赫爾曼金鑰交換（ECDH）
- MQV（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]（這不會增加運算時間）。另外也可以使用愛德華曲線，這是一類特別的橢圓曲線，其中的加倍和加法可以用同一個運算完成[6]。另一個ECC系統的疑慮是差別錯誤分析的風險，特別是在智能卡上的應用[7]。
後門[編輯]
密碼學專家擔心，美國國家安全域（NSA）可能已在至少一個以橢圓曲線為基礎的偽亂數產生器中置入kleptographic後門[8]。前美國中央情報局（CIA）職員愛德華·斯諾登所洩漏的內部摘要暗示，NSA在雙橢圓曲線確定性隨機位元生成器標準中加入後門[9]。微軟公司的研究人員針對此標準中一個的疑似後門進行分析，並得出結論：擁有此演算法私鑰的攻擊者，可以只根據32位元組的PRNG輸出，找到加密的金鑰[10]。
密碼學家發起了「SafeCurves」計劃，整理並列出安全性易實現且設計過程完全公開可驗證的曲線，以減少曲線被植入後門的可能性[11]。
量子計算攻擊[編輯]
如果攻擊者擁有大型量子電腦，那麼他可以使用秀爾演算法解決離散對數問題，從而破解私鑰和共用秘密。目前的估算認為：破解256位質數域上的橢圓曲線，需要2330個量子位元與1260億個托佛利閘。[12]相比之下，使用秀爾演算法破解2048位元的RSA則需要4098個量子位元與5.2萬億個托佛利閘。因此，橢圓曲線會更先遭到量子電腦的破解。目前還不存在建造如此大型量子電腦的科學技術，但是密碼學家已經積極展開了後量子密碼學的研究。
無效曲線攻擊[編輯]
若ECC是在虛擬機器運作，攻擊者可以用無效的曲線來取得完整的PDH私鑰[13]。
相關條目[編輯]
- SECG（高效密碼學標準組）
- 橢圓曲線數碼簽章演算法
- 橢圓曲線迪菲-赫爾曼金鑰交換
- 公開金鑰加密
- 抽象代數
- 奇幻熊
- 金鑰合意協定
- ECMQC
- 加密貨幣
- Curve25519
- FourQ
- DNSCurve
- RSA加密演算法
- 橢圓曲線密碼學專利
- 橢圓曲線迪菲-赫爾曼金鑰交換 (ECDH)
- 橢圓曲線數碼簽章演算法 (ECDSA)
- EdDSA
- ECMQV
- 橢圓曲線的純量乘法
- 網絡編碼的同態簽名
- 超橢圓曲線密碼學
- 基於配對的密碼學
- 公開金鑰加密
- 量子密碼學
- 超奇異同基因金鑰交換
參考文獻[編輯]
- ^ 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