跳到主要内容

椭圆曲线算法

椭圆曲线算法

核心本质：数字签名到底是什么？​

数字签名 = 用私钥生成一个数学证明，证明某条消息确实是你发的，且没有被篡改。

它基于一个完美的数学特性：

有一对密钥（私钥 d，公钥 Q），满足：

  1. 用私钥 d 可以很容易地计算出公钥 Q
  2. 用公钥 Q 几乎不可能反推出私钥 d
  3. 用私钥 d 对消息 m 生成的签名 S，只有用对应的公钥 Q 才能验证其有效性

这个特性的底层是单向数学难题，目前区块链使用最广泛的是：

  • 椭圆曲线离散对数问题（ECDLP）：secp256k1（比特币、以太坊）、ed25519（Solana、Cardano）
  • 已被证明在现有计算能力下无法破解

一、底层数学基础：椭圆曲线​

所有区块链的签名算法都建立在椭圆曲线之上。我们以最常用的 secp256k1 为例

1. secp256k1 曲线方程​

y² = x³ + 7

这是一个极其简单的方程，没有任何复杂的参数，这也是它被选中的原因之一。

2. 椭圆曲线的核心运算​

椭圆曲线上只有两种运算：

  • 点加法：P + Q = R
  • 标量乘法：k * P = Q（将点 P 加 k 次）

标量乘法是单向的：

  • 已知 k 和 P，计算 Q = k*P 非常快（O (log k) 时间）
  • 已知 Q 和 P，计算 k 几乎不可能（这就是椭圆曲线离散对数问题）

3. 密钥对的生成​

  • 私钥 d：一个随机的 256 位整数（范围：1 ≤ d < n，n 是曲线的阶）
  • 公钥 Q：Q = d * G，其中 G 是曲线的基点（一个固定的点）

这就是密钥对生成的全部过程！公钥就是私钥乘以基点得到的一个点。

这里特别要补充一点，这里的 G 是一个固定值

secp256k1 的 G 是中本聪在 2009 年选的，是一个完全公开的固定点，它的坐标是 Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

二、ECDSA 签名算法底层原理（secp256k1）​

ECDSA（椭圆曲线数字签名算法）是目前使用最广泛的签名算法。我会一步步推导它的数学过程。

1. 签名过程（私钥 d，消息 m）​

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

步骤 1：计算消息哈希

h = SHA256(m)  // 或 Keccak256(m)，取决于链

将任意长度的消息压缩成一个 256 位的哈希值。

步骤 2：生成随机数 k

k = 一个随机的256位整数（1 ≤ k < n）

⚠️ 这是整个签名算法中最危险的一步！ k 值必须是唯一且不可预测的。如果两次签名使用了相同的 k 值，攻击者可以直接计算出你的私钥！

步骤 3：计算点 R

R = k * G
r = R.x mod n  // 取R点的x坐标模n

这里的模n 是椭圆曲线的运算都是在一个有限的数字世界里进行的，这个世界的大小就是 n 对于 secp256k1 曲线来说，n 是一个超级大的质数 n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

如果 r=0，重新生成 k。

步骤 4：计算 s

s = k⁻¹ * (h + d * r) mod n

其中 k⁻¹ 是 k 在模 n 下的乘法逆元。

模逆元就是 "模运算世界里的倒数" 在 mod n 的世界里，没有除法，只有乘法。所以我们用 模逆元 来代替除法。 定义：如果 k * k⁻¹ ≡ 1 mod n，那么 k⁻¹ 就是 k 的模逆元。 大白话翻译：k 乘以 k⁻¹，再除以 n，余数正好是 1。

如果 s=0，重新生成 k。

最终签名：(r, s)，通常会加上一个恢复标识 v，用于从签名恢复公钥。

这里的 v 是一个 奇偶判断值，因为椭圆曲线，已知 x ，求解 y 时，有两个解（奇偶） v = 0/1 eth v = 27/28 27 - 偶；28 - 奇

2. 验签过程（公钥 Q，消息 m，签名 (r, s)）​

输入：公钥Q，消息m，签名(r, s)
输出：true/false

步骤 1：计算消息哈希

h = SHA256(m)  // 和签名时使用相同的哈希算法

