Hotdry.
归档
ai-security

secp256k1 核心曲线运算：点加/倍、Montgomery阶梯标量乘与 RFC6979 确定性 k 生成

secp256k1 椭圆曲线点加/倍运算公式、Montgomery阶梯常数时间标量乘实现，以及 ECDSA 签名中 RFC6979 确定性 nonce 生成的工程参数与安全清单。

secp256k1 是比特币和以太坊等区块链的核心椭圆曲线，其高效性和安全性源于精心设计的参数与优化运算。核心运算包括点加 / 倍、标量乘法（Montgomery 阶梯）和 ECDSA 签名中的确定性 nonce 生成。这些操作需常数时间执行，以抵抗侧信道攻击。本文聚焦可落地实现，提供公式、伪代码和参数阈值，确保工程部署的安全性。

secp256k1 曲线参数

secp256k1 定义于有限域 GF (p)，参数如下（十六进制）：

  • p = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F（2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1）
  • a = 0000000000000000000000000000000000000000000000000000000000000000
  • b = 0000000000000000000000000000000000000000000000000000000000000007
  • Gx = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
  • Gy = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
  • n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBAAEDCE6AF48A03BBFD25E8CD0364141（曲线阶）
  • h = 01（协因子）

曲线方程：y² = x³ + 7 (mod p)。这些参数确保了 128-bit 安全级别，私钥 d ∈ [1, n-1]，公钥 Q = d・G。

点加与点倍运算

点运算是标量乘的基础，使用仿射坐标公式，但生产环境中采用 Jacobian 坐标 (X, Y, Z) 优化，避免昂贵的模逆（费 80M+，M 为模乘）。

点加（P ≠ ±Q）：

  • λ = (Y₂ - Y₁) · inv(X₂ - X₁) (mod p)
  • X₃ = λ² - X₁ - X₂ (mod p)
  • Y₃ = λ · (X₁ - X₃) - Y₁ (mod p)

点倍（P + P）：

  • λ = (3 · X₁² + a) · inv(2 · Y₁) (mod p)
  • X₃ = λ² - 2 · X₁ (mod p)
  • Y₃ = λ · (X₁ - X₃) - Y₁ (mod p)

Jacobian 坐标转换：

  • 仿射 (x, y) → Jacobian (X=x, Y=y, Z=1)
  • Jacobian → 仿射：x = X・inv (Z²)，y = Y・inv (Z³)

落地参数：

  • 模运算：优先 Montgomery 乘法（预计算 R² mod p），secp256k1 专用 ModMulK1 利用 p ≡ 2^256 - 2^32 - 977 加速约简。
  • 阈值：模逆使用 Fermat 小定理或扩展欧几里德，超时 > 1μs 触发回滚。
  • 清单：验证输入点在曲线上（y² ≡ x³ + 7 mod p），拒绝无穷远点或低阶点。

libsecp256k1 使用统一加倍公式，避免分支泄露定时信息。

Montgomery 阶梯标量乘

标量乘 k・P 是 ECDSA 核心（公钥生成 kG，验证 uG + vQ）。标准双加易受侧信道攻击，Montgomery 阶梯提供常数时间实现。

算法（从 MSB 到 LSB 处理 k 的 256 位）：

R0 = O  // 无穷远点
R1 = P
for i = 255 downto 0:
    if k_i == 0:
        R1 = R0 + R1
        R0 = 2 * R0
    else:
        R0 = R0 + R1
        R1 = 2 * R1
return R0
  • 每次迭代固定执行 1 加 + 1 倍，无数据依赖分支。
  • 窗口优化：w=5，预计算 16・G 表，结合 Shamir's trick 加速验证 (aP + bG)。

落地参数：

  • 坐标：Jacobian + Chudnovsky 混合加法，12M + 4S（M = 乘，S = 平方）。
  • 端 omorphism：secp256k1 支持 λ = u + v√-7 分解标量，加速 25%。
  • 监控：功耗偏差 > 5% 或时间波动 > 10ns 报警；禁用预计算表若内存 < 64KB。

此实现比 double-and-add 快 30%，常用于 libsecp256k1。

RFC6979 确定性 k 生成（ECDSA）

ECDSA 签名：r = (kG)_x mod n，s = k^{-1}・(z + r d) mod n。随机 k 易重复泄私钥，RFC6979 使用 HMAC-DRBG 基于 d || z1 生成 k。

流程：

  1. h1 = HMAC_SHA256 (d, z1) //z1 = SHA256 (z) 左填充至 32 字节
  2. V = 0x01...01 (32 字节)，K = HMAC_SHA256 (V || 0x00 || d || z1 || 0x00)
  3. loop: T = HMAC_SHA256 (K, V || 0x01)，V = HMAC_SHA256 (K, V)；若 T ∈ [1,n-1] 则 k=T，break
  4. qlen = bitlen (n)，若 bitlen (T) > qlen 则 T >>= bitlen (T)-qlen

伪代码：

def rfc6979(d, z):
    h = sha256(z).digest()
    V = b'\x01' * 32
    K = hmac_sha256(V + b'\x00' + d + h + b'\x00')
    while True:
        T = hmac_sha256(K, V + b'\x01')
        V = hmac_sha256(K, V)
        K = hmac_sha256(V + b'\x00' + d + h + b'\x01')
        if 1 <= int.from_bytes(T) < n: return int.from_bytes(T)

落地参数：

  • 哈希：SHA256，迭代上限 512 次（概率 <2^{-128} 失败）。
  • 验证：签名后检查 r,s ∈ [1,n-1]，s ≤ n/2（低 S 规范化）。
  • 回滚：k=0 或生成失败率 > 0.1% 更换私钥；结合 blinding 防故障攻击。

比特币核心默认启用，避免 Android RNG 漏洞重演。

安全清单与监控

  • 输入验证：点坐标 ∈ [0,p-1]，k ∈ [1,n-1]；曲线校验 y² ≡ x³ + 7。
  • 侧信道防护：全常数时间，无条件交换；掩码运算（random blinding）。
  • 性能阈值：标量乘 <500μs (x86)，内存 < 1KB / 运算。
  • 测试：NIST CAVP，差分功耗分析（DPA）模拟 > 10^6 轨迹无泄露。
  • 部署：HSM/TEE 执行敏感运算，日志盲化。

这些操作在 libsecp256k1 中高度优化，无堆分配，常数内存访问。

资料来源：

  • SEC 2: Recommended Elliptic Curve Domain Parameters (secg.org/sec2-v2.pdf)
  • RFC6979: Deterministic Usage of the Digital Signature Algorithm (tools.ietf.org/html/rfc6979)
  • libsecp256k1 (github.com/bitcoin-core/secp256k1)
查看归档