橢圓曲線迪菲-赫爾曼金鑰交換
橢圓曲線迪菲-赫爾曼密鑰交換(英語:Elliptic Curve Diffie–Hellman key exchange,縮寫為ECDH),是一種匿名的密鑰合意協議(Key-agreement protocol),這是迪菲-赫爾曼密鑰交換的變種,採用橢圓曲線密碼學來加強性能與安全性。在這個協定下,雙方利用由橢圓曲線密碼學建立的公鑰與私鑰對,在一個不安全的通道中,建立起安全的共有加密資料。[1][2][3]臨時ECDH(ECDH Ephemeral,ECDHE)能夠提供前向安全性。
密鑰建立協議
[編輯]假設愛麗絲與鮑勃需要建立共享密鑰,但他們之間唯一的信道可能被第三方伊夫竊聽,此時可以使用橢圓曲線密碼學。首先,需要事先提前約定域參數(質數域時為,二元域時為),它是公開信息,定義了所使用的橢圓曲線;然後,雙方準備符合條件的密鑰(在區間隨機一個整數作為私鑰,並與基點相乘得到點,即公鑰),此時愛麗絲的密鑰為,鮑勃的密鑰為;接著,雙方將自己的公鑰或發送給對方;
愛麗絲計算點,鮑勃計算點,這就得到了雙方的共享秘密(即該點的x坐標)。由於,因此雙方得到的是相等的。在實際應用中,常使用和其他相關參數作為一個密鑰衍生函數的輸入,密鑰為其輸出。
在這個過程中,伊夫知道橢圓曲線的域參數,但愛麗絲只透露了她的公鑰,伊夫無法獲得她的私鑰,除非伊夫能夠解決橢圓曲線上的離散對數問題,這個問題被認為是困難的。同理,鮑勃的私鑰也是安全的。若伊夫要計算出雙方的共享秘密,就需要求解迪菲-赫爾曼問題,而計算離散對數是此問題的已知最優解法,伊夫無法用其他方式直接解出共享秘密。
但是,如果雙方使用的隨機數生成器存在安全隱患,伊夫就可能預測私鑰和。此外,上述的密鑰交換是匿名的,雙方沒有進行身份驗證。如果攻擊者有能力篡改信息,就能冒充雙方的身份。因此,有必要用其他的方式進行身分驗證,例如公鑰基礎設施。
量子計算機
[編輯]如果攻擊者擁有大型量子計算機,那麼他可以使用秀爾算法解決離散對數問題,從而破解私鑰和共享秘密。目前的估算認為:破解256位素數域上的橢圓曲線,需要2330個量子比特與1260億個托佛利門。[4]相比之下,使用秀爾算法破解2048位的RSA則需要4098個量子比特與5.2萬億個托佛利門。因此,橢圓曲線會更先遭到量子計算機的破解。目前還不存在建造如此大型量子計算機的科學技術,因此橢圓曲線密碼學至少在未來十年(或更久)依然是安全的。但是密碼學家已經積極展開了後量子密碼學的研究。其中,超奇異橢圓曲線同源密鑰交換(SIDH)有望取代當前的常規橢圓曲線密鑰交換(ECDH)。
註釋
[編輯]- ^ NIST, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (頁面存檔備份,存於網際網路檔案館), March, 2006.
- ^ Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography (頁面存檔備份,存於網際網路檔案館), Version 2.0, May 21, 2009.
- ^ NSA Suite B Cryptography, Suite B Implementers' Guide to NIST SP 800-56A (頁面存檔備份,存於網際網路檔案館), July 28, 2009.
- ^ Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin. Quantum resource estimates for computing elliptic curve discrete logarithms. 2017. arXiv:1706.06752
[quant-ph].
|