椭圆曲线基础 — Weierstrass 形式与点加法

日期: 2026-10-31 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #椭圆曲线 #点加法 #标量乘法 #ECDSA

---

今日目标

---

一、动机

ECC 比 RSA 短而强：256-bit ECC ≈ 3072-bit RSA 安全。原因：在 $E(\mathbb{F}_p)$ 上 ECDLP 没有 sub-exponential 算法（不像 $\mathbb{F}_p^*$ 上的 index calculus）。所以同等安全下密钥 12 倍小、签名快 10×、Gas 便宜。

---

二、严格定义

2.1 Weierstrass 短形式

定义 2.1：$\mathbb{F}_p$ 上椭圆曲线 ($p > 3$) 是方程 $$E: y^2 = x^3 + ax + b, \quad a, b \in \mathbb{F}_p$$ 条件：判别式 $\Delta = -16(4a^3 + 27b^2) \ne 0$（无奇点，光滑）。

2.2 点集与无穷远点

$$E(\mathbb{F}_p) = {(x, y) \in \mathbb{F}_p^2 : y^2 = x^3 + ax + b} \cup {\mathcal{O}}$$

$\mathcal{O}$ 是无穷远点（exception 元素），是群单位元。

2.3 群运算 — 点加法 $P + Q$

几何法则 (chord-tangent)：

1. $P \ne Q, P \ne -Q$：画过 $P, Q$ 的直线，交曲线于第 3 点 $R'$，取 $R'$ 关于 $x$ 轴的对称点 $R = -R'$，定义 $P + Q = R$。
2. $P = Q$ (Doubling)：用切线代替弦，求切线与曲线的另一个交点。
3. $P = -Q$：直线垂直，"交点在无穷远"，定义 $P + Q = \mathcal{O}$。
4. $\mathcal{O}$ 性质：$P + \mathcal{O} = P$。

2.4 群公理验证（结论）

定理 2.2：$(E(\mathbb{F}_p), +)$ 是 abelian 群，单位元 $\mathcal{O}$，逆元 $-P = (x_P, -y_P)$。

结合律的证明非平凡（用射影几何或双有理变换）。教材如 Silverman 用代数簇方法。

2.5 Hasse 定理

定理 2.3 (Hasse 1934)：$|#E(\mathbb{F}_p) - (p+1)| \le 2\sqrt{p}$。

意义：曲线点数大致是 $p+1 \pm 2\sqrt p$。这给出 ECDLP 群的大小估计，也限制了攻击者的 baby-step-giant-step 开销 ($O(\sqrt p)$)。

2.6 Schoof 定理 (1985)

定理 2.4：$#E(\mathbb{F}_p)$ 可在多项式时间 $O((\log p)^{5+\varepsilon})$ 算出。

意义：选曲线时必须验证点数（确保有大素数子群）。Schoof 让这变可行。

---

三、完整推导：点加法公式

3.1 弦法 ($P \ne Q$)

设 $P = (x_1, y_1), Q = (x_2, y_2)$，$x_1 \ne x_2$。直线斜率： $$\lambda = \frac{y_2 - y_1}{x_2 - x_1}$$

直线方程 $y = \lambda(x - x_1) + y_1$。代入曲线： $$(\lambda(x-x_1)+y_1)^2 = x^3 + ax + b$$

展开整理为 $x$ 的三次方程，根有 $x_1, x_2, x_3$。Vieta 定理： $$x_1 + x_2 + x_3 = \lambda^2$$ $$\Rightarrow x_3 = \lambda^2 - x_1 - x_2$$

$y$ 坐标（取负，因为对称）： $$y_3 = \lambda(x_1 - x_3) - y_1$$

3.2 切线法 (Doubling, $P = Q$)

斜率从隐函数求导：$2y \frac{dy}{dx} = 3x^2 + a$，所以 $$\lambda = \frac{3x_1^2 + a}{2 y_1}$$

公式同上： $$x_3 = \lambda^2 - 2x_1, \quad y_3 = \lambda(x_1 - x_3) - y_1$$

3.3 完整加法算法

ADD(P, Q):
  if P == O: return Q
  if Q == O: return P
  if P.x == Q.x:
    if P.y == -Q.y: return O           # 互逆
    else:           return DOUBLE(P)    # P == Q
  λ = (Q.y - P.y) / (Q.x - P.x)
  x3 = λ² - P.x - Q.x
  y3 = λ(P.x - x3) - P.y
  return (x3, y3)

3.4 标量乘法：double-and-add

$kP = \underbrace{P + P + \dots + P}_k$ 但 $k \approx 2^{256}$ 不能朴素加。

