Skip to content

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 对比 ​

特性ECDSARSA
密钥大小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 等)