ECDSA 签名

目录

1. ECDSA 概述
2. 椭圆曲线基础
3. secp256k1 曲线
4. ECDSA 签名过程
5. ECDSA 验证过程
6. 比特币中的 ECDSA
7. 安全性分析
8. 常见问题

---

ECDSA 概述

什么是 ECDSA

ECDSA 是 Elliptic Curve Digital Signature Algorithm（椭圆曲线数字签名算法）的缩写。

特性	说明
类型	非对称加密算法
发布时间	1992 年
标准	FIPS 186-4
应用领域	数字签名、身份认证
比特币应用	交易签名、私钥管理

ECDSA 的基本概念

ECDSA 使用椭圆曲线上的点进行加密运算。

关键概念：
1. 椭圆曲线：满足特定方程的点的集合
2. 基点 G：曲线上的一个特殊点
3. 私钥：一个随机的大整数
4. 公钥：通过私钥和基点计算得出
5. 签名：使用私钥对消息的数字签名
6. 验证：使用公钥验证签名的真伪

ECDSA 与 RSA 对比

特性	ECDSA	RSA
密钥大小	256 比特	2048 比特+
计算速度	较快	较慢
安全强度	256 位等同	同等强度需2048位
签名大小	64 字节	256+ 字节
实现复杂度	更复杂	更简单
比特币选择	✅ 是	否

---

椭圆曲线基础

1. 什么是椭圆曲线

椭圆曲线是指满足以下方程的点的集合：

$$y^2 = x^3 + ax + b$$

其中 $a$ 和 $b$ 是参数，需要满足 $4a^3 + 27b^2 \neq 0$（确保曲线没有奇异点）。

2. 椭圆曲线的几何特性

在实数域上的椭圆曲线示例：
y^2 = x^3 - x

图形：
      y
      |
      |    ╭─
      |   ╱
      |  ╱
  ────┼──────────── x
      | ╱
      |╱
      |    ╰─

3. 点的加法运算

椭圆曲线上定义了一个特殊的"加法"运算，不同于普通的向量加法。

规则 1：点到无穷远点

设 O 为无穷远点（椭圆曲线上的"零元素"）

对于任何点 P：
  P + O = O + P = P

O 类似于普通加法中的 0。

规则 2：点的反元素

对于曲线上的点 P(x, y)，其反元素 -P 为 (x, -y)

P + (-P) = O

这点很重要，因为 -P 是 P 关于 x 轴的镜像。

规则 3：两个不同点的相加

设 P = (x1, y1) 和 Q = (x2, y2) 是曲线上的两个不同点，
且 P ≠ -Q。

加法过程：
1. 计算斜率 λ：
   λ = (y2 - y1) / (x2 - x1)

2. 新点 R = P + Q = (x3, y3)，其中：
   x3 = λ^2 - x1 - x2
   y3 = λ(x1 - x3) - y1

几何解释：
  - 通过 P 和 Q 画一条直线
  - 这条直线与曲线相交于第三点 R'
  - 将 R' 关于 x 轴镜像得到 R
  - R 就是 P + Q 的结果

规则 4：点的倍加（点加点本身）

当 P = Q 时（同一点自身相加）

加法过程：
1. 计算切线的斜率 λ：
   λ = (3x1^2 + a) / (2y1)
   
   其中 a 是曲线方程中的参数

2. 新点 R = 2P = (x3, y3)，其中：
   x3 = λ^2 - 2x1
   y3 = λ(x1 - x3) - y1

几何解释：
  - 在点 P 处做曲线的切线
  - 切线与曲线的第二个交点为 P'
  - 将 P' 关于 x 轴镜像得到 R
  - R 就是 2P 的结果

推广：
  kP = P + P + ... + P （k 次）
  
  例如：
  3P = P + P + P
  5P = P + P + P + P + P

4. 椭圆曲线上的离散对数问题

离散对数问题（ECDLP）是 ECDSA 安全性的基础。

问题描述：
  给定椭圆曲线上的两个点 G 和 Q，
  其中 Q = kG（k 是某个整数），
  
  求解 k。

难度等级：
  - 正向：已知 k，计算 Q = kG 
    → 容易（可以快速计算）
  
  - 反向：已知 G 和 Q，求 k
    → 困难（没有已知的快速算法）

