橢圓曲線 • 嚴謹密碼學：現代加密實務入門

橢圓曲線密碼學（ECC）於 1985 年引入，徹底改變了我們做公鑰密碼學的方式。

ECC 比 RSA、古典 Diffie–Hellman 這類替代方案更強大也更有效率——256 位元金鑰的 ECC 比 4096 位元金鑰的 RSA 更強——但它也更複雜。

與 RSA 一樣，ECC 也做大數相乘，但與 RSA 不同的是，它這麼做是為了組合數學曲線上的點——這種曲線稱為橢圓曲線（順帶一提，它與橢圓一點關係也沒有）。

更麻煩的是，橢圓曲線有許多不同型態——簡單的與精巧的、有效率的與沒效率的、安全的與不安全的。

採用歷程#

儘管 1985 年就被提出，ECC 直到 2000 年代初才被標準化機構採用，更晚才出現在主要工具包中：

OpenSSL 於 2005 年加入 ECC。
OpenSSH 等到 2011 年。

但現代系統幾乎沒有理由不用 ECC——你會在比特幣與 Apple 裝置的許多安全元件中找到它。
橢圓曲線讓你能比古典方案更快地執行加密、簽章與金鑰協商這些常見的公鑰密碼學操作。
多數依賴離散對數問題（DLP）的密碼應用，換成它的橢圓曲線版本 ECDLP 之後也能運作——唯一值得注意的例外是 SRP（Secure Remote Password）協定。

本章脈絡#

什麼是橢圓曲線——點的加法與乘法、有限體、橢圓曲線群。
ECDLP 問題——ECC 的困難性基礎，以及它為何能用更小的數字。
橢圓曲線上的金鑰協商——ECDH、ECDSA 簽章、ECIES 加密。
選擇曲線——NIST 曲線、Curve25519 與其他曲線。

常見錯誤#

橢圓曲線因其複雜度與龐大的攻擊面而有其缺點。

它們使用比古典 Diffie–Hellman 更多的參數，這帶來更大的攻擊面、更多犯錯與濫用的機會，以及可能影響其實作的軟體 bug。
橢圓曲線軟體也可能因其算術所用的大數而易受旁道攻擊：若計算速度取決於輸入，攻擊者就可能取得關於所用加密公式的資訊。

以下兩個例子是協定漏洞而非實作漏洞——即使實作本身是安全的，它們仍會發生。

隨機性不良的 ECDSA#

ECDSA 簽章是隨機化的，因為它在 s = (h + rd) / k mod n 中用到一個秘密隨機數 k。

s₁ = (h₁ + rd) / k
s₂ = (h₂ + rd) / k

相減得到：

s₁ − s₂ = (h₁ − h₂) / k
⟹ k = (h₁ − h₂) / (s₁ − s₂)

k 一旦已知，私鑰 d 就能輕易被還原：

(k·s₁ − h₁) / r = ((h₁ + rd) − h₁) / r = rd / r = d

與 RSA 簽章不同——RSA 即使使用了弱的 PRNG 也不會讓金鑰被還原——使用非隨機的數字會讓 ECDSA 的 k 可被還原。
這正是 2010 年 fail0verflow 團隊在柏林第 27 屆混沌通訊大會上發表的 PlayStation 3 遊戲主機攻擊所發生的事。

用另一條曲線攻破 ECDH#

若你未能驗證輸入的點，ECDH 可以被優雅地攻破。

主要原因是：計算 P + Q 座標的公式從不涉及曲線的 b 係數——它們只依賴 P 與 Q 的座標，以及 a 係數（倍點時）。
不幸的後果是：相加兩個點時，你永遠無法確定自己在正確的曲線上運算——你可能實際上是在一條 b 係數不同的曲線上相加點。

無效曲線攻擊（invalid curve attack）流程：

Alice 與 Bob 執行 ECDH，已就一條曲線與基點 G 達成共識。Bob 把公鑰 dB·G 送給 Alice。
Alice 不送商定曲線上的公鑰 dA·G，而是送出另一條曲線上的一個點（有意或無意）。
這條新曲線很弱，讓 Alice 能挑一個「求解 ECDLP 很容易」的點 P——她挑一個低階的點，使得存在一個相對小的 k 滿足 kP = O。
Bob 以為自己拿到合法公鑰，計算他以為的共享秘密 dB·P、雜湊它、用所得金鑰加密送給 Alice 的資料。

問題在於：Bob 計算 dB·P 時，他不知不覺是在較弱的曲線上運算。
由於 P 被挑選為屬於大點群中的一個小子群，結果 dB·P 也會屬於那個小子群——只要攻擊者知道 P 的階，就能有效率地判定共享秘密 dB·P。

2015 年在某些 TLS 協定的實作中發現了這樣的無效曲線攻擊——TLS 使用 ECDH 協商工作階段金鑰。
細節見 Jager、Schwenk 與 Somorovsky 的論文〈Practical Invalid Curve Attacks on TLS-ECDH〉。

採用歷程#

本章脈絡#

常見錯誤#

隨機性不良的 ECDSA#

用另一條曲線攻破 ECDH#

延伸閱讀#