九思札记
教程›区块链›区块链技术›ch02›2.4 椭圆曲线密码学（ECC）与 secp256k1：从零实现

本页目录

graph TD
    Curve[有限域上的椭圆曲线<br/>y² = x³ + ax + b mod p] --> Add[点加法 P + Q]
    Add --> Dbl[倍点 P + P = 2P]
    Dbl --> Scalar[标量乘法 k·G<br/>Double-and-Add 算法]
    Scalar --> Pub[公钥 = 私钥 · G]
    Scalar --> ECDLP[安全假设 ECDLP<br/>已知公钥难推私钥]
    Pub --> Sig[ECDSA 签名/验签]
    style Curve fill:#bbdefb
    style ECDLP fill:#ffcdd2
    style Sig fill:#c8e6c9

2.3 节澄清了区块链中的非对称密码学本质是数字签名，并指出 ECC 在密钥尺寸和签名效率上远超 RSA。本节深入 ECC 的数学心脏——椭圆曲线群上的点运算，并用 TypeScript 从零实现 secp256k1 的点加法、倍点和标量乘法。

2.4.1 椭圆曲线的定义与 secp256k1 参数

标准方程（Weierstrass 形式）

素数域（即模一个素数 pp）上的椭圆曲线定义为满足以下方程的所有点 (x,y)(x, y) 的集合：

y2=x3+ax+b(modp)y^2 = x^3 + ax + b \pmod{p}

其中 a,b∈Fpa, b \in \mathbb{F}_p，且判别式 Δ=4a3+27b2≢0(modp)\Delta = 4a^3 + 27b^2 \not\equiv 0 \pmod{p}（保证曲线非奇异——没有"尖点"或"自交点"）。

secp256k1 的精确参数

secp256k1 是 Standards for Efficient Cryptography - Prime 256-bit Koblitz curve 的缩写。Koblitz 曲线是指 a=0a = 0 的特殊形式，这种选择允许额外的优化。

参数十六进制值意义
aa0曲线参数，简化为 y2=x3+by^2 = x^3 + b
bb7曲线参数 y2=x3+7y^2 = x^3 + 7
pp（域阶）0xFFFFFFFFFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F一个接近 22562^{256} 的素数，定义有限域 Fp\mathbb{F}_p
nn（生成点阶）0xFFFFFFFFFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141生成点 GG 的乘法阶，是一个大素数，约为 22562^{256}
GG（生成点）04 79BE667E F9DCBBAC 55A06295...曲线上一个特定点，所有公钥都是 GG 的标量倍
hh1余因子（cofactor），为 1 表示曲线没有小的子群
typescript
/**
 * secp256k1 参数定义
 */
const SECP256K1 = {
  a: 0n,
  b: 7n,
  p: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fn,
  n: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n,
  // 生成点 G 的坐标
  G: {
    x: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798n,
    y: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8n,
  },
  h: 1n,
} as const;

2.4.2 有限域上的算术

椭圆曲线上的所有运算都在有限域 Fp\mathbb{F}_p 中进行，即所有计算结果必须对 pp 取模。核心运算包括：

模加/模减

a+b(modp)=(a+b)mod  pa + b \pmod{p} = (a + b) \mod p

模乘

a⋅b(modp)=(a⋅b)mod  pa \cdot b \pmod{p} = (a \cdot b) \mod p

模逆元（Fermat 小定理）

a−1≡ap−2(modp)a^{-1} \equiv a^{p-2} \pmod{p}

因为 pp 是素数，且由 Fermat 小定理 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}，所以 ap−2≡a−1(modp)a^{p-2} \equiv a^{-1} \pmod{p}。

typescript
/**
 * 模幂运算：快速幂算法（二进制法）
 * 计算 base^exponent mod mod
 * 时间复杂度：O(log exponent)
 */
function modPow(base: bigint, exponent: bigint, mod: bigint): bigint {
  if (mod === 1n) return 0n;
  let result = 1n;
  let b = ((base % mod) + mod) % mod;
  let e = exponent;
  while (e > 0n) {
    if (e & 1n) {
      result = (result * b) % mod;
    }
    b = (b * b) % mod;
    e >>= 1n;
  }
  return result;
}

