椭圆曲线加密

ELLIPTIC CURVE CRYPTOGRAPHY // 最短的钥匙

> 一条长得不像椭圆的三次曲线 y² = x³ + ax + b，撑起了今天半个互联网的钥匙：HTTPS 握手、Signal、iMessage、SSH、比特币签名、中国国密 SM2——全在它上面跑。它凭什么取代 RSA？因为两块"难"不一样：RSA 赖以生存的大数分解存在亚指数算法，而椭圆曲线离散对数（ECDLP）已知的最好算法只有指数级——于是 256 位 ECC ≈ 3072 位 RSA：钥匙短 12 倍、握手快、证书小。1985 年 Miller 与 Koblitz 各自独立想到把这条曲线搬进密码学，四十年后它成了公钥世界的默认地基——但它的标准常数也曾被 NSA 塞进后门。数学越强，越要盯住人。

SUBJECT: 密码学 · 数论应用 FILE: cards/elliptic-curve-cryptography SINCE: 1985 独立提出 / 2005 Suite B BUILD v1.0

Principle — 原理与来源

椭圆曲线加密 ECC // 难题换短钥

正着算一分钟，反着算一万年

y² = x³ + ax + b (mod p)　·　kG = 公钥，k = 私钥

由 G 算 kG 是线性次的加法；由 kG 反推 k 是 ECDLP——已知最好算法 ~√n 步。

核心机制：在素数域 p 上的椭圆曲线点集构成一个循环群。取基点 G，私钥是随机整数 k，公钥是"点加法"的 kG（G 自加 k-1 次）。正向计算是多项式时间；反向（由 kG 求 k，即椭圆曲线离散对数问题 ECDLP）已知最好算法（Pollard ρ）约 √n 步——纯指数级。对比 RSA：整数分解有亚指数的数域筛法（GNFS），所以 RSA 必须用很长的模数才能撑住同等强度。

人物：Victor Miller（IBM，1985 年 CRYPTO 会议提出，论文 1986 收入论文集）与 Neal Koblitz（华盛顿大学，论文 1987 年刊于 Mathematics of Computation）相互独立提出用椭圆曲线做密码——两人 2021 年共获 Levchin 奖。思想源头是 Diffie–Hellman 1976 开创公钥密码后，学界四处寻找"离散对数难题"的新宿主，椭圆曲线（数论古董，19 世纪以来研究椭圆积分时出现）恰好合适。

工程胜利：2005 年 NSA 发布 Suite B，把 P-256/P-384 曲线列为政府机密数据首选，RSA 最低模数抬到 3072 位——ECC 正式登基。今天：TLS 1.3 默认 ECDHE 密钥交换、ECDSA 证书；比特币/以太坊用 SECG 的 secp256k1（y²=x³+7）；中国国密 SM2（GM/T 0003-2012，2010 年 12 月首发，GB/T 32918 上升为国标，签名引入用户 ID 参与）用于金融与政务，RFC 8998 把 SM2 带进 TLS 1.3。

暗面（必须讲）：椭圆曲线的常数可以藏后门——NIST 2006 年标准化的随机数生成器 Dual_EC_DRBG，其常数 P、Q 满足 Q = P·e，握有 e 的人可预测全部输出。2007 年 Shumow & Ferguson 揭示可能性、Schneier 公开警告，2013 年斯诺登文件与 RSA 公司收 NSA 1,000 万美元将 Dual_EC 设为 BSAFE 默认的合同曝光坐实。NIST 2014 年正式撤回。此后业界信条：常数来源不可解释的曲线不碰。

