🏠 总目录📚 本教程 16 · 椭圆曲线 ← →
📑 本页目录（点开跳转）

16 · 椭圆曲线

⏱ 24 分钟 ｜ ⭐ 同样的安全，密钥小一个数量级

🎯 一句话

椭圆曲线做的事和 DH、RSA 完全一样， 但它换了一个"群" —— 而这个群里的离散对数问题难得多， 所以256 bit 就能达到 RSA 3072 bit 的安全强度。

PQ第三个交点P + Q在椭圆曲线上，「加法」是这样定义的① 连 P、Q 一条线② 找第三个交点③ 关于 x 轴翻过去⭐ 「乘法」就是把这个加法重复 k 次 —— 正着算很容易但已知 P 和 kP 反推 k，目前没有快速算法 —— 这就是 ECC 的安全根基同等安全强度下，ECC 的密钥比 RSA 短得多（256 位 ≈ RSA 3072 位）
连线 → 找第三个交点 → 关于 x 轴翻过去，这就是曲线上的「加法」。⭐ 把它重复 k 次很容易，但已知 P 和 kP 反推 k 目前没有快速算法 —— 这就是 ECC 的安全根基，也是它密钥能比 RSA 短得多的原因。

📈 一、曲线长什么样

$$y^2 = x^3 + ax + b \pmod p$$

xy实数域上的直觉图：曲线关于 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 的密钥，签名要几秒）。

实际收益：

关键信息

🛠️ 三、常用的曲线（以及选哪个）

曲线 用途 备注
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 章会用）

关键信息

🔗 和站内其他章的关系

相关的地方 和这一章的关系
第 15 章 DH ECDH 就是把群换成椭圆曲线 ⭐
第 13 章 群与阶 椭圆曲线点群
第 13 章 亚指数 vs 指数算法 ECC 密钥更小的根本原因
第 17 章 签名 ECDSA / Ed25519
第 22 章 云密码学 双线性配对的应用
第 23 章 后量子 ⚠️ Shor 算法同样摧毁 ECC
数学原理 · 核技巧 完全相同的抽象手法：核技巧把算法写成只依赖内积、再换掉内积；ECDH 把 DH 写成只依赖群运算、再换掉群 ⭐
数学原理 · 维度灾难 「亚指数 vs 指数」到底差多少？那一章用四个实测数字，把指数增长有多可怕演示了一遍

✅ 检查点

  1. 椭圆曲线上的"加法"是怎么定义的？
  2. ECDLP 是什么问题？为什么它比 Z*_p 上的 DLP 难？
  3. 128-bit 安全需要多长的 ECC 密钥？和 RSA 差多少倍？
  4. 为什么说"差距在拉大"？这对 RSA 意味着什么？
  5. Curve25519 的五个设计优点是什么？体现了什么设计哲学？
  6. NIST 曲线的争议是什么？
  7. 无效曲线攻击是怎么回事？怎么防？
  8. 双线性配对的性质是什么？它让什么成为可能？
  9. 椭圆曲线能抵抗量子计算机吗？
👀 答案
  1. 过 P、Q 画直线，找与曲线的第三个交点，再关于 x 轴翻转。这个定义让点集构成一个群（有单位元"无穷远点"、有逆元、满足结合律）。
  2. 给定 P 和 Q=kP 求 k。更难是因为 Z*_p 上存在亚指数算法（指数演算法、数域筛法，利用整数的因子分解结构），而椭圆曲线上目前只有指数级算法（Pollard's rho，约 √n），曲线上没有类似结构可利用。
  3. 256 bit，RSA 需要 3072 bit，差 12 倍。
  4. 因为安全级别越高差距越大：112-bit 差 9 倍，256-bit 差 30 倍（15360 vs 512）。意味着 RSA 在高安全级别基本不可用（15360 bit 密钥签名要几秒）。
  5. ①所有 32 字节串都是合法公钥（不需点验证）②Montgomery ladder 天然恒定时间 ③参数选择过程完全公开 ④结构性排除无效曲线和小子群攻击 ⑤不需处理无穷远点。哲学：好的密码学原语不只是"数学上安全"，还要"难以用错"。
  6. P-256 等曲线的参数由一个"随机种子"生成，但 NIST 从未解释那个种子从哪来。在 Dual_EC_DRBG 后门事件后，这个不透明性让很多人转向 Curve25519。目前无后门证据，但"无法验证"本身就是问题。
  7. 攻击者发一个不在曲线上的点，后续运算会泄露私钥信息。防御：必须验证收到的点确实在曲线上。曾影响 Java JCE、多个 TLS 实现、一批硬件钱包，根因是"收到公钥直接拿去运算，没验证合法性"。
  8. e(aP, bQ) = e(P,Q)^(ab)——指数可以"搬出来"。让BLS 签名聚合（一千个签名合成一个）、基于身份的加密（用邮箱当公钥）、属性基加密成为可能。
  9. 不能。Shor 算法同样摧毁 ECC——它解决离散对数和整数分解两类问题。

🛑 可以停在这里

⚡ 走神救援

⭐ 椭圆曲线做的事和之前那些一样，只是换了一个群。

⭐ 为什么它更划算：传统群上有亚指数级的攻击算法（能利用因子分解的结构），而椭圆曲线上目前只有指数级的——⭐ 于是同样的安全强度，密钥短一个数量级。⭐ 而且差距还在拉大：安全级别再往上，倍数还要翻几番——所以传统方案在高安全级别基本不可用了。

选型上首选那两条现代曲线，⚠️ 而广泛兼容的那条参数来源有争议（种子从哪来一直没有解释，加上后来的后门事件，很多人转向了前者）。

⭐⭐ Curve25519 受推崇的真正理由不是数学，是设计目标：让实现难以出错。 所有字节串都是合法公钥（不需要点验证）、标准算法天然是恒定时间、参数公开、结构上排除了几类攻击——⭐ 好的原语不只要数学上安全，还要难以用错。

特有的坑三条：💥 无效曲线攻击——⚠️ 收到一个不在曲线上的点会泄露私钥，所以必须验证（历史上影响过主流运行时、多个 TLS 实现和硬件钱包）；小子群攻击；💀 签名里那个一次性随机数重复或可预测就直接泄露私钥——⭐ 处方是确定性生成它，或者直接用内建了这一点的方案。

⭐ 最后一条通向别处：双线性配对能把指数搬出来，⭐ 正是它让签名聚合、基于身份的加密这些东西成为可能。

⚠️ 但量子计算同样摧毁它——短密钥不等于抗量子。

下一节 👉 17-数字签名.md

打卡记录保存在你的浏览器里，首页能看到总进度