橢圓曲線密碼學：更小的金鑰，同樣的安全性

Published: Sat Feb 01 2025 | Modified: Sat Feb 07 2026 , 9 minutes reading.

1. 為什麼要關心這個問題？

比較兩個具有同等安全性的金鑰：

RSA-3072 公鑰（384 位元組）：
-----BEGIN PUBLIC KEY-----
MIIBojANBgkqhkiG9w0BAQEFAAOCAY8AMIIBigKCAYEA2a3Y...
[大約 12 行 base64]
-----END PUBLIC KEY-----

ECC P-256 公鑰（65 位元組，或帶編碼 91 位元組）：
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAE...
[2 行 base64]
-----END PUBLIC KEY-----

同樣的安全性，小 6 倍。這對以下場景很重要：

HTTPS 憑證（更小 = 更快的握手）
物聯網裝置（有限的儲存和頻寬）
行動應用程式（更快的操作，更省電）
區塊鏈（每個位元組都要錢）

2. 定義

橢圓曲線密碼學（ECC） 使用有限域上橢圓曲線的代數結構來建立密碼學操作。

其安全性基於 橢圓曲線離散對數問題（ECDLP）：給定曲線上的點 P 和 Q = kP，找出 k 在計算上是不可行的。

單向函式：

容易：    k × P = Q    （純量乘法）
          給定 k 和 P，計算 Q

困難：    Q / P = k    （離散對數）
          給定 P 和 Q，找出 k

3. 什麼是橢圓曲線？

數學形式

在實數上，橢圓曲線是：

y² = x³ + ax + b

其中：4a³ + 27b² ≠ 0（確保沒有奇點）

視覺形狀

        y
        │     *
        │   *   *
        │  *     *
    ────┼──*─────*──────── x
        │  *     *
        │   *   *
        │     *
        │

密碼學曲線使用有限域

在密碼學中，我們不使用實數。
我們使用對某個質數 p 取模的整數：

y² ≡ x³ + ax + b  (mod p)

例子：P-256 曲線
p = 2²⁵⁶ - 2²²⁴ + 2¹⁹² + 2⁹⁶ - 1

所有運算在 p 處迴繞
結果總是 0 到 p-1 之間的整數

4. 點加法：核心操作

幾何直覺（在實數上）

要把點 P 和 Q 相加：

1. 畫一條穿過 P 和 Q 的線
2. 這條線與曲線相交於第三點 R
3. 將 R 關於 x 軸反射得到 P + Q

        y
        │     P*
        │   *   *
        │  *  Q  *
    ────┼──*─────*──────── x
        │  *  R' *  (P + Q)
        │   *   *
        │     R

點倍增

要計算 P + P = 2P：

1. 在點 P 處畫切線
2. 切線與曲線相交於點 R
3. 將 R 關於 x 軸反射得到 2P

無窮遠點

特殊點 O（單位元）：

P + O = P
P + (-P) = O

-P 是 P 關於 x 軸的反射

5. 純量乘法：安全性所在

計算 Q = kP

k = 7, P = 某個點

樸素方法：P + P + P + P + P + P + P = 7P
          （7 次加法）

倍增加法（高效）：
7 = 111（二進位）

步驟 1：P
步驟 2：2P（倍增）
步驟 3：2P + P = 3P（加，因為位元是 1）
步驟 4：6P（倍增）
步驟 5：6P + P = 7P（加，因為位元是 1）

只需要 ~log₂(k) 次操作

困難問題

給定：P（基點，公開）
      Q = kP（結果點，公開）

找出：k（純量，私鑰）

對於 256 位元曲線：
- k 有 ~2²⁵⁶ 種可能
- 沒有已知的捷徑（不像分解）
- 最佳攻擊：~2¹²⁸ 次操作（生日界）

6. 常用曲線

NIST 曲線

P-256（secp256r1，prime256v1）：
- 256 位元質數域
- 部署最廣泛
- NIST 標準化，NSA 設計
- 因為未解釋的常數而有一些不信任

P-384（secp384r1）：
- 384 位元質數域
- 更高的安全邊際
- 用於政府應用

P-521（secp521r1）：
- 521 位元質數域
- 最高安全性，更慢
- 很少需要

