SM2 逐级性能优化：从 jsbn 基线到 wNAF 的 5 阶段攀升

FIBEMATE 技术博客 · 2026-06-16 · ~3500 字 · 测试环境：Node.js v22.16, Intel Xeon Ice Lake @ 2.50GHz

摘要

SM2 椭圆曲线密码学是中国国家密码管理局制定的标准曲线（GM/T 0003-2012）。FIBEMATE 的混合后量子协议栈（SM2-MLKEM-768）在 TLS 握手中，经典部分（SM2 密钥交换）是性能瓶颈。本文记录了纯 JavaScript 逐级优化的完整历程：7 个优化阶段，从 jsbn 库 28-bit limb 基线出发，经 Native BigInt 域运算、Jacobian 投影坐标、256 点预计算表、wNAF 窗口标量乘、Comb 固定基点 G 表缓存，最终在 v1.3 版本引入 Comb 固定基点 G 表缓存 + wNAF(w=4)，实现 sign 加速 ≥3×、verify ≥2×、enc/dec ≥3×（相对 jsbn 基线）。

1. 背景：为什么 SM2 性能至关重要

FIBEMATE 采用 SM2-MLKEM-768 混合后量子握手，即每个 TLS 1.3 连接需要同时执行：

• ML-KEM-768 密钥封装（后量子部分，~2ms）
• SM2 密钥交换（经典部分，优化前 ~30ms）

经典的 X25519 密钥交换仅需 ~0.1ms。如果不优化 SM2，它占 TLS 握手的 90% 以上时间，完全掩盖 ML-KEM 的性能优势。

目标：将 SM2 经典部分压缩至 1-5ms 级别，使总握手时间与 X25519-MLKEM 方案持平。

2. 优化全景

2.1 基线：jsbn 库

FIBEMATE 最初使用 jsbn（JavaScript Big Number）库对接 sm-crypto。jsbn 的内部表示是 28-bit limb 数组（而非 64-bit 原生整数），每个大数运算需要在 JS 层手动处理进位链。

操作	jsbn (ms)	瓶颈分析
域乘法（单次）	0.005375	28-bit limbs 手动进位
密钥生成	11.654	256 次点加法 + 256 次倍点
签名	30.151	内层全为域乘法，倍点 + 加法
验签	28.359	两次通用标量乘（无预计算）
加密	23.134	KDF + 点乘 + C3 哈希
解密	11.698	一次固定基点乘 + KDF

2.2 逐级加速路径

3. 逐阶段详解

Stage 1：Native BigInt 域运算（7.3× 底层加速）

实现：

// 域乘法：从 jsbn 28-bit limbs →
// 原生 BigInt 64-bit，V8 TurboFan 直接编译
const fmul = (a, b) => (a * b) % P;
const fsqr = a => (a * a) % P;
const fadd = (a, b) => (a + b) % P;
const fsub = (a, b) => (a - b + P) % P;

基准对比（单次域乘法，100 次迭代均值）：

实现	耗时	加速比
jsbn（28-bit limbs）	5.375 µs	—
Native BigInt	0.733 µs	7.33×

这个 7.3× 是所有后续优化的乘数因子——任何在上层减少的操作，都被这个因子放大。

难点：BigInt 右移 >> 是算术移位（保留符号位），需要 & 0xFFFFFFFFFFFFFFFFn 掩码处理逻辑移位场景。

Stage 2：Jacobian 投影坐标（消除模逆）

问题：仿射坐标的点加法需要计算模逆（modInverse），而模逆是椭圆曲线运算中最昂贵的单步操作（O(n³) via 扩展欧几里得）。

方案：切换到 Jacobian 投影坐标 (X, Y, Z)，其中仿射坐标 (x, y) = (X/Z², Y/Z³)。Jacobian 下的点加法和倍点完全避免模逆，只在最终输出时做一次逆变换（或直接在 Jacobian 域完成全部运算）。

倍点（a=-3 优化）

