2005 - 橢圓曲線密碼學#

案件摘要#

1985 年 Neal Koblitz 與 Victor Miller 各自獨立提出：用橢圓曲線上的點加法取代模乘法的冪運算，同樣的單向性難題，但同等安全性只需 1/6 的金鑰長度——160 位元 ECC ≈ 1024 位元 RSA。2005 年起 ECC 進入 TLS 與行動裝置的標準，今天 iPhone、Android 的 TLS 憑證多為 ECDSA/ECDH，而美國 NSA 與各國情報機構早已全面轉向 ECC。ECC 是同樣數學、更小金鑰的典範。

前因 -- 為什麼會有這個案子#

RSA 的金鑰長度軍備競賽（見 1977-RSA.md）：512（1990s）→ 1024 → 2048 → 4096 位元。原因是分解的算法（數域篩）在改進，RSA 需要不斷加長金鑰才能維持安全。

1970 年代的數學線索：1977 年 Neal Koblitz 在《美國數學月刊》發表〈 elliptic curve cryptosystems〉——同一篇論文裡包含 ECC 與 RSA（1985 Miller 獨立提出，用了 2 年先驅工作）：在橢圓曲線群上做同樣的運算。

Koblitz 的洞見：橢圓曲線的離散對數問題沒有像 RSA 那樣的「亞指數」算法——橢圓曲線沒有類比數域篩的結構，最好的攻擊是 Pollard rho（ \(O(\sqrt{n})\) ）， \(n\) 位元金鑰給 \(2^{n/2}\) 級安全。160 位元 ECC ≈ RSA-1024、256 位元 ECC ≈ RSA-3072。

線索與推理 -- 數學式、程式、理論#

橢圓曲線上的群運算#

短韋斯特拉斯形式（Weierstrass form）：

點 \((x, y)\) 加法（弦線法）：兩點 \(P, Q\) 的連線交曲線於第三點 \(R\) ，則 \(P + Q = -R\) （對徑點反射）。加上無窮遠點 \(O\) （零元素）——構成阿貝爾群。

倍點（scalar multiplication）： \(kP = P + P + \dots\) （ \(k\) 次）——容易（平方乘法， \(O(\log k)\) ）。

離散對數：給定 \(P, Q = kP\) ，求 \(k\) ——難（Pollard rho 需 \(O(\sqrt{k})\) 次群運算）。

ECC 的的安全性基礎：橢圓離散對數問題（ECDLP）被認為無多項式或亞指數算法（但未被證明——與 RSA 的分解問題同樣的處境：不是定理，是共識）。

點的表示與壓縮（smart attack 的教訓）#

難點：橢圓曲線點 \((x, y)\) 是 2 個 \(n\) 位元數， \(x\) 已知可算 \(y\) ——故用 \(x\) 座標表示「點的數量」看似減半，但丢了 \(y\) 資訊。

錯誤做法：只用 \(x\) 座標——Smart 攻擊（1999, 1997）：橢圓曲線上的配對 \(E \times E \to E\) 是雙線性映射， \(x(x(P) + x(Q))\) 可由 \(x\) 算出——雙線性配對攻擊使 \(x\) 座標表示的可見性被用來攻擊。

正確：壓縮表示 \(x\) + \(y\) 的最低有效位（1 位元標記）——保持雙線性非退化性。

偵探筆記：Smart 攻擊是密碼學史的經典教訓——看似安全的優化（省金鑰）破壞了代數結構，用雙線性配對把資訊「用回來」。這與 Enigma 的反射器（見 1918-Enigma機.md）、RSA 去掉雜湊的教科書簽章（見 1977-RSA.md）同源：「省」的決策常毀滅安全性。

ECC 的金鑰效率#

相同安全強度：

手機時代的決定性因素：行動裝置的 CPU 與頻寬有限——256 位元 ECC 的簽章比 3072 位元 RSA 快、憑證小 12 倍——ECC 成為 TLS 的首選（2015 年起 iOS 憑證全部 ECC）。

