HotPDF は PDF 向けの楕円曲線鍵合意と署名検証を、pure Object Pascal で実行します。パスに OpenSSL バインディングもプラットフォーム暗号プロバイダーもありません。これがカバーするのは 5 つの曲線です。NIST 素数ファミリーの P-256、P-384、P-521 に加え、Montgomery 曲線の鍵合意のための X25519 と X448 です。リンクするのではなくこのコードを書く理由は、純粋さではなく配備です。1 つの実行ファイルだけを出荷し暗号 DLL を持たない Delphi または Free Pascal アプリケーションには、管理すべきバージョンのずれがなく、プラットフォームごとのプロバイダーの検出もなく、顧客がシステムライブラリにパッチを当てても変わる振る舞いもありません
その代償は、演算の所有者があなたになったことです。多倍長整数のモジュラ乗算は容赦のないコードです。公開テストベクトルに対してバイト単位で同一の結果を生むか、それとももっともらしい外見のゴミを生むかのどちらかであり、この 2 つの状態の距離は 1 つの比較であり得ます。これはその比較の物語です。バグの形状が、体の演算のあらゆる Pascal 移植に一般化するからです
PDF ライブラリにそもそも曲線演算が必要なのはなぜか
2 つの機能がこれを引っ張り込みます。1 つ目は文書の公開鍵暗号化です。ISO 32000 の受取人リストハンドラは、指名された証明書のために文書ごとの鍵をラップし、受取人が EC 鍵を持つとき、ラップは RSA 鍵転送ではなく鍵合意を通って走ります。ECDH がなければ、そのような文書を開く方法はありません。2 つ目は署名検証です。/ByteRange バイト上の ECDSA 署名の検証には、署名者の曲線上の点乗算が必要であり、P-384 は政府と合格署名のプロフィールで一般的です。そこでは P-256 は目標ではなく下限と見なされます。HotPDF はこの作業の結果をECDSA と CMS の検証経路およびプラグイン可能な署名プロバイダーモデルを通じて公開します
CIOS と、最後の 1 つの減算
Montgomery 乗算は、削減がシフトになる変換ドメインで作業することで除算を避けます。HotPDF が使うバリアントは Coarsely Integrated Operand Scanning であり、乗算と削減を limb ごとにインターリーブするため、中間値は法の幅プラス 1 limb を超えて成長しません。ループ本体は単純でテストしやすいものです。末尾はそうではありません。インターリーブされたパスの後、アキュムレータは法の 2 倍までの範囲のどこにでもあり得るため、アルゴリズムは条件付き減算で終わります。アキュムレータが素数以上であるときに限り、素数の 1 コピーを取り除きます
2 つの多 limb 数の比較とは、最上位 limb から下向きに歩きながら borrow を運ぶことです。自明な書き方は、アキュムレータ limb を、法 limb に入ってくる borrow を加えたものと比較することです。その式は誤りであり、しかもほとんどの曲線が隠してしまう形で誤りです
// 誤り：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;borrow の桁あふれは実際にはどのように見えるのか
見た目は、本番以外ではどこでも動く曲線です。P-384 と P-521 の素数は、完全に 1 だけの limb を含みます。つまり P[I] が $FFFFFFFFFFFFFFFF に等しい limb です。そこへ入ってくる borrow の 1 を加えると、64 ビット符号なしはゼロへ桁あふれします。比較は次に、アキュムレータ limb がゼロ未満かを問い、そうではないと判断し、borrow は不要と結論します。結果の 1 limb が 1 だけずれます
P-256 は免れます。その limb に完全に 1 だけのものがないため、加算は決して桁あふれせず、バグのある式はたまたま正しい式と一致するからです。これはテストスイートにとって最悪の帰結です。最もテストされた曲線は通り、テストの少ない曲線はオペランドの値に応じて断続的に失敗し、その失敗は、完全に正当な文書への「無効な署名」という検証結果として表面化します。HotPDF はまさにこの理由で、P-384 に明示的なゲートを設け、誤った答えではなく利用不可ステータスを返していました。演算が参照ベクトルに対して証明されるまで
バグが実際にどう特定されたか
コードを読んでではありません。生産的だった手順は機械的で、再利用可能です。まず定数を排除します。p、R、R^2 のすべての limb を独立に再生成し、limb ごとに比較しました。これで曲線バグの最も一般的な単一の発生源が除外されます。次に、API ではなく演算に計測を入れます。一時的なダンプ procedure が、既知の点に対する R^2、x^3、y^2 の Montgomery 乗算の中間値を出力し、独立に計算された真値と照合できるようにしました
この比較は容疑者をまっすぐ指しました。x の連鎖は端から端まで正しかったのに対し、y^2 は正確に 1 limb だけ、正確に 1 だけ異なっていました。1 limb の差が 1 というのは、乗算のバグでも、桁上がり伝播のバグでも、定数のバグでもありません。borrow 連鎖のバグであり、ルーチンの中の唯一の borrow 連鎖は最後の条件付き減算です。1 つの細部がこれをほぼ脱線させました。ダンプに使った参照定数自体が、最初の試みでは誤ったバイト順で書かれており、y 値の不一致を生み、一時的に 2 つ目の、実在しない欠陥を示唆したのです。コードを告発させる前に、グラウンドトゥルースのエンディアンを確認してください
同じルーチン内の隣接する罠
さらに 3 つの障害モードが、この比較の数行以内に住んでいます。そして 3 つすべてが、開発中のどこかの時点で実在していました
// 1. アキュムレータは法の幅より 1 limb 上にある。下位 L limb だけの
// 比較では、T が正確に p + 2^(64*L) に等しいケースを見落とす。
// P-256 では 2p が 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 はゼロへ桁あふれし、
// borrow はクリアされるのではなく次の limb へ生き延びる必要がある
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));3 つ目はコードではなく、出所の問題です。P-521 の素数は最初、131 桁ではなく 130 桁の 16 進数、つまり F が 1 つ足りない状態で書き写され、その後 Montgomery 定数はその誤った素数から計算されました。定数は自己整合的であり、共同で誤っていました。曲線パラメータは導出しなければならず、決して手打ちしてはいけません。実際に使っている素数から R を (1 shl (64 * L)) mod p として計算し、その上で R * R mod p を、R^2 定数が主張する値とクロスチェックします。互いに一致する定数のペアは、どちらかについても何も証明しません
1 つの曲線を超えて拡張できる検証戦略
X25519 と X448 を扱いやすくした技法は、無限精度整数を持つ言語でミラー実装を書き、Pascal の制御フローを 1 行ずつそれへ書き写すことでした。ミラーが正しい答えを生み、Pascal が生まないとき、欠陥は転記のミスであり、両実装で同じ中間値を調べれば数秒で見つかります。RFC 7748 の定番の 3 つのラダーミスはすべてこの方法で捕まりました。2 行目がすでにスワップ済みの値を再利用していた定数時間スワップ、X へ乗算する代わりに z をマイナス 1 乗で返していた最後の逆数、そしてビット単位 or でハーフワード積を組み立てて桁上がりを失っていた小定数乗算です
テスト素材については、ベクトルをテキストではなくバイトとして受け取ってください。テキストパターンで秘密鍵を抽出すると、抽出ステップに完全に存在する 1 バイトずれのエラーで、正しい実装が告発されることになります。DER エンコーディングから既知のオフセットで 16 進を切り出し、バイト配列を比較してください
borrow 連鎖を修正した結果、5 曲線すべてが公開参照ベクトルとバイト単位で一致し、HotPDF はどれにもゲートを設けなくなりました。証明書ベースの署名や受取人リスト暗号化を統合するなら、実務上の教訓は、曲線の選択が今や機能の問題ではなくポリシーの判断になったということです。署名側のプロフィールとバイト順の落とし穴は、PAdES 署名のウォークスルーで扱っています。コンポーネントの詳細と対応アルゴリズムマトリックスは、HotPDF Delphi PDF component の製品ページにあります