椭圆曲线迪菲-赫尔曼金钥交换

椭圆曲线迪菲-赫尔曼密钥交换（英语：Elliptic Curve Diffie–Hellman key exchange，缩写为ECDH），是一种匿名的密钥合意协议（英语：Key-agreement protocol）（Key-agreement protocol），这是迪菲－赫尔曼密钥交换的变种，采用椭圆曲线密码学来加强性能与安全性。在这个协定下，双方利用由椭圆曲线密码学建立的公钥与私钥对，在一个不安全的通道中，建立起安全的共有加密资料。^[1][2][3]临时ECDH（ECDH Ephemeral，ECDHE）能够提供前向安全性。

密钥建立协议

参见：椭圆曲线密码学

假设爱丽丝与鲍勃需要建立共享密钥，但他们之间唯一的信道可能被第三方伊夫窃听，此时可以使用椭圆曲线密码学。首先，需要事先提前约定域参数（质数域${\displaystyle F_{p}}$时为${\displaystyle (p,a,b,G,n,h)}$，二元域${\displaystyle F_{2}}$时为${\displaystyle (m,f(x),a,b,G,n,h)}$），它是公开信息，定义了所使用的椭圆曲线；然后，双方准备符合条件的密钥（在区间${\displaystyle [1,n-1]}$随机一个整数作为私钥${\displaystyle d}$，并与基点${\displaystyle G}$相乘得到点${\displaystyle Q=dG}$，即公钥），此时爱丽丝的密钥为${\displaystyle (d_{A},Q_{A})}$，鲍勃的密钥为${\displaystyle (d_{B},Q_{B})}$；接着，双方将自己的公钥${\displaystyle Q_{A}}$或${\displaystyle Q_{B}}$发送给对方；

爱丽丝计算点${\displaystyle (x_{k},y_{k})=d_{A}Q_{B}}$，鲍勃计算点${\displaystyle (x_{k},y_{k})=d_{B}Q_{A}}$，这就得到了双方的共享秘密${\displaystyle x_{k}}$（即该点的x坐标）。由于${\displaystyle d_{A}Q_{B}=d_{A}d_{B}G=d_{B}d_{A}G=d_{B}Q_{A}}$，因此双方得到的${\displaystyle x_{k}}$是相等的。在实际应用中，常使用${\displaystyle x_{k}}$和其他相关参数作为一个密钥衍生函数（英语：Key derivation function）的输入，密钥为其输出。

在这个过程中，伊夫知道椭圆曲线的域参数，但爱丽丝只透露了她的公钥${\displaystyle Q_{A}}$，伊夫无法获得她的私钥${\displaystyle d_{A}}$，除非伊夫能够解决椭圆曲线上的离散对数问题，这个问题被认为是困难的。同理，鲍勃的私钥也是安全的。若伊夫要计算出双方的共享秘密${\displaystyle x_{k}}$，就需要求解迪菲-赫尔曼问题（英语：Diffie–Hellman problem），而计算离散对数是此问题的已知最优解法，伊夫无法用其他方式直接解出共享秘密。

但是，如果双方使用的随机数生成器存在安全隐患，伊夫就可能预测私钥${\displaystyle d_{A}}$和${\displaystyle d_{B}}$。此外，上述的密钥交换是匿名的，双方没有进行身份验证。如果攻击者有能力篡改信息，就能冒充双方的身份。因此，有必要用其他的方式进行身份验证，例如公钥基础设施。

量子计算机

如果攻击者拥有大型量子计算机，那么他可以使用秀尔算法解决离散对数问题，从而破解私钥和共享秘密。目前的估算认为：破解256位素数域上的椭圆曲线，需要2330个量子比特与1260亿个托佛利门。^[4]相比之下，使用秀尔算法破解2048位的RSA则需要4098个量子比特与5.2万亿个托佛利门。因此，椭圆曲线会更先遭到量子计算机的破解。目前还不存在建造如此大型量子计算机的科学技术，因此椭圆曲线密码学至少在未来十年（或更久）依然是安全的。但是密码学家已经积极展开了后量子密码学的研究。其中，超奇异椭圆曲线同源密钥交换（英语：Supersingular isogeny key exchange）（SIDH）有望取代当前的常规椭圆曲线密钥交换（ECDH）。

注释

1. NIST, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography （页面存档备份，存于互联网档案馆）, March, 2006.
2. Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography （页面存档备份，存于互联网档案馆）, Version 2.0, May 21, 2009.
3. NSA Suite B Cryptography, Suite B Implementers' Guide to NIST SP 800-56A （页面存档备份，存于互联网档案馆）, July 28, 2009.
4. Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin. Quantum resource estimates for computing elliptic curve discrete logarithms. 2017. arXiv:1706.06752  [quant-ph].