程式碼：橢圓曲線加法與 ECDH#

# 短韋斯特拉斯曲線 y^2 = x^3 + ax + b (mod p)
P = 2**256 - 2**32 - 977
A, B = -3, 0x1F3D              # NIST 曲線參數（概念示範）

def inv(x, p): return pow(x, p - 2, p)   # Fermat 定理：x^{p-2} = x^{-1}

def point_add(P1, P2):
    """橢圓曲線點加法：弦線法"""
    if P1 is None: return P2
    if P2 is None: return P1
    (x1, y1), (x2, y2) = P1, P2
    if x1 == x2 and (y1 + y2) % P == 0:
        return None                             # P + (-P) = O
    if P1 == P2:
        lam = (3 * x1 * x1 + A) * inv(2 * y1, P) % P   # 倍點
    else:
        lam = (y2 - y1) * inv(x2 - x1, P) % P          # 弦線斜率
    x3 = (lam * lam - x1 - x2) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)

def point_mul(k, P0, p=P):
    """平方乘法：k*P0，O(log k) 次群運算"""
    R = None
    while k:
        if k & 1: R = point_add(R, P0)
        P0 = point_add(P0, P0)                   # 倍點
        k >>= 1
    return R

# ECDH：金鑰交換
G = (0x79BE667E, 0x483ADA77)                   # 基點（概念示範：截斷的 secp256k1 生成元）
a_priv = 987654321; b_priv = 123456789
A_pub, B_pub = point_mul(a_priv, G), point_mul(b_priv, G)
s_A = point_mul(a_priv, B_pub)                 # = a*b*G
s_B = point_mul(b_priv, A_pub)                 # = a*b*G
print(f"ECDH 共享秘密一致：{s_A == s_B}")        # True
print("ECC：256 位元金鑰 ≈ RSA-3072，但快 12 倍、憑證小 12 倍")

標準與現況#

• secp256r1（NIST P-256）：主流 TLS 曲線
• Curve25519 / Ed25519（Bernstein）：更快、更安全的形式化證明（EdDSA 簽章）——WireGuard、Signal _protocol 的首選
• ECC 的隱憂：NIST 的 P-192/P-224 有「隱藏通道」疑慮（後設機構/backdoor 爭議）；Curve25519 因構造簡潔無此爭議——閉源曲線 vs 透明曲線的信任問題
• 量子：Shor 演算法同樣破 ECC（ECDLP 是離散對數）——同樣需要後量子替代（見 2017-後量子密碼學.md）

結案 -- 後果與影響#

• 行動裝置的密碼學：ECC 是智慧手機時代的預設——小金鑰是行動裝置的必需品。
• TLS 的首選：2015 年起 iOS 憑證全部 ECC，ECDHE + ECDSA 是主流。
• 區塊鏈的基礎：比特幣/以太坊的簽章是 secp256k1（ECDSA）；以太坊的 account abstraction 用更好的簽章——見 2016-區塊鏈密碼學.md。
• 硬體安全：ECC 的硬體實作更簡單（點運算）——HSM、安全晶片的主流。
• 安全的同源性：同一數學（離散對數）跨 RSA/DH/ElGamal/ECC 四代體系——離散對數的歷史。

關鍵人物與文獻#

• Neal Koblitz（1953–）：華盛頓大學；椭圆曲線密码系统 (1987, American Mathematical Monthly)
• Victor Miller（1952–）：IBM；1985 獨立提出
• Neal Koblitz & Victor Miller：各自獨立，1985/1987
• Daniel J. Bernstein：Curve25519 / Ed25519 (2005–2008)
• SEC（SEC 1/2/3）：ECC 標準（2009 起）
• 交叉參照：1985-ElGamal.md、1977-RSA.md、2016-區塊鏈密碼學.md、1994-Shor演算法.md