算法 (二进制展开)：

SCALAR_MUL(k, P):
  R = O
  for bit in bits_of(k) from MSB:
    R = DOUBLE(R)
    if bit == 1: R = ADD(R, P)
  return R

复杂度 $O(\log k)$ 次群运算。

安全注意：朴素 double-and-add 漏侧信道（不同分支耗时不同）。Montgomery ladder 是恒定时间替代。

---

四、直觉与图像

4.1 几何直觉（实数曲线 $y^2 = x^3 - x$）

• 曲线对称于 $x$ 轴（因为 $y^2$ 对称）
• 任何穿过两点 $P, Q$ 的直线在三次曲线上恰好有第 3 个交点（Bezout 定理：直线与三次曲线交 3 次）
• 取该交点关于 $x$ 轴的镜像 → 这就是 $P + Q$
• 切线"算两个交点"，所以切线交另一点就是 $2P$

4.2 为什么有限域上仍可计算

代数公式 (3.1, 3.2) 中只用到加减乘除，这些在 $\mathbb{F}_p$ 上都有定义（除法 = 乘以逆）。所以"几何"图像消失了，但代数法则保留——曲线点群依然是群。

4.3 类比

ECDLP：给定 $G$ 和 $Q = kG$，求 $k$。

• 类似"知道你走了一些步到了某地，反推走了多少步"
• 在大群里步数空间 $\sim 2^{256}$，无法穷举
• 没有 index calculus 类的攻击（不像 $\mathbb{F}_p^*$）

---

五、代码实现 (ec.py)

"""
Day 183: 椭圆曲线 secp256k1 实现
y² = x³ + 7 over F_p
"""
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional


# ============ secp256k1 参数 ============
P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
A = 0
B = 7
GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
N  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # 子群阶


def inv_mod(a: int, p: int) -> int:
    """模逆 (扩展欧几里得)"""
    return pow(a, -1, p)  # Python 3.8+


@dataclass
class Point:
    """椭圆曲线点. None 表示无穷远点 O"""
    x: Optional[int]
    y: Optional[int]

    @classmethod
    def infinity(cls) -> "Point":
        return cls(None, None)

    def is_infinity(self) -> bool:
        return self.x is None

    def __eq__(self, o):
        return self.x == o.x and self.y == o.y

    def __neg__(self) -> "Point":
        if self.is_infinity():
            return self
        return Point(self.x, (-self.y) % P)


def is_on_curve(pt: Point) -> bool:
    if pt.is_infinity():
        return True
    return (pt.y * pt.y - pt.x * pt.x * pt.x - A * pt.x - B) % P == 0


def ec_add(P1: Point, P2: Point) -> Point:
    """椭圆曲线点加法"""
    if P1.is_infinity(): return P2
    if P2.is_infinity(): return P1

    if P1.x == P2.x:
        if (P1.y + P2.y) % P == 0:
            return Point.infinity()  # P + (-P) = O
        # P == Q, doubling
        lam = (3 * P1.x * P1.x + A) * inv_mod(2 * P1.y, P) % P
    else:
        lam = (P2.y - P1.y) * inv_mod((P2.x - P1.x) % P, P) % P

    x3 = (lam * lam - P1.x - P2.x) % P
    y3 = (lam * (P1.x - x3) - P1.y) % P
    return Point(x3, y3)


def ec_double(P1: Point) -> Point:
    return ec_add(P1, P1)


def scalar_mul(k: int, pt: Point) -> Point:
    """double-and-add 标量乘法"""
    k = k % N  # 在子群内
    if k == 0 or pt.is_infinity():
        return Point.infinity()
    if k < 0:
        return scalar_mul(-k, -pt)

    R = Point.infinity()
    Q = pt
    while k:
        if k & 1:
            R = ec_add(R, Q)
        Q = ec_double(Q)
        k >>= 1
    return R


