Botan库椭圆曲线签名算法深度实现解析

Botan作为业界功能最全面的密码学库之一，其椭圆曲线签名模块涵盖了从国际通用标准到各国特有标准的多层次算法体系。本文将从底层算术实现、各算法核心差异和具体工程实现三个维度，深入剖析Botan库中ECDSA、Ed25519、Ed448、ECGDSA、ECKCDSA、SM2、GOST 34.10这七种椭圆曲线签名算法的实现细节。

一、Botan椭圆曲线基础设施：统一的底层运算层

1.1 核心数据类型

Botan将所有椭圆曲线运算抽象为两个基础类：EC_Scalar（标量）和EC_AffinePoint（仿射点），两者共同构成了上层签名算法的”积木”。

EC_Scalar 表示一个位于 [0, n) 范围内的椭圆曲线标量，其中 n 为基点的阶。其关键操作包括：

  • 随机生成：EC_Scalar::random() 返回非零随机标量，为ECDSA、ECGDSA、ECKCDSA等算法的nonce生成提供支持
  • 序列化与反序列化：deserialize() 要求字节串严格等于群阶长度，拒绝前导零截断；from_bytes_with_trunc() 则实现ECDSA特有的哈希截断规则
  • 模运算：invert() 计算乘法逆元，保证常数时间执行；negate() 计算加法逆元
  • 模阶乘加与乘加：add_mod_order() 和 mul_mod_order() 分别执行 (a + b) mod n 和 (a · b) mod n 运算

EC_AffinePoint 表示曲线上的一个点，包含无穷远点 O。其核心功能包括：

  • 点乘运算：mul() 实现变基点标量乘法，常数时间执行；g_mul() 利用固定基点预计算表加速；mul_px_qy() 实现双标量乘法 p·x + q·y，专门用于签名验证
  • 点序列化：支持SEC1压缩格式（serialize_compressed_to）和非压缩格式（serialize_uncompressed_to），覆盖不同算法的编码需求
  • 坐标获取：get_affine_x() 和 get_affine_y() 返回仿射坐标的模数值

1.2 加速结构：预计算表

Botan提供 EC_Group::Mul2Table 类，专门优化双标量乘法的验证场景。该类对公钥点 h 建立预计算表，用于快速计算 g·x + h·y。其 mul2_vartime_x_mod_order_eq 方法可直接提取结果点的x坐标并与期望值比较，避免完整的点到仿射坐标转换，大幅提升验证性能。该方法的”vartime”标识意味着它允许在执行时间上泄露 x 和 y 的值，因为验证过程不涉及私密数据，这种优化是安全且高效的。

1.3 曲线群对象 EC_Group

EC_Group 是Botan中管理曲线参数的核心类，封装了：

  • 曲线方程系数 a、b 和模数 p
  • 基点 G 及其阶 n
  • 余因子 h
  • OID（对象标识符），用于在ASN.1编码中唯一标识曲线
  • PEM编码的曲线参数导入导出功能

所有上层签名算法通过 EC_Group 获取曲线参数并创建 EC_Scalar 和 EC_AffinePoint 实例，从而实现了算法实现与具体曲线的解耦。

二、ECDSA：经典实现与底层接口

2.1 签名生成流程

ECDSA签名生成在Botan中通过高层API调用底层 EC_Scalar 和 EC_AffinePoint 完成。核心步骤为：

第一步：哈希映射
对消息 M 计算 z = HASH(M) mod n，使用 EC_Scalar::from_bytes_with_trunc 实现哈希截断规则。该函数会截取哈希值最左侧的 log2(n) 位，若截取值大于等于 n，则减去 n 进行模约减。

第二步：临时密钥生成
调用 EC_Scalar::random(group, rng) 获取非零的临时密钥 k。Botan内部会确保 k 在 [1, n-1] 范围内均匀随机选取，并自动拒绝 k = 0 的情况。

第三步：计算 R = k·G
使用 EC_AffinePoint::g_mul(scalar, rng) 执行固定基点标量乘法。由于基点 G 是固定的，Botan内部维护了 G 的预计算表，将点乘运算的复杂度从 O(log k) 的逐次点加优化为窗口法，显著提升签名速度。

