# EC / ECDH 筆記：橢圓曲線依賴的難題
## 先跑一個真的能算出來的玩具例子
拿一條刻意選小的曲線 `y² = x³ + 2x + 3 (mod 97)`，曲線上的「點」是所有滿足這個方程式、座標落在 0~96 之間的整數座標對，「加法」則是一套幾何加代數的固定規則（兩點連線、找出跟曲線的第三個交點、再對 `y` 取負），這個運算本身有良好定義，可以重複套用。
選定一個起點 `G = [0, 10]`，把 `G` 自己加自己重複做 `k` 次（這個操作叫「純量乘法」，寫成 `Q = k·G`），可以很快算出結果：
```
生成元 G = [0, 10]，是否真的在曲線上: true
私鑰 k=42（秘密），算公鑰 Q = k*G = [84, 60]，耗時 0.467ms（極快）
```
現在反過來，假裝自己是攻擊者，手上只有 `G` 跟 `Q`，想找出 `k` 是多少：
```
現在假裝我們是攻擊者，只知道 G 跟 Q，要找出 k（窮舉法）：
窮舉找到 k = 42，耗時 0.566ms（這個玩具尺寸下窮舉也很快，但方法本身是「一個一個試」）
驗證: 找到的 k 是否等於原本的私鑰 42？ true
```
窮舉一下就找到了，因為這條玩具曲線上總共只有大約 97 個點，反著試個幾十次就結束。這個玩具例子看起來完全不安全，但它精準示範了問題的骨架——**橢圓曲線離散對數問題（ECDLP）**：給定曲線上的起點 `G` 跟另一個點 `Q = k·G`，反推出純量 `k`。正向（用 `k` 算出 `Q`）永遠很快，反向能不能算得動，完全取決於曲線上總共有多少個點。
真正在用的曲線，比如 P-256，點的數量大約是 `2^256` 個——不是 97，是天文數字。已知最好的通用攻擊法（Pollard's rho）複雜度約 `√(點的數量) = 2^128` 次運算，這在可預見的未來完全不可行。跟這條玩具曲線唯一的差別只有「群有多大」，運算規則和攻擊手法本身完全一樣。
## ECDLP 跟 RSA 的整數分解問題，差在哪
如果只比較「安全性」，兩者半斤八兩——都沒有已知的高效通用攻擊法。真正的差別在於，整數分解問題存在一種叫**一般數域篩法（GNFS）**的專門算法，複雜度是次指數等級（比純窮舉快很多，但也不到多項式時間），所以想維持同等安全強度，RSA 得不斷加大金鑰（現在都建議 2048~3072 bit）；而 ECDLP 至今沒有找到類似 GNFS 的專門捷徑，只能用上面說的那種最慢的指數級通用攻擊，所以想要同樣的安全強度，EC 用小得多的金鑰就夠了。
拿同一套 Web Crypto API 實測 RSA-2048 跟 EC P-256 的金鑰、簽章大小：
```
RSA-2048 公鑰 SPKI DER 長度: 294 bytes
EC P-256 公鑰 SPKI DER 長度: 91 bytes
RSA-2048 簽章長度: 256 bytes
EC P-256 簽章長度: 64 bytes
RSA-2048 簽章 200 次耗時: 122.0ms（平均 0.610ms/次）
EC P-256 簽章 200 次耗時: 34.1ms（平均 0.171ms/次）
```
P-256 的公鑰只有 91 bytes、簽章只要 64 bytes，都不到 RSA-2048 的三分之一，簽章速度也快了三倍多——這不是因為 ECDLP「本質上比整數分解更難」，是因為它沒有已知的捷徑算法，不需要靠「把金鑰做大」來防堵捷徑。
## ECDH：這其實不是「加密」，是「金鑰協商」
RSA 的公鑰能直接拿去做加密（`密文 = 明文^e mod n`），但橢圓曲線的公鑰沒有對應的「加密某段資料」的操作。**ECDH（Elliptic Curve Diffie-Hellman）**做的事情，是讓雙方各自產生一組金鑰對、交換公鑰之後，各自用「自己的私鑰 + 對方的公鑰」算出**同一把**共用密鑰——而且全程不需要真的把這把密鑰傳輸過去。
實際跑一次雙方各自運算的過程：
```
Alice 算出的共用密鑰: 522ece93bdd158b50e7d3adc2d7f5e432a3d6cf75329dc537fd0d4c2b0eb312a
Bob 算出的共用密鑰: 522ece93bdd158b50e7d3adc2d7f5e432a3d6cf75329dc537fd0d4c2b0eb312a
兩者逐 byte 相同: true
```
Alice 用「自己的私鑰 + Bob 的公鑰」、Bob 用「自己的私鑰 + Alice 的公鑰」，兩人各自算出了完全相同的一串密鑰，過程中誰都沒有把這串密鑰本身傳給對方——這正是 Diffie-Hellman 的核心性質。這把共用密鑰的原始輸出不保證均勻分布在整個金鑰空間，業界標準做法會再過一次 KDF（這裡用 HKDF）才拿來當真正的對稱金鑰使用：
```
Bob 用自己導出的金鑰解密結果: hello from alice
```
## ECIES：把 ECDH 包成真正的「加密」功能
既然 ECDH 本身只能協商出雙方共用的密鑰，要做出「用某人的公鑰加密一段資料」這種體驗，得再加一層設計，業界稱為 **ECIES**：發送端每次加密都臨時產生一組一次性的金鑰對，用這把臨時私鑰跟收件人的公鑰做 ECDH 算出共用密鑰，經 HKDF 導出一把 AES-256 金鑰後，用它把真正的內容做 AES-GCM 加密。收件人只要收到這把隨密文一起送來的「臨時公鑰」，配上自己的私鑰做同樣的 ECDH，就能獨立算出跟發送端一模一樣的共用密鑰，進而解出金鑰、解密內容。整個組合密文的結構是：
```
[臨時公鑰 SPKI DER][16 bytes HKDF salt][12 bytes AES-GCM IV][AES-GCM 密文 + 16 bytes 認證標籤]
```
這跟 RSA 混合加密（RSA-OAEP 直接包住一把 AES 金鑰）是同一種「用非對稱手段保護一把對稱金鑰」的設計模式，只是保護的手法不同：RSA 是直接把金鑰加密包起來，EC 這邊是讓雙方各自算出同一把，全程不傳輸這把金鑰本身。
## 不同曲線的差異
Web Crypto API 支援的三種常用曲線，安全強度跟金鑰大小都不一樣：
```
P-256: 公鑰 SPKI 91 bytes, 私鑰 PKCS8 138 bytes, deriveBits(256) 成功取得 32 bytes
P-384: 公鑰 SPKI 120 bytes, 私鑰 PKCS8 185 bytes, deriveBits(256) 成功取得 32 bytes
P-521: 公鑰 SPKI 158 bytes, 私鑰 PKCS8 241 bytes, deriveBits(256) 成功取得 32 bytes
```
值得注意的是，就算共用密鑰是從 P-521 這種原生輸出比較長的曲線算出來的，`deriveBits` 呼叫時要幾個 bit 是自己指定的——上面這組實測不論哪條曲線都只要求 256 bits，這是因為 HKDF 只需要「足夠熵的輸入材料」，不需要曲線原生的完整長度。另外，EC 的公鑰在匯入時用 `usages: []` 就夠了，因為它只會被當成另一方 `deriveKey`/`deriveBits` 呼叫裡的參數，不會被單獨拿去做任何操作，只有私鑰才需要 `deriveKey`/`deriveBits` 這兩個 usage。
## 跟量子電腦、跟 RSA 的關係
ECDLP 跟整數分解問題面對量子電腦時的處境是一樣的——Shor's Algorithm 理論上能有效率地解掉橢圓曲線離散對數問題，跟它能解掉整數分解問題是同一件事的兩個變形，並不是「換成 EC 就對量子電腦免疫」。真正能防禦量子電腦的是另一整套跟橢圓曲線、跟 RSA 都無關的後量子密碼學技術。EC 存在的理由，從頭到尾都是「效率」——用小得多的金鑰達到跟 RSA 一樣的安全強度，不是因為 RSA 的數學被攻破了才需要換掉它。
## 小結
| 項目 | 內容 |
|---|---|
| 依賴的難題 | 橢圓曲線離散對數問題（給定 `G` 跟 `Q=k·G`，反推 `k`） |
| 已知的專門攻擊法 | 沒有（RSA 有 GNFS，EC 沒有類似的次指數捷徑） |
| P-256 公鑰大小（SPKI DER） | 91 bytes（RSA-2048 是 294 bytes） |
| P-256 簽章大小 | 64 bytes（RSA-2048 是 256 bytes） |
| ECDH 本身是不是加密 | 不是，是金鑰協商——雙方各自算出同一把共用密鑰 |
| 怎麼變成「加密」功能 | ECIES：臨時金鑰對 + ECDH + HKDF 導出對稱金鑰 + AES-GCM |
| 對量子電腦的抵抗力 | 跟 RSA 一樣脆弱，兩者都需要後量子密碼學才能防禦 |