橢圓曲線點壓縮數學原理完整指南：從代數基礎到 secp256k1 實作

進階 📅 發布：2026-03-22 🏷️ privacy, elliptic-curve, point-compression, secp256k1, cryptography, mathematics, solidity, smart-contract, side-channel, security, ethereum, bitcoin 計算中...

橢圓曲線點壓縮是以太坊、比特幣等區塊鏈系統中廣泛使用的空間優化技術。通過僅存儲曲線點的 x 座標和一個奇偶校驗位，點壓縮可以將 64 位元組的未壓縮座標減少到僅 33 位元組，節省約 50% 的存儲空間和傳輸帶寬。本文從數學原理出發，深入解析點壓縮的代數基礎、橢圓曲線密碼學中的實際應用、以及在 secp256k1 曲線上的完整推導過程。涵蓋模平方根計算、Tonelli-Shanks 算法、SEC 1/2 標準、以太坊智能合約實作，以及側信道攻擊防禦等核心主題。

橢圓曲線點壓縮數學原理完整指南：從代數基礎到 secp256k1 實作

概述

橢圓曲線點壓縮（Point Compression）是以太坊、比特幣等區塊鏈系統中廣泛使用的空間優化技術。通過僅存儲曲線點的 x 座標和一個奇偶校驗位，點壓縮可以將 64 位元組的未壓縮座標減少到僅 33 位元組，節省約 50% 的存儲空間和傳輸帶寬。本文從數學原理出發，深入解析點壓縮的代數基礎、橢圓曲線密碼學中的實際應用、以及在 secp256k1 曲線上的完整推導過程，為開發者提供理論與實作兼備的完整指南。

一、橢圓曲線代數基礎回顧

1.1 橢圓曲線的數學定義

橢圓曲線密碼學的安全性建立在曲線方程的代數結構之上。secp256k1 使用的魏爾斯特拉斯（Weierstrass）標準形式定義為：

$$E: y^2 = x^3 + ax + b \pmod{p}$$

其中 secp256k1 的參數為：

$a = 0$
$b = 7$
$p = 2^{256} - 2^{32} - 2^9 - 2^6 - 2^4 - 2^0 = 115792089237316195423570985008687907852837564279074904382605163141518161494337$

曲線上的點 $(x, y)$ 滿足上述方程，且所有運算均在質數域 $\mathbb{F}_p$ 上進行。

1.2 曲線方程的對稱性

曲線方程 $y^2 = x^3 + ax + b$ 具有一個關鍵的代數性質：對 x 軸的對稱性。

對於任意滿足方程的點 $(x, y)$，由於方程左邊是 $y^2$，所以 $(x, -y \bmod p)$ 同樣是方程的解：

$$(-y)^2 = y^2 = x^3 + ax + b$$

這個對稱性意味著：給定 x 座標，曲線上最多有兩個可能的點（y 取正值或負值）。這是點壓縮能夠成立的數學基礎。

1.3 有限域的算術

在有限域 $\mathbb{F}p$ 中，每個元素都有唯一的「負元素」表示。對於任意 $a \in \mathbb{F}p$：

$$-a \equiv p - a \pmod{p}$$

例如，在 secp256k1 中：

如果 $y = 123456789$
那麼 $-y \equiv p - 123456789 = 115792089237316195423570985008687907852837564279074904382605163141518161494337 - 123456789$

這種負元素的表示允許我們通過單個位元（y 的奇偶性）來區分兩個可能的 y 值。

二、點壓縮的數學原理

2.1 從 x 座標恢復 y 座標

點壓縮的核心思想是：給定 x 座標和 y 座標的奇偶性，可以唯一確定完整的點 $(x, y)$。

推導過程：

已知：曲線方程 $y^2 = x^3 + ax + b$
已知：x 座標（用於定位曲線上的點）
計算：$y^2 \equiv x^3 + ax + b \pmod{p}$
求解：$y = \pm\sqrt{y^2}$（兩個可能的平方根）
確定：通過奇偶校驗位選擇正確的根

為什麼只有兩個可能的 y 值：

在有限域 $\mathbb{F}p$ 中（p 為質數），乘法群 $\mathbb{F}p^*$ 是 $p-1$ 階循環群。根據拉格朗日定理：

若 $p - 1$ 為偶數（恆成立，因為 p 是奇質數）
對於任意非零 $a \in \mathbb{F}_p$，$a^{(p-1)/2}$ 的值為 $+1$ 或 $-1$
這意味著每個非零平方根恰好有兩個：一個是另一個的負元

對於 $y = 0$ 的特殊情況，該點是自身的負元，但這種情況在密碼學應用中極為罕見（概率約為 $1/p$）。

2.2 模平方根的計算

從 $y^2 \pmod{p}$ 計算 $y$ 需要求解模平方根。這在 secp256k1 中特別有趣，因為 $p \equiv 3 \pmod{4}$。

Tonelli-Shanks 算法：

對於一般的質數 p，求解 $y^2 \equiv n \pmod{p}$ 使用 Tonelli-Shanks 算法：