Curve25519（現代選擇）

由 Daniel Bernstein 設計：
- 255 位元質數域（2²⁵⁵ - 19）
- 設計上抵抗時序攻擊
- 比 NIST 曲線更快
- 沒有未解釋的常數
- 用於：Signal、WhatsApp、SSH、WireGuard

變體：
- X25519：金鑰交換（ECDH）
- Ed25519：簽章（EdDSA）

比特幣的曲線

secp256k1：
- 256 位元 Koblitz 曲線
- 比 P-256 稍快
- 被比特幣、以太坊使用
- 和 P-256 (secp256r1) 不同

7. ECC 金鑰產生

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.backends import default_backend

# 產生金鑰對
private_key = ec.generate_private_key(
    ec.SECP256R1(),  # P-256 曲線
    default_backend()
)
public_key = private_key.public_key()

# 內部是什麼：
# private_key：隨機 256 位元整數 k
# public_key：點 Q = k × G（G 是產生點）

# 提取數值
private_numbers = private_key.private_numbers()
public_numbers = private_numbers.public_numbers

print(f"私鑰 (k): {private_numbers.private_value}")
print(f"公鑰 (x): {public_numbers.x}")
print(f"公鑰 (y): {public_numbers.y}")

金鑰大小

曲線       | 私鑰       | 公鑰        | 安全性
-----------+------------+-------------+-----------
P-256      | 32 位元組  | 65 位元組*  | 128 位元
P-384      | 48 位元組  | 97 位元組*  | 192 位元
P-521      | 66 位元組  | 133 位元組* | 256 位元
Curve25519 | 32 位元組  | 32 位元組   | 128 位元

* 未壓縮格式 (04 || x || y)
  壓縮格式：(02/03 || x)，大約一半大小

8. ECDSA：橢圓曲線數位簽章

簽章過程

用私鑰 k 簽章訊息 m：

1. 計算雜湊：e = HASH(m)
2. 產生隨機 nonce r（關鍵：必須隨機）
3. 計算 R = r × G
4. 取 x 座標：rx = Rx mod n
5. 計算 s = r⁻¹(e + rx × k) mod n
6. 簽章是 (rx, s)

驗證過程

用公鑰 Q 驗證訊息 m 上的簽章 (rx, s)：

1. 計算雜湊：e = HASH(m)
2. 計算 u1 = e × s⁻¹ mod n
3. 計算 u2 = rx × s⁻¹ mod n
4. 計算 R = u1 × G + u2 × Q
5. 檢查：Rx mod n == rx?

程式碼範例

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# 產生金鑰
private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# 簽章
message = b"Hello, ECDSA!"
signature = private_key.sign(
    message,
    ec.ECDSA(hashes.SHA256())
)

# 驗證
try:
    public_key.verify(
        signature,
        message,
        ec.ECDSA(hashes.SHA256())
    )
    print("簽章有效!")
except Exception:
    print("簽章無效!")

9. EdDSA：現代替代方案

為什麼選擇 EdDSA 而不是 ECDSA？

ECDSA 的問題：
1. 每次簽章都需要安全的隨機 nonce
   - PlayStation 3 被駭：重用 nonce → 私鑰洩露
   - 同樣的 nonce 用兩次 = 遊戲結束

2. 安全實作複雜
   - 時序攻擊
   - 故障攻擊

EdDSA (Ed25519) 的解決方案：
1. 從訊息雜湊確定性產生 nonce
   - 簽章時不需要亂數
   - 不會意外重用

2. 設計為常數時間實作
   - 抵抗時序攻擊

3. 更快更簡單

Ed25519 範例

from cryptography.hazmat.primitives.asymmetric import ed25519

# 產生金鑰
private_key = ed25519.Ed25519PrivateKey.generate()
public_key = private_key.public_key()

# 簽章（不需要指定演算法——它是內建的）
message = b"Hello, Ed25519!"
signature = private_key.sign(message)

# 驗證
try:
    public_key.verify(signature, message)
    print("簽章有效!")
except Exception:
    print("簽章無效!")

10. ECDH：用曲線做金鑰交換

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