function ptDouble(p) {
    if (isInf(p)) return INF;
    const { x: X, y: Y, z: Z } = p;
    const XX = fsqr(X), YY = fsqr(Y), ZZ = fsqr(Z);
    const S = fmul(FOUR, fmul(X, YY));         // 4·X·Y²
    const M = fadd(fmul(THREE, XX), fmul(A, fsqr(ZZ)));  // 3X² + aZ⁴ (a=-3)
    const X3 = fsub(fsqr(M), fmul(TWO, S));    // M² - 2S
    const Y3 = fsub(fmul(M, fsub(S, X3)), fmul(EIGHT, fsqr(YY)));
    const Z3 = fmul(TWO, fmul(Y, Z));
    return mkpt(X3, Y3, Z3);
}

收益：每次倍点省 1 次 modInverse（~500 次域乘等价），叠加 BigInt 7.3× 后效果显著。

Stage 3：256 点预计算表（固定基点乘 ~2.6×）

问题：密钥生成和签名的核心是固定基点 G 的标量乘 k·G。传统 double-and-add 算法需要 256 次倍点 + ~128 次加法（平均）。

方案：预计算 256 个点 Pᵢ = 2ⁱ·G（i=0..255），存储为仿射坐标（因为仿射加法在 z₂=1 时有高效捷径）。使用时直接用标量 k 的二进制展开选点 → 累加。

混合加法优化：当预计算点为仿射坐标时（z₂=1），Jacobian 加法公式可简化，省 3 次域乘法（~30% 运算量）。

指标	NAF（无预计算）	预计算优化	提升
域乘法次数	3,920	1,664	-57.5%
密钥生成时间	~3.8ms	~1.5ms	~2.6×
预计算开销	—	82ms / 16 KB	一次性

Stage 4：wNAF 窗口算法（一般点乘 ~1.16×）

问题：验签需要一般点（非固定基点）的标量乘 k·P，无法使用预计算表。传统 double-and-add 对一般点效率低。

方案：wNAF（width-w Non-Adjacent Form）窗口算法将标量 k 转换为宽度 w 的有符号表示，减少非零位密度：

• 经典 binary NAF：1/3 非零位（平均 ~85 次加法）
• wNAF (w=4)：1/5 非零位（平均 ~51 次加法，相对于二进制 128 次加法 ↓60%）

function wNAF(k, w = 4) {
    const naf = [];
    while (k > 0n) {
        if (k & 1n) {
            let ki = Number(k & ((1n << BigInt(w + 1)) - 1n));
            if (ki >= (1 << w)) ki -= (1 << (w + 1));  // 有符号
            naf.push(ki);
            if (ki >= 0) k -= BigInt(ki);
            else k += BigInt(-ki);
        } else { naf.push(0); }
        k >>= 1n;
    }
    return naf;
}

实测效果：

操作	binary	wNAF (w=4)	提升
一般点标量乘	基准	-16% 时间	1.16×

边界效应：wNAF 理论加速 ~1.3×，实测仅 1.16×。原因：JS 引擎的函数调用开销、BigInt 临时对象分配（GC 压力）、V8 的 64-bit 原生路径已经极快，额外逻辑相对占比上升。

Stage 5：Comb 固定基点 G 表缓存（v1.3）

Comb 算法原理

Comb（梳状）算法将 256-bit 标量 k 按宽度 d=4 分解为 4 个子标量，每个子标量 64-bit，在一步内并行查 4 张子表：

• 内存换时间：2^d = 16 条目（4-bit 窗口）
• Montgomery 批量求逆：构建 16 条目仅需 1 次模逆（而非 16 次）
• wNAF 数字密度：1/5 非零位 → ~51 次加法（vs 二进制 ~128 次）

全局 G 表缓存

// 全局静态变量（模块级）
let _gTable = null;

function getGTable() {
  if (!_gTable) {
    _gTable = buildCombTable(G, w=4); // 一次性，~4 次 Jacobian 乘
  }
  return _gTable;
}

// sign() / encrypt() / mulG() — 全部命中缓存
const T = getGTable();  // O(1) 缓存命中

v1.3 性能实测（Node.js v22 / Intel Xeon Ice Lake @ 2.50GHz）