为什么困难？
  - 没有"除法"的概念（在椭圆曲线上）
  - 无法直接反演运算
  - 最好的已知算法是指数级的
  
  例子：
  如果 k 是 256 比特的数字，
  蛮力搜索需要大约 2^256 次操作，
  即使世界上所有计算机也无法在可预见的时间内完成。

---

secp256k1 曲线

1. secp256k1 的参数

比特币使用的椭圆曲线称为 secp256k1，其中 "sec" 代表 Standards for Efficient Cryptography。

曲线方程

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

其中 $a = 0$，$b = 7$（这是特殊的简化形式）。

有限域

所有运算都在模一个大素数 $p$ 的有限域上进行：

p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

p (十六进制)：
  0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

p (十进制)：
  115792089237316195423570985008687907853269984665640564039457584007908834671663

这是一个 256 比特的素数，确保了有限域中的所有运算都是定义良好的。

生成点 G

基点 G 是曲线上的一个预定义点：

G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

这个点是公开的，所有比特币节点都使用相同的 G。

性质：
  - G 是椭圆曲线上的一个点
  - G 的阶（最小的正整数 n 使得 nG = O）是一个大素数
  - 任何 256 比特的整数乘以 G 都不会导出 O

曲线阶

曲线的阶（不同点的数量）：

n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

这是一个 256 比特的素数，非常重要。

意义：
  - 任何私钥 k 必须满足 0 < k < n
  - kG（k 倍的基点）对所有有效的 k 都给出不同的公钥
  - n 的大小确保了没有有效的私钥会导致 nG = O

2. secp256k1 的选择原因

为什么比特币选择 secp256k1 而不是其他曲线？

1. 安全性
   - 参数经过充分验证
   - 没有已知的弱点
   - 被 NIST、RFC 等标准推荐

2. 计算效率
   - a = 0 使得某些计算可以优化
   - 曲线上的运算相对快速
   - 适合高频交易签名

3. 透明性
   - 参数来源清晰（不由 NSA 设计）
   - 没有后门的嫌疑
   - 开放社区验证

4. 标准化
   - SEC（Standards for Efficient Cryptography）标准
   - 多个编程语言都有实现
   - 广泛采用（比特币、以太坊等）

历史背景：
  - secp256k1 不是 NIST 官方推荐的曲线
  - NIST 推荐的是 P-256（secp256r1）
  - 但中本聪选择了 secp256k1，可能是为了避免 NSA 可能的后门嫌疑

---

ECDSA 签名过程

ECDSA 签名算法

输入：
  - 私钥 d（一个 0 < d < n 的整数）
  - 消息 m
  - 哈希函数 H（比特币中是 SHA-256）

输出：
  - 签名 (r, s)，其中 r 和 s 都是 256 比特的整数

签名步骤

第 1 步：计算消息哈希

h = H(m) = SHA256(m)

例如，对于交易 m：
  h = SHA256(SHA256(m))  （比特币使用双重哈希）

h 的值是 256 比特的整数（0 到 2^256 - 1）

第 2 步：生成随机数

在每次签名时，生成一个随机数 k，满足：
  0 < k < n
  
其中 n 是曲线的阶。

关键注意事项：
  - k 必须是随机的（至关重要）
  - k 必须保密（如果 k 泄露，私钥可被恢复）
  - 每次签名都必须使用不同的 k
  - 如果两次使用了相同的 k，可以恢复私钥

安全性警告：
  ECDSA 的安全性完全依赖于 k 的随机性。
  如果攻击者可以预测 k，就可以恢复私钥。
  这是 ECDSA 最常见的实现漏洞。

第 3 步：计算 R 点

计算点 R = kG，其中：
  - k 是刚生成的随机数
  - G 是基点
  - 乘法在椭圆曲线上定义

得到的 R 点的坐标为 (R_x, R_y)。

R = kG = (R_x, R_y)

关键性质：
  - R 是椭圆曲线上的一个点
  - R 依赖于随机数 k
  - 每次签名时 R 都不同（因为 k 不同）

第 4 步：计算 r 值

从 R 点的 x 坐标计算 r：

r = R_x mod n

其中 n 是曲线的阶。

注意事项：
  - 取 R_x 的值模以 n（不是模 p）
  - 如果 r = 0，返回第 2 步重新选择 k
    （概率极低，大约 1 / 2^256）

