4.4 椭圆曲线密码学：以短胜长

4.4 椭圆曲线密码学：以短胜长

本节摘要：椭圆曲线密码学（ECC）把离散对数问题从乘法群搬到椭圆曲线的点群上，由于一般曲线上不存在亚指数级的求解算法，它用 256 位密钥就能达到 RSA 3072 位的等效强度。本节讲清点加法与标量乘法的几何规则、ECDLP 的难在哪、256 位对 3072 位的等效账怎么算，以及 Curve25519 何以成为 TLS 1.3 时代的新默认。

把离散对数搬上一条曲线

1985 年，华盛顿大学的 Koblitz 与 IBM 的 Miller 相互独立地提出同一个念头：椭圆曲线上定义一种"加法"，让曲线的点构成一个群，再把离散对数问题整个搬进来。这里的"椭圆曲线"是形如 y² = x³ + ax + b（模一个大素数 p）的三次曲线，取遍所有满足方程的整数点，再添一个"无穷远点"充当单位元，就得到一个有限的交换群。

"加法"的几何规则是弦切法：过两点 P、Q 作直线，该直线与曲线的第三个交点取反，就定义为 P+Q。同点相加则用切线。工程上反复运算的是标量乘法：nP = P + P + … + P（n 次），可用倍加算法在多项式时间内完成。于是单向性登场：已知 P 与 n，算 Q = nP 飞快；已知 P 与 Q，反推 n——这就是椭圆曲线离散对数问题（ECDLP）。

用一条小曲线亲手做一次点加法（p=17、a=2、b=2，生成元 P=(5,1)）：

# 迷你椭圆曲线 y 平方 = x 立方 + 2x + 2 (mod 17)，仅供理解运算规则
p, a, b = 17, 2, 2
INF = None                                    # 无穷远点：群的单位元

def add(P, Q):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return INF                            # 两点互逆，和为单位元
    if P == Q:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p   # 切线斜率
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p          # 割线斜率
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

P = (5, 1)
Q = add(P, P)                                  # 2P
print(Q)                                       # -> (6, 3)
print(add(P, Q), add(add(P, P), P))            # 3P 两种算法结果一致
​

二、以短胜长的账本

ECC 的核心优势来自一个纯数学事实：对付有限域乘法群上的离散对数，攻击者手握指数级加速的"指数演算"（index calculus）类算法，所以 RSA 与有限域 DH 必须用 2048 位起步的大数抵消它；而一般椭圆曲线上至今没有找到可比拟的亚指数算法，攻击基本退回到对数级的暴力（生日攻击量级）。难度曲线从"亚指数"换成"指数"，密钥长度立刻压下来一整个数量级。

NIST 的安全强度分级给出精确的等效对照：

256 位 ECC ≈ 3072 位 RSA这行是现代工程的默认配置：密钥与证书体积缩小一个量级，握手少传几 KB，手机与物联网设备的运算时间低两位数毫秒即可完成。RSA 在移动端的位宽与功耗劣势，正是 ECC 十年间完成替代的经济学原因。

图：同等安全强度下的密钥长度对比

三、Curve25519：新一代的默认答案

椭圆曲线安全性的坑不在数学，在选曲线：参数经不起暗箱操纵的曲线可能藏着攻击者预知的弱点（2013 年的双椭圆曲线随机数后门疑云给全行业上了一课）。丹·伯恩斯坦 2006 年发布的 Curve25519 用完全"可解释"的方式构造参数——素数取 2²⁵⁵−19、系数取尽可能小的满足抗攻击保守值的数字——堵住"为什么是这些参数"的质疑。配套的两件套已成事实标准：X25519（基于该曲线的 ECDH 密钥协商）与 Ed25519（EdDSA 签名，见下一节）。TLS 1.3 的密钥交换中 X25519 已超越 P-256 成为最常用组；Signal 协议、SSH、WireGuard、比特币的隔离见证全部采用曲线家族。

工程侧还有两条纪律：其一，点校验必须做——不验证对端公钥是否真在曲线上，会招致"无效曲线攻击"把私钥一步步榨出来；其二，标量乘法必须恒定时间实现，否则模逆的时序抖动就是 7.2 节侧信道的活靶子。这些纪律已经被成熟库（libsodium 等）内化，再次印证那条工程铁律：用审计过的库，别手搓。

💡 关键直觉：ECC 的短钥不是"更高效的 RSA"，而是换了一道更难翻越的数学墙——RSA 的墙（大数分解）对亚指数攻击缴械，曲线的墙（ECDLP）暂时只有指数级梯子。墙的形状决定墙的高度需要多少块砖。

两个问答

问：既然 256 位够了，能不能再砍到 128 位求更快？不能。128 位强度的曲线会把安全边际压进生日攻击与未来分析的同温层，标准曲线的位宽都留了约一倍的余量——安全参数不做极限压榨，这与 3.2 节 DES 的教训是同一笔账。

问：项目里选 P-256 还是 Curve25519？合规优先（部分认证体系只认 NIST 曲线）选前者；工程优先（实现更抗侧信道、参数更透明）选后者。两者都是当前安全的选择，关键是不要自造曲线。

本节要点回顾

• 曲线群：y² = x³ + ax + b 的点在弦切法加法下成群，标量乘法 nP 提供单向性，反演即 ECDLP；
• 等效账本：256 位 ECC ≈ 3072 位 RSA ≈ 128 位对称强度；384 位 ≈ 7680 位；一般曲线无亚指数攻击是短钥的数学根源；
• Curve25519 家族：参数可解释、抗侧信道，X25519 协商与 Ed25519 签名成为 TLS 1.3 与现代协议默认；
• 工程纪律：公钥点必须做曲线校验、实现必须恒定时间、实现交给成熟密码库。

曲线把"协商"做短做快了，签名这半边同样有戏。下一节看数字签名的完整闭环：不可否认性从哪来，ECDSA 的随机数又为什么能让人一夜丢掉全部私钥。