ECDSA 数字签名算法：从离散对数到比特币的密码学基石

概述

数字签名是现代密码学的三大支柱之一（加密、签名、哈希），它解决了"谁发的""有没有改""能不能抵赖"三个核心问题。在众多签名方案中，ECDSA（Elliptic Curve Digital Signature Algorithm） 是最广泛应用的标准之一——TLS 证书使用 ECDSA-P256 签名、比特币使用 ECDSA-secp256k1 签名、国产 SM2 本质上是 ECDSA 在国密曲线上的变体。

ECDSA 由 Scott Vanstone 于 1992 年提出，1998 年被 NIST 纳入 FIPS 186 标准。它的核心思想极其优雅：将 DSA 签名方案从有限域乘法群迁移到椭圆曲线点群。这一迁移使得相同安全强度下，密钥长度从 RSA 的 3072 位骤降至 ECDSA 的 256 位，效率提升数量级。

本文将从数学基础出发，完整推导 ECDSA 算法流程，分析安全陷阱，并与国密 SM2 和国际标准 EdDSA 进行对比。

数学基础：椭圆曲线上的离散对数问题

椭圆曲线群结构

令 $E$ 为定义在有限域 $\mathbb{F}_p$ 上的椭圆曲线，其 Weierstrass 方程为：

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

其中 $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$ 确保曲线非奇异。

曲线上所有点（含无穷远点 $\mathcal{O}$）构成一个阿贝尔群，群运算规则如下：

• 加法单位元：$\mathcal{O} + P = P$
• 逆元：若 $P = (x, y)$，则 $-P = (x, -y)$
• 自加（倍点）：若 $P = Q$，则 $2P = P + P$，切线斜率 $\lambda = \frac{3x_P^2 + a}{2y_P} \pmod{p}$
• 点加：若 $P \neq Q$，则 $P + Q$，斜率 $\lambda = \frac{y_Q - y_P}{x_Q - x_P} \pmod{p}$

以上公式均对域特征不等于 2、3 的素数域成立。SM2、secp256r1、secp256k1 均采用此类曲线。

离散对数问题（ECDLP）

给定椭圆曲线 $E$、生成元 $G$（阶为素数 $n$）、以及点 $Q = [d]G$，求整数 $d \in [1, n-1]$ 在计算上是困难的。这个问题称为椭圆曲线离散对数问题（Elliptic Curve Discrete Logarithm Problem, ECDLP）。

目前解决 ECDLP 最有效的通用算法是 Pollard's rho 算法，时间复杂度为 $O(\sqrt{n})$。因此，256 位椭圆曲线提供约 128 位的安全强度（$\sqrt{2^{256}} = 2^{128}$）。

ECDSA 算法设计

参数体系

设椭圆曲线参数为 $(p, a, b, G, n, h)$，其中：

• $p$：域素数
• $a, b$：曲线方程系数
• $G$：生成元（基点），阶为 $n$
• $n$：生成元的阶（素数）
• $h$：余因子（cofactor），对于 prime field 曲线通常为 1

密钥生成

输入：曲线参数 (p, a, b, G, n)
输出：私钥 d，公钥 Q = [d]G

1. 随机选择 d ∈ [1, n-1] 作为私钥
2. 计算 Q = [d]G 作为公钥

私钥长度 = $\lceil \log_2 n \rceil$ 位，公钥长度 = $2 \times \lceil \log_2 p \rceil$ 位（未压缩）或 $\lceil \log_2 p \rceil + 1$ 位（压缩形式）。

签名生成

对消息 $m$ 的签名过程：

输入：私钥 d，消息 m
输出：签名 (r, s)

1. 计算消息哈希 e = H(m)，截断至 n 位
2. 随机选择 nonce k ∈ [1, n-1]
3. 计算曲线点 [k]G = (x₁, y₁)
4. 计算 r = x₁ mod n；若 r = 0，返回步骤 2
5. 计算 s = k⁻¹ · (e + d·r) mod n；若 s = 0，返回步骤 2
6. 输出签名 (r, s)

其中：

• $H$ 为哈希函数（SHA-256、SM3 等）
• $k^{-1}$ 为 $k$ 在模 $n$ 下的乘法逆元
• $e$ 为消息摘要，通常对 $n$ 位不足时高位补零

签名验证

对签名 $(r, s)$ 和消息 $m$ 的验证过程：

输入：公钥 Q，消息 m，签名 (r, s)
输出：接受/拒绝

1. 验证 r, s ∈ [1, n-1]；否则拒绝
2. 计算消息哈希 e = H(m)，截断至 n 位
3. 计算 w = s⁻¹ mod n
4. 计算 u₁ = e·w mod n，u₂ = r·w mod n
5. 计算曲线点 (x₁, y₁) = [u₁]G + [u₂]Q
6. 验证 r ≡ x₁ mod n；若成立则接受，否则拒绝

正确性证明：

$$[u_1]G + [u_2]Q = [e \cdot w]G + [r \cdot w]Q = [w(e + r \cdot d)]G = [w \cdot k \cdot s]G$$

由于 $s = k^{-1}(e + d \cdot r) \bmod n$，代入得：

$$[w \cdot k \cdot s]G = [s^{-1} \cdot k \cdot s]G = [k]G = (x_1, y_1)$$

因此 $x_1 \equiv r \pmod{n}$，验证通过。∎

RFC 6979：确定性 Nonce 构造

问题背景

ECDSA 的安全性依赖于 nonce $k$ 的随机性和唯一性。一旦 $k$ 被重复使用或可预测，私钥即可被恢复。历史上多次严重事故源于此：

• 2010 年 Sony PS3 漏洞：Sony 在游戏签名中使用固定 $k$，导致私钥被公开
• 2013 年 Nintendo 漏洞：同样使用固定 nonce，私钥泄露
• 2018 年 Ethereum 漏洞：多个钱包因 nonce 可预测导致私钥泄露

