LlosLab Software Development Blog面向 PDF、Delphi 和文档软件开发者的工程笔记

技术文章

面向 PDF 签名的纯 Pascal NIST 曲线算术

HotPDF Delphi Component

HotPDF 以纯 Object Pascal 为 PDF 执行椭圆曲线密钥协商与签名验证,路径上没有 OpenSSL 绑定,也没有平台加密提供者。覆盖五条曲线:NIST 素数族的 P-256、P-384 与 P-521,外加用于 Montgomery 曲线密钥协商的 X25519 与 X448。写这段代码而不是链接现成库的理由是部署,不是纯洁性。一个只交付单个可执行文件、不带加密 DLL 的 Delphi 或 Free Pascal 应用,没有版本漂移要管理,没有逐平台提供者要探测,客户给系统库打补丁也不会改变行为

代价是算术从此归你所有。大整数模乘是不肯通融的代码:它要么对照已发布测试向量产出逐字节一致的结果,要么产出貌似合理的垃圾,而这两种状态之间的距离可能只是一次比较。这就是那次比较的故事,因为这个 bug 的形态可以推广到域算术的任何 Pascal 移植

PDF 库到底为什么需要曲线算术?

两个功能把它拉了进来。第一个是文档公钥加密:ISO 32000 的接收者列表处理器为指定证书包装每文档密钥,当接收者持有 EC 密钥时,包装走密钥协商而非 RSA 密钥传输。没有 ECDH 就无法打开这类文档。第二个是签名验证。验证 /ByteRange 字节上的 ECDSA 签名需要在签署者曲线上做一次点乘,而 P-384 在政府与合格签名 profile 中很常见——那里 P-256 被视为下限而非目标。HotPDF 通过ECDSA 与 CMS 验证路径和可插拔签名提供者模型暴露这些成果

HotPDF 纯 Pascal 曲线算术的用武之地:接收者列表 ECDH 加密与 ByteRange 上的 ECDSA 签名验证
密钥协意为指定接收者打开 EC 加密文档,签名验证则需在签署者曲线上点乘

CIOS,以及结尾那一次减法

Montgomery 乘法通过在一个约减即移位的变换域中工作来避开除法。HotPDF 用的变体是 Coarsely Integrated Operand Scanning,它逐 limb 交织乘法与约减,使中间值从不超过模宽加一个 limb。循环体直截了当,容易测试。尾部不是:交织遍历完成后,累加器可能落在最高两倍模宽的任何位置,所以算法以一次条件减法收尾——当且仅当累加器大于等于素数时减去一份素数

比较两个多 limb 数意味着从最高 limb 向下走,同时携带借位。显而易见的写法是把累加器 limb 与模 limb 加传入借位相比较。这个表达式是错的,而且错在大多数曲线都会掩盖的地方

// 错误:当 P[I] 为 $FFFFFFFFFFFFFFFF 时 P[I] + Borrow 会回绕
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// 正确:比较,而不对 limb 做任何加法
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

借位回绕实际上长什么样?

它长成一条除生产环境外处处正常的曲线。P-384 与 P-521 的素数包含全一的 limb,即 P[I] 等于 $FFFFFFFFFFFFFFFF。往上加传入借位一,64 位无符号数回绕成零。比较随即问累加器 limb 是否小于零,判断不是,于是结论是不需要借位。结果有一个 limb 差一

Montgomery 约减借位回绕图:对比 HotPDF P-384 算术中错误的 limb 比较与正确的借位传播
对全一 limb 加借位会回绕成零,于是 P-384 与 P-521 漏掉减法,而 P-256 掩盖缺陷

P-256 逃脱是因为它的 limb 没有全一的,加法从不溢出,错误表达式碰巧与正确表达式一致。这是测试套件可能遇到的最坏结局:被测最多的曲线通过,测得少的那些随操作数值间歇性失败,而且失败表现为对完全有效文档给出"无效签名"的验证结果。正是因此,HotPDF 在算术对照参考向量证明正确之前,对 P-384 挂了显式闸门,返回不可用状态而不是错误答案

bug 实际是如何被定位的

不是靠读代码。有效的流程是机械的,而且可复用。第一,排除常量:p、R 与 R^2 的每个 limb 都独立重新生成并逐 limb 比较,这排除了曲线 bug 最常见的单一来源。第二,给算术插桩而不是给 API 插桩:一个临时 dump 过程打印已知点的 R^2、x^3 与 y^2 的 Montgomery 乘法中间值,使它们可以对照独立计算的真值检查

那次比较直指元凶。x 链从头到尾正确,而 y^2 恰好在一个 limb 上恰好差一。单个 limb 恰差一,不是乘法 bug、进位传播 bug 或常量 bug;它是借位链 bug,而例程中唯一的借位链就是结尾的条件减法。有一个细节差点让排查脱轨:用于 dump 的参考常量第一次抄录时字节序就是错的,导致 y 值不匹配,一度暗示存在第二个并不存在的缺陷。在让你的基准真值指控你的代码之前,先核实它的字节序

HotPDF 曲线 bug 定位流程图:重新生成常量、倾泻 Montgomery 中间值、与镜像真值做 diff
单个 limb 恰好差一直指例程中唯一的借位链,而字节序颠倒的参考值差点把追查带偏

同一例程里的邻近陷阱

还有三种失败模式就在那次比较的几行之内,而且三者都曾在开发过程中真实存在过

// 1. 累加器在模宽之上还有一个 limb。只比较低 L 个 limb
//    会漏掉 T 恰好等于 p 加 2^(64*L) 的情形;由于 2p 超过
//    P-256 的 2^256 与 P-384 的 2^384,随机输入中有相当比例会命中
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. 通用多 limb 减法有同样的回绕风险:当 Y[I] 为
//    $FFFFFFFFFFFFFFFF 时,Y[I] + Borrow 回绕成零,
//    借位必须存续到下一个 limb,而不是被清掉
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

第三个不是代码,是出处。P-521 的素数最初抄成 130 个十六进制数字而不是 131 个,少了一个 F,Montgomery 常量随后就从这个错误素数计算出来,于是常量彼此自洽却共同错误。曲线参数必须推导,绝不能手敲:从你实际使用的素数计算 R 为 (1 shl (64 * L)) mod p,再把 R * R mod p 与 R^2 常量声称的值交叉核对。一对互相吻合的常量,证明不了它们任何一个的正确性

能扩展到多条曲线的验证策略

让 X25519 与 X448 变得可控的技术,是用一门支持无界整数的语言写一个镜像实现,把 Pascal 控制流逐行转写进去。当镜像产出正确答案而 Pascal 没有时,缺陷就是转写笔误,在两个实现里探测同一中间值几秒钟就能找到。RFC 7748 阶梯的三个经典错误全是这样抓到的:常时交换的第二行复用了已交换的值;最终求逆返回了 z 的负一次幂而没有乘进 X;小常量乘法用按位或拼装半字乘积,弄丢了进位

测试素材要按字节取向量,而不是按文本。用文本模式提取私钥,正是让一个正确实现背上差一字节罪名的缘由——那错误完全存在于提取步骤里。按已知偏移从 DER 编码中切出十六进制,比较字节数组

借位链修正后,五条曲线全部与已发布参考向量逐字节一致,HotPDF 不再对任何一条设闸。如果你在集成基于证书的签名或接收者列表加密,务实的结论是:曲线选择如今是策略决策而不是能力问题;签名侧的 profile 与字节序陷阱见PAdES 签名演练。组件细节与支持的算法矩阵见 HotPDF Delphi PDF component 产品页