密碼學 - 橢圓曲線密碼學(ECC)

在當今數位化的世界中，資訊安全至關重要。橢圓曲線密碼學 (Elliptic Curve Cryptography, ECC) 作為一種現代化的公鑰加密技術，憑藉其高效率和高安全性的優點，已廣泛應用於網頁加密 (HTTPS)、數位簽章、虛擬貨幣（如比特幣）等領域。

本文將深入淺出地介紹 ECC 的歷史、數學原理、金鑰交換機制，並透過 Python 範例實際演練。

ECC 的起源

橢圓曲線密碼學的概念最初在 1985 年由兩位數學家各自獨立提出，分別是華盛頓大學的 Neal Koblitz 和 IBM 的 Victor S. Miller。
他們發現，基於橢圓曲線的離散對數問題可以建構出一個比傳統 RSA 演算法更難破解的密碼系統，從而在提供相同安全強度的情況下，可以使用更短的金鑰。

領導此項技術標準化的公司是 Certicom，該公司擁有超過 130 項相關專利，並制定了業界廣泛採用的 SEC (Standards for Efficient Cryptography) 標準，例如 SEC 1 和 SEC 2。

核心數學概念：有限體 (Finite Field)

要理解 ECC，首先必須認識「有限體」(Finite Field)，又稱為伽羅瓦域 (Galois Field, GF) 。

一個有限體具有以下關鍵特性：

• 有限元素：集合中的元素數量是有限的。
• 封閉運算：集合內的元素可以進行加、減、乘、除運算，且結果依然落在該集合內。

ECC 主要建立在兩種類型的有限體之上：

1. 質數有限體 (Prime Finite Field, F_p)：這是最常見的類型，體中的所有運算都在模一個大質數 p 的情況下進行。
   其橢圓曲線方程式定義為 ：

   $$
   \begin{aligned}
   y^2 &\equiv x^3 + ax + b \pmod{p} \
   \end{aligned}
   $$

   其中 $a$ 和 $b$ 是定義曲線的參數，且必須滿足 $4a^3 + 27b^2 \neq 0 \pmod{p}$ 以避免奇異點。

2. 二元有限體 (Binary Finite Field, $GF(2^m)$)：此類型體中的元素以多項式來表示 ，運算則基於特徵值為 2 的不可約多項式。
   其曲線方程式定義為 ：

   $$
   \begin{aligned}
   y^2 + xy &\equiv x^3 + ax^2 + b\
   \end{aligned}
   $$

   二元體又可根據其數學基礎，分為多項式基底 (Polynomial Basis) 和常態基底 (Normal Basis)。

橢圓曲線上的運算

橢圓曲線的安全性來自於其上的特殊運算規則。在曲線上，我們可以定義一個「點」為座標 $(x, y)$，滿足橢圓曲線方程式。
所有在曲線上的點，加上一個稱為「無窮遠點」$O$ 的特殊元素，共同組成一個阿貝爾群。在此群中，無窮遠點 $O$ 扮演著單位元素 (Identity Element) 的角色，類似於整數加法中的 0 (例如 $P+O=P$ )。

點加法 (Point Addition)

取曲線上兩個不同的點 $P$ 和 $Q$，畫一條直線穿過它們，這條線會與曲線交於第三點。此點相對於 $X$ 軸的對稱點，即為 $P+Q$ 的結果。

在質數有限體 $F_p$ 中，若 $P = (x_1, y_1)$ 和 $Q = (x_2, y_2)$，則 $P+Q$ 的計算公式為：

$$
\begin{aligned}
λ &= \frac{y_2 - y_1}{x_2 - x_1} \pmod{p} \
\
x^′ &= λ^2 - x_1 - x_2 \pmod{p} \
\
y^′ &= λ(x_1 - x^′) - y_1 \pmod{p} \
\end{aligned}
$$

其中 $λ$ 是 $P$ 和 $Q$ 之間的斜率。

點倍加 (Point Doubling)

當兩個點重合時 (即 $P = Q$)，點加法變為「點倍加」，用來計算 $2P$。此時，通過 $P$ 和 $Q$ 的直線變成了在 $P$ 點的切線。其公式為：

$$
\begin{aligned}
λ &= \frac{3x^2 + a}{2y} \pmod{p} \
\
x^′ &= λ^2 - 2x \pmod{p} \
\
y^′ &= λ(x - x^′) - y \pmod{p} \
\end{aligned}
$$