步骤 2：计算 u1 和 u2

u1 = h * s⁻¹ mod n
u2 = r * s⁻¹ mod n

步骤 3：计算点 P

P = u1 * G + u2 * Q

步骤 4：验证

如果 P.x mod n == r → 签名有效
否则 → 签名无效

3. 为什么这个验证是成立的？（数学证明）​

这是最神奇的地方，我给你做一个简单的推导：

从签名的 s 公式开始：

s = k⁻¹ * (h + d * r) mod n

两边乘以 k：

k * s = h + d * r mod n

两边乘以 s⁻¹：

k = h * s⁻¹ + d * r * s⁻¹ mod n

代入 u1 和 u2 的定义：

k = u1 + d * u2 mod n

两边乘以基点 G：

k * G = u1 * G + d * u2 * G

因为 Q = d * G，所以：

R = u1 * G + u2 * Q = P

所以 P 点的 x 坐标就是 R 点的 x 坐标，也就是 r。验证成立！

三、最致命的安全漏洞：k 值重复​

必须单独强调这一点，因为历史上无数的私钥泄露都是因为 k 值处理不当。

如果两次签名使用了相同的 k 值，攻击者可以在 1 毫秒内计算出你的私钥！

推导过程：

假设两次签名使用了相同的 k，得到两个签名 (r, s1) 和 (r, s2)：

s1 = k⁻¹ * (h1 + d * r) mod n
s2 = k⁻¹ * (h2 + d * r) mod n

两式相减：

s1 - s2 = k⁻¹ * (h1 - h2) mod n

解出 k：

k = (h1 - h2) * (s1 - s2)⁻¹ mod n

有了 k，就可以解出私钥 d：

d = (s1 * k - h1) * r⁻¹ mod n

四、解决方案：RFC 6979 确定性 k 值生成​

为了解决 k 值的问题，现在所有的钱包都使用 RFC 6979 标准生成确定性的 k 值。

原理：k 不再是随机生成的，而是通过私钥和消息哈希计算出来的：

k = HMAC-SHA256(私钥d, 消息哈希h)

这样，对于相同的私钥和相同的消息，k 值永远是相同的；对于不同的消息，k 值永远是不同的。

优点：

  • 完全消除了随机数生成器的漏洞
  • 签名是确定性的：相同的私钥和消息永远生成相同的签名
  • 不需要依赖任何外部随机源

五、Ed25519 签名算法（Solana 等新链使用）​

Ed25519 是一种更新、更安全、更快的签名算法，基于 edwards25519 椭圆曲线。

与 ECDSA 的主要区别​

  1. 没有 k 值问题：Ed25519 的签名过程不需要随机数 k，完全是确定性的
  2. 更快：签名速度比 secp256k1 快约 2 倍，验签速度快约 3 倍
  3. 更小的签名：签名长度是 64 字节，而 ECDSA 是 71-73 字节
  4. 更安全：没有侧信道攻击漏洞，所有操作都是常量时间实现

Ed25519 解决了 ECDSA 的什么问题？​

只要两次签名用了同一个 k 值，攻击者就能在 1 毫秒内算出你的私钥。

为了解决这个问题，我们不得不引入 RFC 6979 确定性 k 值生成，但这只是一个 "补丁"，不是根本解决方案。

Ed25519 从算法设计上彻底消灭了这个问题：

  • 它完全不需要外部随机数
  • 每次签名的 k 值是用私钥和消息哈希计算出来的
  • 相同私钥 + 相同消息永远生成相同签名，不同消息永远生成不同 k 值

除此之外，Ed25519 还有这些优势：

  • ✅ 签名速度比 secp256k1 快 2 倍
  • ✅ 验签速度比 secp256k1 快 3 倍
  • ✅ 签名长度固定 64 字节（ECDSA 是 71-73 字节）
  • ✅ 公钥和私钥都是 32 字节（ECDSA 公钥是 65 字节）
  • ✅ 所有操作都是常量时间实现，原生抗侧信道攻击
  • ✅ 没有模逆元运算，实现更简单，不易出错

Ed25519 使用的是 扭曲爱德华兹曲线（Twisted Edwards Curve），方程比 ECDSA 的 Weierstrass 曲线简单得多：