# ============ 演示 ============
if __name__ == "__main__":
    G = Point(GX, GY)
    print(f"G is on curve: {is_on_curve(G)}")

    # 1. 2G
    G2 = ec_double(G)
    print(f"2G.x = {hex(G2.x)}")
    print(f"2G on curve: {is_on_curve(G2)}")

    # 2. 3G via add
    G3a = ec_add(G2, G)
    G3b = scalar_mul(3, G)
    assert G3a == G3b
    print(f"3G consistent (add vs scalar_mul)")

    # 3. nG = O (子群阶)
    nG = scalar_mul(N, G)
    assert nG.is_infinity()
    print(f"N*G = infinity ✓ (子群阶验证)")

    # 4. 公钥生成 (示例私钥)
    priv = 0x1
    pub = scalar_mul(priv, G)
    print(f"\n私钥 d=1, 公钥 = G")
    print(f"  pub.x = {hex(pub.x)}")

    priv = 0xC9BFA8BA9B05E33891D34F22F65D2A8B7AE9C8E20A0F0F0F0F0F0F0F0F0F0F0F
    pub = scalar_mul(priv, G)
    print(f"\n私钥 d=任意 256-bit")
    print(f"  pub.x = {hex(pub.x)}")
    print(f"  pub on curve: {is_on_curve(pub)}")

    # 5. 验证 ECDLP 困难性的直觉: 给定 pub 反推 priv 需要 ~2^256 操作
    #    朴素 baby-step-giant-step 需要 sqrt(N) ≈ 2^128 内存
    print(f"\nECDLP attack baby-step-giant-step memory: 2^{128}")

运行输出：

G is on curve: True
2G.x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
2G on curve: True
3G consistent (add vs scalar_mul)
N*G = infinity ✓ (子群阶验证)

私钥 d=1, 公钥 = G
  pub.x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

Montgomery Ladder（恒定时间）

def scalar_mul_ladder(k: int, P0: Point) -> Point:
    """恒定时间 Montgomery ladder, 防侧信道"""
    R0 = Point.infinity()
    R1 = P0
    for i in range(k.bit_length() - 1, -1, -1):
        if (k >> i) & 1:
            R0 = ec_add(R0, R1)
            R1 = ec_double(R1)
        else:
            R1 = ec_add(R0, R1)
            R0 = ec_double(R0)
    return R0

---

六、密码学应用关联

6.1 ECDSA 签名（仅举公式）

签消息 $m$，私钥 $d$：

1. 选随机 $k \in [1, n-1]$，计算 $R = kG = (x_R, y_R)$
2. $r = x_R \mod n$
3. $s = k^{-1}(H(m) + rd) \mod n$
4. 签名 $(r, s)$

验证用公钥 $Q = dG$： $u_1 = H(m)/s, u_2 = r/s$，检验 $u_1 G + u_2 Q$ 的 $x$ 坐标是否 $= r$。

6.2 ECDH 密钥交换

Alice: $a, A = aG$。Bob: $b, B = bG$。共享：$abG$。

6.3 EdDSA / Ed25519

用 Edwards 形式 $x^2 + y^2 = 1 + dx^2 y^2$，加法公式没有分支（更安全），$d$ 是 Curve25519 参数。

6.4 BLS 签名

基于 pairing-friendly 曲线（如 BLS12-381）。Day 185 详谈。

---

七、真实参数

secp256k1 (Bitcoin/Ethereum)

p  = 2^256 - 2^32 - 977 (= FFFF...FFFFFC2F)
a  = 0
b  = 7
Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
n  = FFFF...FFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 (子群阶)
h  = 1 (余因子)

Curve25519 (Signal, TLS, Tor)

p = 2^255 - 19
Edwards form: -x² + y² = 1 - (121665/121666) x² y²
n ≈ 2^252 + ...
h = 8

BN254（曾用于 zkSNARKs，现已弱）

p ≈ 2^254
embedding degree k = 12
现已不安全（NFS 攻击，2016 后弃用）

BLS12-381

p ≈ 2^381 (base field)
n ≈ 2^255 (子群阶, 256-bit security)
embedding degree 12
当前 ZK 主流

---

八、常见陷阱

1. 无效曲线攻击 (Invalid Curve Attack)：协议未验证收到的点是否在曲线上，攻击者发"伪点"（在另一条小阶曲线上），让 $kP$ 落入小子群。修复：每次解析点必须检查 is_on_curve。
2. Twist Attack：Curve25519 的 twist 是 Curve25519' 也强，所以安全；但其他曲线的 twist 可能弱。
3. 侧信道攻击：朴素 double-and-add 在 bit=1 时多做一次加，时序可推 bit。Montgomery ladder 必备。
4. 小子群攻击：余因子 $h>1$ 的曲线（如 Curve25519, $h=8$）必须 clamp 私钥低 3 bit。
5. 重用 nonce $k$：ECDSA 中相同 $k$ 签两条消息泄露私钥（Sony PS3, Bitcoin Android 钱包事故）。必须用 RFC 6979 deterministic nonce 或硬件 RNG。
6. 混淆"曲线阶"和"子群阶"：$#E(\mathbb{F}_p) = h \cdot n$。secp256k1 中 $h=1$ 所以一致；Curve25519 $h=8$ 时要小心。