其中 $λ$ 為 $P$ 點的切線斜率。

純量乘法 (Scalar Multiplication)

ECC 的核心運算就是純量乘法，即計算 $Q = dG$，其中 $d$ 是一個隨機產生的大整數，$G$ 是是曲線上的基準點 (Base Point)。而 $Q$ 則是運算後得到的新點。這個運算本質上是將點 $G$ 自己跟自己相加 $d$ 次。

$d$ 被當作私鑰 (Private Key)，而計算結果 $Q$ 則成為公鑰 (Public Key)。

ECC 的安全性基礎在於：給定 $d$ 和 $G$，計算出 $Q$ 是非常快速且容易的；但反過來，從 $Q$ 和 $G$ 反推出 $d$ 卻是極其困難的，這就是所謂的「橢圓曲線離散對數問題」(ECDLP)。

金鑰交換協議：ECDH

橢圓曲線迪菲-赫爾曼金鑰交換 (Elliptic Curve Diffie-Hellman, ECDH) 是一個讓兩個互不信任的個體能夠在不安全的通道上協商出共享秘密金鑰的協議。

流程如下：

1. 共用參數：Alice 和 Bob 雙方同意使用同一組橢圓曲線參數，包括曲線方程式、質數 $p$、以及基準點 $G$
2. 各自生成金鑰：
   • Alice 生成她的私鑰
     $d_A$，計算公鑰 $Q_A = d_A G$
   • Bob 生成他的私鑰
     $d_B$，計算公鑰 $Q_B = d_B G$
3. 交換公鑰：Alice 將她的公鑰 $Q_A$ 傳送給 Bob，Bob 也將他的公鑰 $Q_B$ 傳送給 Alice。
4. 計算共享秘密：

   • Alice 用自己的私鑰和 Bob 的公鑰計算出共享秘密：

     $$
     \begin{aligned}
     Z = d_A Q_B = d_A (d_B G) = d_A d_B G
     \end{aligned}
     $$

   • Bob 用自己的私鑰和 Alice 的公鑰計算出共享秘密：

     $$
     \begin{aligned}
     Z = d_B Q_A = d_B (d_A G) = d_B d_A G
     \end{aligned}
     $$

由於純量乘法滿足結合律，雙方會得到完全相同的點 $Z$，通常會取這個點的 X 座標作為後續對稱加密所需要的共享金鑰。

ECC 與 RSA 的安全性比較

雖然橢圓曲線密碼學 (ECC) 和 RSA 都是目前最安全、最被廣泛使用的非對稱加密演算法，但它們的數學基礎和運作效率有著顯著差異。了解這些差異，有助於我們明白為何在許多現代應用中，ECC 會成為優先選擇。

以下是兩者在各個面向的比較表：

為何 RSA-4096 對應到 ECC-384？

您可能會注意到，RSA-4096 的安全強度（約 140-150 位元）其實介於 ECC-256（128 位元強度）和 ECC-384（192 位元強度）之間。

那為什麼不選一個介於 256 和 384 之間的 ECC 曲線呢？

原因在於標準化和安全性考量：

• 標準曲線：業界使用的橢圓曲線都是經過嚴格數學驗證和安全審核的「命名曲線」（Named Curves），例如 secp256r1 (P-256) 和 secp384r1 (P-384)。並沒有一個廣泛採用的標準曲線是介於兩者之間的（例如 320 位元）。
• 向上相容原則：在密碼學實踐中，當目標安全等級沒有剛好對應的標準時，永遠要選擇「下一個更高等級」的標準來確保安全性。直接選用 ECC-384 可以確保其安全強度絕對高於 RSA-4096，提供了更強的保障。

因此，當一個系統要求使用 RSA-4096 金鑰時，與其對應的 ECC 實作方案就是 secp384r1 (P-384)。

標準化的命名曲線 (Named Curves)

為了確保不同系統間的互通性與安全性，標準化組織定義了一系列經過安全驗證的橢圓曲線，稱為「命名曲線」。開發者可以直接選用，無需自行設計複雜的曲線參數。

主要的標準化機構包括：

