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

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