第四步：计算 r = x_R mod n
调用 EC_Scalar::gk_x_mod_order(k, rng) 直接返回结果点的x坐标模阶后的值。该方法避免了完整点的序列化开销，仅提取所需数据。若 r = 0，则重新从第二步开始。

第五步：计算 s = k⁻¹ · (z + r·d) mod n
首先使用 EC_Scalar::invert() 计算 k 的模逆元，然后通过 EC_Group::multiply_mod_order() 执行模乘和模加运算。若 s = 0，则重新从第二步开始。

最终签名输出为 (r, s) 对，序列化格式依据上层调用者的需求，可能是固定64字节的 r || s 拼接格式，也可能是ASN.1 DER编码格式。

2.2 验证流程优化

验证需要计算 P = u₁·G + u₂·Q，其中 u₁ = z·s⁻¹ mod n，u₂ = r·s⁻¹ mod n。Botan使用 Mul2Table::mul2_vartime_x_mod_order_eq 方法执行验证：

第一步：验证签名格式，确保 r, s ∈ [1, n-1]，否则直接拒绝

第二步：计算哈希值 z = HASH(M) mod n

第三步：计算 s 的模逆元 s_inv = s⁻¹ mod n

第四步：计算 u₁ = z · s_inv mod n，u₂ = r · s_inv mod n

第五步：调用 mul2_vartime_x_mod_order_eq 计算双标量乘法并提取x坐标

第六步：比较计算结果与签名中的 r 值，相等则接受，否则拒绝

该实现的关键优化在于：公钥点 Q 被预先转换为 Mul2Table 所需的查表格式，在验证多条签名时可复用同一个预计算表，大幅提升批量验证场景的性能。

2.3 RFC 6979 确定性 ECDSA 支持

Botan额外实现了 RFC 6979 标准，即确定性 ECDSA 签名生成。该标准通过 HMAC 派生机制，将消息哈希与私钥结合生成临时密钥 k，完全替代了随机数生成器：

k = HMAC_K(私钥) (消息哈希 || 计数器)

这种实现从根本上消除了因随机数生成器质量不佳导致的私钥泄露风险，是生产环境中推荐使用的模式。Botan通过 ECDSA_Deterministic_Signature_Generator 类提供此功能。

三、Ed25519与Ed448：确定性签名的底层差异

3.1 Edwards曲线的独特算术

Ed25519和Ed448基于扭曲爱德华曲线（Twisted Edwards），其方程形式为：

-a·x² + y² = 1 + d·x²·y²

其中 Ed25519 使用 a = -1，而 Ed448 使用 a = 1。这种曲线形式具有一个极其重要的性质：统一加法公式，即同一个公式可以处理点的加法、倍点和无穷远点：

(x₁, y₁) + (x₂, y₂) = (
    (x₁·y₂ + y₁·x₂) / (1 + d·x₁·x₂·y₁·y₂),
    (y₁·y₂ - a·x₁·x₂) / (1 - d·x₁·x₂·y₁·y₂)
)

由于不存在特殊分支条件，该公式天然抵抗时序侧信道攻击，无需像Weierstrass曲线那样手动实现恒定时间逻辑。

Botan内部实现与Weierstrass曲线完全不同：

  • 点表示：使用Edwards曲线的仿射坐标 (x, y)，而非Jacobian投影坐标
  • 点乘算法：利用Edwards曲线的固定基点预计算，使用窗口法（window method）加速，窗口大小通常为 4 或 5
  • 模算术：使用专门针对 p = 2²⁵⁵ – 19（Ed25519）和 p = 2⁴⁴⁸ – 2²²⁴ – 1（Ed448）优化的模乘和模约减算法

3.2 确定性随机数生成

EdDSA签名的核心是确定性nonce生成，完全无需随机数生成器。根据RFC 8032第5.1.6节（Ed25519）和第5.2.6节（Ed448），临时密钥 k 的计算过程为：

对于Ed25519：

h = SHA-512(私钥)  // 私钥为32字节
r = SHA-512(h[32..63] || 消息)  // 取哈希值前32字节作为 k
R = r · G
S = (r + SHA-512(R || 公钥 || 消息) · 私钥) mod n