# Alice 產生她的金鑰對
alice_private = ec.generate_private_key(ec.SECP256R1())
alice_public = alice_private.public_key()

# Bob 產生他的金鑰對
bob_private = ec.generate_private_key(ec.SECP256R1())
bob_public = bob_private.public_key()

# 雙方計算相同的共享金鑰
alice_shared = alice_private.exchange(ec.ECDH(), bob_public)
bob_shared = bob_private.exchange(ec.ECDH(), alice_public)

assert alice_shared == bob_shared  # 相同！

# 從共享金鑰衍生實際金鑰
derived_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b'handshake data'
).derive(alice_shared)

X25519：現代 ECDH

from cryptography.hazmat.primitives.asymmetric import x25519

# Alice
alice_private = x25519.X25519PrivateKey.generate()
alice_public = alice_private.public_key()

# Bob
bob_private = x25519.X25519PrivateKey.generate()
bob_public = bob_private.public_key()

# 共享金鑰
alice_shared = alice_private.exchange(bob_public)
bob_shared = bob_private.exchange(alice_public)

assert alice_shared == bob_shared

11. ECC 安全考量

ECDSA 中的 Nonce 重用

如果你用同一個 nonce r 簽章兩則不同的訊息：

簽章 1：s1 = r⁻¹(e1 + rx × k)
簽章 2：s2 = r⁻¹(e2 + rx × k)

從這些可以得到：
s1 - s2 = r⁻¹(e1 - e2)
r = (e1 - e2) / (s1 - s2)

然後：
k = (s1 × r - e1) / rx

私鑰被恢復了！

索尼的 PlayStation 3 使用固定的 r → 被駭了

曲線選擇很重要

要避免的弱曲線：
- 嵌入度小的曲線（配對攻擊）
- 二進位域上的曲線（近期攻擊）
- 常數可疑的曲線

安全的選擇：
- Curve25519/Ed25519（推薦）
- P-256（廣泛支援）
- P-384（更高安全需求）

實作攻擊

時序攻擊：
- 測量操作需要多長時間
- 從時序推斷金鑰位元

防禦：
- 使用常數時間實作
- libsodium 等函式庫處理了這個問題
- Curve25519 設計上抵抗

無效曲線攻擊：
- 發送不在曲線上的點
- 弱群結構

防禦：
- 始終驗證點
- 使用 Montgomery 曲線 (Curve25519)

12. ECC vs RSA：最終對比

                    | RSA              | ECC
--------------------+------------------+-----------------
金鑰大小（128 位元）| 3072 位元        | 256 位元
金鑰大小（256 位元）| 15360 位元       | 512 位元
金鑰產生            | 慢（質性測試）    | 快
簽章                | 較慢             | 較快
驗證                | 較快             | 較慢
加密支援            | 直接（混合）      | 只能金鑰交換
量子抵抗            | 被 Shor 破解     | 被 Shor 破解
成熟度              | 1977             | 1985+
採用情況            | 遺留主導         | 現代主導

13. 常見誤區

誤區	現實
「ECC 是新的未經驗證的」	ECC 始於 1985 年，2000 年代以來廣泛部署
「更小的金鑰 = 更不安全」	金鑰大小比較只在同一演算法內有效
「P-256 不安全」	它沒問題，只是不如 Curve25519 受信任
「ECC 完全替代了 RSA」	ECC 不能做直接加密
「Ed25519 和 ECDSA 是一樣的」	不同的演算法有不同的特性

14. 本章小結

三點要記住：

ECC 用更小的金鑰達到同樣的安全性。 256 位元 ECC ≈ 3072 位元 RSA。這意味著更快的操作、更小的憑證、更少的頻寬。
曲線選擇很重要。 新專案使用 Curve25519/Ed25519。為了相容性回退到 P-256。
絕不要重用 ECDSA nonce。 一次重用 = 私鑰洩露。優先使用 Ed25519 的確定性簽章。

15. 下一步

我們已經看到 RSA 如何使用分解，ECC 如何使用曲線。但兩者都需要解決一個根本問題：兩個從未見面的人如何協商出共享金鑰？

在下一篇文章中：Diffie-Hellman 金鑰交換——讓安全通訊無需預共享金鑰成為可能的數學魔法。

Luke Sun