以純 Pascal 為 PDF 實作 Ed448 與 Brainpool ECDSA

PDFlibPas 以純 Object Pascal 實作 Ed448 與三條 Brainpool ECDSA 曲線的簽章與驗證。不需要外部加密程式庫、不需要平台提供者、也沒有 DLL:PDFlibEd448 在 edwards448 上實作 RFC 8032 PureEdDSA,PDFlibBrainpool 則實作 RFC 5639 的 brainpoolP256r1、brainpoolP384r1 與 brainpoolP512r1。兩者都以相同方式建置:先在撰寫任何 Pascal 程式碼之前獨立產生已知答案測試向量,再對照實作;而兩者值得寫成文章的原因,主要是那些錯誤

欄位算術是少見的誠實程式碼:它要嘛與已公開的測試向量逐位元組一致,要嘛就不一致,所以沒有「大致可用」的空間。真正困難的地方在於,錯誤的實作依然會產生簽章、依然能驗證自己產生的簽章,而且看起來完全合理

為什麼選這些曲線,又為什麼用 Pascal 實作

Brainpool 曲線出現在歐洲合格簽章設定檔中,因此面向該市場簽署文件的程式庫不能把它們當成冷門選項。Ed448 則在 ISO/TS 32002 帶進 PDF 的演算法集合中,其內部摘要採用 SHAKE256 而非 SHA-2。這兩個家族在常用的 Pascal 加密程式庫裡都不存在,所以想支援它們的 PDF 程式庫就必須自己擁有

部署上的論證與這個程式庫所有密碼學元件一致:只出貨單一執行檔、沒有任何加密相依性的應用程式,不需要偵測提供者、不需要對齊版本,也不會因為主機被修補而出現行為改變。簽章恰恰是最不希望相依性浮動的領域

常數一律取自規格文字,絕不憑記憶

edwards448 基底點的第一次嘗試是憑記憶寫的,結果是錯的。這不是什麼罕見的失誤,但代價非常高,因為錯誤的基底點會產生一個自洽的系統:您的金鑰產生、簽章與驗證彼此一致,卻與世界上其他所有實作都不一致

正確的工作程序是:每一個網域參數都取自規格文字,然後交叉驗證。對 edwards448 來說,這代表把 RFC 8032 中的質數、曲線常數、群階,以及基底點的兩個十進位座標轉換成內部 limb 表示,再對照同一份文件發布的測試向量檢查。對 Brainpool 曲線來說,則是使用 RFC 5639 的參數、另寫一個獨立實作來產生向量,並在執行任何 Pascal 程式碼之前,先與系統程式庫做雙向交叉比對

有一條推導捷徑值得警告,因為它看起來放諸四海皆準,其實不然:從固定的 y 值還原基底點,在 25519 曲線上行得通,在 edwards448 上卻行不通,因為該值在那裡沒有平方根。一支指令碼幾秒鐘就否證了它,遠比透過除錯器發現它便宜

方法:在寫任何 Pascal 之前先做 limb 級鏡射實作

讓這兩個單元變得可掌控的技術,是在一門支援無界整數的語言裡自底向上建一個鏡射實作。先只做算術層:欄位乘法、減法與進位傳遞,用代數不變式對數百個隨機案例做壓力測試。接著在鏡射裡做完整金鑰產生,語意錯誤就藏在這一層,也只有在這裡找到才便宜。最後才做 Pascal 轉寫

鏡射的收益是診斷性的,而非開發性的。一旦確認鏡射正確,鏡射與 Pascal 之間的任何分歧就都是轉寫失誤,在兩個實作裡探查同一個中間值,立刻就能定位。這把一類幾乎無法除錯的錯誤——純量乘法深處某一個 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

第二個是弄混的指數運算形狀。正確的平方-乘法形式有兩種,它們以相反方向消耗指數:右到左形式先乘後平方基底,必須從最低有效端讀位元;左到右形式先平方後乘,從最高有效端讀。模反元素迴圈卻是右到左的主體配上了最高位優先的位元走訪。兩半各自都是教科書內容,組合起來卻不是,結果是一個看起來仍像合理欄位元素的錯誤反元素

// 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;

代價比錯誤本身更高的兩個流程教訓

增量式的熱修補在密碼學單元上不會收斂。有一份草稿被反覆修補,直到累積了 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 產品頁