对于Ed448（含预哈希标志 f）：

h = SHAKE256(私钥, 114)  // 私钥为57字节，输出114字节
r = SHAKE256(h[57..113] || 消息 || (f ? 0x00 : 0x80) || 上下文, 114)
R = r · G
S = (r + SHAKE256(R || 公钥 || 消息 || (f ? 0x00 : 0x80) || 上下文, 114) · 私钥) mod n

Botan的 sign_message 函数完全按RFC规范实现上述流程，输出固定长度签名（Ed25519为64字节，Ed448为114字节），格式为 R || S 的简单拼接，无任何变体。

3.3 验证的常数时间保证

Ed25519验证需要检查等式 [8]R = [8](r·G + k·Q)，其中包含余因子8的清除操作。该步骤确保即使攻击者提供位于小子群的点，验证依然安全。

Botan的 verify_signature 实现保证常数时间执行，所有比较和分支操作都使用掩码运算而非条件跳转，避免攻击者通过验证失败的时间差异获取信息。具体做法包括：

  • 使用恒定时间的点解码函数，拒绝任何不在主子群上的点
  • 使用恒定时间的标量乘法，确保操作次数不依赖于输入值
  • 使用恒定时间的等号比较，避免早期退出

3.4 预哈希变体（HashEdDSA）

Botan同时支持RFC 8032中定义的预哈希变体，即对消息先进行哈希再签名，适用于需要处理大消息或流式数据的场景：

  • Ed25519ph：先计算 SHA-512(消息)，再对哈希值签名
  • Ed448ph：先计算 SHAKE256(消息, 64)，再对哈希值签名

该变体通过 sign_message 函数的 f 参数控制。

四、ECGDSA与ECKCDSA：德国与韩国的特色变体

4.1 ECGDSA（德国签名算法）

ECGDSA（Elliptic Curve German Digital Signature Algorithm）由德国BSI（联邦信息安全办公室）标准化，主要用于德国政府内部系统。其与ECDSA的核心差异在于签名计算公式。

签名生成：

z = HASH(M) mod n
k = random(1, n-1)
R = k · G
r = x_R mod n
s = k⁻¹ · (z - d) mod n    // 与ECDSA的 s = k⁻¹·(z + r·d) 不同

若 s = 0 则重新生成 k。

验证流程：

z = HASH(M) mod n
u₁ = z · s⁻¹ mod n
u₂ = (-d) · s⁻¹ mod n    // 注意符号差异
P = u₁·G + u₂·Q
接受当且仅当 x_P mod n = r

这一差异使得ECGDSA的验证需要处理负号，但底层 EC_Scalar 和 EC_AffinePoint 接口足以支撑该算法的实现——只需在签名和验证公式中调整标量运算的顺序和符号即可。

Botan对ECGDSA的支持通过独立的 ECGDSA_Signature_Generator 和 ECGDSA_Signature_Verifier 类提供，内部复用标准的 EC_Group 和点乘接口。

4.2 ECKCDSA（韩国证书签名算法）

ECKCDSA（Korean Certificate-based Digital Signature Algorithm）是韩国基于证书的数字签名标准，定义于 TTAK.KO-12.0015/R3。其独特之处在于签名过程涉及证书信息的哈希。

签名生成：

// 预计算证书哈希
cert_hash = HASH(证书)
// 消息签名
z = HASH(cert_hash || 消息) mod n
k = random(1, n-1)
R = k · G
r = x_R mod n
s = k - r · d mod n     // 与ECDSA公式不同

验证流程：

cert_hash = HASH(证书)
z = HASH(cert_hash || 消息) mod n
P = s·G + r·Q
接受当且仅当 x_P mod n = r

ECKCDSA的特点包括：

  • 基于证书的签名：签名方需要先持有有效的数字证书，证书哈希参与每一次签名计算
  • 签名结构：签名输出为 (R, S) 对，但编码格式可能与标准ECDSA不同，Botan采用与韩国国家标准一致的ASN.1编码
  • 公钥验证：验证前需额外验证公钥属于曲线、非无穷远点且阶为 n

