椭圆曲线密码学

椭圆曲线在密码学中的使用是在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万亿个托佛利门。因此，椭圆曲线会更先遭到量子计算机的破解。目前还不存在建造如此大型量子计算机的科学技术，因此椭圆曲线密码学至少在未来十年（或更久）依然是安全的。但是密码学家已经积极展开了后量子密码学的研究。其中，超奇异椭圆曲线同源密钥交换（英语：Supersingular isogeny key exchange）（SIDH）有望取代当前的常规椭圆曲线密钥交换（ECDH）。

无效曲线攻击

若ECC是在虚拟机器运作，攻击者可以用无效的曲线来取得完整的PDH私钥^[13]。