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

橢圓曲線迪菲-赫爾曼密鑰交換（英語：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].