橢圓曲線密碼學

橢圓曲線密碼學(ECC, Elliptic curve cryptography)是基於橢圓曲線數學的一種公鑰密碼的方法。

橢圓曲線密碼學

ECC, Elliptic curve cryptography)是基於橢圓曲線數學的一種公鑰密碼的方法。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。
ECC的主要優勢是在某些情況下它比其他的方法使用更小的密鑰——比如RSA——提供相當的或更高等級的安全。ECC的另一個優勢是可以定義群之間的雙線性映射,基於Weil對或是Tate對;雙線性映射已經在密碼學中發現了大量的套用,例如基於身份的加密。不過一個缺點是加密和解密操作的實現比其他機制花費的時間長。
橢圓曲線密碼學的許多形式有稍微的不同,所有的都依賴於被廣泛承認的解決橢圓曲線離散對數問題的困難性上,對應有限域上橢圓曲線的群。
對橢圓曲線來說最流行的有限域是以素數為模的整數域(參見 模運算)<math>GF(p)</math>,或是特徵為2的伽羅華域GF(2m)。後者在專門的硬體實現上計算更為有效,而前者通常在通用處理器上更為有效。專利的問題也是相關的。一些其他素數的伽羅華域的大小和能力也已經提出了,但被密碼專家認為有一點問題。
給定一條橢圓曲線E以及一個域<math>GF(q)</math>,我們考慮具有<math>(x, y)</math>形式有理數點<math>E(q)</math>的阿貝爾群,其中x和y都在<math>GF(q)</math>中並且定義在這條曲線上的群運算"+"在文章橢圓曲線中描述。我們然後定義第二個運算"*" | Z×<math>E(q)->E(q)</math>:如果P是<math>E(q)</math>上的某個點,那么我們定義<math>2*P=P+P, 3*P=2*P+P=P+P+P</math>等等。注意給定整數 j和k,<math>j*(k*P)=(j*k)*P=k*(j*P)</math>。橢圓曲線離散對數問題(ECDLP)就是給定點P和Q,確定整數k使<math>k*P=Q</math>。
一般認為在一個有限域乘法群上的離散對數問題(DLP)和橢圓曲線上的離散對數問題(ECDLP)並不等價;ECDLP比DLP要困難的多。
在密碼的使用上,曲線<math>E(q)</math>和其中一個特定的基點G一起被選擇和公布。一個私鑰k被作為隨機整數來選擇;值<math>P=k*G</math>被作為公鑰來公布(注意假設的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之間的報文進行加密的實際方法是適應以前的,最初是在其他組中描述使用的離散對數密碼系統。這些系統包括:
Diffie-Hellman — ECDH
MQV — ECMQV
ElGamal discrete log cryptosystem — ECElGamal
DSA — ECDSA
對於ECC系統來說,完成運行系統所必須的群操作比同樣大小的因數分解系統或模整數離散對數系統要慢。不過,ECC系統的擁護者相信ECDLP問題比DLP或因數分解問題要難的多,並且因此使用ECC能用小的多的密鑰長度來提供同等的安全,在這方面來說它確實比例如RSA之類的更快。到目前為止已經公布的結果趨於支持這個結論,不過一些專家表示懷疑。
ECC被廣泛認為是在給定密鑰長度的情況下,最強大的非對稱算法,因此在對頻寬要求十分緊的連線中會十分有用。
國家標準與技術局和ANSI X9已經設定了最小密鑰長度的要求,RSA和DSA是1024位,ECC是160位,相應的對稱分組密碼的密鑰長度是80位。NIST已經公布了一列推薦的橢圓曲線用來保護5個不同的對稱密鑰大小(80, 112, 128, 192, 256)。一般而言,二進制域上的ECC需要的非對稱密鑰的大小是相應的對稱密鑰大小的兩倍。
Certicom是ECC的主要商業支持者,擁有超過130項專利,並且已經以2千5百萬美元的交易獲得了國家安全機構(NSA)的技術許可。他們也已經發起了許多對ECC算法的挑戰。已經被解決的最複雜的是109位的密鑰,是在2003年初由一個研究團隊破解的。破解密鑰的這個團隊使用了基於生日攻擊的大塊並行攻擊,用超過10,000台奔騰級的PC機連續運行了540天以上。對於ECC推薦的最小密鑰長度163位來說,當前估計需要的計算資源是109位問題的108倍。
在2005年2月16日,NSA宣布決定採用橢圓曲線密碼的戰略作為美國政府標準的一部分,用來保護敏感但不保密的信息。NSA推薦了一組被稱為Suit B的算法,包括用來密鑰交換的Menezes-Qu-Vanstone橢圓曲線和Diffie-Hellman橢圓曲線,用來數字簽名的橢圓曲線數字簽名算法。這一組中也包括AES和SHA。

其它

文化藝術,生活娛樂,人物百科,社會人文,中外歷史...

盤點密碼學相關知識

盤點密碼學相關知識,密碼學是研究編制密碼和破譯密碼的技術科學。

相關詞條

相關搜尋

熱門詞條

聯絡我們