雞卵行曲線密碼學

雞卵行曲線密碼學（英語：EllipticCurveCryptography，縮寫：ECC）是一種基於雞卵行數學的數學的公開密鎖加密演算法。

ECC 的主要優勢是伊相比 RSA 加密演算法使用較細的密鎖長度並提供相當的安全性。ECC 的另外一个優勢會當定義群之間的雙線性炤著，是因為 Weil 著抑是 Tate 著；雙線性映射已經佇密碼學中發現了大量的應用，譬如講基於身份的加密。

歷史

雞卵行曲線佇密碼學中的使用是佇一九八五年由 Neal Koblitz 和 Victor Miller 分別獨立提出的。雞卵行曲線密碼學的演算法是佇二空空四年到二空空五年開始講法應用。

理論

針對密碼學應用上的雞卵行曲線是佇有限域（毋是實數域）的平面曲線，若是其方程式這馬：

$ y ^ { 二 }=x ^ { 三 } + ax + b , \ , $

有一个特別的無窮遠點（標示為 ∞）。 座標會選定做特定的有限域，其特徵無等於二抑是三，嘛有可能是閣較複雜的曲線方面。

由雞卵圓曲線產生的集合是阿貝爾群，以無窮遠點為單位元。這陣的結構會繼承以下代數圍中除子的結構：

$ \ mathrm { Div } ^ { 零 } ( E ) \ to \ mathrm { Pic } ^ { 零 } ( E ) \ simeq E , \ , $

密鎖交換

雞卵行曲線密碼學的真濟形式有小可仔無仝，所有的攏依賴佇咧被廣泛承認的解決「雞卵行曲線離散著數」問題的困難性上，對應有限域上雞卵行的群。

伽羅瓦域

對雞卵行曲線來講上時行的有限域是以素數為模的整數域（參見模運算）$ GF ( p ) $，抑是特徵做二的伽羅瓦域 GF（二 m）。 後者佇專門的硬體實現計算更為有效，進前遮的通常佇咧通用處理器上閣較為有效。專利的問題嘛是相關的。一寡其他素數的伽羅瓦域的大小和能力嘛已經提出矣，但是予密碼專家認為有小可問題。

予定一个雞卵行 E 猶閣有一个域 $ GF ( q ) $，考慮的物件有 $ ( x , y ) $ 形式有理數點 $ E ( q ) $ 的阿貝爾群，其中 x 和 y 攏佇咧 $ GF ( q ) $ 並且定義佇這條曲線頂懸的群運算 " + "（運算 " + " 佇條目雞卵行中間咧講）。 然後定義第二个運算 " \ * " | Z× $ E ( q )-> E ( q ) $：若是 P 是 $ E ( q ) $ 某一个點，遐爾仔定義 $ 二 * P=P + P , 三 * P=二 * P + P=P + P + P $ 等咧。針對予定整數 j 和 k，$ j * ( k * P )=( jk ) * P=k * ( j * P ) $。雞卵行曲線離散去的問題（ECDLP）就是予定點 P 和 Q，確定整數 k 使 $ k * P=Q $。 -- 一般認為佇一个有限域乘法群頂面的離散對數問題（DLP）佮雞卵行線頂的離散對數問題（ECDLP）並無等價；ECDLP 比 DLP 欲困難的濟。

佇密碼的使用，會選擇曲線 $ E ( q ) $ 佮其中一个特定的點 G，而且公開遮的資料。會閣選擇一个隨機整數 k 做私鎖；公布值為 $ P=k * G $ 公鎖（注意假使的 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 之間的報文進行加密的實際方法是適應較早的，上頭先是佇其他組中所描述使用的離散對數密碼系統。𪜶的遮的系統攏包括：

• 雞卵行曲線迪菲-赫爾曼密鎖交換（ECDH）
• MQV（ECMQV）
• ElGamal 離散對數密碼體制（ECElGamal）
• 雞卵行曲線數字簽名算法（ECDSA）