r 值的意义：
  - r 是签名的第一个部分
  - r 编码了随机点 R 的信息
  - r 是公开的（显示在签名中）

第 5 步：计算 s 值

计算 s：

s = k^(-1) × (h + r × d) mod n

其中：
  - k^(-1) 是 k 在模 n 域内的乘法逆元
  - h 是消息哈希
  - r 是前面计算的值
  - d 是私钥
  - n 是曲线的阶

计算顺序（详细）：
  1. 计算 h + r × d (mod n)
  2. 计算 k 的模逆元 k_inv
  3. 计算 s = k_inv × (h + r × d) (mod n)

如果 s = 0，返回第 2 步重新选择 k
（概率极低）

s 值的意义：
  - s 是签名的第二个部分
  - s 包含了私钥 d 的信息，但以加密的形式
  - s 只有签署者（持有 d 的人）才能计算

第 6 步：返回签名

最终签名是一对整数：
  sig = (r, s)

编码方式（DER 格式，比特币使用）：
  - r 和 s 都编码为可变长度的整数
  - 签名的大小通常为 71-72 字节（有时 70 字节）
  - 格式：30 [总长] 02 [r长] [r] 02 [s长] [s]

例子：
  30 44              // DER 序列头，总长 68 字节
  02 20              // 整数标签，长度 32 字节
  [32字节的r]        // r 值
  02 20              // 整数标签，长度 32 字节
  [32字节的s]        // s 值

签名过程总结

签名流程图：

消息 m
  ↓
哈希：h = SHA256(SHA256(m))
  ↓
生成随机 k
  ↓
计算点 R = kG
  ↓
提取 r = R_x mod n
  ↓
计算 s = k^(-1) × (h + r × d) mod n
  ↓
输出签名 (r, s)

---

ECDSA 验证过程

ECDSA 签名验证算法

输入：
  - 公钥 Q（等于 dG，其中 d 是私钥）
  - 消息 m
  - 签名 (r, s)

输出：
  - 有效 ✅ 或 无效 ❌

验证算法的关键特性：
  - 不需要知道私钥 d
  - 只需要公钥 Q
  - 任何人都可以验证
  - 签名不能被伪造

验证步骤

第 1 步：检查基本有效性

检查 r 和 s 的范围：
  0 < r < n
  0 < s < n

如果不满足，签名无效 ❌

这是快速的完整性检查。

第 2 步：计算消息哈希

计算消息的哈希值：
  h = SHA256(SHA256(m))

使用与签名时相同的哈希函数。

第 3 步：计算 w 值

w = s^(-1) mod n

其中 s^(-1) 是 s 在模 n 域内的乘法逆元。

这是 s 的倒数，用于反推原始运算。

第 4 步：计算 u1 和 u2

u1 = (h × w) mod n
u2 = (r × w) mod n

这两个值用于重建原始点 R。

含义：
  - u1 是哈希值的加权版本
  - u2 是签名的加权版本

第 5 步：计算验证点 P

P = u1 × G + u2 × Q

其中：
  - G 是基点
  - Q 是公钥
  - × 表示椭圆曲线点乘
  - + 表示椭圆曲线点加

这个运算重建了原始的点 R。

数学原理（为什么有效）：
  
  签名时：s = k^(-1) × (h + r × d) mod n
  
  因此：k = s^(-1) × (h + r × d) mod n
  
  而：R = kG
  
  所以：
    R = [s^(-1) × (h + r × d)] × G
      = s^(-1) × (h + r × d) × G
      = s^(-1) × h × G + s^(-1) × r × d × G
      = (h × s^(-1)) × G + (r × s^(-1)) × (d × G)
      = u1 × G + u2 × Q
      = P

第 6 步：提取 x 坐标并比较

从点 P 的 x 坐标计算：
  v = P_x mod n

验证条件：
  if v == r:
    ✅ 签名有效
  else:
    ❌ 签名无效

验证过程总结

验证流程图：

消息 m，签名 (r, s)，公钥 Q
  ↓
检查 0 < r < n，0 < s < n
  ↓
计算 h = SHA256(SHA256(m))
  ↓
计算 w = s^(-1) mod n
  ↓
计算 u1 = (h × w) mod n
计算 u2 = (r × w) mod n
  ↓
计算点 P = u1 × G + u2 × Q
  ↓