从Go语言实现 github.com/RyuaNerin/go-krypto/eckcdsa 可见，ECKCDSA的API结构与ECDSA高度相似。Botan的实现预计也沿用了类似的接口设计，核心差异在于签名公式中的 s = k - r·d 替代了ECDSA的 s = k⁻¹·(z + r·d)。

4.3 两者的工程实现要点

ECGDSA和ECKCDSA在Botan中的实现共享以下特性：

  • 曲线兼容性：两者均支持NIST P-256、P-384等标准Weierstrass曲线
  • 哈希算法：支持SHA-2系列哈希函数，可根据安全需求配置
  • 随机数依赖：两者均依赖系统随机数生成器产生临时密钥 k，存在与ECDSA相同的随机数复用风险，生产环境中建议使用确定性变体

五、SM2：中国标准的独特性与常数时间实现

5.1 签名公式差异

SM2是中国国家密码管理局发布的椭圆曲线公钥密码算法标准（GM/T 0003-2012），广泛应用于中国境内的电子政务、金融和电子商务领域。其签名公式与ECDSA有显著不同。

签名生成：

// 计算消息摘要
ZA = HASH(标识符 || 曲线参数 || 公钥)
e = HASH(ZA || 消息) mod n

// 生成签名
k = random(1, n-1)
(x₁, y₁) = k · G
r = (e + x₁) mod n
s = (k - r·d) / (1 + d) mod n  // 关键差异：分母为 (1+d)⁻¹

其中 d 为私钥，分母 (1 + d) 要求计算模逆元 (1 + d)⁻¹ mod n，这是SM2实现中需要特别处理的数学运算。若 s = 0 或 r = 0，则重新生成 k。

验证流程：

ZA = HASH(标识符 || 曲线参数 || 公钥)
e = HASH(ZA || 消息) mod n
t = (r + s) mod n
(x₁, y₁) = s·G + t·Q
R = (e + x₁) mod n
接受当且仅当 R = r

5.2 素域求逆的常数时间挑战

SM2签名过程中的关键数学运算 (1 + d)⁻¹ mod n 是安全实现的核心挑战。若使用扩展欧几里得算法（EEA），其迭代次数依赖于输入值的二进制长度分布，可能通过时序攻击泄露私钥 d 的信息。

Botan对此采用了两种常数时间实现策略：

策略一：费马小定理法

根据费马小定理，在素数阶 n 的有限域中：

(1+d)⁻¹ ≡ (1+d)^(n-2) mod n

该方法的优势是操作次数完全固定：需要执行约 log₂(n) ≈ 255 次平方和约 187 次乘法，不依赖于 (1+d) 的具体值。缺点是需要 255 轮循环，性能开销较大。

策略二：加法链优化

利用 n-2 的固定二进制展开，使用 addchain 工具生成最优加法链，将乘法次数从187次降至41次。例如，对于SM2标准曲线使用的 n 值，其二进制展开中有大量连续的1，可以通过巧妙的加法链大幅减少乘法操作。

Botan的SM2实现默认采用策略二，在保证常数时间的前提下，将模逆运算的性能提升约 4-5 倍。

5.3 用户标识符（ID）的处理

SM2标准要求签名者和验证者共享一个用户标识符（Distinguishing Identifier），该标识符参与 ZA 的计算：

ZA = HASH(ENTL || ID || a || b || x_G || y_G || x_Q || y_Q)

其中 ENTL 为标识符长度的两字节编码。这一设计将签名与具体用户身份绑定，防止跨域签名攻击。

Botan的SM2签名接口要求调用者通过 SM2_Signature_Generator::set_identifier() 设置标识符，并在签名和验证时保持一致。

5.4 密钥交换与加密的协同实现

值得一提的是，SM2标准不仅包含数字签名（GM/T 0003.2），还包含密钥交换协议（GM/T 0003.3）和公钥加密（GM/T 0003.4）。Botan的SM2实现以 SM2_PrivateKey 和 SM2_PublicKey 为核心，统一管理签名、加密和密钥交换功能，代码复用率高。

六、GOST R 34.10：俄罗斯标准的双版本实现