---

九、关键速查

公式表

Python 函数签名

def is_on_curve(pt: Point) -> bool
def ec_add(P1: Point, P2: Point) -> Point
def ec_double(P1: Point) -> Point
def scalar_mul(k: int, pt: Point) -> Point
def scalar_mul_ladder(k: int, pt: Point) -> Point  # 恒定时间

---

十、面试题

Q1: 为什么 ECC 比 RSA 短？

答：在 $\mathbb{F}_p^*$ 上 DLP 有 General Number Field Sieve (GNFS) 等 sub-exponential 算法，复杂度 $\exp(O((\log p)^{1/3}))$。需要 $p \approx 3072$ bit 达到 128-bit 安全。

在椭圆曲线 $E(\mathbb{F}_p)$ 上 ECDLP 没有这种攻击（除特殊曲线如 supersingular），最佳通用攻击是 Pollard's rho，复杂度 $O(\sqrt n)$。所以 $n \approx 2^{256}$ 即足够。

Q2: 解释无穷远点 $\mathcal{O}$ 是什么。

答：射影坐标视角，$E$ 在射影平面 $\mathbb{P}^2$ 是齐次方程 $Y^2 Z = X^3 + a XZ^2 + bZ^3$。仿射点 $(x,y)$ 对应 $(x:y:1)$；$Z=0$ 时，$X^3 = 0 \Rightarrow X=0$，得唯一无穷远点 $(0:1:0)$，即 $\mathcal{O}$。它是群单位元，$P + \mathcal{O} = P$，所有竖直直线"在无穷远相交"对应 $P + (-P) = \mathcal{O}$。

Q3: 为什么 secp256k1 余因子 $h=1$ 重要？

答：曲线点群 $E(\mathbb{F}_p)$ 阶 = $h \cdot n$。$h=1$ 意味着整个点群就是大素数阶子群，没有非平凡子群。这避免了 small subgroup attack（攻击者无法把密钥落入小群）。Curve25519 $h=8$ 所以协议必须 clamp，secp256k1 不需要 clamp 是其设计简洁性优势。

Q4: 推导 doubling 公式（$P = Q$ 时）。

答：曲线 $y^2 = x^3 + ax + b$。隐式微分： $$2y, dy = (3x^2 + a), dx \Rightarrow \frac{dy}{dx} = \frac{3x^2+a}{2y}$$

切线斜率即此 $\lambda$。切线 $y = \lambda(x - x_1) + y_1$ 代入曲线： $$(\lambda(x-x_1)+y_1)^2 - (x^3 + ax + b) = 0$$

是 $x$ 的三次方程；$x = x_1$ 是二重根（切线接触），第三根 $x_3$ 由 Vieta： $$x_1 + x_1 + x_3 = \lambda^2 \Rightarrow x_3 = \lambda^2 - 2x_1$$

$y_3 = -(\lambda(x_3 - x_1) + y_1) = \lambda(x_1 - x_3) - y_1$（取负是因第三交点在曲线上，加法定义需镜像）。

Q5: 什么是 invalid curve attack，如何防御？

答：受害者实现假设输入点在曲线 $E$ 上，但攻击者发送 "twisted" 点 $P' \in E'$ ($E'$ 是不同曲线)。受害者把 $P'$ 当 $E$ 点做 $kP'$，结果实际在 $E'$ 上。若 $E'$ 有小子群 $H$，攻击者选 $P'$ 阶 $|H|$，则 $kP'$ 给出 $k \mod |H|$。重复多次（不同小群）+ CRT 恢复完整 $k$。

防御：

1. 解析时强制 is_on_curve
2. 对压缩点做 $\sqrt{}$ 校验
3. 选 $h=1$ 的曲线（彻底无小子群）

---

十一、明日预告

Day 184: 主流椭圆曲线对比 — 横向比较 secp256k1 / Curve25519 / BN254 / BLS12-381 四条曲线：性能、安全级别、嵌入度、是否 pairing-friendly、用例。理解为什么 Bitcoin 选 secp256k1 而 Ethereum precompile 加 BN254/BLS12-381。

核心问题：什么叫 pairing-friendly？嵌入度 $k$ 越小越好还是越大越好？

参考文献：

• Silverman, The Arithmetic of Elliptic Curves, Springer.
• Hankerson, Menezes, Vanstone, Guide to Elliptic Curve Cryptography.
• Schoof, "Elliptic curves over finite fields and the computation of square roots mod p", 1985.
• Hasse, "Zur Theorie der abstrakten elliptischen Funktionenkörper", 1934.