用纯 Pascal 实现 PDF 的 Ed448 与 Brainpool ECDSA

PDFlibPas 以纯 Object Pascal 实现了 Ed448 与三条 Brainpool ECDSA 曲线的签名和验证。无外部加密库、无平台 provider、无 DLL:PDFlibEd448 在 edwards448 上实现 RFC 8032 PureEdDSA,PDFlibBrainpool 实现 RFC 5639 的 brainpoolP256r1、brainpoolP384r1 与 brainpoolP512r1。两者的构建方式相同:在写下一行 Pascal 之前,先用独立生成的已知答案向量做校验基准;而它们值得一写,主要也是因为那些 bug

域算术是一种异常"诚实"的代码:它要么与已发布向量逐字节一致,要么就是不一致,没有"基本能跑"的中间地带。难点在于,错误的实现照样产出签名、照样能验证自己的签名,而且看起来完全可信

为什么选这些曲线,又为什么用 Pascal

Brainpool 曲线出现在欧洲合格签名(qualified signature)profile 中,因此面向该市场签署文档的库不能把它们当成冷门算法。Ed448 属于 ISO/TS 32002 引入 PDF 的算法集,其内部摘要用 SHAKE256 而非 SHA-2。这两个曲线族在常用的 Pascal 加密库里都找不到,所以想要它们的 PDF 库只能自己实现

部署层面的理由与这个库所有加密组件的理由一致:一个只交付单个二进制、不带任何加密依赖的应用,既没有 provider 要探测,也没有版本要匹配,更不会因为宿主系统打补丁而行为突变。签名恰恰是最不希望依赖漂移的领域

常量必须抄自规范文本,绝不能凭记忆

edwards448 基点的第一次尝试是凭记忆写下的,结果是错的。这算不上罕见的失误,但代价极高,因为错误的基点会构造出一个自洽的体系:密钥生成、签名和验证彼此一致,却与世界其他实现格格不入

可靠的流程是:每个域参数都取自规范文本,然后交叉验证。对 edwards448 而言,即从 RFC 8032 抄出素数、曲线常数、群阶和基点的两个十进制坐标,转换成内部 limb 表示,再对照同一文档发布的测试向量检查。对 Brainpool 曲线,则意味着参数取自 RFC 5639,另写一个独立实现来生成向量,并在任何 Pascal 代码运行之前与系统库做双向交叉验证

有一条推导捷径值得警示,因为它看似通用实则不然:从固定 y 值恢复基点在 25519 曲线上可行,在 edwards448 上却行不通,因为该值在那里没有平方根。一个脚本几秒钟就否定了它,比在调试器里发现要便宜得多

方法:在任何 Pascal 之前先做 limb 级镜像实现

让这两个单元变得可控的技术,是用一门支持无界整数的语言自底向上构建一个镜像实现。先只做算术层:域乘法、减法与进位传播,用代数不变量对几百个随机用例做压力测试。然后在镜像内部完成完整密钥生成——语义类 bug 正是藏在这里,而且在这里抓最便宜。最后才做 Pascal 转写

回报体现在诊断而非开发环节。一旦镜像被证明正确,镜像与 Pascal 之间的任何分歧就都是转写笔误,在两边探测同一个中间值即可立刻定位。这类 bug——标量乘法深处单个 limb 出错——原本几乎无法调试,如今只需五分钟的比对

Ed448 的四个根因

这四个问题都靠探测中间值发现,而且都属于能产出看似有效输出的那类错误

第一个是记号陷阱。多数已发表的统一 Edwards 加法公式假定曲线常数为负一,而 edwards448 是正一。原样照搬后,y 坐标的分子本应是差,却写成了和。修复方法不是修补符号,而是针对正确的曲线从仿射加法律重新推导无求逆乘积形式,由此得到四个坐标表达式,不给符号留下从错误来源继承的任何机会

第二个出在点解压缩。从射影坐标恢复仿射 x 需要一次乘以 Z 的逆;若误乘逆的平方,得到的值仍是合法的射影表示,却是错误的仿射坐标,症状表现为 y 正确而 x 错误。只要一个坐标对、另一个错,问题就出在归一化,而不是算术本身

第三个是从更短曲线带来的习惯。每次签名的标量和挑战标量都必须从完整摘要归约——Ed448 是 114 字节——而不是取其前 57 字节。32 字节曲线同样用满 64 字节摘要,规则本身是一致的;错的只是"摘要的一半就是标量宽度"这个假设

