橢圓曲線密碼學

維基百科,自由的百科全書
跳至導覽 跳至搜尋

橢圓曲線密碼學(英語:Elliptic Curve Cryptography,縮寫:ECC)是一種基於橢圓曲線數學公開密鑰加密演算法。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz英語Neal KoblitzVictor Miller英語Victor Miller分別獨立提出的。

ECC的主要優勢是它相比RSA加密演算法使用較小的密鑰長度並提供相當等級的安全性[1]。ECC的另一個優勢是可以定義群之間的雙線性映射,基於Weil對或是Tate對;雙線性映射已經在密碼學中發現了大量的應用,例如基於身份的加密

密鑰交換[編輯]

橢圓曲線密碼學的許多形式有稍微的不同,所有的都依賴於被廣泛承認的解決橢圓曲線離散對數問題的困難性上,對應有限域橢圓曲線的群。

伽羅瓦域[編輯]

對橢圓曲線來說最流行的有限域是以素數為模的整數域(參見模運算),或是特徵為2的伽羅瓦域 GF(2m)。後者在專門的硬體實現上計算更為有效,而前者通常在通用處理器上更為有效。專利的問題也是相關的。一些其他素數的伽羅瓦域的大小和能力也已經提出了,但被密碼專家認為有一點問題。

給定一條橢圓曲線E以及一個域,我們考慮具有形式有理數點阿貝爾群,其中x和y都在中並且定義在這條曲線上的群運算"+"(運算"+"在文章橢圓曲線中描述)。我們然後定義第二個運算"*" | Z×:如果P是上的某個點,那麼我們定義等等。注意給定整數j和k,。橢圓曲線離散對數問題(ECDLP)就是給定點P和Q,確定整數k使。 -- 一般認為在一個有限域乘法群上的離散對數問題(DLP)和橢圓曲線上的離散對數問題(ECDLP)並不等價;ECDLP比DLP要困難的多。

在密碼的使用上,曲線和其中一個特定的基點G一起被選擇和公布。一個私鑰k被作為隨機整數來選擇;值被作為公鑰來公布(注意假設的ECDLP困難性意味著k很難從P中確定)。如果Alice和Bob有私鑰kAkB,公鑰是PAPB,那麼Alice能計算kA*PB=(kA*kB)*G;Bob能計算同樣的值kB*PA=(kB*kA)*G

這允許一個「秘密」值的建立,這樣Alice和Bob能很容易地計算出,但任何的第三方卻很難得到。另外,Bob在處理期間不會獲得任何關於kA的新知識,因此Alice的私鑰仍然是私有的。

加密[編輯]

基於這個秘密值,用來對Alice和Bob之間的報文進行加密的實際方法是適應以前的,最初是在其他組中描述使用的離散對數密碼系統。這些系統包括:

對於ECC系統來說,完成運行系統所必須的群操作比同樣大小的因數分解系統或模整數離散對數系統要慢。不過,ECC系統的擁護者相信ECDLP問題比DLP或因數分解問題要難的多,並且因此使用ECC能用小的多的密鑰長度來提供同等的安全,在這方面來說它確實比例如RSA之類的更快。到目前為止已經公布的結果趨於支持這個結論,不過一些專家表示懷疑。

ECC被廣泛認為是在給定密鑰長度的情況下,最強大的非對稱算法,因此在對帶寬要求十分緊的連接中會十分有用。

建議[編輯]

美國國家標準與技術局ANSI X9已經設定了最小密鑰長度的要求,RSADSA是最小2048位,ECC是最小224位,相應的對稱密鑰加密的密鑰長度是最小128位,這樣的組合在2030年以前是安全的[2]

在2005年2月16日,NSA宣布決定採用橢圓曲線密碼的戰略作為美國政府標準的一部分,用來保護敏感但不保密的信息。NSA推薦了一組被稱為Suit B的算法,包括用來密鑰交換的橢圓曲線Menezes-Qu-Vanstone(ECMQV)和橢圓曲線Diffie-HellmanECDH),用來數字簽名橢圓曲線數字簽名算法。這一組中也包括AESSHA

安全性[編輯]

如果攻擊者擁有大型量子計算機,那麼他可以使用秀爾算法解決離散對數問題,從而破解私鑰和共享秘密。目前的估算認為:破解256位素數域上的橢圓曲線,需要2330個量子比特與1260億個托佛利門[3]相比之下,使用秀爾算法破解2048位的RSA則需要4098個量子比特與5.2萬億個托佛利門。因此,橢圓曲線會更先遭到量子計算機的破解。目前還不存在建造如此大型量子計算機的科學技術,因此橢圓曲線密碼學至少在未來十年(或更久)依然是安全的。但是密碼學家已經積極展開了後量子密碼學的研究。其中,超奇異橢圓曲線同源密鑰交換英語Supersingular isogeny key exchange(SIDH)有望取代當前的常規橢圓曲線密鑰交換(ECDH)。

另見[編輯]

參考文獻[編輯]

外部連結[編輯]

  1. ^ Elliptic Curve Cryptography - OpenSSLWiki. wiki.openssl.org. [2020-05-02]. 
  2. ^ Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-06]. 
  3. ^ Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin. Quantum resource estimates for computing elliptic curve discrete logarithms. 2017. arXiv:1706.06752 [quant-ph].