曲线方程​

-x² + y² = 1 + d x² y²

其中：

  • p = 2²⁵⁵ - 19（这就是 "25519" 名字的由来）
  • d = -121665 / 121666 mod p

曲线参数（全部硬编码）​

和 secp256k1 一样，Ed25519 的所有参数都是固定的，硬编码在所有实现中：

p = 2²⁵⁵ - 19
L = 2²⁵² + 27742317777372353535851937790883648493（曲线的阶）
Gx = 15112221349535400772501151409588531511454012693041857206046113283949847762202
Gy = 46316835694926478169428394003475163141307993866256225615783033603165251855960
G = (Gx, Gy)（基点）

密钥生成过程​

Ed25519 的密钥生成比 ECDSA 稍微复杂一点，但更安全：

1. 生成私钥种子​

生成一个 32 字节的随机数，这就是你的私钥种子。

2. 扩展私钥​

将私钥种子通过 SHA-512 哈希，得到一个 64 字节的扩展私钥：

hash = SHA-512(私钥种子)
a = hash[0:32]（核心私钥，256位）
prefix = hash[32:64]（前缀，用于生成k值）

3. 生成公钥​

公钥就是核心私钥乘以基点 G：

A = a * G

公钥 A 是曲线上的一个点，编码成 32 字节。

注意：Ed25519 的私钥是 64 字节（种子 + 扩展），但通常我们说的 "私钥" 指的是 32 字节的种子。

签名过程（详解）​

输入：扩展私钥(a, prefix)，消息M
输出：签名(R, S)，共64字节

步骤 1：生成确定性 k 值​

这是和 ECDSA 最大的区别：k 值不是随机生成的，而是用私钥前缀和消息哈希计算出来的：

k = SHA-512(prefix || M) mod L
  • || 表示字节拼接
  • L 是曲线的阶

这个设计的绝妙之处：

  • 对于相同的私钥和相同的消息，k 值永远相同
  • 对于不同的消息，k 值永远不同
  • 不需要依赖任何外部随机数生成器
  • 从根本上杜绝了 k 值重复泄露私钥的可能

步骤 2：计算临时公钥 R​

R = k * G

R 是曲线上的一个点，编码成 32 字节。

步骤 3：计算挑战值 h​

h = SHA-512(R || A || M) mod L

这个挑战值把临时公钥 R、公钥 A 和 消息 M 三者绑定在了一起。

步骤 4：计算签名 S​

S = (k + h * a) mod L

S 是一个 256 位的整数，编码成 32 字节。

最终签名​

签名 = R(32字节) + S(32字节)

总共 64 字节，固定长度。

验签过程（一步步推导）​

验签过程非常简单，只有两步，而且不需要任何模逆元运算，这是 Ed25519 比 ECDSA 快的主要原因。

验签流程​

输入：公钥A，消息M，签名(R, S)
输出：true/false

步骤 1：重新计算挑战值 h​

h = SHA-512(R || A || M) mod L

和签名时使用完全相同的哈希算法和输入。

步骤 2：验证椭圆曲线等式​

验证：S * G == R + h * A

如果等式成立，签名有效；否则无效。

最神奇的部分：为什么这个等式成立？​

现在我们来做一个代数变形，证明如果签名是合法的，这个等式一定成立。 从签名的 S 公式开始：

S = (k + h * a) mod L

两边同时乘以基点 G：

S * G = (k + h * a) * G

展开右边：

S * G = k * G + h * a * G

注意到两个关键替换：

  1. 左边第一项 k * G 就是签名时的临时公钥 R
  2. 左边第二项 a * G 就是公钥 A

所以代入后得到：

S * G = R + h * A

证明完毕！ 这个推导比 ECDSA 的验签推导简单得多，也优雅得多，没有任何复杂的模逆元运算。

Ed25519 的局限性​

不支持公钥恢复

这就是为什么以太坊不用 Ed25519 的原因。以太坊的交易格式依赖于公钥恢复：节点收到交易后，从签名中恢复公钥，再算出地址。如果用 Ed25519，交易就必须额外携带 32 字节的公钥，每个交易增加 32 字节的开销。

但对于新的区块链来说，这个问题已经有了解决方案：Solana 就使用了 Ed25519，它的交易格式中包含了公钥。