6.1 算法基础

GOST R 34.10是俄罗斯联邦的国家数字签名标准，其最新版本为2012年发布的标准（GOST R 34.10-2012），替代了早期的2001版本。该算法基于广义ElGamal方案，构建在椭圆曲线点群的素数阶子群上。

签名生成：

e = HASH(M) mod q  // q 为群阶
k = random(1, q-1)
P = k · G = (x, y)
r = x mod q
s = (r · d + k · e) mod q

其中 d 为私钥，e 为消息哈希。签名输出为 (r, s) 对。

验证流程：

e = HASH(M) mod q
v = e⁻¹ mod q
z₁ = s · v mod q
z₂ = (-r) · v mod q
P = z₁·G + z₂·Q
接受当且仅当 x_P mod q = r

6.2 双版本支持

Botan支持GOST R 34.10-2012的两个安全级别变体：

256位版本：

  • 使用256位曲线参数和256位群阶
  • 哈希算法：GOST R 34.11-2012（Streebog）256位输出
  • 签名长度：64字节（S || R 拼接，各32字节）
  • 对应安全级别：约128位

512位版本：

  • 使用512位曲线参数和512位群阶
  • 哈希算法：GOST R 34.11-2012（Streebog）512位输出
  • 签名长度：128字节（S || R 拼接，各64字节）
  • 对应安全级别：约256位

Botan通过 GOST_3410_2012_Signature_Generator 类统一支持两个版本，构造函数通过参数指定版本号。

6.3 曲线参数集

GOST 2012标准允许多组曲线参数，以满足不同应用场景的需求。Botan支持的参数集包括：

256位参数集：

  • paramSetA（id-GostR3410-2012-256-paramSetA）：最为常用，在DNSSEC、TLS等国际标准中被指定
  • paramSetB（id-GostR3410-2012-256-paramSetB）：替代曲线
  • paramSetC（id-GostR3410-2012-256-paramSetC）：替代曲线
  • paramSetD（id-GostR3410-2012-256-paramSetD）：替代曲线

512位参数集：

  • paramSetA（id-GostR3410-2012-512-paramSetA）：最常用
  • paramSetB（id-GostR3410-2012-512-paramSetB）：替代曲线
  • paramSetC（id-GostR3410-2012-512-paramSetC）：替代曲线

部分曲线同时提供Weierstrass规范形式和扭曲爱德华曲线形式两种表示，后者可提升点乘运算效率约15-20%。

6.4 性能优化技术

GOST R 34.10的标量乘法性能优化主要依赖两种技术：

多基非相邻形式（wmbNAF）：

将标量表示为多个基数（如 2、3、5）的加权组合，例如：

k = Σ (c_i · 2^a · 3^b · 5^c)

通过允许负系数（非相邻形式要求相邻非零位之间至少有一个零），可以将非零位数从平均 50% 降低至约 20%，从而减少点加操作的次数。

联合多基NAF（jwmbNAF）：

在签名验证阶段，需要同时计算两个标量乘法 s·G + t·Q。jwmbNAF将两个标量联合编码，共享基数分解，将总点加次数从单独计算的和降低约 30-40%。

Botan的实现通过预计算少量点（通常为 16 个窗口点）并对标量进行特殊编码，将验证性能提升约 3 倍。

6.5 与旧版本的兼容性

GOST R 34.10-2001（旧版）使用不同的哈希算法（GOST R 34.11-94）和曲线参数，在俄罗斯老旧系统中仍有部署。Botan通过 GOST_3410_Signature_Generator（不带年份后缀）提供向后兼容支持，但文档明确标注已过时（deprecated），建议新系统使用2012版本。

七、综合对比与选型建议

7.1 算法实现复杂度对比

算法底层曲线类型特殊算术需求常数时间关键点代码复用程度
ECDSAWeierstrass标准点乘nonce生成、模逆基准实现
Ed25519/Ed448Edwards统一加法公式全程天然常数时间独立实现
ECGDSAWeierstrass签名公式变体同ECDSA高度复用ECDSA
ECKCDSAWeierstrass证书哈希参与同ECDSA高度复用ECDSA
SM2Weierstrass分母模逆 (1+d)⁻¹模逆必须常数时间部分复用ECDSA
GOST 34.10Weierstrass/EdwardsElGamal变体同ECDSA独立实现