對於 ECC 系統來講，完成運行系統所必須的群操作比仝款大細的因數分解系統或者是模整數離散對數系統愛慢。猶毋過，ECC 系統的擁護者相信 ECDLP 問題比 DLP 抑是因數分解問題困難的濟，並且就按呢使用 ECC 會當用細的加的密鎖長度來提供同等的安全，佇這方面來講伊確實比如講 RSA 彼款的閣較緊。到目前為止已經公佈的結果趨於支持這个結論，毋過一寡專家表示懷疑。

ECC 被廣泛認為是咧予定密鎖長度的狀況之下，上大的非對稱算法，所以佇對帶寬要求十分漸漸仔牽連會十分有路用。

建議喔

美國國家標準佮技術局佮 ANSI X 九已經設定矣上細漢密鎖長度的要求，RSA 和 DSA 是上細漢兩千空四十八个，ECC 是上細漢兩百二十四个，相應的對稱密鎖加密的密鎖長度是上小一百二十八位，這款的組合佇咧二空三空年進前是安全的。

佇二空空五年二月十六，NSA 宣布決定採用雞卵行機線密碼的戰略作為美國政府標準的一部份，好來保護敏感毋過無保密的信息。NSA 推薦一組予人號做 Suit B 的算法，包括用來密鎖交換的雞卵行曲線 Menezes-Qu-Vanstone（ECMQV）佮雞卵行曲線 Diffie-Hellman（ECDH）， 用來數字簽名的雞卵行算數字簽名算法。這組內底嘛包括 AES 和 SHA。

安全性

邊仔路攻擊

雞卵行曲線密碼學佮其他的離散對數無仝，佇離散對數中會當用仝款的程序處理平方佮乘法，但雞卵行的線頂懸的加法佇加倍（_ P _=_ Q _）佮一般加法（_ P _ ≠ _ Q _）上會因為使用的座標系統有顯示的無仝。所以有關係邊路的攻擊（譬如講時間抑是能量分析）的防治就格外的重要。像用固定的模式窗口（fixed pattern window，嘛叫做 comb）的方式（這袂增加運算時間啊）。 另外嘛會使用愛德華曲線，這是一類特別的雞卵行曲線，其中的加倍和加法會使用仝一个運算完成。另外一个 ECC 系統的疑慮是差別錯誤分析的風險，特別是佇智慧卡上的應用。

後尾門

密碼學專家煩惱，美國國家安全局（NSA）可能已經佇咧至少一个以雞卵行曲線為基礎的造假數產生器當中囥入去 kleptographic 後尾門。前美國中央情報局（CIA）職員愛德華 ・ 斯諾登所洩漏的內部挽欲暗示，NSA 佇雙雞卵行曲線確定性隨機比特生成器標準中加入後門。微軟公司的研究人員針對這標準中一个的疑似後門進行分析，並且會出結論：有這个演算法私鎖的攻擊者，會當干焦根據三十二位元組的 PRNG 輸出，揣著加密的密鎖。

密碼學家發起矣「SafeCurves」計畫，整理並列出安全性𠢕實現而且設計的過程完全公開可驗證的曲線，以減少曲線被植入後門的可能性。

量仔計算攻擊

若攻擊者有大型的量算機器，按呢伊會當使用秀爾算法解決離散對數問題，對欲破解私鎖和共享秘密。目前的估算認為：破解兩百五十六位素數域頂懸的雞卵行曲線，需要兩千三百三十个量比特佮一千兩百六十億托佛利門。比並之下，使用秀爾算法破解兩千空四十八位的 RSA 是需要四千空九十八个量比特佮五鋪二萬億托佛利門。所以，雞卵行曲線會閣較先拄著佇量仔計算機的破解。目前猶閣不存在建造這陣大型的量子計算機的科學技術，就按呢雞卵行曲線密碼學至少佇未來十年（抑是閣較久）猶原嘛是安全的。但是密碼學家已經積極展開了後量子密碼學的研究。其中，超奇異雞卵行曲線同源密鎖交換（SIDH）有望取代當前的定規雞卵行曲線密鎖交換（ECDH）。

無效曲線攻擊

若是 ECC 是佇咧虛擬機器運作，攻擊者會當用無效的曲線來取得完整的 PDH 私鎖。