/**
 * 模逆元：使用 Fermat 小定理
 * a^{-1} ≡ a^{p-2} (mod p)，要求 p 为素数
 */
function modInverse(a: bigint, p: bigint): bigint {
  return modPow(((a % p) + p) % p, p - 2n, p);
}

// --- 模运算验证 ---
const p = 17n; // 用小素数验证
console.log(`模逆 3^{-1} mod 17 = ${modInverse(3n, p)}`);
// 应输出 6，因为 3 * 6 = 18 ≡ 1 (mod 17)

2.4.3 点加法：椭圆曲线上的群运算法则

椭圆曲线上的点集（包含一个特殊的"无穷远点" O\mathcal{O}）在点加法下构成一个阿贝尔群。

几何直觉

给定两个不同的点 P=(x1,y1)P = (x_1, y_1) 和 Q=(x2,y2)Q = (x_2, y_2)：

  1. 过 P,QP, Q 画一条直线，与曲线相交于第三点 R′R'。
  2. 将 R′R' 关于 xx 轴对称，得到 P+Q=RP + Q = R。

代数公式（需在有限域 Fp\mathbb{F}_p 中计算）：

λ=y2−y1x2−x1(modp)=(y2−y1)⋅(x2−x1)−1 mod p\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod{p} = (y_2 - y_1) \cdot (x_2 - x_1)^{-1} \bmod p
x3=λ2−x1−x2(modp)x_3 = \lambda^2 - x_1 - x_2 \pmod{p}
y3=λ(x1−x3)−y1(modp)y_3 = \lambda(x_1 - x_3) - y_1 \pmod{p}

倍点运算（P+P=2PP + P = 2P）

当 P=QP = Q 时，直线变为切线：

λ=3x12+a2y1(modp)=(3x12+a)⋅(2y1)−1 mod p\lambda = \frac{3x_1^2 + a}{2y_1} \pmod{p} = (3x_1^2 + a) \cdot (2y_1)^{-1} \bmod p
typescript
/**
 * 椭圆曲线上的点
 * 使用 bigint 支持 256 位大整数运算
 */
class ECPoint {
  constructor(
    public x: bigint | null, // null 表示无穷远点 O
    public y: bigint | null,
  ) {}

  isInfinity(): boolean {
    return this.x === null || this.y === null;
  }

  isEqual(other: ECPoint): boolean {
    return this.x === other.x && this.y === other.y;
  }

  toString(): string {
    if (this.isInfinity()) return "O (Infinity)";
    return `(this.x!.toString(16).slice(0,16)...,{this.x!.toString(16).slice(0, 16)}...,{this.y!.toString(16).slice(0, 16)}...)`;
  }
}

/**
 * 在 secp256k1 曲线上执行点加法 P + Q
 */
function ecAdd(P: ECPoint, Q: ECPoint, a: bigint, p: bigint): ECPoint {
  // O + P = P, P + O = P
  if (P.isInfinity()) return new ECPoint(Q.x, Q.y);
  if (Q.isInfinity()) return new ECPoint(P.x, P.y);

  // 如果 P 和 Q 的 x 相同但 y 相反，P + Q = O
  if (P.x === Q.x && P.y !== Q.y) {
    return new ECPoint(null, null);
  }

  let lambda: bigint;
  const x1 = P.x!, y1 = P.y!, x2 = Q.x!, y2 = Q.y!;

  if (P.isEqual(Q)) {
    // 倍点：P = Q，lambda = (3x₁² + a) / (2y₁)
    const numerator = (3n * x1 * x1 + a) % p;
    const denominator = modInverse(2n * y1, p);
    lambda = (numerator * denominator) % p;
  } else {
    // 普通点加：lambda = (y₂ - y₁) / (x₂ - x₁)
    const numerator = ((y2 - y1) % p + p) % p;
    const denominator = modInverse(((x2 - x1) % p + p) % p, p);
    lambda = (numerator * denominator) % p;
  }

  const x3 = ((lambda * lambda) % p - x1 - x2) % p;
  const y3 = (lambda * ((x1 - x3) % p) - y1) % p;

  return new ECPoint(
    ((x3 % p) + p) % p,
    ((y3 % p) + p) % p,
  );
}

