📑 本页目录（点开跳转）
16 · 椭圆曲线
⏱ 24 分钟 ｜ ⭐ 同样的安全，密钥小一个数量级
🎯 一句话
椭圆曲线做的事和 DH、RSA 完全一样， 但它换了一个"群" —— 而这个群里的离散对数问题难得多， 所以256 bit 就能达到 RSA 3072 bit 的安全强度。
📈 一、曲线长什么样
$$y^2 = x^3 + ax + b \pmod p$$
实数上画出来是这样（帮助建立直觉）：
y
│ ╭──────
│ ╱
─────┼──╱─────────── x
│ ╲
│ ╰──────
⚠️ 但密码学里是在【有限域】上，
实际是一堆离散的点，没有"曲线"的样子
关键在于"点加法"这个运算：
两个点 P、Q 相加：
① 过 P、Q 画一条直线
② 找它和曲线的【第三个交点】
③ 关于 x 轴翻转 → 得到 P + Q
⭐ 这个定义看起来很随意，但它让点集构成了一个【群】：
有单位元（无穷远点 O）、有逆元、满足结合律
标量乘法：
kP = P + P + ... + P（k 次）
⭐ 用"倍点-加"算法（和快速幂一样的思路），O(log k) 次运算
🔒 二、ECDLP：为什么它更难
椭圆曲线离散对数问题（ECDLP）：
给定点 P 和 Q = kP，求 k
⭐ 关键区别：
在 Z*_p 上（RSA/DH）：
存在【亚指数】算法 —— 指数演算法、数域筛法
→ 因为整数有"因子分解"这种结构可以利用
在椭圆曲线上：
目前只有【指数级】算法 —— Pollard's rho，约 √n 次
→ 曲线上没有类似的结构可以利用 ⭐
直接后果：
| 安全级别 | RSA/DH | 椭圆曲线 | 差距 |
|---|---|---|---|
| 112 bit | 2048 | 224 | 9× |
| 128 bit | 3072 | 256 | 12× ⭐ |
| 192 bit | 7680 | 384 | 20× |
| 256 bit | 15360 | 512 | 30× ⭐ |
🔑 注意差距在拉大：安全级别越高，椭圆曲线的优势越明显。 RSA 在高安全级别上基本不可用了（15360 bit 的密钥，签名要几秒）。
实际收益：
├─ 密钥小 → 证书小 → TLS 握手少传几 KB
├─ 运算快 → 移动设备省电
├─ 签名短 → Ed25519 签名 64 字节，RSA-3072 签名 384 字节 ⭐
└─ 内存小 → 嵌入式设备能用
🛠️ 三、常用的曲线（以及选哪个）
| 曲线 | 用途 | 备注 |
|---|---|---|
| Curve25519 / X25519 | 密钥交换 | ⭐ 首选。设计上排除了大量实现坑 |
| Ed25519 | 签名 | ⭐ 首选。快、短、确定性签名 |
| P-256 / secp256r1 | 通用 | NIST 标准，兼容性最好，但参数来源有争议 |
| secp256k1 | 比特币/以太坊 | 特殊结构，签名验证可加速 |
| P-384 / P-521 | 高安全级别 | 政府/军用场景 |
💡 为什么 Curve25519 特别受推崇
它的设计目标是【让实现难以出错】：
✅ 所有 32 字节串都是合法公钥 → 不需要"点验证"
✅ 使用 Montgomery ladder → 天然恒定时间，抗计时攻击 ⭐
✅ 参数选择过程完全公开（"nothing up my sleeve"）
✅ 无效曲线攻击、小子群攻击被结构性地排除
✅ 不需要处理"无穷远点"这类特殊情况
🔑 这是一个重要的设计哲学： 好的密码学原语不只是"数学上安全"，还要"难以用错"。 🔗 这和第 7 章推荐 AES-GCM-SIV、 第 11 章推荐直接用 AEAD 是同一个思路。
⚠️ NIST 曲线的争议
P-256 等曲线的参数由一个"随机种子"生成，
但【那个种子从哪来的，NIST 从未解释】
→ 在 Dual_EC_DRBG 后门事件（2013 年 Snowden 文件确认）之后，
这个不透明性让很多人转向 Curve25519 ⭐
💡 目前没有证据表明 NIST 曲线有后门，
但"无法验证"本身就是一个问题
💥 四、椭圆曲线特有的坑
| 坑 | 说明 | 防御 |
|---|---|---|
| 无效曲线攻击 | 攻击者发一个不在曲线上的点，运算会泄露私钥信息 | 必须验证收到的点在曲线上 ⭐ |
| 小子群攻击 | 发一个阶很小的点，把私钥限制在小范围 | 检查点的阶 / 用 cofactor 清除 |
| ECDSA 的 k 值 | 重复或可预测 ⟹ 私钥直接泄露 💀 | 用 RFC 6979 确定性 k 或 Ed25519 |
| 点压缩的边界 | 解压缩时的实现错误 | 用成熟库 |
💥 无效曲线攻击是真实的：曾影响过 Java 的 JCE、 多个 TLS 实现、以及一批硬件钱包。 根因是"收到公钥就直接拿去运算，没验证它是否合法"。
💥 k 值泄露的经典案例（第 17 章会详细讲原理）： PlayStation 3 把 ECDSA 的 k 写成了常数 → 私钥被算出，主机被完全越狱。 多个比特币钱包因为随机数缺陷导致 k 重复 → 私钥被算出，钱被盗。
🔮 五、双线性配对（了解，第 22 章会用）
某些特殊曲线上存在一个"配对"运算：
e(aP, bQ) = e(P, Q)^(ab) ⭐ 指数可以"搬出来"
💡 这个性质让一些原本做不到的事成为可能：
├─ BLS 签名：签名可以【聚合】—— 一千个签名合成一个 ⭐
├─ 基于身份的加密（IBE）：直接用邮箱地址当公钥
└─ 属性基加密（ABE）：按属性策略解密（第 22 章）
⚠️ 代价：配对运算慢，且这些曲线的安全参数要求更高
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 15 章 DH | ECDH 就是把群换成椭圆曲线 ⭐ |
| 第 13 章 群与阶 | 椭圆曲线点群 |
| 第 13 章 亚指数 vs 指数算法 | ECC 密钥更小的根本原因 |
| 第 17 章 签名 | ECDSA / Ed25519 |
| 第 22 章 云密码学 | 双线性配对的应用 |
| 第 23 章 后量子 | ⚠️ Shor 算法同样摧毁 ECC |
| 数学原理 · 核技巧 | 完全相同的抽象手法：核技巧把算法写成只依赖内积、再换掉内积；ECDH 把 DH 写成只依赖群运算、再换掉群 ⭐ |
| 数学原理 · 维度灾难 | 「亚指数 vs 指数」到底差多少？那一章用四个实测数字，把指数增长有多可怕演示了一遍 |
✅ 检查点
- 椭圆曲线上的"加法"是怎么定义的？
- ECDLP 是什么问题？为什么它比 Z*_p 上的 DLP 难？
- 128-bit 安全需要多长的 ECC 密钥？和 RSA 差多少倍？
- 为什么说"差距在拉大"？这对 RSA 意味着什么？
- Curve25519 的五个设计优点是什么？体现了什么设计哲学？
- NIST 曲线的争议是什么？
- 无效曲线攻击是怎么回事？怎么防？
- 双线性配对的性质是什么？它让什么成为可能？
- 椭圆曲线能抵抗量子计算机吗？
👀 答案
- 过 P、Q 画直线，找与曲线的第三个交点，再关于 x 轴翻转。这个定义让点集构成一个群（有单位元"无穷远点"、有逆元、满足结合律）。
- 给定 P 和 Q=kP 求 k。更难是因为 Z*_p 上存在亚指数算法（指数演算法、数域筛法，利用整数的因子分解结构），而椭圆曲线上目前只有指数级算法（Pollard's rho，约 √n），曲线上没有类似结构可利用。
- 256 bit，RSA 需要 3072 bit，差 12 倍。
- 因为安全级别越高差距越大：112-bit 差 9 倍，256-bit 差 30 倍（15360 vs 512）。意味着 RSA 在高安全级别基本不可用（15360 bit 密钥签名要几秒）。
- ①所有 32 字节串都是合法公钥（不需点验证）②Montgomery ladder 天然恒定时间 ③参数选择过程完全公开 ④结构性排除无效曲线和小子群攻击 ⑤不需处理无穷远点。哲学：好的密码学原语不只是"数学上安全"，还要"难以用错"。
- P-256 等曲线的参数由一个"随机种子"生成，但 NIST 从未解释那个种子从哪来。在 Dual_EC_DRBG 后门事件后，这个不透明性让很多人转向 Curve25519。目前无后门证据，但"无法验证"本身就是问题。
- 攻击者发一个不在曲线上的点，后续运算会泄露私钥信息。防御：必须验证收到的点确实在曲线上。曾影响 Java JCE、多个 TLS 实现、一批硬件钱包，根因是"收到公钥直接拿去运算，没验证合法性"。
- e(aP, bQ) = e(P,Q)^(ab)——指数可以"搬出来"。让BLS 签名聚合（一千个签名合成一个）、基于身份的加密（用邮箱当公钥）、属性基加密成为可能。
- 不能。Shor 算法同样摧毁 ECC——它解决离散对数和整数分解两类问题。
🛑 可以停在这里
⚡ 走神救援
椭圆曲线做的事和 DH/RSA 一样，只是换了一个群。曲线 y²=x³+ax+b mod p，点加法=过两点画直线取第三交点再翻转（这让点集成为群）；标量乘 kP 用倍点-加，O(log k)。⭐ECDLP（给 P 和 Q=kP 求 k）比 Z*_p 上的 DLP 难，因为 Z*_p 有亚指数算法（数域筛法，利用因子分解结构），椭圆曲线目前只有指数级算法（Pollard's rho ≈ √n） → ⭐128-bit 安全只要 256 bit，RSA 要 3072（12×）；⭐差距还在拉大（256-bit 安全时 512 vs 15360 = 30×）→ RSA 在高安全级别基本不可用。收益：证书小、运算快、Ed25519 签名 64 字节 vs RSA-3072 的 384 字节。选型：X25519（密钥交换）/ Ed25519（签名）首选，P-256 兼容性最好但参数来源有争议（种子从哪来 NIST 从未解释，Dual_EC_DRBG 后门事件后很多人转向 Curve25519），secp256k1 用于比特币。⭐Curve25519 受推崇是因为设计目标是"让实现难以出错"：所有32字节串都是合法公钥（不需点验证）、Montgomery ladder 天然恒定时间、参数公开、结构性排除无效曲线和小子群攻击 → 好的原语不只要数学上安全，还要难以用错。特有的坑：💥无效曲线攻击（发一个不在曲线上的点会泄露私钥，⭐必须验证收到的点在曲线上；影响过 Java JCE、多个 TLS 实现、硬件钱包）、小子群攻击、💀ECDSA 的 k 重复或可预测 ⟹ 私钥直接泄露（PS3 把 k 写成常数被越狱；多个比特币钱包因此被盗）→ 用 RFC 6979 确定性 k 或 Ed25519。双线性配对 e(aP,bQ)=e(P,Q)^ab（指数能搬出来）让 BLS 签名聚合、基于身份的加密、ABE 成为可能。⚠️Shor 同样摧毁 ECC。
下一节 👉 17-数字签名.md