前言

在 Day 28 中，我們鋪設好了抽象代數的舞台——有限域 GF(p) 與 群論（Group Theory）。我們知道了密碼學需要在無捨入誤差、封閉且滿足算術公理的離散空間中進行運算。

本章將正式讓舞者登場：我們將在有限域 GF(p) 上繪製出橢圓曲線（Elliptic Curve），學習如何在曲線上定義幾何「點加法」與「點倍加」，並徹底推導出現代非對稱密碼學的核心運算公式——Q = kG（公開金鑰 = 私密純量 X 基準點）。

一、 橢圓曲線方程與幾何結構

在密碼學中，最常用的是短 Weierstrass 方程式（Short Weierstrass Form）：

y^2 ≡ x^3 + ax + b (mod p)

其中 a, b ∈ GF(p) 為決定曲線形狀的公開參數，p 為定義有限域的大質數。

1. 非奇異條件（Non-singular Condition）

為確保曲線平滑且沒有交叉點或尖點（Cusp），參數必須滿足以下判別式限制：

4a^3 + 27b^2 ≠ 0 (mod p)

此條件保證了方程式的右半部 x^3 + ax + b = 0 沒有重根，進而確保曲線上每一點都能繪製出唯一的切線。

2. 從連續實數到離散散點圖

• **實數平面 R **：滿足方程式的 (x, y) 是平滑連續的幾何曲線，且關於 x 軸對稱（若 (x, y) 在曲線上，則 (x, -y) 必在曲線上）。
• 質數有限域（GF(p)）：x, y ∈ {0, 1, 2, ..., p-1}。連續的曲線散落為平面上的離散點陣列，但其內含的代數同餘對稱性（(x, y) 與 (x, p-y)）依然完美保留。

二、 曲線上的群運算：點加法與點倍加

我們在曲線上定義一種二元運算 "+"（點加法）。注意：這不是將點的 x, y 座標直接相加，而是基於「割線與切線」的幾何交點所導出的同餘運算。

1. 幾何直覺：割線法與切線法

1. 點加法（P + Q）：穿過 P, Q 兩點繪製一條割線，該直線必與橢圓曲線相交於第三點。將第三個交點沿 x 軸做垂直反射（y \to -y (pmod p），所得的點即為 R = P + Q。)
2. 點倍加（2P = P + P）：做點 P 在曲線上的切線，該切線與曲線相交於另一點。將該點沿 x 軸做垂直反射，所得的點即為 R = 2P。
3. 無窮遠點（Point at Infinity, O）：若畫出的割線或切線為垂直線（例如 P = (x, y) 與 -P = (x, -y)），直線將向上延伸交於無窮遠處。我們定義 O 為該點群的單位元素（Identity Element），滿足：

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

2. 代數推導公式

給定兩點 P = (x_1, y_1) 與 Q = (x_2, y_2)：

情況 A：點加法（Point Addition, P ≠ Q 且 x_1 ≠ x_2）

1. 計算割線斜率 λ：

λ ≡ \frac{y_2 - y_1}{x_2 - x_1} ≡ (y_2 - y_1)(x_2 - x_1)^{-1} (mod p)

2. 計算和點 R = (x_3, y_3)：

x_3 ≡ λ^2 - x_1 - x_2 (mod p)

y_3 ≡ λ(x_1 - x_3) - y_1 (mod p)

情況 B：點倍加（Point Doubling, P = Q 且 y_1 ≠ 0）

1. 計算切線斜率 λ（由隱微分 \frac{dy}{dx} = \frac{3x^2 + a}{2y} 匯出）：

λ ≡ \frac{3x_1^2 + a}{2y_1} ≡ (3x_1^2 + a)(2y_1)^{-1} (mod p)

2. 計算倍點 2P = (x_3, y_3)：

x_3 ≡ λ^2 - 2x_1 (mod p)

y_3 ≡ λ(x_1 - x_3) - y_1 (mod p)

三、 有限域點加法手算範例 (Worked Numerical Example)

設有限域 GF(17)，選定橢圓曲線：

y^2 ≡ x^3 + 2x + 2 (mod 17 ) , (a = 2, b = 2, p = 17)

驗證點 P = (5, 1) 與 Q = (6, 3) 是否在曲線上：

• 對 P(5,1)：y^2 = 1^2 = 1；x^3 + 2x + 2 = 125 + 10 + 2 = 137 ≡ 1 (mod 17 )（同餘成立）。
• 對 Q(6,3)：y^2 = 3^2 = 9；x^3 + 2x + 2 = 216 + 12 + 2 = 230 ≡ 9 (mod 17 )（同餘成立）。

求解 R = P + Q = (x_3, y_3)：

Step 1: 計算割線斜率 λ

λ ≡ (3 - 1) * (6 - 5)^{-1} ≡ 2 * 1^{-1} ≡ 2 (mod 17 )

Step 2: 計算 x_3

x_3 ≡ λ^2 - x_1 - x_2 ≡ 2^2 - 5 - 6 = 4 - 11 = -7 ≡ 10 (mod 17 )

Step 3: 計算 y_3