// --- 用小参数验证 ---
// 使用一个小素数 p=97，曲线 y^2 = x^3 + 7 进行可视化和验证
const testP = 97n;
const testA = 0n;
const testB = 7n;
// 手动验证点 (3, 91) 是否在曲线上：91^2 mod 97 = 8281 mod 97 = 42; 3^3 + 7 = 34 mod 97；不相等，重新计算
// 找到曲线上的点：x=10: 10^3+7=1007, 1007 mod 97 = 1007 - 97*10 = 37
// y^2 ≡ 37 (mod 97) → 需要找 y 使得 y^2 mod 97 = 37
// y=17: 289 mod 97 = 289 - 2*97 = 95; y=23: 529 - 5*97 = 529 - 485 = 44; 
// 实际上在 secp256k1 的大参数下验证更直接
console.log("\n点加法实现完成，准备用 secp256k1 参数测试...");

2.4.4 标量乘法：私钥到公钥的核心运算

标量乘法是椭圆曲线密码学中最重要的运算：k×P=P+P+…+Pk \times P = P + P + \ldots + P（kk 次）。

核心安全假设：椭圆曲线离散对数问题（ECDLP）

给定 PP 和 Q=k×PQ = k \times P，求 kk 在计算上是不可行的。当前已知最好的通用算法（如 Pollard's Rho）的时间复杂度约为 O(n)≈2128O(\sqrt{n}) \approx 2^{128} 次运算——这在当前及可预见的计算能力下是不可能的。

快速标量乘法：双倍-加算法（Double-and-Add）

简单的 kk 次重复加法需要 O(k)O(k) 次点加法。但使用快速幂思想（将 kk 展开为二进制），可以将复杂度降到 O(log⁡k)O(\log k)：

text
输入：标量 k（二进制：k_{n-1} ... k_1 k_0）
结果 = O
当前点 = P

对 i 从 0 到 n-1：
  如果 k_i == 1：结果 = 结果 + 当前点
  当前点 = 2 * 当前点

返回 结果
typescript
/**
 * 快速标量乘法：k * P
 * 使用 Double-and-Add 算法
 */
function scalarMultiply(k: bigint, P: ECPoint, a: bigint, p: bigint): ECPoint {
  let result = new ECPoint(null, null); // O (无穷远点，群的单位元)
  let addend = new ECPoint(P.x, P.y);
  
  let n = k;
  while (n > 0n) {
    if (n & 1n) {
      result = ecAdd(result, addend, a, p);
    }
    addend = ecAdd(addend, addend, a, p); // 2 * addend
    n >>= 1n;
  }
  
  return result;
}

// --- 完整验证链 ---
const p = SECP256K1.p;
const a = SECP256K1.a;
const G = new ECPoint(SECP256K1.G.x, SECP256K1.G.y);

// 1. 验证 G 在曲线上：y^2 = x^3 + 7 (mod p)
const lhs = (G.y! * G.y!) % p;
const rhs = ((modPow(G.x!, 3n, p) + SECP256K1.b) % p);
console.log(`G 点验证: y^2 (lhs.toString(16).slice(0,16)...)=x3+7?{lhs.toString(16).slice(0, 16)}...) = x^3+7?{lhs === rhs}`);

// 2. 测试标量乘法: 2*G, 3*G
const twoG = scalarMultiply(2n, G, a, p);
const threeG = scalarMultiply(3n, G, a, p);
console.log(`2*G 计算完成: ${twoG.toString()}`);
console.log(`3*G 计算完成: ${threeG.toString()}`);

// 3. 验证 2*G + G = 3*G（标量乘法的分配律）
const addCheck = ecAdd(twoG, G, a, p);
console.log(`(2G + G = 3G)? ${addCheck.isEqual(threeG)}`);

// 4. 一个随机私钥对应的公钥
const d = 0x4c656f6e206973206120676f6f6420626f79n; // "Leon is a good boy" → 用熵编码的私钥
const P = scalarMultiply(d, G, a, p);
console.log(`\n私钥 d=0x${d.toString(16).slice(0, 16)}...`);
console.log(`公钥 P=${P.toString()}`);
console.log(`验证: d*G 在曲线上? ${((P.y! * P.y!) % p === (modPow(P.x!, 3n, p) + 7n) % p)}`);

