椭圆曲线密码学

椭圆曲线密码学（英語：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]

歷史

理論