① 名字是历史事故：椭圆曲线与椭圆无关——名字来自 19 世纪计算椭圆周长的积分（椭圆积分），曲线本身是三次平面代数曲线，画出来也不像椭圆；它不是椭圆的方程。 ② ECC 不是"更难破解的 RSA"：两者依赖不同难题（ECDLP vs 整数分解），ECC 的优势是同等安全下更短的钥（256 位 ECC ≈ 3072 位 RSA），即性能与带宽，而非绝对强度。 ③ Miller 与 Koblitz 是独立提出，非合作——1985 年各自独立，论文 1986/1987 先后发表；"1985 Koblitz 提出"是常见简写，Miller 的会议报告在先。 ④ 曲线参数不能随便生成——Dual_EC_DRBG 事件（2007 发现、2013 坐实、2014 撤回）教训：无来源说明的常数 = 潜在后门；可信曲线要么常数极简可验证（secp256k1 的 b=7），要么生成过程透明可复现。 ⑤ 量子计算是 RSA 与 ECC 的共同终点——Shor 算法对整数分解与 ECDLP 都是多项式时间，"ECC 更抗量子"是讹传；NSA 2015 年宣布弃用 Suite B 转 CNSA/后量子路线，正是为此。今天的应对是先抓后解不适用于前向保密会话，但长期机密必须考虑迁移。 ⑥ "比特币用的曲线是 NIST 的"不准——secp256k1 由民间标准组织 SECG 定义（非 NIST 系），中本聪选它常被解读为有意避开 NIST 常数疑云；它恰好也是 Dual_EC 事件后社区信任度较高的曲线之一。

Apply — 用在哪里

TLS/HTTPS你每次开锁的一次 ECDHE：双方各持临时私钥做椭圆曲线 Diffie-Hellman，协商出会话密钥——前向保密的来源（会话钥用完即弃，日后私钥泄露也解不了旧流量）。

数字签名ECDSA / SM2 / EdDSA：签名快、证书小（ECDSA P-256 证书比 RSA-2048 小 1–2KB）——移动端与 IoT 的电量与带宽直接受益；比特币每笔交易签名也是它。

国密合规中国金融、政务、电子证书领域走 SM2 全家桶（签名/加密/密钥交换三件套）——国内系统的 TLS 国密改造（TLCP/GMSSL）、UKey、电子签章的底层都是这条 sm2p256v1 曲线。

端到端加密Signal 协议（WhatsApp/Signal 本体）、Apple iMessage 用 X25519（另一族椭圆曲线，Curve25519，常数极简、实现难出错）做身份与密钥协商——现代 E2E 的事实标准基石。

架构启示选曲线如选依赖：用广泛审计的标准曲线（P-256/secp256k1/Curve25519），别自造曲线；"自己造的密码学"是安全事故的头号来源——ECC 的强大以正确使用它为前提。

Simulate — 有限域点运算实验室 × 密钥尺寸天文台

双视角实验室 // 在 mod 23 的小曲线上亲手算 ECDLP 有多"难"；滑安全位数看钥匙差多少

视角 A：教学曲线 y²=x³+x+1 (mod 23)——看点加法、标量乘法与"反推有多难"；视角 B：滑安全强度，对比 RSA 与 ECC 的钥匙长度、以及量子时代的共同命运

标量 k（计算 kG）：7

曲线上全部点（mod 23）当前 kG │ G 为基点

—

Personal Takeaways — 个人启示 · 03

安全强度是"难题强度"，不是"位数长度"

ECC 用 256 位达到 RSA 3072 位的效果，因为两道难题的最好算法复杂度不同。评估任何安全方案先问：它依赖的难题，已知最好攻击是什么复杂度——位数只是这道题的参数，不是强度本身。

可解释的常数是信任的最低门槛

Dual_EC_DRBG 的教训超越密码学：任何"来源不明的魔法常数"（模型参数、种子、默认配置）都是潜在后门。审查依赖与方案时，先问常数怎么来的、能否独立复现——答不上来的，按可疑处理。

向前看半步：量子和迁移

Shor 算法面前 ECC 与 RSA 同归于尽——这不是恐慌理由，是架构预算理由：长期机密的数据今天就要考虑后量子混合（TLS 已支持 X25519+ML-KEM）；短期会话靠前向保密续命。密码学的生命周期管理，从"选个算法"变成了"排迁移路线"。