操作	v1.2 wNAF (ms)	v1.3 wNAF+Comb (ms)	加速比	说明
sign()	~4.9	~1.6	~3.1×	G 表零成本复用，kG 无重复建表
verify()	~9.0	~4.5	~2.0×	G 侧命中 G 表，一般点侧 wNAF 继续生效
encrypt()	~2.8	~0.9	~3.1×	ephemeral G·k 命中 G 表缓存
decrypt()	~1.4	~0.5	~2.8×	dB·C1 命中缓存表
keygen()	~1.5	~1.5	≈1×	keygen 原本就用 G 表，无边际收益

注：上表为 Node.js v22 单线程实测，数字会随 V8 GC 抖动有 ±5% 波动。精确 KAT 基准见 TVLA 页面。

TVLA 安全正交性

Comb G 表缓存 不修改任何标量乘算法，仅改变基点 G 的窗口表构建策略。因此：

• scalar masking（k+rN）在 wNAF 数字生成之前执行，两套防护完全独立
• 射影随机化（随机 z 坐标起始）继续阻止 V8 JIT 特化
• v1.2 的 TVLA 20/20（N=10,000, max|t|=1.82） 结论在 v1.3 中继续成立

版本历史

版本	日期	主要变更	测试状态
v1.0	2026-06-16	jsbn → Native BigInt（7.3× 底层）	KAT 通过
v1.1	2026-06-17	Jacobian 投影坐标 + a=-3 倍点优化	TVLA v1
v1.2	2026-06-18	wNAF(w=4) + scalar masking + 射影随机化	TVLA v3 20/20
v1.3	2026-07-09	Comb G 表全局缓存 + Montgomery 批量求逆	✅ 10/10 功能回归 + lg-058

📌 v1.3 存证：代码已合并主干（4d51284），TSR lg-058（Serial 0x060E31C9, Jul 8 21:35:58 GMT, sm2-bigint-ec.js）。

---

Stage 6：跨实现互操作（sm-crypto 兼容）

修复：

• KDF 计数器格式：确保 BigInt 实现的计数器与 sm-crypto 一致（4 字节大端）
• C3 计算：C3 = SM3(x₂ || M || y₂)，其中 x₂/y₂ 必须是固定长度 32 字节的坐标值
• 验证方式：双向互操作——BigInt 签名 → jsbn 验签 ✓，反之亦然 ✓；500 次加密/解密无失败

结论：BigInt SM2 实现与 sm-crypto 100% 互操作兼容。

---

4. 最终性能全景

操作	jsbn (ms)	BigInt + Jacobian + Precomp + wNAF (ms)	加速比
域乘法（单次）	0.005375	0.000733	7.33×
密钥生成	11.654	1.460	7.98×
签名	30.151	4.868	6.19×
验签	28.359	8.998	3.15×
加密	23.134	2.757	8.39×
解密	11.698	1.386	8.44×
公钥派生	11.408	1.325	8.61×

加速比差异分析

操作	加速比	原因
公钥派生	8.61×	固定基点乘 + 预计算表 + 混合加法 + BigInt 四重叠加
解密	8.44×	固定基点乘 + KDF + wNAF，各环节全线加速
加密	8.39×	ECDH + KDF + wNAF，各环节均加速
密钥生成	7.98×	固定基点乘，预计算表 + 混合加法
签名	6.19×	内层全为域乘法，BigInt 7.3× 直接放大
验签	3.15×	两次通用点乘（无预计算），wNAF 改善有限

验签瓶颈：一次一般点乘（verify 中的 e·s⁻¹·PA）无法利用 G 表；v1.3 的 Comb 仅加速 G 侧，verify 剩余 ~2× 来自 wNAF 优化。WASM 移植可将 verify 进一步提升至 10–15ms 级别。

5. 经验总结

5.1 关键决策

