Loading AI tools
基于有限域椭圆曲线代数结构的公钥密码学方法 来自维基百科,自由的百科全书
橢圓曲線密碼學(英語:Elliptic Curve Cryptography,縮寫:ECC)是一種基於橢圓曲線數學的公開密鑰加密演算法。
ECC的主要優勢是它相比RSA加密演算法使用較小的密鑰長度並提供相當等級的安全性[1]。ECC的另一個優勢是可以定義群之間的雙線性映射,基於Weil對或是Tate對;雙線性映射已經在密碼學中發現了大量的應用,例如基於身份的加密。
橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz[2]和Victor Miller[3]分別獨立提出的。橢圓曲線密碼學的演算法是在2004年至2005年開始廣泛應用。
針對密碼學應用上的橢圓曲線是在有限域(不是實數域)的平面曲線,其方程式如下:
有一個特別的無窮遠點(標示為∞)。座標會選定為特定的有限域,其特徵不等於2或是3,也有可能是更複雜的曲線方程。
由橢圓曲線產生的集合是阿貝爾群,以無窮遠點為單位元。此群的結構會繼承以下代數簇中除子的結構:
橢圓曲線密碼學的許多形式有稍微的不同,所有的都依賴於被廣泛承認的解決「橢圓曲線離散對數」問題的困難性上,對應有限域上橢圓曲線的群。
對橢圓曲線來說最流行的有限域是以素數為模的整數域(參見模運算),或是特徵為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有私鑰kA和kB,公鑰是PA和PB,那麼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已經設定了最小密鑰長度的要求,RSA和DSA是最小2048位,ECC是最小224位,相應的對稱密鑰加密的密鑰長度是最小128位,這樣的組合在2030年以前是安全的[4]。
在2005年2月16日,NSA宣布決定採用橢圓曲線密碼的戰略作為美國政府標準的一部分,用來保護敏感但不保密的信息。NSA推薦了一組被稱為Suit B的算法,包括用來密鑰交換的橢圓曲線Menezes-Qu-Vanstone(ECMQV)和橢圓曲線Diffie-Hellman(ECDH),用來數字簽名的橢圓曲線數字簽名算法。這一組中也包括AES和SHA。
橢圓曲線密碼學和其他的離散對數不同,在離散對數中可以用相同的程序處理平方以及乘法,但橢圓曲線上的加法在加倍(P = Q)和一般加法(P ≠ Q)上會因為使用的座標系統而有顯著的不同。因此有關旁路攻擊(例如時間或能量分析)的防治就格外的重要。例如用固定模式窗口(fixed pattern window,也稱為comb)的方式[需要解釋][5](這不會增加運算時間)。另外也可以使用愛德華曲線,這是一類特別的橢圓曲線,其中的加倍和加法可以用同一個運算完成[6]。另一個ECC系統的疑慮是差別錯誤分析的風險,特別是在智慧卡上的應用[7]。
密碼學專家擔心,美國國家安全局(NSA)可能已在至少一個以橢圓曲線為基礎的偽亂數產生器中置入kleptographic後門[8]。前美國中央情報局(CIA)職員愛德華·斯諾登所洩漏的內部摘要暗示,NSA在雙橢圓曲線確定性隨機比特生成器標準中加入後門[9]。微軟公司的研究人員針對此標準中一個的疑似後門進行分析,並得出結論:擁有此演算法私鑰的攻擊者,可以只根據32位元組的PRNG輸出,找到加密的密鑰[10]。
密碼學家發起了「SafeCurves」計劃,整理並列出安全性易實現且設計過程完全公開可驗證的曲線,以減少曲線被植入後門的可能性[11]。
如果攻擊者擁有大型量子計算機,那麼他可以使用秀爾算法解決離散對數問題,從而破解私鑰和共享秘密。目前的估算認為:破解256位素數域上的橢圓曲線,需要2330個量子比特與1260億個托佛利門。[12]相比之下,使用秀爾算法破解2048位的RSA則需要4098個量子比特與5.2萬億個托佛利門。因此,橢圓曲線會更先遭到量子計算機的破解。目前還不存在建造如此大型量子計算機的科學技術,因此橢圓曲線密碼學至少在未來十年(或更久)依然是安全的。但是密碼學家已經積極展開了後量子密碼學的研究。其中,超奇異橢圓曲線同源密鑰交換(SIDH)有望取代當前的常規橢圓曲線密鑰交換(ECDH)。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.