def tonelli_shanks(n, p):
    """
    Tonelli-Shanks 算法：求解 x^2 ≡ n (mod p)
    
    假設 n 不是 0 且 p 是奇質數
    返回 x 和 -x（若不存在返回 None）
    """
    
    # 勒讓德符號檢查
    if legendre_symbol(n, p) != 1:
        return None
    
    # 特殊情况：p ≡ 3 (mod 4)
    if p % 4 == 3:
        # 直接計算：x = ±n^((p+1)/4)
        return pow(n, (p + 1) // 4, p), p - pow(n, (p + 1) // 4, p)
    
    # 一般情况：Tonelli-Shanks
    # 將 p-1 分解為 Q * 2^S，其中 Q 為奇數
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    
    # 找到一個非平方剩余
    z = 2
    while legendre_symbol(z, p) != -1:
        z += 1
    
    # 初始化
    m = s
    c = pow(z, q, p)
    t = pow(n, q, p)
    r = pow(n, (q + 1) // 2, p)
    
    # 主循環
    while True:
        if t == 0:
            return 0, 0
        if t == 1:
            return r, p - r
        
        # 找到最小的 i 使得 t^(2^i) = 1
        i = 1
        t2i = t * t % p
        while t2i != 1:
            t2i = t2i * t2i % p
            i += 1
        
        # 更新
        b = pow(c, 2 ** (m - i - 1), p)
        m = i
        c = b * b % p
        t = t * c % p
        r = r * b % p
    
def legendre_symbol(a, p):
    """勒讓德符號：(a/p)"""
    a = a % p
    result = 1
    while a != 0:
        while a % 2 == 0:
            a //= 2
            if p % 8 in [3, 5]:
                result = -result
        a, p = p, a
        if a % 4 == 3 and p % 4 == 3:
            result = -result
        a = a % p
    if p == 1:
        return result
    return 0

secp256k1 的特殊優化：

由於 secp256k1 的質數 $p$ 滿足 $p \equiv 3 \pmod{4}$，我們可以使用更簡潔的公式：

$$y = \pm n^{\frac{p+1}{4}} \pmod{p}$$

這是因為：

$$y^2 = n^{\frac{p+1}{2}} = n^{\frac{p-1}{2}} \cdot n \equiv \left(\frac{n}{p}\right) \cdot n \equiv n \pmod{p}$$

當 $n$ 確實是平方剩余時（$\frac{n}{p} = 1$），上述公式給出正確的平方根。

2.3 奇偶校驗位的編碼

在點壓縮格式中，y 座標的奇偶性通過一個額外位元來表示：

y 值	奇偶校驗位	壓縮前綴
偶數	0	0x02
奇數	2	0x03

為什麼用 0x02 和 0x03：

這是 SEC 1（Standards for Efficient Cryptography）標準定義的編碼方式：

0x02：表示 y 座標是偶數（$y \bmod 2 = 0$）
0x03：表示 y 座標是奇數（$y \bmod 2 = 1$）

對於無窮遠點（通常不用於密碼學應用），使用 0x00 作為前綴。

三、secp256k1 點壓縮完整推導

3.1 secp256k1 的特殊性質

secp256k1 的質數 $p$ 具有以下特殊結構：

$$p = 2^{256} - 2^{32} - 2^9 - 2^6 - 2^4 - 2^0$$

計算驗證：

$p \bmod 4 = 3$（因為 $2^{256} \equiv 0$、$-2^{32} \equiv 0$、$-2^9 - 2^6 - 2^4 - 2^0 = -735 \equiv 1 \pmod{4}$，總和 $0 + 0 + 1 = 1$）
因此可以使用快速平方根算法

3.2 點壓縮算法推導

輸入：

x 座標：$x \in \mathbb{F}_p$
y 奇偶校驗位：$parity \in \{0, 1\}$

輸出：

壓縮格式：$[parity + 2] \concat x$

步驟一：計算 $y^2$

$$y^2 = x^3 + 7 \pmod{p}$$

步驟二：計算 y 的候選值

$$y_{cand} = (y^2)^{\frac{p+1}{4}} \pmod{p}$$

這個步驟利用了 $p \equiv 3 \pmod{4}$ 的性質。

步驟三：根據奇偶校驗位選擇正確的 y

如果 y_cand mod 2 == parity:
    y = y_cand
否則:
    y = p - y_cand  # 取負元

選擇的原因：$y{cand}$ 和 $p - y{cand}$ 的奇偶性必然相反。

步驟四：驗證

確認 $(x, y)$ 確實在曲線上：

$$y^2 \equiv x^3 + 7 \pmod{p}$$

3.3 完整 Python 實現

import hashlib

# secp256k1 參數
P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
A = 0
B = 7

def mod_sqrt(n, p):
    """
    計算 n 在模 p 下的平方根
    假設 p ≡ 3 (mod 4) 且 n 是二次剩余
    """
    # 使用快速公式：x = ±n^((p+1)/4)
    return pow(n, (p + 1) // 4, p)

def compress_point(x, y):
    """
    點壓縮：將 (x, y) 編碼為 33 位元組
    
    格式：[0x02 或 0x03] || [32 位元組的 x 座標]
    
    Args:
        x: x 座標（整數）
        y: y 座標（整數）
    
    Returns:
        33 位元組的壓縮點
    """
    # 確定奇偶校驗位
    parity = y & 1
    
    # 添加前綴
    prefix = 0x02 | parity
    
    # x 座標編碼為 32 位元組大端序
    x_bytes = x.to_bytes(32, 'big')
    
    # 組合
    compressed = bytes([prefix]) + x_bytes
    
    return compressed

def decompress_point(compressed):
    """
    點解壓：從壓縮格式恢復完整的 (x, y)
    
    Args:
        compressed: 33 位元組的壓縮點
    
    Returns:
        (x, y) 元組
    
    Raises:
        ValueError: 如果點不在曲線上
    """
    if len(compressed) != 33:
        raise ValueError("Compressed point must be 33 bytes")
    
    # 解析前綴和 x 座標
    prefix = compressed[0]
    x = int.from_bytes(compressed[1:33], 'big')
    
    # 驗證前綴
    if prefix not in (0x02, 0x03):
        raise ValueError(f"Invalid prefix: {hex(prefix)}")
    
    parity = prefix & 1
    
    # 計算 y^2
    y_squared = (pow(x, 3, P) + B) % P
    
    # 計算 y 的候選值
    y = mod_sqrt(y_squared, P)
    
    # 選擇正確的 y（基於奇偶校驗位）
    if (y & 1) != parity:
        y = P - y
    
    # 驗證
    if (pow(y, 2, P) - y_squared) % P != 0:
        raise ValueError("Point is not on the curve")
    
    return x, y

def is_on_curve(x, y):
    """檢查點是否在 secp256k1 曲線上"""
    return (pow(y, 2, P) - (pow(x, 3, P) + B) % P) % P == 0

# 測試
if __name__ == "__main__":
    # 使用已知的 secp256k1 基點
    Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
    Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    
    # 測試點壓縮
    compressed = compress_point(Gx, Gy)
    print(f"壓縮格式: {compressed.hex()}")
    print(f"壓縮前綴: 0x{compressed[0]:02x}")
    
    # 測試點解壓
    x, y = decompress_point(compressed)
    print(f"解壓後 x: {hex(x)}")
    print(f"解壓後 y: {hex(y)}")
    
    # 驗證
    print(f"x 匹配: {x == Gx}")
    print(f"y 匹配: {y == Gy}")
    print(f"在曲線上: {is_on_curve(x, y)}")
    
    # 測試不同的點
    print("\n--- 測試其他點 ---")
    # 計算 2G
    def point_add(x1, y1, x2, y2):
        if x1 == 0 and y1 == 0:
            return x2, y2
        if x2 == 0 and y2 == 0:
            return x1, y1
        
        if x1 == x2:
            if y1 == y2:
                # 倍點
                lam = (3 * x1 * x1) * pow(2 * y1, -1, P) % P
            else:
                return 0, 0
        else:
            lam = (y2 - y1) * pow(x2 - x1, -1, P) % P
        
        x3 = (lam * lam - x1 - x2) % P
        y3 = (lam * (x1 - x3) - y1) % P
        return x3, y3
    
    # 2G
    x2, y2 = point_add(Gx, Gy, Gx, Gy)
    compressed2 = compress_point(x2, y2)
    print(f"2G 壓縮: {compressed2.hex()}")
    
    # 解壓 2G
    x2d, y2d = decompress_point(compressed2)
    print(f"2G 解壓匹配: {x2 == x2d and y2 == y2d}")

3.4 Solidity 實現

在以太坊智能合約中實現點壓縮解壓：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

/**
 * @title Secp256k1PointCompression
 * @notice secp256k1 點壓縮與解壓縮的 Solidity 實現
 */
library Secp256k1PointCompression {
    
    // secp256k1 質數
    uint256 constant P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F;
    
    // 曲線參數
    uint256 constant A = 0;
    uint256 constant B = 7;
    
    /**
     * @notice 從壓縮格式解壓縮點
     * @param compressed 33 位元組的壓縮點 [prefix || x]
     * @return x x 座標
     * @return y y 座標
     */
    function decompress(bytes calldata compressed) 
        internal 
        pure 
        returns (uint256 x, uint256 y) 
    {
        require(compressed.length == 33, "Invalid compressed point length");
        
        // 解析前綴和 x 座標
        uint256 prefix = uint8(compressed[0]);
        x = uint256(bytes32(compressed[1:33]));
        
        // 驗證前綴
        require(prefix == 0x02 || prefix == 0x03, "Invalid prefix");
        
        // 提取奇偶校驗位
        uint256 parity = prefix & 1;
        
        // 計算 y^2 = x^3 + 7
        uint256 ySquared = addmod(
            mulmod(x, x, P),  // x^2
            mulmod(x, ySquared, P),  // x^3 (這裡需要修正)
            P
        );
        
        // 實際計算 x^3 + 7
        ySquared = addmod(
            mulmod(mulmod(x, x, P), x, P),
            7,
            P
        );
        
        // 使用費馬小定理計算模逆元
        // y = (y^2)^((p+1)/4) mod p  (因為 p ≡ 3 mod 4)
        uint256 exp = (P + 1) / 4;
        y = modExp(ySquared, exp, P);
        
        // 檢查 y 的奇偶性是否匹配
        if ((y & 1) != parity) {
            y = P - y;
        }
        
        // 驗證結果（可選，取消注釋以啟用）
        // require(mulmod(y, y, P) == ySquared, "Point not on curve");
    }
    
    /**
     * @notice 點壓縮
     * @param x x 座標
     * @param y y 座標
     * @return compressed 33 位元組的壓縮點
     */
    function compress(uint256 x, uint256 y) 
        internal 
        pure 
        returns (bytes memory compressed) 
    {
        compressed = new bytes(33);
        
        // 前綴：根據 y 的奇偶性
        compressed[0] = bytes1(uint8(0x02 | (y & 1)));
        
        // x 座標
        bytes32 xBytes = bytes32(x);
        for (uint i = 0; i < 32; i++) {
            compressed[i + 1] = xBytes[i];
        }
    }
    
    /**
     * @notice 計算 a^e mod n（使用預編譯合約）
     */
    function modExp(
        uint256 base, 
        uint256 exp, 
        uint256 mod
    ) internal view returns (uint256 result) {
        assembly {
            let pointer := mload(0x40)
            mstore(pointer, 0x20)
            mstore(add(pointer, 0x20), 0x20)
            mstore(add(pointer, 0x40), base)
            mstore(add(pointer, 0x60), exp)
            mstore(add(pointer, 0x80), mod)
            
            // 調用預編譯合約 0x05 (modexp)
            if iszero(staticcall(sub(gas(), 2000), 0x05, pointer, 0xa0, pointer, 0x20)) {
                revert(0, 0)
            }
            
            result := mload(pointer)
        }
    }
}

/**
 * @title 使用點壓縮的示例合約
 */
contract PointCompressionExample {
    using Secp256k1PointCompression for bytes;
    
    // 存儲解壓縮後的座標
    struct Point {
        uint256 x;
        uint256 y;
    }
    
    // 存儲多個點
    mapping(uint256 => Point) public points;
    uint256 public pointCount;
    
    /**
     * @notice 添加點（使用壓縮格式）
     * @param compressed 33 位元組的壓縮點
     */
    function addCompressedPoint(bytes calldata compressed) external {
        (uint256 x, uint256 y) = compressed.decompress();
        
        points[pointCount] = Point(x, y);
        pointCount++;
    }
    
    /**
     * @notice 獲取點的壓縮格式
     * @param index 點的索引
     * @return compressed 33 位元組的壓縮點
     */
    function getCompressedPoint(uint256 index) 
        external 
        view 
        returns (bytes memory compressed) 
    {
        Point memory p = points[index];
        compressed = Secp256k1PointCompression.compress(p.x, p.y);
    }
}

四、以太坊中的實際應用

4.1 交易簽名中的點壓縮

以太坊交易簽名使用 ECDSA，簽名結果 $(r, s)$ 只依賴於公鑰的 x 座標。雖然簽名本身不使用點壓縮，但公鑰在區塊鏈上傳輸時可以使用點壓縮來節省空間。

以太坊簽名結構：

未壓縮公鑰: 65 位元組
  - 1 位元組前綴 (0x04)
  - 32 位元組 x 座標
  - 32 位元組 y 座標

壓縮公鑰: 33 位元組
  - 1 位元組前綴 (0x02 或 0x03)
  - 32 位元組 x 座標

在以太坊中：

ecrecover 預編譯合約接受未壓縮公鑰（65 位元組）
但錢包和節點之間可以使用壓縮格式傳輸

4.2 區塊頭中的交易樹

以太坊區塊頭包含交易的 Merkle 樹根。交易可以選擇使用壓縮格式存儲以節省磁盤空間，但這需要節點軟體支援。

4.3 智能合約中的應用場景

場景一：驗證簽名者身份

假設你需要驗證某個簽名來自特定的公鑰，可以使用點壓縮來高效存儲公鑰：

contract CompressedSignatureVerifier {
    using Secp256k1PointCompression for bytes;
    
    // 存儲授權的公鑰（點壓縮格式）
    mapping(bytes32 => bool) public authorizedSigners;
    
    /**
     * @notice 添加授權簽名者
     * @param compressedKey 33 位元組的壓縮公鑰
     */
    function addSigner(bytes calldata compressedKey) external {
        require(compressedKey.length == 33, "Invalid key length");
        
        // 計算公鑰的哈希作為識別符
        bytes32 keyHash = keccak256(compressedKey);
        authorizedSigners[keyHash] = true;
    }
    
    /**
     * @notice 驗證簽名
     * @param message 簽名的消息
     * @param signature 65 位元組的 ECDSA 簽名
     * @param compressedKey 33 位元組的壓縮公鑰
     * @return bool 是否為授權簽名
     */
    function verify(
        bytes32 message,
        bytes calldata signature,
        bytes calldata compressedKey
    ) external view returns (bool) {
        // 解壓縮公鑰
        (uint256 x, uint256 y) = compressedKey.decompress();
        
        // 恢復簽名者地址
        address signer = ecrecover(
            message,
            uint8(signature[64]),
            bytes32(signature[:32]),
            bytes32(signature[32:64])
        );
        
        // 驗證地址是否來自指定的公鑰
        address derived = address(uint160(uint256(keccak256(abi.encodePacked(x, y))) % type(uint160).max));
        
        // 或者直接使用 ecrecover 返回的地址
        return authorizedSigners[keccak256(compressedKey)] && 
               signer != address(0);
    }
}

場景二：高效存儲多個點

當合約需要存儲大量公鑰或地址時，點壓縮可以節省約 50% 的存儲成本：

contract EfficientPointStorage {
    using Secp256k1PointCompression for bytes;
    
    // 未壓縮格式存儲：65 * N 位元組
    // struct UncompressedPoint { uint256 x; uint256 y; }
    
    // 壓縮格式存儲：33 * N 位元組
    bytes[] public compressedPoints;
    
    // 存儲 x 座標（32 位元組）+ 奇偶校驗（1 位）
    struct CompactPoint {
        uint256 x;
        bool yIsOdd;
    }
    CompactPoint[] public compactPoints;
    
    /**
     * @notice 添加點（壓縮格式）
     * @param compressed 33 位元組的壓縮點
     */
    function addCompressed(bytes calldata compressed) external {
        compressedPoints.push(compressed);
    }
    
    /**
     * @notice 添加點（緊湊格式）
     * @param x x 座標
     * @param yIsOdd y 是否為奇數
     */
    function addCompact(uint256 x, bool yIsOdd) external {
        compactPoints.push(CompactPoint(x, yIsOdd));
    }
    
    /**
     * @notice 批量驗證點是否在曲線上
     * @param indices 要驗證的點索引
     * @return results 驗證結果
     */
    function batchVerifyOnCurve(uint256[] calldata indices) 
        external 
        view 
        returns (bool[] memory results) 
    {
        results = new bool[](indices.length);
        
        for (uint i = 0; i < indices.length; i++) {
            CompactPoint memory p = compactPoints[indices[i]];
            uint256 ySquared = addmod(
                mulmod(mulmod(p.x, p.x, p.x), p.x, P),
                7,
                P
            );
            
            // 計算 y 並檢查奇偶性
            uint256 y = modSqrt(ySquared, P);
            results[i] = (y & 1 == (p.yIsOdd ? 1 : 0));
        }
    }
    
    uint256 constant P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F;
    
    function modSqrt(uint256 a, uint256 p) internal view returns (uint256) {
        if (a == 0) return 0;
        if (p % 4 == 3) {
            return powmod(a, (p + 1) / 4, p);
        }
        // 使用 Tonelli-Shanks
        // ...
    }
    
    function powmod(uint256 a, uint256 e, uint256 m) internal view returns (uint256) {
        uint256 result;
        assembly {
            let pointer := mload(0x40)
            mstore(pointer, 0x20)
            mstore(add(pointer, 0x20), 0x20)
            mstore(add(pointer, 0x40), a)
            mstore(add(pointer, 0x60), e)
            mstore(add(pointer, 0x80), m)
            if iszero(staticcall(sub(gas(), 2000), 0x05, pointer, 0xa0, pointer, 0x20)) {
                revert(0, 0)
            }
            result := mload(pointer)
        }
        return result;
    }
}

4.4 與橢圓曲線配對的交互

在 zk-SNARK 和其他需要配對的場景中，點壓縮用於減少 CRS（Common Reference String）的存儲大小。

Groth16 CRS 的壓縮優化：

class CompressedGroth16CRS:
    """
    壓縮 Groth16 CRS 以減少存儲需求
    
    原始 CRS:
    - G1 元素: 每個 48-64 位元組
    - G2 元素: 每個 96-128 位元組
    
    壓縮後:
    - G1 元素: 每個 33 位元組（點壓縮）
    - G2 元素: 每個 64 位元組（優化表示）
    """
    
    P_G1 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    P_G2 = 0x1A0111EA397FE69A4B1BA7B6434BACD76468B6985D2462CF4A3732E79A3F8F2B5
    
    def compress_g1(self, x, y):
        """壓縮 G1 點"""
        prefix = 0x02 | (y & 1)
        return bytes([prefix]) + x.to_bytes(32, 'big')
    
    def decompress_g1(self, compressed):
        """解壓縮 G1 點"""
        prefix = compressed[0]
        x = int.from_bytes(compressed[1:33], 'big')
        parity = prefix & 1
        
        y_squared = (pow(x, 3, self.P_G1) + 3) % self.P_G1  # BN128: y^2 = x^3 + 3
        y = pow(y_squared, (self.P_G1 + 1) // 4, self.P_G1)
        
        if (y & 1) != parity:
            y = self.P_G1 - y
            
        return x, y
    
    def compress_g2(self, g2_point):
        """
        壓縮 G2 點
        
        G2 點在 Fp2 域上：
        - x = x0 + x1 * i
        - y = y0 + y1 * i
        
        優化壓縮只存儲 x0, x1 和一個選擇位
        """
        x0, x1 = g2_point[0]  # 假設格式
        y0, y1 = g2_point[1]
        
        # 選擇位：y0 的奇偶性
        selection = y0 & 1
        
        # 存儲：x0 || x1 || selection
        compressed = (
            x0.to_bytes(32, 'big') + 
            x1.to_bytes(32, 'big') + 
            bytes([selection])
        )
        
        return compressed
    
    def decompress_g2(self, compressed):
        """解壓縮 G2 點"""
        x0 = int.from_bytes(compressed[0:32], 'big')
        x1 = int.from_bytes(compressed[32:64], 'big')
        selection = compressed[64]
        
        # 恢復 y
        # 需要求解兩個二次方程
        # 這裡省略詳細實現
        # ...
        
        return (x0, x1), (y0, y1)

五、安全考量與最佳實踐

5.1 側信道攻擊防禦

點解壓過程可能成為側信道攻擊的目標。攻擊者可能通過分析執行時間來推斷私鑰信息。

防禦措施：

恆定時間實現：確保解壓縮過程的執行時間與輸入無關

def constant_time_decompress(compressed, expected_parity=None):
    """
    恆定時間的點解壓
    
    防止基於時間的側信道攻擊
    """
    prefix = compressed[0]
    x = int.from_bytes(compressed[1:33], 'big')
    
    # 計算 y^2
    y_squared = (pow(x, 3, P) + B) % P
    
    # 計算 y
    y = pow(y_squared, (P + 1) // 4, P)
    
    # 恆定時間選擇
    # 如果 expected_parity 為 None，使用原始奇偶性
    # 否則根據 expected_parity 選擇 y
    
    if expected_parity is not None:
        actual_parity = y & 1
        parity_match = constant_time_compare(actual_parity, expected_parity)
        
        # 恆定時間選擇：如果不匹配，取負元
        y_corrected = (y + (P - y)) & ~parity_match | y & parity_match
        
        # 或者更簡潔：
        # y = parity_match * y + (1 - parity_match) * (P - y)
        # y = (y ^ (P - y)) * parity_match + y
        # 這會導致執行時間與 parity_match 無關
        
        y = constant_time_select(y, P - y, parity_match ^ actual_parity)
    else:
        # 根據壓縮前綴選擇
        parity = prefix & 1
        if (y & 1) != parity:
            y = P - y
    
    return x, y

def constant_time_compare(a, b):
    """恆定時間比較"""
    a = a ^ a  # 確保是 0 或 1
    b = b ^ b
    return 0 if a == b else 1

def constant_time_select(when_0, when_1, selector):
    """恆定時間選擇：selector=0 返回 when_0，selector=1 返回 when_1"""
    # selector 應該是 0 或 1
    mask = -selector  # 如果 selector=1，mask=0xFFF...；如果 selector=0，mask=0
    return (when_0 & mask) | (when_1 & ~mask)

避免分支：使用恆定時間操作替代分支

安全的隨機化：在計算前添加隨機偏移

def randomized_decompress(compressed, random_seed):
    """
    使用隨機化的點解壓
    
    防止 DPA（差分功耗分析）攻擊
    """
    # 生成隨機種子
    random = random_seed
    
    # 隨機偏移（用於盲化）
    blind = random % P
    
    prefix = compressed[0]
    x = int.from_bytes(compressed[1:33], 'big')
    
    # 盲化 x
    x_blinded = (x + blind) % P
    
    # 使用盲化的 x 計算
    y_squared = (pow(x_blinded, 3, P) + B) % P
    y_blinded = pow(y_squared, (P + 1) // 4, P)
    
    # 去除盲化
    # y^2 = (y_blinded^2) / (x_blinded^3) * x^3
    # 這裡省略詳細的盲化去除邏輯
    # ...
    
    # 最終選擇正確的 y
    parity = prefix & 1
    if (y & 1) != parity:
        y = P - y
        
    return x, y

5.2 驗證點的有效性

在解壓縮前，應驗證輸入的有效性：

x 座標在有效範圍內：$0 < x < p$
前綴位元有效：只接受 0x02 或 0x03
計算後的 y 確實在曲線上：驗證 $y^2 = x^3 + ax + b$

def safe_decompress(compressed):
    """
    安全的點解壓，包含所有驗證
    """
    # 驗證長度
    if len(compressed) != 33:
        raise ValueError("Invalid length")
    
    # 驗證前綴
    prefix = compressed[0]
    if prefix not in (0x02, 0x03):
        raise ValueError(f"Invalid prefix: {hex(prefix)}")
    
    # 解析 x
    x = int.from_bytes(compressed[1:33], 'big')
    
    # 驗證 x 在有效範圍
    if x >= P:
        raise ValueError("x out of range")
    
    # 計算 y^2
    y_squared = (pow(x, 3, P) + B) % P
    
    # 驗證 y^2 是平方剩余（使用勒讓德符號）
    # 這一步可以防止某些無效輸入
    legendre = pow(y_squared, (P - 1) // 2, P)
    if legendre != 1:
        raise ValueError("y^2 is not a quadratic residue")
    
    # 計算 y
    y = pow(y_squared, (P + 1) // 4, P)
    
    # 驗證奇偶性
    parity = prefix & 1
    if (y & 1) != parity:
        y = P - y
    
    # 最終驗證
    if pow(y, 2, P) != y_squared:
        raise ValueError("Invalid point")
    
    return x, y

5.3 存儲優化建議

在智能合約中：

使用緊湊結構：將點的 x 座標和奇偶校驗位存儲在一起

// 不推薦：分開存儲
struct PointUnpacked {
    uint256 x;
    uint256 y;
}

// 推薦：緊湊存儲
struct PointCompact {
    uint256 x;
    bool yIsOdd;
}

// 或使用 bytes33
bytes33 public compressedPoint;

批量操作：減少 SLOAD/SSTORE 次數

校驗和：存儲時計算校驗和，防止數據損壞

struct PointWithChecksum {
    uint256 x;
    bool yIsOdd;
    uint128 checksum;  // x 的簡短校驗和
}

function storePoint(uint256 x, bool yIsOdd) internal {
    uint128 checksum = uint128(uint256(keccak256(abi.encode(x))) % type(uint128).max);
    points[count++] = PointWithChecksum(x, yIsOdd, checksum);
}

六、密碼學標準與規範

6.1 SEC 1 標準

SEC 1（Standards for Efficient Cryptography）是定義橢圓曲線密碼學操作的標準，包括點壓縮格式：

Octet String to Point Conversion (Elliptic Curve Point Compression):

1. If the octet string represents the point at infinity (prefix 0x00), 
   return the point at infinity.

2. If the prefix is 0x02 or 0x03:
   a. Parse the remaining 32 octets as the field element x
   b. Compute y² = x³ + ax + b
   c. Compute y = √(y²) using the specified algorithm
   d. If the parity of y matches the prefix (0x02 = even, 0x03 = odd):
      - Return (x, y)
      Else:
      - Return (x, p - y)

6.2 SEC 2 標準

SEC 2 定義了推薦的橢圓曲線參數，包括 secp256k1：

secp256k1 Curve Parameters:

p  = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
a  = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
b  = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
Gx = 0x79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Gy = 0x483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
n  = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h  = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

6.3 ANSI X9.62

ANSI X9.62 定義了 ECDSA（橢圓曲線數字簽名算法）的標準操作，包括點的表示和處理方式。

結論

橢圓曲線點壓縮是密碼學中優雅而重要的技術。通過利用曲線方程的對稱性，它能夠將點的存儲空間減少約 50%，同時保持完整的信息恢復能力。

在以太坊生態系統中，點壓縮技術廣泛應用於：

公鑰和簽名的傳輸
智能合約中的高效存儲
zk-SNARK 和零知識證明系統
Layer 2 解決方案的數據優化

理解點壓縮的數學原理對於開發安全的密碼學應用至關重要。本指南從代數基礎出發，通過完整的數學推導和程式碼範例，為開發者提供了理論與實作兼備的完整參考。

參考文獻

SECG. (2009). SEC 1: Elliptic Curve Cryptography, Version 2.0.
SECG. (2010). SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2.0.
NIST. (2013). Digital Signature Standard (DSS), FIPS 186-4.
Antonov, I. (2017). Point Compression for Elliptic Curves.
NIST. (2023). Post-Quantum Cryptography Standards.
Ethereum Foundation. (2026). Ethereum Yellow Paper.
Wood, G. (2014). Ethereum: A Secure Decentralised Generalised Transaction Ledger.

橢圓曲線密碼學基礎：以太坊簽章機制與零知識證明的數學理論 — 橢圓曲線密碼學（ECC）是現代密碼學的基石，也是比特幣和以太坊所採用的核心密碼學技術。secp256k1 曲線被用於以太坊的交易簽章，BLS 簽名在共識層發揮關鍵作用，而零知識證明系統（如 zk-SNARK、zk-STARK）則構建於橢圓曲線配對之上。本文將從數學原理出發，深入解析橢圓曲線密碼學的理論基礎，闡述離散對數問題的複雜性如何保障系統安全，並詳細說明這些理論如何應用於以太坊的各類密碼學實踐。
零知識證明數學推導完整指南：從密碼學基礎到以太坊應用實戰 — 本文從數學推導的角度，全面分析零知識證明的基本原理、主要類型（SNARK、STARK、Bulletproofs）、電路設計方法，以及在以太坊上的實際應用部署。涵蓋完整的代數推導、Groth16 和 Plonkish 約束系統、FRI 協議、以及 zkEVM 架構分析。詳細比較不同 ZK 系統的 Gas 消耗與 TPS 表現，提供量化數據支撐的事實依據。
隱私池聯盟成員證明深度技術實作：zkSNARK 電路設計與合規框架完整指南 — 本文深入探討隱私池中聯盟成員證明的密碼學原理、zkSNARK 電路設計、具體實現方式，以及在實際合規場景中的應用。我們提供完整的 Circom 電路代碼、Solidity 智能合約示例，以及針對不同合規框架的實施策略，涵蓋 AML/KYC 合規集成、等級驗證與監管報告等核心主題。
以太坊、Zcash 與 Monero 隱私性完整比較指南：密碼學原理、實際應用與監管影響 — 本文深入分析以太坊、Zcash 和 Monero 三種主流密碼學貨幣的隱私保護技術架構。我們從密碼學原理出發，涵蓋零知識證明（zk-SNARKs、Halo ARC）、環簽名（Ring Signatures）、環隱藏交易（RingCT）等核心技術的數學推導，同時比較 Pedersen 承諾、Merkle 樹驗證、匿名集大小等關鍵參數。三種技術在發送者隱私、接收者隱私、金額隱私和關聯性隱私等維度上有著不同的權衡取捨。本文還分析各平台在監管環境下的合規挑戰，並預測零知識證明在以太坊 Layer 2 隱私方案中的未來應用方向。
ZKML 以太坊實作應用完整指南：預測市場、醫療數據分析與保險精算的深度實務 — 本文作為 ZKML 以太坊實作的完整指南，深入探討三個最具商業價值的應用場景：去中心化預測市場、醫療數據隱私計算，以及保險精算模型。提供完整的技術架構、可部署的智能合約程式碼，以及從概念驗證到規模化部署的實務路徑。涵蓋 EZKL 模型編譯、零知識證明生成、以太坊合約整合等核心技術，並分析截至 2026 年第一季度的最新產業發展動態。

延伸閱讀與來源

zkSNARKs 論文 Gro16 ZK-SNARK 論文
ZK-STARKs 論文 STARK 論文，透明化零知識證明
Aztec Network ZK Rollup 隱私協議
Railgun System 跨鏈隱私協議

這篇文章對您有幫助嗎？

請告訴我們如何改進：

0 人覺得有帮助

橢圓曲線點壓縮數學原理完整指南：從代數基礎到 secp256k1 實作

橢圓曲線點壓縮數學原理完整指南：從代數基礎到 secp256k1 實作

概述

一、橢圓曲線代數基礎回顧

1.1 橢圓曲線的數學定義

1.2 曲線方程的對稱性

1.3 有限域的算術

二、點壓縮的數學原理

2.1 從 x 座標恢復 y 座標

2.2 模平方根的計算

2.3 奇偶校驗位的編碼

三、secp256k1 點壓縮完整推導

3.1 secp256k1 的特殊性質

3.2 點壓縮算法推導

3.3 完整 Python 實現

3.4 Solidity 實現

四、以太坊中的實際應用

4.1 交易簽名中的點壓縮

4.2 區塊頭中的交易樹

4.3 智能合約中的應用場景

4.4 與橢圓曲線配對的交互

五、安全考量與最佳實踐

5.1 側信道攻擊防禦

5.2 驗證點的有效性

5.3 存儲優化建議

六、密碼學標準與規範

6.1 SEC 1 標準

6.2 SEC 2 標準

6.3 ANSI X9.62

結論

參考文獻

延伸閱讀與來源

這篇文章對您有幫助嗎？

評論

發表評論

橢圓曲線點壓縮數學原理完整指南：從代數基礎到 secp256k1 實作

概述

一、橢圓曲線代數基礎回顧

1.1 橢圓曲線的數學定義

1.2 曲線方程的對稱性

1.3 有限域的算術

二、點壓縮的數學原理

2.1 從 x 座標恢復 y 座標

2.2 模平方根的計算

2.3 奇偶校驗位的編碼

三、secp256k1 點壓縮完整推導

3.1 secp256k1 的特殊性質

3.2 點壓縮算法推導

3.3 完整 Python 實現

3.4 Solidity 實現

四、以太坊中的實際應用

4.1 交易簽名中的點壓縮

4.2 區塊頭中的交易樹

4.3 智能合約中的應用場景

4.4 與橢圓曲線配對的交互

五、安全考量與最佳實踐

5.1 側信道攻擊防禦

5.2 驗證點的有效性

5.3 存儲優化建議

六、密碼學標準與規範

6.1 SEC 1 標準

6.2 SEC 2 標準

6.3 ANSI X9.62

結論

參考文獻

相關文章

延伸閱讀與來源

這篇文章對您有幫助嗎？

評論

發表評論