ECDSA公钥恢复​

公钥恢复是 ECDSA 算法天生自带的特性，不是什么黑科技。它本质是：

签名 (r,s,v) 里已经藏了公钥的所有信息，我们只是把它 "解包" 出来而已。

你不需要提前知道公钥，仅凭消息 + 65 字节签名 (r+s+v)，就能 100% 准确算出对应的公钥。这也是以太坊交易不需要带公钥的根本原因。

签名里到底藏了什么？​

我们之前讲过 ECDSA 签名生成的两个核心公式，这是公钥恢复的基础：

  1. r = (k * G).x mod n → r 是随机点 R 的 x 坐标
  2. s = k⁻¹ * (h + d * r) mod n → s 把私钥 d、消息哈希 h、随机数 k 绑在了一起
  3. 公钥 Q = d * G → 我们要恢复的目标

关键发现：签名 (r,s) 里包含了 R 点的 x 坐标 (r)，以及私钥 d 和随机数 k 的关系 (s)。只要我们能找到 R 点，就能推导出公钥 Q。

公钥恢复的完整步骤​

整个过程只有两步，没有任何魔法，全是初中数学的变形：

步骤 1：从 r 和 v，恢复出完整的 R 点​

我们知道 r 是 R 点的 x 坐标，但椭圆曲线方程是 y² = x³ + 7。

  • 给定一个 x，y 有且只有两个可能的解：y 和 n-y（n 是曲线的阶）
  • 这两个解一个是偶数，一个是奇数（或者说一个小于 n/2，一个大于 n/2）

v 值的唯一作用：就是告诉我们选哪个 y！

  • v=27 → 选 y 是偶数的那个解
  • v=28 → 选 y 是奇数的那个解

这样，我们就从 r 和 v 得到了完整的 R 点 (x=r, y=正确的y)，也就是 k*G。

步骤 2：用 R 点，推导出公钥 Q​

这是最神奇的一步，我们把签名的 s 公式做个简单变形： 从 s = k⁻¹ * (h + d * r) mod n 开始：

  1. 两边乘以 k → s*k = h + d*r
  2. 移项 → d*r = s*k - h
  3. 两边乘以 r 的 "倒数"(模 n 下) → d = (s*k - h) * r⁻¹ mod n
  4. 两边同时乘以基点 G → d*G = (s*k*G - h*G) * r⁻¹ mod n

注意到 k*G 就是我们刚才恢复的 R 点，而 d*G 就是公钥 Q！

所以最终公式简化为：

Q = (s*R - h*G) * r⁻¹ mod n

用大白话翻译：

  1. 把 R 点放大 s 倍
  2. 把基点 G 放大 h 倍
  3. 两者相减
  4. 再放大 r 的 "倒数" 倍
  5. 得到的点就是公钥 Q！

为什么这个方法是安全的？​

很多人会问：既然能从签名恢复公钥，那会不会也能恢复私钥？

绝对不会！ 原因很简单：

  • 我们得到的是 d*G（公钥），不是 d（私钥）
  • 从 d*G 反推 d，就是椭圆曲线离散对数问题，这是目前数学上无法破解的

公钥恢复只是把签名里已经包含的公钥信息提取出来，没有破解任何东西。

什么需要 v 值？​

刚才说了，从 r 只能得到 x 坐标，y 有两个可能的解，所以会得到两个可能的 R 点，进而得到两个可能的公钥。

如果没有 v 值，我们就需要两个都试一遍，看哪个能通过验签。但这样效率太低，所以签名的时候会把 v 值一起带上，直接告诉我们哪个是正确的。

以太坊的 v 值：

  • 主网：27 或 28（对应 y 的奇偶性）

  • EIP-155 后：2_chainId + 35 或 2_chainId + 36（同时包含链 ID，防止重放攻击）

  • 公钥恢复是 ECDSA 算法的原生特性，不是漏洞

  • 签名 (r,s,v) 里已经藏了公钥的所有信息

  • 第一步：用 r 和 v 恢复出完整的 R 点

  • 第二步：用公式 Q = (sR - hG) * r⁻¹ 算出公钥

  • 只能恢复公钥，不能恢复私钥，是安全的