橢圓曲線迪菲-赫爾曼金鑰交換

(重定向自ECDH

橢圓曲線迪菲-赫爾曼密钥交換(英語:Elliptic Curve Diffie–Hellman key exchange,縮寫為ECDH),是一種匿名的密鑰合意協議英语Key-agreement protocol(Key-agreement protocol),這是迪菲-赫尔曼密钥交换的變種,採用橢圓曲線密码学來加強性能与安全性。在這個協定下,雙方利用由橢圓曲線密码学建立的公鑰與私鑰對,在一個不安全的通道中,建立起安全的共有加密資料[1][2][3]臨時ECDH(ECDH Ephemeral,ECDHE)能夠提供前向安全性

密鑰建立協議

假设爱丽丝与鲍勃需要建立共享密钥,但他们之间唯一的信道可能被第三方伊夫窃听,此时可以使用椭圆曲线密码学。首先,需要事先提前约定域参数(質数域 时为 ,二元域 时为 ),它是公开信息,定义了所使用的椭圆曲线;然后,双方准备符合条件的密钥(在区间 随机一个整数作为私钥 ,并与基点 相乘得到点 ,即公钥),此时爱丽丝的密钥为 ,鲍勃的密钥为 ;接着,双方将自己的公钥  发送给对方;

爱丽丝计算点 ,鲍勃计算点 ,这就得到了双方的共享秘密 (即该点的x坐标)。由于 ,因此双方得到的 是相等的。在实际应用中,常使用 和其他相关参数作为一个密钥衍生函数英语Key derivation function的输入,密钥为其输出。

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

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

量子计算机

如果攻击者拥有大型量子计算机,那么他可以使用秀尔算法解决离散对数问题,从而破解私钥和共享秘密。目前的估算认为:破解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].