提取 v = P_x mod n
  ↓
比较：v == r ?
  ↓
输出：有效 ✅ 或 无效 ❌

---

比特币中的 ECDSA

1. 比特币如何使用 ECDSA

密钥对生成

比特币中的密钥生成：

1. 生成私钥（256 比特的随机数）
   priv_key = random_256_bits()
   
   范围：0 < priv_key < n

2. 计算公钥
   pub_key = priv_key × G
   
   pub_key 是椭圆曲线上的一个点（两个坐标）

3. 压缩公钥
   比特币通常使用压缩格式的公钥：
   - 前缀字节：0x02 或 0x03（表示 y 坐标的奇偶性）
   - x 坐标：32 字节
   - 总计：33 字节（而不是 65 字节的未压缩格式）

4. 生成地址
   address = RIPEMD160(SHA256(pub_key))
   
   地址是从公钥派生的。

交易签名

签署比特币交易的过程：

1. 序列化交易
   tx_data = serialize(transaction)

2. 计算交易哈希
   txhash = SHA256(SHA256(tx_data))

3. 为每个输入签名
   对于交易中的每个输入：
   
   a. 构造签名消息（SIGHASH_ALL）
   b. 使用私钥签名
      sig = ECDSA_Sign(txhash, priv_key)
   
   c. 签名被编码为 DER 格式
   d. 添加 SIGHASH 类型字节（0x01）

4. 构造解锁脚本
   scriptSig = sig + pub_key + OP_CHECKSIG

5. 放入交易中
   input.scriptSig = scriptSig

交易验证

网络上的节点验证交易：

对于每个输入：
  1. 提取签名和公钥
  2. 构造相同的签名消息
  3. 使用 ECDSA 验证签名
     if ECDSA_Verify(message, sig, pub_key):
       ✅ 输入有效
     else:
       ❌ 输入无效，交易被拒绝

2. 签名格式

DER 编码

比特币签名使用 DER（Distinguished Encoding Rules）格式：

标准 DER 签名：
  30              // SEQUENCE 标签
  [总长]          // 整个签名的长度
  02              // INTEGER 标签（r 值）
  [r 长]          // r 的长度
  [r 值]          // r 的字节
  02              // INTEGER 标签（s 值）
  [s 长]          // s 的长度
  [s 值]          // s 的字节

例子：
  30 44           // 序列，长度 68 字节
  02 20           // 整数，长度 32 字节
  6e45e16c3b40...（32字节的r）
  02 20           // 整数，长度 32 字节
  b7b6c75d8d2e...（32字节的s）

签名大小：
  - 最小：70 字节（当 r 和 s 的高位是 0 时）
  - 标准：71 字节
  - 最大：72 字节
  
  变化的原因：
  - 如果 r 或 s 的最高位是 1，需要添加 0x00 前缀
  - 这会增加签名的大小

SIGHASH 类型

在签名后附加 SIGHASH 字节，指定签名的适用范围：

SIGHASH_ALL (0x01)：
  - 签名适用于整个交易
  - 最常见的方式
  - 任何字段改变都使签名失效

SIGHASH_NONE (0x02)：
  - 签名只适用于输入，不关心输出
  - 少见使用

SIGHASH_SINGLE (0x03)：
  - 签名适用于相应索引的输出
  - 特殊用途

SIGHASH_ANYONECANPAY (0x80)：
  - 可与上述任何一个组合
  - 表示签名不涵盖其他输入

3. 比特币中的安全性实践

随机数生成

关键安全问题：k 的随机性

历史漏洞：
  - Sony PlayStation 3 固件使用相同的 k
    → 私钥被恢复
  
  - Android Wallet 使用弱 PRNG
    → 私钥被恢复

最佳实践：
  - 使用密码学安全的 PRNG（/dev/urandom）
  - 每次签名生成新的 k
  - 永远不要重复使用 k

比特币的处理：
  - 比特币核心使用高熵的随机数源
  - libsecp256k1 库加强了安全性
  - RFC 6979 建议确定性 k 的生成

RFC 6979 确定性 ECDSA

改进方法：使用确定性生成 k

而不是使用随机的 k，使用以下方式：
  k = HMAC_DRBG(private_key || message_hash)

优点：
  - 消除了 k 的随机性风险
  - 同一消息每次生成相同的签名
  - 仍然保持安全性
  