确定性构造

RFC 6979 提出了一种从私钥和消息确定性派生 nonce 的方法，消除了随机数生成的风险：

输入：私钥 d，消息哈希 e，曲线参数 n
输出：nonce k

算法流程（简化版）：
1. 计算 h = HMAC-SHA256(d || e, ...)
2. 通过 KDF 派生足够长度的字节串
3. 取前 ⌈log₂n⌉ 位作为候选 k
4. 若 k ∈ [1, n-1] 则接受，否则迭代

优势：

• 消除随机数源缺陷风险
• 便于测试向量构建
• 避免侧信道泄露随机数生成过程

• 服务器端签名（确定性更高）
• 标准化测试
• 高安全要求的密钥托管系统

• 确定性 nonce 不能替代安全随机数用于密钥生成
• 某些场景（如门限签名）需要共享随机性，不适用 RFC 6979

安全分析

k 重用攻击

若同一 nonce $k$ 被用于签名两条不同消息 $m_1, m_2$，产生签名 $(r, s_1), (r, s_2)$，攻击者可以恢复私钥：

$$s_1 = k^{-1}(e_1 + d \cdot r) \bmod n$$ $$s_2 = k^{-1}(e_2 + d \cdot r) \bmod n$$

两式相减：

$$s_1 - s_2 = k^{-1}(e_1 - e_2) \bmod n$$

解得：

$$k = (e_1 - e_2)(s_1 - s_2)^{-1} \bmod n$$ $$d = (s_1 \cdot k - e_1) \cdot r^{-1} \bmod n$$

防护：每次签名必须使用不同的 nonce；优先使用 RFC 6979 确定性构造。

旁路攻击

ECDSA 实现可能受到以下旁路攻击：

哈希函数选择

ECDSA 安全性依赖于哈希函数的抗碰撞性。常用组合：

注意：哈希输出长度必须至少为曲线阶的位数，否则存在生日攻击风险。

与 SM2、EdDSA 的横向对比

ECDSA vs SM2

SM2 是中国的椭圆曲线密码标准，与 ECDSA 具有相似结构但关键差异：

• ZA 预处理：SM2 签名前先计算 $Z_A = H_{256}(ENTL_A \| ID_A \| a \| b \| x_G \| y_G \| x_A \| y_A)$，将身份绑定到签名，这是 SM2 的国密特色。
• 签名公式变体：SM2 使用 $(1+d_A)^{-1}$ 而非 $d_A^{-1}$，防止某些特定的攻击变体。

• 使用 SM3 哈希，不可替换为 SHA-256
• 私钥长度 256 位，公钥为 $(x_A, y_A)$ 坐标对
• 签名值 $(r, s)$ 各 256 位，共 512 位
• 证书格式遵循 GM/T 0015-2023《密码应用标识规范》

ECDSA vs EdDSA

EdDSA（Edwards-curve Digital Signature Algorithm）是较新的签名方案，RFC 8032 标准化了 Ed25519 和 Ed448：

• 确定性 nonce 消除了随机数风险
• 签名公式不依赖模逆运算，性能更稳定
• 官方参考实现（libsodium）经过严格审计

• 历史更久，生态更成熟
• 硬件加速支持更广泛（Smart Card、HSM）
• 与现有 PKI 体系无缝集成

工程实践建议

算法选型决策树

是否需要国密合规？
├── 是 → 使用 SM2（GM/T 0003.2-2012）
└── 否 → 是否需要后量子迁移准备？
    ├── 是 → 考虑 EdDSA（兼容性好）或 ML-DSA（NIST PQC）
    └── 否 → 使用 ECDSA（secp256r1）或 EdDSA（Ed25519）

代码实现要点

Python 示例（使用 gmssl）：

from gmssl import sm2, func

# 生成密钥对
priv_key = func.random_hex(64)  # 256位私钥
pub_key = sm2.CryptSM2(priv_key).generate_public_key()

# 签名（自动处理 ZA 和 SM3 哈希）
message = b"Hello, SM2!"
signature = sm2.CryptSM2(priv_key, pub_key).sign(message)

# 验签
is_valid = sm2.CryptSM2(priv_key, pub_key).verify(signature, message)
print(f"Signature valid: {is_valid}")

Python 示例（使用 cryptography）：

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric.utils import decode_dss_signature, encode_dss_signature

# 生成密钥对
private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# 签名
message = b"Hello, ECDSA!"
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))
r, s = decode_dss_signature(signature)

# 验签
public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))

常见错误与防护

相关实践

• SM2 签名算法深度解析 — 国密 SM2 与 ECDSA 的差异详解
• GM/T 0009-2012 SM2 椭圆曲线公钥密码算法第 2 部分：数字签名算法 — SM2 签名使用规范（完整编号：GM/T 0009-2012）
• Schnorr 签名算法原理 — 线性可加性签名方案
• EdDSA 数字签名算法 — Edwards 曲线确定性签名

参考资料

• NIST FIPS 186-5: Digital Signature Standard (DSS), 2023. https://csrc.nist.gov/publications/detail/fips/186/5/final
• RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), 2013. https://datatracker.ietf.org/doc/rfc6979/
• GM/T 0003.2-2012: 密码领域信息系统密码基本要求 第 2 部分：SM2 椭圆曲线公钥密码算法
• SEC 1: Elliptic Curve Cryptography, Certicom Research, 2000.
• "ECC vs RSA: A Comparative Analysis", NIST Special Publication 800-57 Part 1 Rev. 5, 2020.
• "The Elliptic Curve Digital Signature Algorithm (ECDSA)", Handbook of Applied Cryptography, Chapter 8.