• NIST：美國國家標準與技術研究院，定義了廣泛使用的 P 系列曲線 (如 P-256, P-384) 和 K/B 系列曲線。
• SECG：高效密碼學標準組織，定義了 secp 和 sect 系列曲線，其中許多與 NIST 的標準重疊，例如 secp256r1 就是 NIST P-256 。廣為人知的 secp256k1 則被用於比特幣 。
• BrainPool：由德國提出的標準曲線。
• 中國 SM2：中國國家密碼管理局制定的橢圓曲線標準。

Python 實作 ECDH 範例

以下我們使用 Python 的 cryptography 函式庫來示範 ECDH 金鑰交換的過程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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

# --- 1. 雙方同意使用一條命名曲線 ---
# 我們選用 SECG 定義的 secp256r1，也就是 NIST P-256
curve = ec.SECP256R1()

# --- 2. Alice 生成自己的金鑰對 ---
# d_A 是私鑰物件，包含了私有的純量 d
d_A = ec.generate_private_key(curve)
# Q_A 是公鑰物件，包含了點 (x, y)
Q_A = d_A.public_key()

# 將 Alice 的公鑰序列化，以便傳輸 (例如透過網路)
Q_A_bytes = Q_A.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo
)

print("--- Alice 的金鑰 ---")
print(f"使用的曲線: {curve.name}")
# 為了簡潔，我們不直接印出私鑰的數值
print("Alice 已生成私鑰 d_A")
print(f"Alice 的公鑰 Q_A:\n{Q_A_bytes.decode('utf-8')}")


# --- 3. Bob 生成自己的金鑰對 ---
d_B = ec.generate_private_key(curve)
Q_B = d_B.public_key()

Q_B_bytes = Q_B.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo
)

print("--- Bob 的金鑰 ---")
print(f"使用的曲線: {curve.name}")
print("Bob 已生成私鑰 d_B")
print(f"Bob 的公鑰 Q_B:\n{Q_B_bytes.decode('utf-8')}")

# --- 4. 雙方交換公鑰並計算共享秘密 ---

# Alice 使用自己的私鑰 d_A 和 Bob 的公鑰 Q_B 來計算
shared_key_A = d_A.exchange(ec.ECDH(), Q_B)

# Bob 使用自己的私鑰 d_B 和 Alice 的公鑰 Q_A 來計算
shared_key_B = d_B.exchange(ec.ECDH(), Q_A)

print("--- 共享金鑰計算結果 ---")
print(f"Alice 計算出的共享金鑰: {shared_key_A.hex()}")
print(f"Bob 計算出的共享金鑰:   {shared_key_B.hex()}")

# 驗證雙方計算出的金鑰是否一致
if shared_key_A == shared_key_B:
    print("\n成功！雙方已協商出相同的共享金鑰。")
else:
    print("\n失敗！金鑰不一樣。")

執行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

--- Alice 的金鑰 ---
使用的曲線: secp256r1
Alice 已生成私鑰 d_A
Alice 的公鑰 Q_A:
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEPnG0hBWR0/C/5e1Da0rxZcAn9G6M
2N1hZxO0l5qp52ahFHNIjXuwLGOVe6S1e4LbisMKrsckPMO9Aq6MW0anMw==
-----END PUBLIC KEY-----

--- Bob 的金鑰 ---
使用的曲線: secp256r1
Bob 已生成私鑰 d_B
Bob 的公鑰 Q_B:
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAENVev+eNR2rmf/yKPbJI/lWtDxaM/
dzt/dw657X8aDRLuzE67rhtdSYVvkw6P9aNjPQenmEyRh2sYOLaG/WwvSA==
-----END PUBLIC KEY-----

--- 共享金鑰計算結果 ---
Alice 計算出的共享金鑰: b9d130c6171bb27bd5e0c4fbc75011a2dbf010bca7601c4ceff82a2768d34e5a
Bob 計算出的共享金鑰:   b9d130c6171bb27bd5e0c4fbc75011a2dbf010bca7601c4ceff82a2768d34e5a

成功！雙方已協商出相同的共享金鑰。

結論

橢圓曲線密碼學以其精簡的金鑰長度和卓越的安全性，成為了現代密碼學的基石。從保護我們的網路瀏覽紀錄到確保金融交易的安全，ECC 無所不在。透過理解其背後的數學原理和如 ECDH 這樣的應用協議，我們能更深刻地體會到這個強大工具如何在數位時代中捍衛我們的資訊安全。

也許你也會想看看

• 密碼學 - AES
• 密碼學 - SignedData 與 EnvelopedData
• 密碼學 - DSA