7.2 各算法的典型应用场景

ECDSA：

  • 国际通用场景，TLS证书、加密货币（secp256k1）
  • 兼容性要求高、需要FIPS合规的系统（P-256）
  • 使用建议：务必启用RFC 6979确定性nonce生成

Ed25519/Ed448：

  • 新系统默认选择，性能和安全的最佳平衡
  • 物联网设备、即时通信协议（Signal）、OpenSSH
  • 无需FIPS合规的通用项目

ECGDSA：

  • 德国政府内部系统
  • 需要与德国BSI标准对接的特定项目
  • 国际范围内应用极少

ECKCDSA：

  • 韩国电子政务和金融系统
  • 基于证书的签名场景
  • 国际范围内应用极少

SM2：

  • 中国境内的电子政务、金融、能源等关键基础设施
  • 需要遵守《中华人民共和国密码法》的场景
  • 中国境内商业系统的必选项

GOST 34.10：

  • 俄罗斯国家信息系统
  • 俄罗斯企业内部的合规需求
  • DNSSEC中俄罗斯域名（.ru）的部署

7.3 工程实现要点总结

第一点：ECDSA、ECGDSA、ECKCDSA的共享基础设施

三者共享相同的底层 EC_Scalar 和 EC_AffinePoint 基础设施，主要差异在签名公式和编码格式。Botan通过统一的 EC_Group 接口适配不同曲线参数，代码复用率超过80%。

第二点：Ed25519与Ed448的独立实现路径

Ed25519和Ed448完全不依赖通用的Weierstrass点乘实现，而是使用Edwards曲线的专用算术和RFC 8032的确定性nonce生成。这种独立性保证了实现的安全性和性能，但增加了代码库的维护成本。

第三点：SM2的常数时间挑战

SM2的模逆运算 (1+d)⁻¹ 是实现安全的关键瓶颈。Botan采用费马小定理加加法链优化的组合策略，在保证常数时间的前提下尽可能提升性能。开发者在使用SM2时需确保底层库正确实现了该优化，否则存在侧信道泄露风险。

第四点：GOST 34.10的多版本管理

GOST标准同时支持256位和512位两个安全级别，以及多组曲线参数。Botan通过统一的类接口和参数配置管理这些变体，开发者只需在构造函数中指定版本号即可。

7.4 Botan的设计哲学总结

Botan将这些算法集成在统一API下的能力，源于其精心设计的底层抽象层：

  • EC_Scalar 封装了所有与群阶相关的模运算，包括模加、模乘、模逆和模幂
  • EC_AffinePoint 屏蔽了点序列化和基本点乘的细节，提供统一的点操作接口
  • EC_Group 管理曲线参数和预计算表的生命周期
  • 上层签名算法只需组合这些基础操作，按照各自标准的公式实现签名和验证逻辑即可

这种分层架构使得添加新的椭圆曲线签名算法变得相对容易——开发者只需实现签名公式的逻辑，而无需关注底层点乘和模运算的实现细节。

八、结语

Botan库对七种椭圆曲线签名算法的支持，反映了现代密码学库在全球化背景下的设计挑战。从国际通用的ECDSA、性能优先的Ed25519，到各国特有的SM2、GOST 34.10，Botan通过统一的底层抽象层实现了代码复用与算法多样性的平衡。

对于开发者而言，选择合适的算法需要综合考虑合规性要求（中国项目选SM2、俄罗斯项目选GOST）、性能需求（追求速度选Ed25519）和兼容性约束（与现有系统对接选ECDSA）。在Botan的统一框架下，不同算法的API风格保持一致，切换算法的学习成本被降到最低。

随着量子计算威胁的临近，未来Botan的签名算法模块很可能将进一步扩展，纳入格基签名算法（如Dilithium、Falcon）。届时，如何在保持统一API风格的同时支持经典密码和抗量子密码的混合模式，将是Botan工程团队面临的下一项重要挑战。

作者

老丹

关注我
其他文章