以純 Pascal 實作 PDF 簽章用的 NIST 曲線算術

HotPDF 以純 Object Pascal 為 PDF 執行橢圓曲線金鑰協議與簽章驗證,路徑上沒有 OpenSSL 綁定,也沒有平台加密提供者。涵蓋五條曲線:P-256、P-384、P-521 屬於 NIST 質數家族,加上用於 Montgomery 曲線金鑰協議的 X25519 與 X448。寫這段程式碼而不是連結現成的原因是部署,而不是純度。只出貨單一執行檔、沒有任何加密 DLL 的 Delphi 或 Free Pascal 應用程式,沒有版本錯位要管理、沒有各平台提供者要偵測,客戶修補系統程式庫時也沒有任何行為會改變

代價是您從此擁有這套算術。大整數模乘是不留情面的程式碼:它要嘛對照已公開測試向量產出逐位元組一致的結果,要嘛產出看似合理的垃圾,而這兩個狀態之間的距離可能只是單一次比較。本文講的就是那次比較,因為這個錯誤的形狀可以推廣到任何欄位算術的 Pascal 移植

PDF 程式庫到底為什麼需要曲線算術?

兩個功能把它拉進來。第一是文件的公開金鑰加密:ISO 32000 的收件者清單處理器為指定憑證包裝每份文件的金鑰,而當收件者持有 EC 金鑰時,包裝走金鑰協議而不是 RSA 金鑰傳輸。沒有 ECDH 就無法開啟這種文件。第二是簽章驗證。對 /ByteRange 位元組驗證 ECDSA 簽章,需要在簽署者曲線上做一次點乘法,而 P-384 在政府與合格簽章設定檔中很常見,那裡 P-256 被視為底線而不是目標。HotPDF 透過ECDSA 與 CMS 驗證路徑和可插拔簽章提供者模型暴露這些成果

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 的質數包含整個全為 1 的 limb,所以 P[I] 等於 $FFFFFFFFFFFFFFFF。把傳入借位 1 加上去,64 位元無號數回繞到零。比較接著問累加器 limb 是否小於零,判定不是,得出不需要借位的結論。結果恰好有一個 limb 差了一

P-256 逃過一劫,因為它的 limb 沒有一個是全 1,加法永遠不會溢位,錯誤運算式碰巧與正確的一致。這是測試套件最壞的結果:被測得最多的曲線通過,被測得少的曲線依運算元值間歇性失敗,而失敗以「簽章無效」的驗證結果浮現,針對的卻是完全有效的文件。HotPDF 正是為此對 P-384 保留了明確閘控,回報不可用狀態而不是錯誤答案,直到算術對照參考向量驗證通過

錯誤實際上是怎麼定位的

不是靠讀程式碼。有效的程序是機械性的,而且可以重用。第一,排除常數:p、R 與 R^2 的每個 limb 都獨立重新產生並逐 limb 比對,這排除了曲線錯誤最常見的單一來源。第二,對算術加儀器而不是對 API:一支臨時傾印程序列印 R^2、x^3 與某已知點 y^2 的 Montgomery 乘法中間值,讓它們可以對照獨立計算出的真值

那次比較直接指向元兇。x 鏈從頭到尾正確,而 y^2 恰好有一個 limb 恰好差一。單 limb 差一的差異不是乘法錯誤、不是進位傳遞錯誤、也不是常數錯誤;它是借位鏈錯誤,而常式裡唯一的借位鏈就是結尾的條件減法。有一個細節幾乎讓調查脫軌:傾印用的參考常數第一次轉寫時位元組序就是錯的,造成 y 值不符,一度暗示存在第二個其實不存在的缺陷。在信任您的基準真值去指控程式碼之前,先驗證它的位元組序

同一常式裡的鄰近陷阱

另外三種失敗模式就住在那個比較的幾行之內,三者在開發過程中某個時點都真實存在過

// 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;一個小常數乘法用位元 or 組合半字組乘積並丟掉了進位

測試素材方面,以位元組而不是文字取用向量。用文字模式擷取私密金鑰,就是讓正確實作被指控一個完全出在擷取步驟的差一位元組錯誤的方式。從 DER 編碼的已知偏移切出十六進位,比較位元組陣列

借位鏈修正後,五條曲線全部與已發布參考向量逐位元組一致,HotPDF 不再對任何一條設閘。如果您正在整合基於憑證的簽章或收件者清單加密,實際心得是:曲線選擇如今是政策決策而不是能力問題;簽章側的設定檔與位元組順序陷阱在PAdES 簽章逐步解說中涵蓋。元件細節與支援的演算法矩陣在 HotPDF Delphi PDF component 產品頁