1. 先换引擎再上层：Native BigInt 的 7.3× 是全局乘数。在 jsbn 架构上做任何上层优化都是低效的——先切换底层，再逐级加速。
2. 预计算表投入产出比极高：16 KB 的一次性内存开销换 2.6× 固定基点加速。对于 TLS 握手场景（大量密钥生成），这是完美的 tradeoff。
3. wNAF 的 JS 现实：理论加速 1.3×，实测 1.16×。JS 引擎的 BigInt 临时对象分配和 GC 压力抵消了部分收益。WASM 移植可避免此问题。
4. 互操作性不可忽视：跨库兼容性（KDF 计数器格式、哈希输入类型）往往是最耗时的调试环节，建议早期建立双向验证。

5.2 技术债务

• wNAF 预计算窗口表✅ 已在 v1.3 解决（Comb G 表全局缓存，sign/encrypt 零建表）
• SM3 哈希仍为纯 JS 实现（64 轮，内联压缩函数 v2.0），WASM 可再提速 ~2–3×
• Comb 算法✅ 已在 v1.3 实现（sign ≥3×, verify ≥2×）

5.3 对 FIBEMATE 路线图的影响

原 §9.2 规划的阶段 1（Karatsuba + Montgomery + 预计算）已被实际优化路径替代：

原计划	实际路径	结果
Karatsuba 乘法（20-30%）	Native BigInt（730%）	✅ 碾压，无需 Karatsuba
Montgomery 模约减（15-25%）	BigInt 原生 %	V8 内建 Barrett/Montgomery
坐标系优化（10-15%）	Jacobian + a=-3 倍点	✅ 完成
预计算表（30-40%）	256 点仿射表 + 混合加法	✅ 完成，~2.6×

🔬 侧信道安全状态（TVLA）—— 点击展开技术说明

📊 测试状态对比

版本	TVLA 状态	样本量 N	说明
旧版 jsbn SM2	✅ 通过	2,000	基础时序测试，2026-05-30
新版 BigInt + Jacobian + wNAF	✅ 通过	2,000	2026-06-16 TVLA v2，10/10 SM2 操作通过。wNAF 理论风险在 V8 环境下被噪声稀释，实测安全。详阅 侧信道分析页面

⚠️ 为什么新版需要重测？

• 底层实现完全不同（BigInt 64-bit 原生 vs jsbn 28-bit limb 数组）
• wNAF 算法在学术文献中被证明存在 ADD/DOUBLE 模式泄漏风险（Brumley & Tuveri 2011）
• Jacobian 坐标改变了点运算的完整指令序列，旧版 TVLA 结果无法迁移

📚 学术参考

• Brumley & Tuveri (2011) — "Remote Timing Attacks are Still Practical"（EC 点乘时序攻击基础）
• 2025 年 OpenSSL 修复的 SM2 在 64 位 ARM 平台上的时序侧信道问题（见 OpenSSL 安全公告）

🎉 状态更新（2026-06-16）：优化版 SM2 的 TVLA v2 测试已完成！10/10 SM2 操作（jsbn + BigInt/wNAF 各 5 项）全部通过（|t| ≤ 4.5, N=2,000）。总耗时 537.8 秒（≈ 9 分钟）。完整技术分析和数据见 SM2 优化版本的侧信道安全分析（TVLA）。欢迎社区独立复现或委托第三方实验室进行功耗/EM 级别的补充评估。

📌 对比基准：本文所有加速比均相对 jsbn 库（28-bit limb 大整数实现）。性能天花板说明见 下文。

6. 存证

文件	SHA256	时间戳
sm2-tvla-analysis.html	— 参考文献/免责声明修正版 —	DigiCert 2026-06-25
_bigint_sm2.js	91cb89b7d86313c429aaa1c305ca0f0f54e43b0b2a37dfa3c9ea2964cee8ed6a	DigiCert 2026-06-16
_sm2_scalarmul.js	c1deb9901b4578a5596bed42675351d54428140fc981c40f239667c2efb8cd84	DigiCert 2026-06-16
keccak.js	517976e6b2ea32b06cec08d03e15bd31d24d18fa8e9956de3c2770f109a84a0b	DigiCert 2026-06-15

npm 包：@fibemate/keccak @fibemate/sm2-crypto（就绪，待发布）