跳轉到

7.3 橢圓曲線密碼學 ECC#

概念說明#

橢圓曲線密碼學（Elliptic Curve Cryptography, ECC）於 1985 年由 Koblitz 與 Miller 分別提出：把 7.1 節的離散對數問題搬到橢圓曲線群上。同等的問題難度，ECC 只需約 256 位元的金鑰——RSA 則需要 3072 位元。金鑰短意味著更快的運算、更小的憑證、更省電的裝置，因此 ECC 已成為 TLS 1.3、SSH、比特幣、Apple/Google 安全晶片的主流。

橢圓曲線（素域上 Weierstrass 形式）：

y² = x³ + ax + b（mod p），且 4a³ + 27b² ≠ 0

曲線上的點（加上無窮遠點 𝒪）構成一個阿貝爾群，加法定義為「弦的幾何法則」：過 P、Q 的直線與曲線的第三個交點，對 x 軸反射即為 P+Q。

核心運算#

  • 純量乘法：Q = kP（P 加自己 k 次，用 double-and-add 快速計算）。
  • ECDLP：給定 P 與 Q=kP，求 k。最佳通用演算法（Pollard rho）需約 √n 步，n 為群的階——256 位元曲線給約 128 位元安全度。
  • ECDH：Alice 送 A = aG、Bob 送 B = bG，雙方得 S = abG（與 7.1 節 DH 完全同構，只是把模指數換成純量乘法）。
  • ECDSA/EdDSA：基於 ECDLP 的簽章（6.2 節）。

Python 實作（教學版 ECDH，取自 RFC 6090 風格的素域曲線）#

# 曲線 P-256 的參數（節錄；實務請用標準庫）
p  = 2**256 - 2**224 + 2**192 + 2**96 - 1
a, b = p - 3, 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

def add(P, Q):                    # 橢圓曲線點加法（仿射座標，教學用）
    if P is None: return Q
    if Q is None: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0: return None   # 相加為 𝒪
    if P == Q:
        m = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p  # 切線斜率
    else:
        m = (y2 - y1) * pow(x2 - x1, -1, p) % p         # 弦斜率
    x3 = (m * m - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p
    return (x3, y3)

def mul(k, P):                    # double-and-add 純量乘法
    R = None
    while k:
        if k & 1: R = add(R, P)
        P, k = add(P, P), k >> 1
    return R

# ECDH（點座標簡化示範；完整基點 G 見 SECG SEC2）
G = (0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
     0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5)
priv_a, priv_b = 1234567, 7654321
A, B = mul(priv_a, G), mul(priv_b, G)
s1, s2 = mul(priv_a, B), mul(priv_b, A)
assert s1 == s2                   # 共享點 = ab·G
print("ECDH 共享點 x 座標:", hex(s1[0])[:18], "...")

# 實務：直接用標準庫
from cryptography.hazmat.primitives.asymmetric import ec
k1 = ec.generate_private_key(ec.SECP256R1())
k2 = ec.generate_private_key(ec.SECP256R1())
s1 = k1.exchange(ec.ECDH(), k2.public_key())
s2 = k2.exchange(ec.ECDH(), k1.public_key())
assert s1 == s2

安全性分析#

  • 優勢：128 位元安全只需 256 位元金鑰（RSA 需 3072）；無「次指數」攻擊通用地適用（特殊曲線除外）；運算快、適合手機與物聯網。
  • 曲線選擇是地雷區：自行「發明曲線」可能引入後門或弱點（seed 不透明曾引發 Dual_EC_DRBG 信任危機）。務必用公開、經分析的曲線：NIST P-256/P-384、Curve25519（X25519，快速、常數時間、無分支洩漏）。
  • ECDSA 的隨機數陷阱：每次簽章需要新鮮隨機 k，k 重用或偏置即洩漏私鑰（PlayStation 3 簽章破解、2010 年 Android 錢包被盜皆源於此）。Ed25519 用確定性派生的 k 根除此類問題。
  • 無效曲線攻擊：實作必須驗證對方的點確實在曲線上且在正確子群中，否則攻擊者可送「曲線外的點」逐步榨出私鑰。標準庫已處理；自寫實作務必檢查。
  • 量子威脅同樣致命：ECDLP 被 Shor 演算法在多項式時間破解，遷移路徑見第 10 章。

練習#

  1. 在 y² = x³ + 2x + 3 (mod 17) 上取 P=(5,1)，用 add 手算 2P、3P，並用 mul 驗證。
  2. 證明：若攻擊者能解 ECDLP，就能從 ECDH 的公開值 (G, aG, bG) 算出共享點 ab·G。
  3. 上網查 Curve25519 的設計標準（RFC 7748），列出至少三項讓它「易於安全實作」的設計決策（提示：常數時間 ladder、無 𝒪 分支、座標形式）。