y_3 ≡ λ(x_1 - x_3) - y_1 ≡ 2(5 - 10) - 1 = 2(-5) - 1 = -11 ≡ 6 (mod 17 )

推導結果：P(5,1) + Q(6,3) = R(10, 6) (mod 17 )。

• 反向代回驗證 R(10, 6)：
• 左式：y^2 = 6^2 = 36 ≡ 2 (mod 17 )
• 右式：x^3 + 2x + 2 = 1000 + 20 + 2 = 1022 = 60 * 17 + 2 ≡ 2 (mod 17 )
• 兩邊皆為 2，證明點 R(10,6) 完美落在曲線上！

四、 純量乘法與 Q = kG 金鑰生成

有了點加法與點倍加，我們就可以定義 ECC 中最重要的單向函數——純量乘法（Scalar Multiplication）：

Q = kG = G + G + ... + G (k 次)

其中：

• G = (x_G, y_G)：曲線上的公開基準點（Base Point）。
• k：私密純量（Private Scalar / 私鑰），為一個安全隨機抽樣的大整數。
• Q = (x_Q, y_Q)：計算出的公開點（Public Point / 公鑰）。

1. 快速演算法：Double-and-Add

若逐次累加 G 共 k 次，演算法複雜度為 O(k)。當 k 為 256-bit 大數時（約 10^{77}），古典電腦耗盡宇宙壽命也無法算完。

工程上採用 Double-and-Add 演算法，將 k 轉為二進位展開，時間複雜度降至 O(log k)（最多只需 256 次點倍加與 256 次點加法）：

以 k = 13_{10} = 1101_2 為例：

13G = (1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0)G = 8G + 4G + G

[ Double-and-Add 運算軌跡 (k = 13 = 1101₂) ]
Bit 3 (1) ──> 初始點 G
Bit 2 (1) ──> Double(2G) ──> Add(2G + G = 3G)
Bit 1 (0) ──> Double(6G) ──> (Bit為0, 不執行Add)
Bit 0 (1) ──> Double(12G) ──> Add(12G + G = 13G) ──> 最終結果 Q

資安警示（時序側信道攻擊）：上述標準 Double-and-Add 中，Add 運算僅在位元為 1 時執行。攻擊者可透過監測 CPU 執行時間或功耗波動（Power Analysis）反推 k 的位元值。生產級密碼庫（如 OpenSSL、Bouncy Castle）必須採用常數時間（Constant-Time） 的 Montgomery Ladder 演算法。

2. 橢圓曲線離散對數難題（ECDLP）

• 正向計算（極快）：已知 k 與 G，計算 Q = kG 只需微秒級。
• 反向推導（極難）：已知 G 與 Q，欲求解私密純量 k = log_G(Q)，在選定合規曲線與足夠大的子群下，古典電腦無有效演算法破譯。這就是 ECC 安全性的鐵壁。

五、 Java JCA 生產級 ECC KeyPair 生成實作

在標準 Java JCA 中，我們可以使用原生 KeyPairGenerator 指定 NIST 標準曲線 secp256r1（即 P-256），生成 ECC 金鑰對並導出其數學參數：

import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.interfaces.ECPrivateKey;
import java.security.interfaces.ECPublicKey;
import java.security.spec.ECGenParameterSpec;
import java.security.spec.ECPoint;
import java.util.Arrays;

public class EccKeyPairProductionExample {

    private static final String EC_ALGORITHM = "EC";
    private static final String CURVE_NAME = "secp256r1"; // NIST P-256 (256-bit)

    public static void main(String[] args) throws Exception {
        System.out.println("正在生成 ECC KeyPair (曲線規格: " + CURVE_NAME + ")...");

        // 1. 初始化 EC 金鑰產生器
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(EC_ALGORITHM);
        ECGenParameterSpec ecSpec = new ECGenParameterSpec(CURVE_NAME);
        keyPairGen.initialize(ecSpec);

        // 2. 執行純量乘法 Q = k * G
        KeyPair keyPair = keyPairGen.generateKeyPair();
        PublicKey pubKey = keyPair.getPublic();
        PrivateKey privKey = keyPair.getPrivate();

        // 3. 提取 ECC 公鑰點座標 Q = (x, y)
        if (pubKey instanceof ECPublicKey ecPubKey) {
            ECPoint qPoint = ecPubKey.getW();
            System.out.println("\n--- ECC 公鑰 (Public Point Q) ---");
            System.out.println("X 座標 (Hex): " + qPoint.getAffineX().toString(16));
            System.out.println("Y 座標 (Hex): " + qPoint.getAffineY().toString(16));
        }

        // 4. 提取 ECC 私鑰純量 k
        if (privKey instanceof ECPrivateKey ecPrivKey) {
            System.out.println("\n--- ECC 私鑰 (Private Scalar k) ---");
            System.out.println("私密純量 S (Bit Length): " + ecPrivKey.getS().bitLength() + " bits");
            System.out.println("私鑰參數 S 必須嚴密保管，嚴禁洩露或寫入 Log 中！");
        }

        System.out.println("\n 生產級 ECC KeyPair 生成成功！");
    }
}