椭圆曲线密码学

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

历史

理论