2.4.5 公钥的压缩表示

未压缩公钥占用 65 字节（0x04 + x 坐标 32 字节 + y 坐标 32 字节）。为了节省区块空间，比特币和以太坊使用压缩公钥：

如果 y 是偶数:0x02∥x（33 字节）如果 y 是奇数:0x03∥x（33 字节）\text{如果 } y \text{ 是偶数} : 0x02 \parallel x \text{（33 字节）}\\ \text{如果 } y \text{ 是奇数} : 0x03 \parallel x \text{（33 字节）}

如何从 xx 恢复 yy？

已知 y2=x3+7(modp)y^2 = x^3 + 7 \pmod{p}，计算 y2y^2 的平方根。在有限域中，a≡a(p+1)/4(modp)\sqrt{a} \equiv a^{(p+1)/4} \pmod{p}（当 p≡3(mod4)p \equiv 3 \pmod{4} 时，secp256k1 的 pp 满足此条件）。

typescript
/**
 * 从 x 坐标和奇偶性恢复 y 坐标
 * 使用 Tonelli-Shanks 的简化版：y = sqrt(x^3 + 7) mod p
 * 对 secp256k1，因 p ≡ 3 (mod 4)，可用简化式：sqrt = a^((p+1)/4) mod p
 */
function recoverY(x: bigint, isEven: boolean, p: bigint): bigint {
  const y2 = (modPow(x, 3n, p) + 7n) % p;
  const y = modPow(y2, (p + 1n) / 4n, p);
  // 选择正确的奇偶性
  const isYEven = (y % 2n === 0n);
  if (isEven === isYEven) return (y + p) % p;
  return (p - y) % p;
}

// 从生成点 G 测试恢复
const gy = recoverY(G.x!, true, p); // G.y 是偶数
console.log(`\n从 x 恢复 y: 计算值=gy.toString(16).slice(0,16)...实际值={gy.toString(16).slice(0, 16)}... 实际值={G.y!.toString(16).slice(0, 16)}...`);
console.log(`恢复一致性: ${gy === G.y!}`);

2.4.6 为什么 secp256k1 而不是其他曲线？

曲线方程特点主要使用方
secp256k1y2=x3+7y^2 = x^3 + 7Koblitz 曲线，高效实现，参数选择无"魔术数"嫌疑比特币、以太坊
secp256r1 / P-256y2=x3−3x+by^2 = x^3 - 3x + bNIST 标准化曲线，b 参数被认为有"后门"嫌疑TLS、政府系统
Curve25519y2=x3+486662x2+xy^2 = x^3 + 486662x^2 + xMontgomery 曲线，更简洁的常数时间实现Signal 协议、WireGuard

中本聪选择 secp256k1 而非 NIST 曲线 P-256，有说法是避免美国政府可能植入的后门。secp256k1 的 a=0,b=7a=0, b=7 选择简单透明，没有未解释的"随机"常数。

核心认知

  1. 椭圆曲线上的点构成一个阿贝尔群——支持加法、减法，有单位元（无穷远点 O\mathcal{O}）。群结构是离散对数难题存在的前提。
  1. 标量乘法是"易算难逆"的密码学单向函数。 d×Gd \times G 可在毫秒内计算，但从 PP 和 GG 反推 dd 需要 21282^{128} 次运算。
  1. 有限域中的模运算需要特别小心——除法变为乘模逆元，利用 Fermat 小定理高效实现。所有中间结果必须保持模 pp 归一化，否则链式错误会迅速放大。
  1. 压缩公钥节省 50% 空间。 从 xx 恢复 yy 依赖 p≡3(mod4)p \equiv 3 \pmod{4} 的特殊性质，这并非所有素域都满足——这也是 secp256k1 参数设计的一部分。

下一预告：2.5 将基于椭圆曲线的标量乘法实现完整的 ECDSA 签名与验签流程，并深入剖析著名的 Sony PS3 私钥泄露事件——为什么一个"随机数重复"的错误可以导致巨额经济损失。

返回 区块链 教程列表

评论

0

评论加载中…

发表评论

0/2000