secp256k1 橢圓曲線密碼學實作：以太坊密碼學原語工程指南
本指南從工程師視角出發，提供 secp256k1 橢圓曲線的完整實作，包括有限域運算、點加法與倍點運算、標量乘法、以及 ECDSA 簽名生成與驗證的詳細程式碼。理解這些底層密碼學原語不僅有助於深入理解區塊鏈安全機制，更能為開發高安全性應用奠定基礎。
secp256k1 橢圓曲線密碼學實作：以太坊密碼學原語工程指南
概述
secp256k1 是比特幣和以太坊使用的橢圓曲線密碼學標準，其數學性質是區塊鏈安全的基石。本指南從工程師視角出發，提供 secp256k1 橢圓曲線的完整實作，包括有限域運算、點加法與倍點運算、標量乘法、以及簽名生成與驗證的詳細程式碼。理解這些底層密碼學原語不僅有助於深入理解區塊鏈安全機制，更能為開發高安全性應用奠定基礎。
第一章：數學基礎與 secp256k1 參數
1.1 橢圓曲線數學
橢圓曲線密碼學（Elliptic Curve Cryptography, ECC）是一種基於橢圓曲線代數結構的公鑰密碼學。與 RSA 相比，ECC 在相同安全強度下使用更短的密鑰，大幅減少計算與儲存成本。
橢圓曲線方程式：
Weierstrass 形式：
y² = x³ + ax + b (mod p)
secp256k1 參數：
a = 0
b = 7
p = 2²⁵⁶ - 2³² - 2⁹ - 2⁶ - 2⁴ - 2⁸ - 2³⁸ - 2¹⁶ - 2⁴ - 2⁶ - 2⁹⁹ - 2¹⁹²
= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
G（生成元）= (Gx, Gy)
Gx = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n（階）= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0
h（餘因子）= 11.2 secp256k1 參數詳解
# secp256k1 曲線參數
class Secp256k1Parameters:
"""
secp256k1 曲線參數定義
所有參數均為質數，可在 secg.org 的 SEC 2 標準中找到
"""
# 曲線方程 y² = x³ + ax + b (mod p) 的係數
# secp256k1 使用 a = 0，這是比其他曲線（如 secp256r1 的 a = -3）更簡單的設計
A = 0
B = 7
# 質數 p（有限域的階）
# 這個特殊的質數選擇使得模運算可以被高效實現
P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
# 生成元 G 的座標
GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
# 生成元的階（曲線上點的數量）
# n 是滿足 n * G = O（無窮遠點）的最小正整數
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0
# 餘因子（用於優化計算）
# h = #E(Fp) / n，其中 #E(Fp) 是曲線上的總點數
H = 1
# 安全參數：用於確保標量乘法不會泄露私鑰信息
# 低位不為零，防止某些攻擊
SECURITY_CHECK_LOW_BITS = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0
@classmethod
def validate_point(cls, x, y):
"""
驗證點 (x, y) 是否在曲線上
驗證方程：y² ≡ x³ + 7 (mod p)
"""
# 檢查座標範圍
if x <= 0 or x >= cls.P or y <= 0 or y >= cls.P:
return False
# 驗證曲線方程
left = (y * y) % cls.P
right = (pow(x, 3, cls.P) + cls.B) % cls.P
return left == right第二章：有限域運算實現
2.1 模運算基礎
有限域（Finite Field）是密碼學的數學基礎。在 secp256k1 中，所有運算都在模質數 p 的有限域 Fp 上進行。
# 有限域運算模組
class FieldElement:
"""
有限域 Fp 元素
封裝模 p 的算術運算
p = 2^256 - 2^32 - 2^9 - 2^6 - 2^4 - 2^3 - 2^8 - 2^38 - 2^16 - 2^4 - 2^6 - 2^99 - 2^192
"""
def __init__(self, value: int, p: int = Secp256k1Parameters.P):
"""
初始化有限域元素
參數：
- value: 元素值（自動取模）
- p: 質數（預設為 secp256k1 的 p）
"""
if value < 0:
# 負數取模確保結果為正
self.value = value % p
else:
self.value = value % p
self.p = p
def __repr__(self):
return f"FieldElement({hex(self.value)})"
def __eq__(self, other):
if not isinstance(other, FieldElement):
return False
return self.value == other.value and self.p == other.p
def __add__(self, other):
"""加法：(a + b) mod p"""
if self.p != other.p:
raise ValueError("Cannot add elements from different fields")
result = self.value + other.value
if result >= self.p:
result -= self.p
return FieldElement(result, self.p)
def __sub__(self, other):
"""減法：(a - b) mod p"""
if self.p != other.p:
raise ValueError("Cannot subtract elements from different fields")
result = self.value - other.value
if result < 0:
result += self.p
return FieldElement(result, self.p)
def __mul__(self, other):
"""乘法：(a * b) mod p"""
if isinstance(other, FieldElement):
if self.p != other.p:
raise ValueError("Cannot multiply elements from different fields")
result = (self.value * other.value) % self.p
else:
# 純量乘法
result = (self.value * other) % self.p
return FieldElement(result, self.p)
def __pow__(self, exponent: int):
"""冪運算：a^e mod p"""
return FieldElement(pow(self.value, exponent, self.p), self.p)
def __neg__(self):
"""加法逆元：-a mod p"""
if self.value == 0:
return FieldElement(0, self.p)
return FieldElement(self.p - self.value, self.p)
def inverse(self):
"""
乘法逆元：a^(-1) mod p
使用擴展歐幾里得演算法或費馬小定理
費馬小定理：a^(-1) ≡ a^(p-2) mod p（當 p 為質數時）
這是 secp256k1 中最常用的方法，因為 p 是質數
"""
# 使用費馬小定理計算乘法逆元
# pow(base, exponent, mod) 使用快速冪演算法，複雜度 O(log p)
return FieldElement(pow(self.value, self.p - 2, self.p), self.p)
def __truediv__(self, other):
"""除法：(a * b^(-1)) mod p"""
if isinstance(other, FieldElement):
if self.p != other.p:
raise ValueError("Cannot divide elements from different fields")
return self * other.inverse()
else:
return self * FieldElement(other, self.p).inverse()
class FieldMath:
"""
高效的有限域運算工具類
提供針對 secp256k1 優化的運算函數
"""
# secp256k1 的質數 p（用於位元運算優化）
P = Secp256k1Parameters.P
@staticmethod
def mod_add(a: int, b: int) -> int:
"""
模加法
優化版本：避免使用 % 運算子
"""
result = a + b
if result >= FieldMath.P:
result -= FieldMath.P
return result
@staticmethod
def mod_sub(a: int, b: int) -> int:
"""
模減法
避免分支的版本：
result = a - b
if result < 0: result += p
"""
result = a - b
if result < 0:
result += FieldMath.P
return result
@staticmethod
def mod_mul(a: int, b: int) -> int:
"""
模乘法
使用 Python 內建的 pow 函數
複雜度：O(log n)
"""
return (a * b) % FieldMath.P
@staticmethod
def mod_inv(a: int) -> int:
"""
模乘法逆元
使用擴展歐幾里得演算法
複雜度：O(log p)
"""
if a == 0:
return 0
# 擴展歐幾里得演算法
# 計算 a^(-1) mod p 使得 a * a^(-1) ≡ 1 (mod p)
t, new_t = 0, 1
r, new_r = FieldMath.P, a
while new_r != 0:
quotient = r // new_r
t, new_t = new_t, t - quotient * new_t
r, new_r = new_r, r - quotient * new_r
if r > 1:
# a 在模 p 下不可逆
raise ValueError(f"{a} has no modular inverse mod {FieldMath.P}")
if t < 0:
t = t + FieldMath.P
return t
@staticmethod
def mod_sqrt(a: int) -> int:
"""
模平方根
使用 Tonelli-Shanks 演算法
對於 secp256k1，由於 p ≡ 3 (mod 4)，
可以使用更簡單的方法：
sqrt(a) = a^((p+1)/4) mod p
"""
# 檢查 p ≡ 3 (mod 4)
# secp256k1: p = 2^256 - 2^32 - 2^9 - ... ≡ 3 (mod 4)
# 計算 a^((p+1)/4) mod p
exponent = (FieldMath.P + 1) // 4
result = pow(a, exponent, FieldMath.P)
# 驗證結果
if (result * result) % FieldMath.P != a:
raise ValueError(f"{a} has no square root mod {FieldMath.P}")
return result2.2 高效模運算（secp256k1 優化）
secp256k1 的質數 p 選擇使得模運算可以被高度優化：
# secp256k1 優化運算
class Secp256k1FieldOptimized:
"""
secp256k1 優化有限域運算
優化技巧：
1. p = 2^256 - 2^32 - 2^9 - 2^6 - 2^4 - 2^3 - 2^8 - 2^38 - 2^16 - 2^4 - 2^6 - 2^99 - 2^192
這個特殊形式允許使用進位傳播減法
2. 對於 32 位元系統的優化
"""
# p 的 32 位元分塊表示
# 這使得定點運算更高效
P0 = 0xFFFFFC2F
P1 = 0xFFFFFFFF
P2 = 0xFFFFFFFF
P3 = 0xFFFFFFFF
P4 = 0xFFFFFFFF
P5 = 0xFFFFFFFF
P6 = 0xFFFFFFFF
P7 = 0xFFFFFFFF
@staticmethod
def add_optimized(a: int, b: int) -> int:
"""
優化加法
使用 64 位元累加器避免分支
"""
# 分塊加法
a0 = a & 0xFFFFFFFF
a1 = (a >> 32) & 0xFFFFFFFF
a2 = (a >> 64) & 0xFFFFFFFF
a3 = (a >> 96) & 0xFFFFFFFF
a4 = (a >> 128) & 0xFFFFFFFF
a5 = (a >> 160) & 0xFFFFFFFF
a6 = (a >> 192) & 0xFFFFFFFF
a7 = (a >> 224) & 0xFFFFFFFF
b0 = b & 0xFFFFFFFF
b1 = (b >> 32) & 0xFFFFFFFF
b2 = (b >> 64) & 0xFFFFFFFF
b3 = (b >> 96) & 0xFFFFFFFF
b4 = (b >> 128) & 0xFFFFFFFF
b5 = (b >> 160) & 0xFFFFFFFF
b6 = (b >> 192) & 0xFFFFFFFF
b7 = (b >> 224) & 0xFFFFFFFF
# 加法（可能溢位）
carry = 0
r0 = a0 + b0
carry = r0 >> 32
r0 &= 0xFFFFFFFF
r1 = a1 + b1 + carry
carry = r1 >> 32
r1 &= 0xFFFFFFFF
r2 = a2 + b2 + carry
carry = r2 >> 32
r2 &= 0xFFFFFFFF
r3 = a3 + b3 + carry
carry = r3 >> 32
r3 &= 0xFFFFFFFF
r4 = a4 + b4 + carry
carry = r4 >> 32
r4 &= 0xFFFFFFFF
r5 = a5 + b5 + carry
carry = r5 >> 32
r5 &= 0xFFFFFFFF
r6 = a6 + b6 + carry
carry = r6 >> 32
r6 &= 0xFFFFFFFF
r7 = a7 + b7 + carry
result = r0 | (r1 << 32) | (r2 << 64) | (r3 << 96) | \
(r4 << 128) | (r5 << 160) | (r6 << 192) | (r7 << 224)
# 模 p 修正
if r7 >= 0x10000000: # 需要減去 p
# 進位傳播減法
result = result - Secp256k1FieldOptimized.P
return result
@staticmethod
def mul_optimized(a: int, b: int) -> int:
"""
優化乘法
使用 Python 的 arbitrary precision integer
對於實際部署，應使用 assembly 或硬體加速
"""
# 標準乘法後取模
return (a * b) % Secp256k1Parameters.P第三章：橢圓曲線點運算
3.1 點的表示與無窮遠點
在橢圓曲線密碼學中，點需要特殊表示：
# 橢圓曲線點
class Point:
"""
橢圓曲線點
表示方式：
- (x, y)：普通點
- None：無窮遠點 O（單位元素）
"""
def __init__(self, x: int, y: int, curve=None):
"""
初始化曲線點
參數：
- x, y：點的座標（若為無窮遠點則 x=y=None）
- curve：曲線參數（用於驗證點是否在曲線上）
"""
self.x = x
self.y = y
self.curve = curve
# 驗證點是否在曲線上（僅在非無窮遠點時）
if curve is not None and x is not None and y is not None:
if not curve.is_on_curve(x, y):
raise ValueError(f"Point ({x}, {y}) is not on the curve")
def __repr__(self):
if self.x is None or self.y is None:
return "Point(Infinity)"
return f"Point({hex(self.x)}, {hex(self.y)})"
def __eq__(self, other):
"""檢查兩點是否相等"""
return self.x == other.x and self.y == other.y
def __neg__(self):
"""
點的加法逆元
在 secp256k1 上，P 的加法逆元是 (x, -y mod p)
"""
if self.x is None:
return self # O + O = O
return Point(self.x, (-self.y) % self.curve.p, self.curve)
def is_infinity(self) -> bool:
"""檢查是否為無窮遠點"""
return self.x is None or self.y is None
class Secp256k1Curve:
"""
secp256k1 曲線定義
"""
A = 0
B = 7
P = Secp256k1Parameters.P
N = Secp256k1Parameters.N
G = Point(Secp256k1Parameters.GX, Secp256k1Parameters.GY)
def is_on_curve(self, x: int, y: int) -> bool:
"""
驗證點是否在曲線上
方程：y² ≡ x³ + 7 (mod p)
"""
return (y * y) % self.P == (pow(x, 3, self.P) + self.B) % self.P
def point_at_infinity(self):
"""返回無窮遠點"""
return Point(None, None, self)3.2 點加法與倍點運算
點加法和倍點是 ECC 的核心運算：
# 點加法與倍點運算
class PointOperations:
"""
橢圓曲線點運算
核心公式推導：
點加法 P + Q：
- 若 P = O，則 P + Q = Q
- 若 Q = O，則 P + Q = P
- 若 P ≠ Q：
λ = (y₂ - y₁) / (x₂ - x₁)
x₃ = λ² - x₁ - x₂
y₃ = λ(x₁ - x₃) - y₁
倍點 2P（P + P）：
- λ = (3x₁² + a) / (2y₁)
- x₃ = λ² - 2x₁
- y₃ = λ(x₁ - x₃) - y₁
其中 a = 0（secp256k1）
"""
def __init__(self, curve: Secp256k1Curve):
self.curve = curve
def add(self, p1: Point, p2: Point) -> Point:
"""
點加法：P + Q
特殊情況處理：
1. P = O：返回 Q
2. Q = O：返回 P
3. Q = -P：返回 O
"""
# 處理無窮遠點
if p1.is_infinity():
return p2
if p2.is_infinity():
return p1
x1, y1 = p1.x, p1.y
x2, y2 = p2.x, p2.y
# 檢查是否為同一点（使用加法逆元）
if x1 == x2:
if y1 == y2:
# 同點，使用倍點公式
return self.double(p1)
else:
# Q = -P，返回無窮遠點
return self.curve.point_at_infinity()
# 一般加法公式
# 計算斜率 λ
# λ = (y₂ - y₁) / (x₂ - x₁) mod p
# 分子
numerator = (y2 - y1) % self.curve.P
# 分母
denominator = (x2 - x1) % self.curve.P
# 計算逆元
denom_inv = pow(denominator, self.curve.P - 2, self.curve.P)
# λ = numerator * denominator^(-1) mod p
lam = (numerator * denom_inv) % self.curve.P
# 計算新點座標
# x₃ = λ² - x₁ - x₂ mod p
x3 = (lam * lam - x1 - x2) % self.curve.P
# y₃ = λ(x₁ - x₃) - y₁ mod p
y3 = (lam * (x1 - x3) - y1) % self.curve.P
return Point(x3, y3, self.curve)
def double(self, p: Point) -> Point:
"""
倍點運算：2P
公式（當 a = 0）：
λ = (3x₁²) / (2y₁) mod p
x₃ = λ² - 2x₁ mod p
y₃ = λ(x₁ - x₃) - y₁ mod p
"""
if p.is_infinity():
return p
x1, y1 = p.x, p.y
# 檢查 y = 0（此時 2P = O）
if y1 == 0:
return self.curve.point_at_infinity()
# 計算 λ = (3x₁²) / (2y₁) mod p
numerator = (3 * x1 * x1) % self.curve.P
denominator = (2 * y1) % self.curve.P
denom_inv = pow(denominator, self.curve.P - 2, self.curve.P)
lam = (numerator * denom_inv) % self.curve.P
# 計算新點座標
x3 = (lam * lam - 2 * x1) % self.curve.P
y3 = (lam * (x1 - x3) - y1) % self.curve.P
return Point(x3, y3, self.curve)
def subtract(self, p1: Point, p2: Point) -> Point:
"""
點減法：P - Q
等價於 P + (-Q)
"""
return self.add(p1, -p2)3.3 標量乘法（Scalar Multiplication）
標量乘法是 ECC 的核心運算，用於計算 kP（P 加到自己 k 次）：
# 標量乘法
class ScalarMultiplication:
"""
標量乘法：kP
這是 ECC 中最重要的運算，用於：
- 私鑰到公鑰的轉換：Q = d * G
- 公鑰運算：多個公鑰的線性組合
演算法：
1. 樸素加法（O(n)）：每次加 P 太慢
2. 二進制法/加倍-相加法（O(log n)）：利用 k 的二進制表示
3. 視窗 NAF 法（Windowed NAF）：減少加法次數
4. Shamir's Trick：同時計算多個標量乘法
"""
def __init__(self, curve: Secp256k1Curve):
self.curve = curve
self.point_ops = PointOperations(curve)
def multiply_binary(self, k: int, p: Point) -> Point:
"""
二進制標量乘法（加倍-相加法）
演算法：
1. 將 k 轉換為二進制
2. 從左到右遍歷每一位
3. 每位先倍點，再（有條件地）加 P
複雜度：O(log k) 點加法
"""
if k == 0:
return self.curve.point_at_infinity()
if k < 0:
# 處理負數標量：(-k) * P = k * (-P)
return self.multiply_binary(-k, -p)
result = None
current = p
# 處理 k 的每一位
while k:
if k & 1:
# 該位為 1：相加
if result is None:
result = current
else:
result = self.point_ops.add(result, current)
# 無論該位如何，都需要倍點
current = self.point_ops.double(current)
# 移到下一位
k >>= 1
return result
def multiply_windowed(self, k: int, p: Point, window_size: int = 4) -> Point:
"""
視窗標量乘法
優化版本：預先計算並快取 2^i * P (i = 0, 1, ..., 2^w - 1)
參數：
- window_size w：視窗大小，通常選擇 4 或 5
- 需要預計算 2^w 個點
優點：
- 減少加法次數
- 缺點：需要更多記憶體
"""
if k == 0:
return self.curve.point_at_infinity()
# 預計算 2^i * P for i = 0, ..., 2^w - 1
precomputed = [p]
for i in range(1, 2 ** window_size):
precomputed.append(self.point_ops.add(precomputed[i - 1], p))
result = self.curve.point_at_infinity()
# 處理 k 的每 w 位
while k > 0:
# 提取低 w 位
digit = k & ((1 << window_size) - 1)
# w 次倍點
for _ in range(window_size):
result = self.point_ops.double(result)
# 加上下一個預計算的點
result = self.point_ops.add(result, precomputed[digit])
k >>= window_size
return result
def multiply_naf(self, k: int, p: Point, window_size: int = 5) -> Point:
"""
NAF（非相鄰形式）標量乘法
NAF 特性：
- 任意整數有唯一的 NAF 表示
- NAF 中非零位的密度較低
- 對於 secp256k1 等曲線，可以減少平均加法次數
NAF 減法比普通減法更快
"""
if k == 0:
return self.curve.point_at_infinity()
# 計算 k 的 NAF 表示
naf = self._compute_naf(k)
# 預計算
precomputed = self._precompute_naf(p, window_size)
result = self.curve.point_at_infinity()
# 從左到右處理 NAF
for digit in naf:
result = self.point_ops.double(result)
if digit > 0:
result = self.point_ops.add(result, precomputed[digit])
elif digit < 0:
result = self.point_ops.subtract(result, precomputed[-digit])
return result
def _compute_naf(self, k: int) -> list:
"""
計算整數 k 的 NAF（非相鄰形式）
NAF 編碼：
- 每位為 -1, 0, 或 1
- 任意兩個連續位不為非零
"""
naf = []
while k > 0:
if k & 1:
# k 為奇數
digit = 2 - (k & 3) # 根據 k mod 4 選擇 1 或 -1
k = k - digit
else:
digit = 0
naf.append(digit)
k >>= 1
return naf
def _precompute_naf(self, p: Point, window_size: int) -> dict:
"""
為 NAF 方法預計算
"""
precomputed = {0: self.curve.point_at_infinity()}
# 2^w 個預計算點
for i in range(1, 2 ** (window_size - 1)):
if i == 1:
precomputed[1] = p
else:
# 使用重複加倍計算
if i % 2 == 1:
precomputed[i] = self.point_ops.add(precomputed[i - 1], p)
else:
precomputed[i] = self.point_ops.double(precomputed[i // 2])
# 添加負值（存儲在字典中以供快速查找）
for i in range(1, 2 ** (window_size - 1)):
precomputed[-i] = -precomputed[i]
return precomputed3.4 固定基點標量乘法優化
對於 secp256k1 的生成元 G，有特殊的優化方法：
# 固定基點優化
class FixedBaseMultiplication:
"""
固定基點標量乘法優化
當基點固定（如 secp256k1 的 G）時，
可以使用更激進的預計算策略
常用方法：
1. 固定基點視窗法（GLV 專用）
2. 批次處理（Straus-Shamir 方法）
"""
def __init__(self):
self.curve = Secp256k1Curve()
self.G = self.curve.G
self.point_ops = PointOperations(self.curve)
def multiply_with_precomputed(self, k: int, precomputed_base: list) -> Point:
"""
使用預計算表的標量乘法
適用場景：
- secp256k1 公鑰生成
- 批量公鑰計算
預計算表通常包含：
- 256 個點（每個位元一個）
- 每個點為 2^i * G
"""
result = self.curve.point_at_infinity()
# 處理 k 的每一位
for i in range(len(precomputed_base)):
if k & 1:
result = self.point_ops.add(result, precomputed_base[i])
k >>= 1
return result
def generate_base_table(self, num_points: int = 256) -> list:
"""
生成 secp256k1 生成元的預計算表
table[i] = 2^i * G
這個表可以重複使用以節省計算
"""
table = [self.G]
current = self.G
for _ in range(1, num_points):
current = self.point_ops.double(current)
table.append(current)
return table
def multiply_glv(self, k: int) -> Point:
"""
Gallant-Lambert-Vanstone (GLV) 方法
專門針對固定基點的優化
原理：
- 將標量 k 拆分為 k1 和 k2
- 同時計算 k1*G 和 k2*G'
- 其中 G' = λ*G，λ 是曲線的輔助參數
優點：
- 減少約 50% 的點加法次數
- 安全強度不變
secp256k1 的 GLV 參數：
λ = 0x1000000000000000000000000000000000000000000000000000000000000000
"""
# GLV 標量拆分
# 這是一個簡化版本，實際實現需要更精確的參數
lambda_param = 0x1000000000000000000000000000000000000000000000000000000000000000
# 將 k 拆分為 k1 + k2 * λ
k1 = k % lambda_param
k2 = (k * 0x1000003D1) % lambda_param # 近似值
# 計算 G' = λ * G
lambda_g = self.multiply_scalar(lambda_param, self.G)
# 分別計算
p1 = self.multiply_scalar(k1, self.G)
p2 = self.multiply_scalar(k2, lambda_g)
# 合併結果
return self.point_ops.add(p1, p2)
def multiply_scalar(self, k: int, point: Point) -> Point:
"""
一般標量乘法（使用二元法）
"""
result = self.curve.point_at_infinity()
current = point
while k:
if k & 1:
result = self.point_ops.add(result, current)
current = self.point_ops.double(current)
k >>= 1
return result第四章：ECDSA 簽名與驗證
4.1 簽名生成
ECDSA（橢圓曲線數位簽章演算法）是以太坊交易的基礎：
# ECDSA 簽名
class ECDSASignature:
"""
ECDSA 簽名結構
簽名由兩個值組成：
- r：公鑰雜湊在曲線上的 x 座標
- s：簽章值
簽名格式：
- 65 bytes（r: 32 bytes, s: 32 bytes, v: 1 byte）
- 或 64 bytes（無 v，v 通常由 recovery id 推導）
"""
def __init__(self, r: int, s: int, v: int = None):
self.r = r
self.s = s
self.v = v # recovery id (0-3)，用於公鑰恢復
def __repr__(self):
return f"Signature(r={hex(self.r)}, s={hex(self.s)}, v={self.v})"
def to_bytes(self, compressed: bool = False) -> bytes:
"""
轉換為位元組格式
"""
if compressed:
# 33 bytes: 0x02/0x03 + x座標
prefix = 0x02 if self.v & 1 == 0 else 0x03
return bytes([prefix]) + self.r.to_bytes(32, 'big')
else:
# 65 bytes: r + s + v
return self.r.to_bytes(32, 'big') + self.s.to_bytes(32, 'big')
class ECDSA:
"""
ECDSA 簽名與驗證
簽名演算法：
1. 選擇隨機 nonce k
2. 計算 R = k * G
3. r = R.x mod n
4. s = k^(-1) * (hash + r * d) mod n
其中 d 是私鑰
驗證演算法：
1. 計算 w = s^(-1) mod n
2. u1 = w * hash mod n
3. u2 = w * r mod n
4. P = u1 * G + u2 * Q
5. 驗證 P.x mod n == r
"""
def __init__(self, curve: Secp256k1Curve):
self.curve = curve
def sign(self, message_hash: int, private_key: int,
nonce: int = None) -> ECDSASignature:
"""
簽名生成
參數：
- message_hash：訊息雜湊值（32 bytes）
- private_key：私鑰 d
- nonce：可選的隨機數 k（用於除錯或確定性簽名）
返回：
- (r, s) 簽名對
"""
# 驗證私鑰範圍
if private_key <= 0 or private_key >= self.curve.N:
raise ValueError("Invalid private key")
# 驗證訊息雜湊
if message_hash <= 0 or message_hash >= self.curve.N:
raise ValueError("Invalid message hash")
# 選擇隨機 nonce（生產環境應使用 RFC 6979）
if nonce is None:
nonce = self._generate_nonce(message_hash, private_key)
else:
# 驗證 nonce
if nonce <= 0 or nonce >= self.curve.N:
raise ValueError("Invalid nonce")
# 步驟 1-2：計算 R = k * G
G = self.curve.G
R = self._scalar_multiply(nonce, G)
# 檢查 R 是否為無窮遠點
if R.is_infinity():
raise ValueError("R is point at infinity")
# 步驟 3：r = R.x mod n
r = R.x % self.curve.N
if r == 0:
raise ValueError("r = 0, retry with different nonce")
# 步驟 4：s = k^(-1) * (hash + r * d) mod n
k_inv = pow(nonce, self.curve.N - 2, self.curve.N) # N 是質數，可用費馬小定理
s = (k_inv * (message_hash + r * private_key)) % self.curve.N
if s == 0:
raise ValueError("s = 0, retry with different nonce")
# DER 格式化時，通常需要低 s 值
# 但我們保留原始 s 以便公鑰恢復
# 計算 recovery id
v = 0 if R.y % 2 == 0 else 1
if R.x != R.x % self.curve.N:
v += 2
return ECDSASignature(r, s, v)
def verify(self, message_hash: int, signature: ECDSASignature,
public_key: Point) -> bool:
"""
簽名驗證
步驟：
1. 驗證 r, s 在有效範圍內
2. w = s^(-1) mod n
3. u1 = w * e mod n
4. u2 = w * r mod n
5. P = u1 * G + u2 * Q
6. 驗證 P.x mod n == r
"""
r, s = signature.r, signature.s
# 驗證 r, s 範圍
if r <= 0 or r >= self.curve.N:
return False
if s <= 0 or s >= self.curve.N:
return False
# 驗證公鑰
if public_key.is_infinity():
return False
if not self.curve.is_on_curve(public_key.x, public_key.y):
return False
# 步驟 1：w = s^(-1) mod n
w = pow(s, self.curve.N - 2, self.curve.N)
# 步驟 2：u1 = w * e mod n, u2 = w * r mod n
e = message_hash % self.curve.N
u1 = (w * e) % self.curve.N
u2 = (w * r) % self.curve.N
# 步驟 3：P = u1 * G + u2 * Q
G = self.curve.G
u1G = self._scalar_multiply(u1, G)
u2Q = self._scalar_multiply(u2, public_key)
P = self._point_add(u1G, u2Q)
# 步驟 4：驗證
if P.is_infinity():
return False
v = P.x % self.curve.N
return v == r
def _scalar_multiply(self, k: int, point: Point) -> Point:
"""標量乘法（使用二元法）"""
result = self.curve.point_at_infinity()
current = point
while k:
if k & 1:
result = self._point_add(result, current)
current = self._point_add(current, current)
k >>= 1
return result
def _point_add(self, p1: Point, p2: Point) -> Point:
"""點加法"""
if p1.is_infinity():
return p2
if p2.is_infinity():
return p1
x1, y1 = p1.x, p1.y
x2, y2 = p2.x, p2.y
if x1 == x2:
if y1 == y2:
# 倍點
lam = (3 * x1 * x1) % self.curve.P
denom_inv = pow(2 * y1, self.curve.P - 2, self.curve.P)
else:
return self.curve.point_at_infinity()
else:
lam = (y2 - y1) % self.curve.P
denom_inv = pow(x2 - x1, self.curve.P - 2, self.curve.P)
lam = (lam * denom_inv) % self.curve.P
x3 = (lam * lam - x1 - x2) % self.curve.P
y3 = (lam * (x1 - x3) - y1) % self.curve.P
return Point(x3, y3, self.curve)
def _generate_nonce(self, message_hash: int, private_key: int) -> int:
"""
生成隨機 nonce（生產環境應使用 RFC 6979）
RFC 6979 提供確定性的 nonce 生成方法
這確保相同的訊息和私鑰總是產生相同的簽名
"""
# 簡化的隨機 nonce（僅用於教學）
# 生產環境必須使用 RFC 6979
import secrets
nonce = secrets.randbelow(self.curve.N - 1) + 1
return nonce4.2 公鑰恢復
以太坊使用特殊的公鑰恢復機制，允許從簽名直接恢復公鑰：
# 公鑰恢復
class PublicKeyRecovery:
"""
公鑰恢復
以太坊使用 ECDSA 的「公鑰恢復」特性：
從簽名 (r, s) 可以恢復兩個可能的公鑰
恢復演算法：
1. 計算 r' = r mod n
2. 計算候選 x 座標
3. 從 x 計算可能的 y 座標（兩種）
4. 驗證候選公鑰
"""
def __init__(self, curve: Secp256k1Curve):
self.curve = curve
def recover_public_key(self, message_hash: int,
signature: ECDSASignature) -> list:
"""
從簽名恢復公鑰
恢復公式：
e = message_hash mod n
r = signature.r
s = signature.s
候選點：
x = r + j * n（j = 0 或 1）
從 x 恢復 y：
y² = x³ + 7 mod p
y = sqrt(y²) mod p
最後驗證：r == (k * G).x mod n
其中 k 需要從 s 和恢復的點計算
"""
r, s = signature.r, signature.s
v = signature.v
if r <= 0 or r >= self.curve.N:
raise ValueError("Invalid r")
if s <= 0 or s >= self.curve.N:
raise ValueError("Invalid s")
# 確定 y 座標的奇偶性
y_parity = v & 1
# 計算候選 x 座標
x = r
# 從 x 計算 y
y_squared = (pow(x, 3, self.curve.P) + self.curve.B) % self.curve.P
y = pow(y_squared, (self.curve.P + 1) // 4, self.curve.P)
# 選擇正確奇偶性的 y
if (y & 1) != y_parity:
y = self.curve.P - y
# 恢復點 R
R = Point(x, y, self.curve)
# 計算 e = -message_hash mod n
e = (-message_hash) % self.curve.N
# 計算候選公鑰 Q = s * R + e * G
s_inv = pow(s, self.curve.N - 2, self.curve.N)
sR = self._scalar_multiply(s_inv, R)
eG = self._scalar_multiply(e, self.curve.G)
Q = self._point_add(sR, eG)
# 驗證恢復的公鑰
if not self._verify_public_key(Q):
raise ValueError("Public key recovery failed")
return [Q]
def recover_public_key_with_candidates(self, message_hash: int,
signature: ECDSASignature) -> list:
"""
恢復所有可能的公鑰（考慮 v 的兩個可能值）
由於從 (r, s) 可以恢復兩個可能的公鑰
需要透過 v 來區分
"""
candidates = []
for v_candidate in [0, 1, 2, 3]:
try:
sig = ECDSASignature(signature.r, signature.s, v_candidate)
pk = self.recover_public_key(message_hash, sig)
candidates.extend(pk)
except:
continue
# 去重
seen = set()
unique = []
for pk in candidates:
pk_tuple = (pk.x, pk.y)
if pk_tuple not in seen:
seen.add(pk_tuple)
unique.append(pk)
return unique
def _scalar_multiply(self, k: int, point: Point) -> Point:
"""標量乘法"""
result = self.curve.point_at_infinity()
current = point
while k:
if k & 1:
result = self._point_add(result, current)
current = self._point_add(current, current)
k >>= 1
return result
def _point_add(self, p1: Point, p2: Point) -> Point:
"""點加法"""
if p1.is_infinity():
return p2
if p2.is_infinity():
return p1
x1, y1 = p1.x, p1.y
x2, y2 = p2.x, p2.y
if x1 == x2:
if y1 == y2:
lam = (3 * x1 * x1) % self.curve.P
denom_inv = pow(2 * y1, self.curve.P - 2, self.curve.P)
else:
return self.curve.point_at_infinity()
else:
lam = (y2 - y1) % self.curve.P
denom_inv = pow(x2 - x1, self.curve.P - 2, self.curve.P)
lam = (lam * denom_inv) % self.curve.P
x3 = (lam * lam - x1 - x2) % self.curve.P
y3 = (lam * (x1 - x3) - y1) % self.curve.P
return Point(x3, y3, self.curve)
def _verify_public_key(self, pk: Point) -> bool:
"""驗證公鑰有效性"""
if pk.is_infinity():
return False
if not self.curve.is_on_curve(pk.x, pk.y):
return False
# 驗證 n * pk = O
n_pk = self._scalar_multiply(self.curve.N, pk)
return n_pk.is_infinity()第五章：實際應用與整合
5.1 以太坊地址生成
# 以太坊地址生成
class EthereumAddress:
"""
以太坊地址生成
流程：
1. 生成隨機私鑰（256 位元隨機數）
2. 使用 secp256k1 計算公鑰：Q = d * G
3. 取公鑰的 Keccak-256 雜湊
4. 取最後 20 位元組作為地址
地址格式：
- 原始：40 個十六進位字元
- EIP-55：加入混合格式（如 0x1234...abcd）
"""
def __init__(self):
self.curve = Secp256k1Curve()
self.ecdsa = ECDSA(self.curve)
self.scalar_mul = ScalarMultiplication(self.curve)
self.point_ops = PointOperations(self.curve)
def generate_private_key(self) -> int:
"""
生成安全的隨機私鑰
重要：
- 必須使用密碼學安全的隨機數生成器
- 私鑰必須在 [1, n-1] 範圍內
"""
import secrets
while True:
# 生成 256 位元隨機數
private_key = int.from_bytes(
secrets.randbits(256).to_bytes(32, 'big'),
'big'
)
# 驗證範圍
if 0 < private_key < self.curve.N:
return private_key
def private_key_to_public_key(self, private_key: int) -> bytes:
"""
從私鑰計算公鑰
Q = d * G
返回：
- 未壓縮公鑰：04 + x + y（65 bytes）
- 壓縮公鑰：02/03 + x（33 bytes）
"""
# 標量乘法
G = self.curve.G
Q = self.scalar_mul.multiply_binary(private_key, G)
# 返回未壓縮格式
x = Q.x.to_bytes(32, 'big')
y = Q.y.to_bytes(32, 'big')
return bytes([0x04]) + x + y
def public_key_to_address(self, public_key: bytes) -> str:
"""
從公鑰計算以太坊地址
1. 取 Keccak-256(public_key)
2. 取最後 20 bytes
3. 轉換為十六進位字串
"""
# 使用 Keccak-256（不是 SHA-3！）
from Crypto.Hash import keccak
keccak_hash = keccak.new(digest_bits=256)
keccak_hash.update(public_key)
hash_bytes = keccak_hash.digest()
# 取最後 20 位元組
address_bytes = hash_bytes[-20:]
# 轉換為十六進位
address = '0x' + address_bytes.hex()
return address
def generate_address(self) -> dict:
"""
生成完整的以太坊地址
返回：
{
'private_key': hex,
'public_key': hex,
'address': hex
}
"""
# 生成私鑰
private_key = self.generate_private_key()
# 計算公鑰
public_key = self.private_key_to_public_key(private_key)
# 計算地址
address = self.public_key_to_address(public_key)
return {
'private_key': hex(private_key),
'public_key': public_key.hex(),
'address': address
}5.2 以太坊交易簽名
# 以太坊交易簽名
class EthereumTransaction:
"""
以太坊交易簽名
交易類型：
- Legacy Transaction (EIP-155)
- EIP-2930 (Access List)
- EIP-1559 (Type 2)
"""
def __init__(self):
self.curve = Secp256k1Curve()
self.ecdsa = ECDSA(self.curve)
def sign_transaction(self, tx_params: dict, private_key: int) -> bytes:
"""
簽名交易
參數：
- nonce: 交易計數
- gas_price / max_fee_per_gas: Gas 價格
- gas_limit: Gas 上限
- to: 目標地址
- value: 轉帳金額
- data: 輸入數據
- chain_id: 鏈 ID
流程：
1. RLP 編碼交易（不含 signature）
2. 計算 Keccak-256 雜湊
3. 使用私鑰簽名
4. 拼接 signature 到交易
"""
# 提取交易參數
tx_type = tx_params.get('type', 0)
nonce = tx_params['nonce']
chain_id = tx_params['chain_id']
if tx_type == 2:
# EIP-1559
max_priority_fee_per_gas = tx_params['max_priority_fee_per_gas']
max_fee_per_gas = tx_params['max_fee_per_gas']
gas_limit = tx_params['gas']
to = tx_params['to']
value = tx_params['value']
data = tx_params.get('data', b'')
# 建構交易物件（RLP 編碼前）
tx_for_signing = {
'chain_id': chain_id,
'nonce': nonce,
'max_priority_fee_per_gas': max_priority_fee_per_gas,
'max_fee_per_gas': max_fee_per_gas,
'gas': gas_limit,
'to': to,
'value': value,
'data': data,
'access_list': tx_params.get('access_list', []),
'max_fee_per_blob_gas': tx_params.get('max_fee_per_blob_gas', 0),
'blob_hashes': tx_params.get('blob_hashes', [])
}
elif tx_type == 1:
# EIP-2930
# ...
pass
else:
# Legacy Transaction
gas_price = tx_params['gas_price']
gas_limit = tx_params['gas']
to = tx_params['to']
value = tx_params['value']
data = tx_params.get('data', b'')
# 計算交易雜湊
tx_hash = self._hash_for_signing(tx_for_signing, tx_type)
# 簽名
signature = self.ecdsa.sign(tx_hash, private_key)
# 處理 s 值（必須低於 n/2 以防止簽章重播攻擊）
# 這是 BIP-62 的要求
if signature.s > self.curve.N // 2:
signature.s = self.curve.N - signature.s
signature.v = 1 - signature.v
# 編碼完整交易
signed_tx = self._encode_signed_transaction(
tx_for_signing,
signature,
tx_type
)
return signed_tx
def _hash_for_signing(self, tx: dict, tx_type: int) -> int:
"""
計算交易雜湊（用於簽名）
對於 EIP-1559，雜湊 = Keccak256(0x02 || RLP(chain_id, nonce, ...))
"""
# RLP 編碼交易
rlp_encoded = self._rlp_encode(tx, tx_type)
# 添加交易類型前綴
if tx_type > 0:
encoded = bytes([tx_type]) + rlp_encoded
else:
encoded = rlp_encoded
# Keccak-256
from Crypto.Hash import keccak
keccak_hash = keccak.new(digest_bits=256)
keccak_hash.update(encoded)
return int.from_bytes(keccak_hash.digest(), 'big')結論
secp256k1 橢圓曲線密碼學是以太坊安全的數學基石。理解其底層實作對於：
開發者的價值：
- 安全開發：深入理解密碼學原語，有助於避免常見的安全錯誤
- 效能優化：了解運算複雜度，可針對特定場景進行優化
- 除錯能力：在密碼學相關 bug 發生時，能快速定位問題根源
關鍵技術要點：
- 有限域運算：所有計算都在模質數 p 的有限域上進行
- 點運算：加法、倍點、標量乘法是核心
- 標量乘法優化：二元法、視窗法、GLV 等技術大幅提升效率
- ECDSA 簽名：數位簽章提供不可否認的認證
安全提醒：
- 密碼學實作極易出錯，強烈建議使用經過審計的密碼學庫
- 不要自己實現密碼學原語用於生產環境
- 隨機數生成（nonce）是 ECDSA 安全的關鍵
- 私鑰處理必須遵守安全最佳實踐
本指南的程式碼主要用於教學目的，深入理解 secp256k1 的工程師應進一步研究比特幣和以太坊的實際密碼學實現（如 libsecp256k1）。
免責聲明：本文旨在教育目的。密碼學實作涉及高度安全性要求，請勿將本指南中的程式碼直接用於生產環境。生產環境應使用經過正式安全審計的密碼學庫。
最後更新日期：2026 年 3 月 22 日
相關文章
- 以太坊密碼學基礎完整指南：橢圓曲線密碼學、簽章機制與 Merkle Tree 結構 — 本文深入分析以太坊密碼學系統的三大支柱：secp256k1 橢圓曲線與 ECDSA 簽章機制的數學原理、KECCAK-256 雜湊函數的設計特點、以及 Patricia Merkle Trie 資料結構在狀態管理中的關鍵角色。我們從密碼學理論出發，經過詳盡的數學推導，最終落實到 Solidity、Go 與 Rust 的實際程式碼範例。涵蓋離散對數問題、點加法/倍增運算、ECDSA 簽章驗證、Merkle Proof、EIP-1559 等核心概念的完整技術解析。
- 橢圓曲線離散對數問題複雜度分析：從數學基礎到密碼學安全 — 橢圓曲線離散對數問題（ECDLP）是現代密碼學最重要的數學假設之一，也是橢圓曲線密碼學安全性的基石。本文深入分析ECDLP的數學定義、Pollard's Rho等已知攻擊算法的複雜度、以及為什麼ECDLP在當前計算能力下是安全的。我們從群論基礎出發，逐步推導各種攻擊算法的複雜度，建立對橢圓曲線密碼學安全性的直觀理解。
- 以太坊密碼學原語直覺解釋：橢圓曲線、布隆過濾器與 Keccak 的工程視角 — 本文從工程師的視角出發，提供橢圓曲線、布隆過濾器（Blooom Filter）等密碼學原語的直覺性解釋、完整的數學推導、以及可直接使用的程式碼範例，幫助讀者建立對這些密碼學原語的深入理解。涵蓋 ECDSA 簽名、Keccak-256 哈希、布隆過濾器的設計原理與實際應用。
- 橢圓曲線密碼學直覺式圖解說明：從基礎原理到以太坊應用 — 本文以直覺式圖解說明讓讀者無需深厚數學背景也能理解橢圓曲線密碼學的核心概念。涵蓋橢圓曲線加法的幾何意義、離散對數問題的安全性基礎、以太坊地址生成的完整流程、ECDSA 簽名演算法、Vitalik 恢復機制，以及零知識電路和 Layer 2 中的橢圓曲線應用。
- Verifiable Delay Functions 與進階密碼學：原理、應用與實現 — Verifiable Delay Function（VDF）是密碼學中相對新興的原語，近年來在區塊鏈領域獲得了廣泛關注。VDF 的核心特性是：計算結果需要經過預定時間才能完成，且驗證過程極為高效。這種「時間綁定」的計算特性為區塊鏈系統提供了獨特的安全保障，特別是在隨機數生成、 時間戳記、PoS 共識等場景中具有重要應用價值。本文深入介紹 VDF 的數學原理、主流實現方案、在區塊鏈中的實際應用，以及
延伸閱讀與來源
- Ethereum.org Developers 官方開發者入口與技術文件
- EIPs 以太坊改進提案完整列表
- Solidity 文檔 智慧合約程式語言官方規格
- EVM 代碼庫 EVM 實作的核心參考
- Alethio EVM 分析 EVM 行為的正規驗證
這篇文章對您有幫助嗎？
請告訴我們如何改進：
0 人覺得有帮助
評論
發表評論
注意：由於這是靜態網站，您的評論將儲存在本地瀏覽器中，不會公開顯示。
目前尚無評論，成為第一個發表評論的人吧！