第四个是顺序。域分离前缀在最前,位于上下文前缀与消息之前——这与直观解读规范中 R 和 A 得到的顺序不同。弄错它产出的签名只能通过你自己的实现验证,其他实现一概不认,这是最具误导性的失败方式

// 域进位设计:纯 floor 语义传播,正负 limb 均适用,减法无需偏置。
// 顶部进位按 2^448 = 2^224 + 1 (mod p) 回折,会触及 limb 0 与 limb 8。
// 循环上限四轮;实际观察到两轮
procedure FeCarry(var A: TFe448);
var
  I, Round: Integer;
  Carry: Int64;
begin
  for Round := 1 to 4 do
  begin
    Carry := 0;
    for I := 0 to 15 do
    begin
      A[I] := A[I] + Carry;
      Carry := Floor28(A[I]);          // floor,而非截断
      A[I] := A[I] - (Carry shl 28);
    end;
    if Carry = 0 then
      Break;
    A[0] := A[0] + Carry;              // 2^448 == 1
    A[8] := A[8] + Carry;              // 2^448 == 2^224
  end;
end;

该例程的早期版本在传播前先加偏置,大输入下会把错误量级的假进位折入低位 limb。基于偏置的进位方案是这类缺陷的顽固来源;带有限次重复循环的 floor 语义更容易推理,而且实测速度也足够

Brainpool 的两个根因

第一个根本不是密码学问题。工作表示是 33 个 limb,两个值相乘需要 66 个,而乘积数组却声明为 64。越界写入破坏了相邻内存,最初表现为结果错误,直到加了更宽的扫描才变成崩溃。由此得出的规则值得套用在每一个定长数值缓冲区上:按最坏情况的乘积宽度定尺寸并留出余量,之后就再也不用想它。发布代码中的数组是 68 个 limb

第二个是搞混的幂运算形态。正确的平方-乘法(square-and-multiply)形式有两种,它们消耗指数的方向相反:从右到左形式先乘后平方底数,必须从最低有效位读取比特;从左到右形式先平方后乘,从最高有效位读取。模求逆循环却写成了右到左主体配最高位优先的比特遍历。两个部分各自都是教科书内容,组合起来却不是,结果是一个错误但看似合理的域元素逆

// Jacobian 倍点与加法,目标记录可能与源是同一个变量。
// 入口处整记录复制是唯一可靠的防御:先写 R 的 limb
// 会污染随后对 P 的读取
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // 先复制,之后仅从 Pin 计算
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

两个代价超过 bug 本身的流程教训

对密码学单元来说,增量式热修复不会收敛。有一份草稿被反复修补,直到背上 32 个重复例程和一处受损结构,最后只能靠重写解决。应当采用的策略是:要么基于验证过的镜像一次写对,要么干脆重写;对尚未理解的算术连续做局部修补,错误累积的速度比修复更快

在相信测试结果之前,先看一下可执行文件的时间戳。一次编译了却没有重新链接的增量构建会跑上一个二进制,由此凭空制造了一整轮关于探测缺失和输出重复的错误线索。调试密码学时,面对无法解释的结果,应先问"这是我刚构建的那个二进制吗",再问"是不是算法错了"

性能、适用范围与调用方式

Brainpool 单元的模归约是从乘积最高置位比特开始的逐位移位减法,因此一次乘法的开销大约在比特宽度量级。P-256 验证落在数百毫秒的低段,对签署或验证文档而言无伤大雅,对 TLS 终结器则不够用。Barrett 归约是显而易见的升级方向,但需要比当前表示更宽的工作值,所以等负载真的提出要求时再改,不必预先优化

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448:PureEdDSA,内部使用 SHAKE256,57 字节密钥
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool:每次签名的 nonce 由调用方提供,
  // nonce 策略因此留在应用侧
  Curve := BPLoadCurve(bpP256r1);
  if BPKeyGen(PubX, PubY, PrivateD, Curve) and
     BPSignFixedK(R, S, Hash, PrivateD, Nonce, Curve) then
    Assert(BPVerify(R, S, Hash, PubX, PubY, Curve));
end;

注意 Brainpool 签名入口接收 nonce 而不是自行生成。这是刻意的:nonce 生成是 ECDSA 中搞错后果最灾难性的一件事,重复或可预测的值会泄露私钥;而随机性来自哪里的决策属于应用程序及其合规体系,不属于 PDF 库

这些曲线与 FIPS 204 ML-DSA 一文所述的后量子工作并列,并接入 PAdES 签名与验证所述的同一条签名与验证管线。关于这些曲线上的测试证书,本地生成路线见 使用 CryptoAPI 的自签名证书。完整算法矩阵列在 losLab PDF Developer Library 产品页