缺点：
  - 签名具有确定性（可预测）
  - 某些应用场景不需要这样

比特币采用：
  - 比特币核心逐步采用 RFC 6979
  - libsecp256k1 支持确定性 ECDSA

---

安全性分析

ECDSA 的安全基础

ECDSA 的安全性基于椭圆曲线离散对数问题（ECDLP）的困难性。

已知事实：
  - 没有已知的多项式时间算法来解决 ECDLP
  - 最好的通用算法是指数级的
  - 对于 256 比特的曲线，需要大约 2^128 次操作

已知的攻击

1. 虚弱的 k 值

攻击条件：
  - 如果 k 值可被预测或重复使用

攻击方式：
  - 已知两个签名 (r1, s1) 和 (r2, s2) 使用相同的 k
  
  从 s = k^(-1) × (h + r × d) 可以恢复 d：
    s1 - s2 = k^(-1) × (h1 - h2) mod n
    k = (h1 - h2) × (s1 - s2)^(-1) mod n
    然后恢复 d

防护：
  - 确保 k 的随机性
  - 使用确定性 ECDSA（RFC 6979）
  - 不要在多个地方共享私钥实现

2. 侧信道攻击

攻击方式：
  - 通过测量执行时间、功耗、电磁辐射等
  - 推断私钥信息

防护措施：
  - 使用常数时间的实现
  - libsecp256k1 等库已优化防护
  - 比特币节点一般不处于容易受到侧信道攻击的环境

3. 量子计算威胁

Shor 算法可以在多项式时间内解决离散对数问题。

影响：
  - ECDSA 会被完全破坏
  - 任何已发布的公钥都可以恢复私钥

时间表：
  - 目前：量子计算机还在早期
  - 预期：可能需要 10-30 年才能威胁密码学
  - 应对：比特币社区已在研究量子抗性算法

应对方案：
  - Lamport 签名（一次性）
  - Merkle 签名
  - 格基密码学

secp256k1 的安全性

参数安全性：

1. 素数 p 的选择
   - 经过验证，没有已知弱点
   - 足够大（256 比特）

2. 曲线参数 a, b
   - a = 0, b = 7 是简化形式
   - 经过分析，没有特殊的漏洞

3. 基点 G 和阶 n
   - G 是素数阶点
   - n 是大素数
   - 确保了所有私钥都有不同的公钥

4. 没有后门
   - 参数来自开放文献
   - 不是由单一机构秘密设计
   - 被多个标准组织推荐

---

常见问题

Q1: 为什么比特币选择 ECDSA 而不是 RSA？

A:

1. 密钥大小更小：256 比特 ECDSA ≈ 2048 比特 RSA
2. 签名更小：64 字节 vs 256+ 字节
3. 计算更快：特别是签名验证
4. 前瞻性：随着需求增长，ECDSA 更容易扩展
5. 标准化：SEC 标准，业界认可

Q2: 如果私钥泄露会怎样？

A:

• 攻击者可以创建任何签名
• 可以窃取地址上的所有比特币
• 无法恢复被偷走的比特币
• 必须立即转移资金到新地址
• 建议：使用硬件钱包保管私钥

Q3: 签名可以被伪造吗？

A:

• 理论上可以，但在计算上不可行
• 需要知道私钥或解决 ECDLP
• 一旦被发现，可以升级到新算法
• 目前被认为是安全的

Q4: 同一消息的签名为什么不同？

A:

• 因为每次签名使用不同的随机数 k
• 即使消息相同，签名也会不同
• 这是安全特性，而不是问题
• RFC 6979 可以生成确定性签名

Q5: 公钥可以从签名推导出来吗？

A:

• 理论上可能
• 但需要解决 ECDLP（困难的问题）
• 比特币有时会暴露公钥（在交易中）
• P2PKH 地址隐藏公钥直到花费
• Taproot 采用进一步的隐私改进

Q6: ECDSA 有替代方案吗？

A:

1. Schnorr 签名

   • 比 ECDSA 更简洁
   • 支持签名聚合
   • Taproot 采用 Schnorr

2. EdDSA

   • Edwards 曲线 DSA
   • 更易于安全实现

3. 量子抗性算法

   • Lamport 签名
   • Merkle 签名
   • 格基密码学（CRYSTALS-Dilithium 等）