椭圆曲线密码学(ECC)基础：有限域、椭圆曲线方程、点加与标量乘法

好，咱们进入正题。这一章是 ECC 的根基，说白了就是搞明白三个东西：有限域是什么、椭圆曲线方程长什么样、点加和标量乘法怎么算。

我刚开始接触 ECC 时，觉得这玩意儿挺玄乎。后来踩了几个坑才明白，其实核心逻辑并不复杂。你想想看，ECC 的安全性本质上就是靠「在有限域上做椭圆曲线点加」这个操作来撑着的。

2.1 有限域：ECC 的「数字沙盘」

先聊有限域。为什么需要它？

实数域上的椭圆曲线是连续的，图像很漂亮。但密码学里不能用连续的东西——计算机算不了无限精度的小数，而且实数域上的离散对数问题太好解了。我们需要一个「离散」的、元素个数有限的集合，这就是有限域。

核心定义：有限域 Fp 是一个包含 p 个元素的集合，p 是素数。所有运算（加、减、乘、除）都在模 p 下进行。

举个例子，F7 包含 {0,1,2,3,4,5,6}。在 F7 里，5 + 6 = 4（因为 11 mod 7 = 4），3 × 4 = 5（12 mod 7 = 5）。

我个人习惯把有限域想象成一个「数字沙盘」——所有操作都被限制在这个沙盘里，出不去。ECC 就在这个沙盘上画椭圆曲线。

域类型 表示 元素个数 典型应用
素数域 Fp p（大素数） secp256k1、P-256
二进制域 F2m 2m Curve25519（部分实现）
扩域 Fpm pm 配对友好曲线

避坑指南：我曾经在实现 ECC 时，忘记把中间结果模 p，导致点坐标越界，算出来的点根本不在曲线上。调试了整整两天才发现。记住：有限域上的每一步运算都要模 p，包括中间结果。

2.2 椭圆曲线方程：Weierstrass 标准型

ECC 用的曲线方程长这样：

y² = x³ + ax + b   (mod p)

其中 a、b 是有限域 Fp 中的常数，且满足 4a³ + 27b² ≠ 0 (mod p)——这个条件保证曲线没有奇点（没有尖点或自交）。

为什么用这个方程？说白了，它满足「群结构」的要求。曲线上任意两点做「点加」运算，结果还在曲线上。这个性质是 ECC 能用于密码学的前提。

关键参数：

  • p：素数，决定有限域大小
  • a, b：曲线系数
  • G：基点（生成元），曲线上一个公开的点
  • n：基点 G 的阶（最小的 n 使得 nG = O，O 是无穷远点）
  • h：余因子（cofactor），通常为 1 或小整数

举个例子，比特币用的 secp256k1 曲线参数：

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
h = 1

你看，a=0，b=7，所以曲线方程就是 y² = x³ + 7。简单吧？但简单不代表不安全。

2.3 点加运算：ECC 的「加法」

点加是 ECC 最核心的运算。两个曲线上的点 P 和 Q，相加得到第三个点 R。

几何意义（在实数域上理解）：

  1. 过 P 和 Q 画一条直线
  2. 这条直线与曲线相交于第三个点 R'
  3. R' 关于 x 轴对称的点就是 R = P + Q

代数公式（在有限域 Fp 上）：

设 P = (x₁, y₁), Q = (x₂, y₂), P ≠ Q, P ≠ -Q

斜率 λ = (y₂ - y₁) / (x₂ - x₁)   (mod p)

x₃ = λ² - x₁ - x₂   (mod p)
y₃ = λ(x₁ - x₃) - y₁   (mod p)

如果 P = Q（点倍乘），斜率公式变成：

λ = (3x₁² + a) / (2y₁)   (mod p)

注意：除法在有限域里是乘以模逆元。比如 λ = (y₂ - y₁) * (x₂ - x₁)⁻¹ mod p。我见过不少新手直接写除法，结果跑出来全是错的。记住：有限域里没有「除法」这个操作，只有「乘以逆元」。

2.4 标量乘法：ECC 的「核心武器」

标量乘法就是 kP，其中 k 是一个整数，P 是曲线上的点。计算方法是重复点加：

kP = P + P + ... + P   (k 次)

但 k 可能是个 256 位的数，直接加 k 次要算到猴年马月。实际用的是 双倍-加算法（Double-and-Add）：

输入：k = (kₙ₋₁ ... k₁ k₀)₂, 点 P
输出：kP

Q = O (无穷远点)
for i from n-1 down to 0:
    Q = 2Q          // 点倍乘
    if kᵢ == 1:
        Q = Q + P   // 点加
return Q

这个算法的时间复杂度是 O(log k)，对于 256 位的 k，只需要 256 次点倍乘和平均 128 次点加。效率非常高。

个人经验：我在做嵌入式 ECC 实现时，发现双倍-加算法有个隐患——时间侧信道攻击。如果每次循环都判断 kᵢ 是否为 1，攻击者可以通过测量运算时间来推断 k 的比特位。后来我改用 Montgomery Ladder，运算时间恒定，才解决了这个问题。

2.5 知识体系总览

下面这张图把本章的核心逻辑串起来了。我建议你多看几遍，把每个模块之间的关系理清楚。

ECC 基础：有限域 → 曲线 → 点运算 有限域 Fₚ 椭圆曲线 y² = x³ + ax + b 点加 P + Q → R 标量乘法 kP 双倍-加算法 Montgomery Ladder 安全性：椭圆曲线离散对数问题 (ECDLP) 所有运算都在有限域 Fₚ 内进行，每一步都要模 p

2.6 为什么 ECC 比 RSA 更「省」？

这个问题我经常被问到。答案就在标量乘法里。

RSA 的安全性基于大整数分解，密钥长度需要 2048 位以上。ECC 的安全性基于 ECDLP，256 位的密钥就能提供同等安全强度。为什么？因为目前已知最好的 ECDLP 攻击算法（Pollard's rho）的复杂度是 O(√n)，而大整数分解的复杂度是亚指数级的。

安全等级 RSA 密钥长度 ECC 密钥长度 性能优势
80 位 1024 160 ECC 快 3-5 倍
128 位 3072 256 ECC 快 5-10 倍
256 位 15360 512 ECC 快 10-20 倍

一句话总结：ECC 用更短的密钥、更少的计算量，达到和 RSA 同等的安全强度。这就是它成为现代密码学主流的原因。

← 上一章 📖 返回目录 下一章 →