Ed448 dan Brainpool ECDSA dalam Pascal Murni untuk PDF

PDFlibPas menandatangani dan memverifikasi dengan Ed448 dan dengan tiga kurva ECDSA Brainpool dalam Object Pascal murni. Tanpa pustaka kriptografi eksternal, tanpa platform provider, tanpa DLL: PDFlibEd448 mengimplementasikan PureEdDSA RFC 8032 pada edwards448, dan PDFlibBrainpool mengimplementasikan brainpoolP256r1, brainpoolP384r1, dan brainpoolP512r1 RFC 5639. Keduanya dibangun dengan cara yang sama, terhadap vektor known-answer yang dibuat secara independen sebelum satu baris Pascal pun ditulis, dan keduanya layak ditulis terutama karena bug-bugnya

Aritmetika medan adalah kode yang luar biasa jujur. Ia cocok dengan vektor yang dipublikasikan byte demi byte atau tidak sama sekali, sehingga tidak ada ruang untuk "hampir berfungsi". Yang membuatnya sulit adalah implementasi yang keliru tetap menghasilkan tanda tangan, tetap memverifikasi tanda tangannya sendiri, dan tetap tampak sepenuhnya masuk akal

Mengapa kurva-kurva ini, dan mengapa dalam Pascal

Kurva Brainpool muncul dalam profil tanda tangan terkualifikasi Eropa, sehingga pustaka yang menandatangani dokumen untuk pasar tersebut tidak dapat memperlakukannya sebagai hal eksotis. Ed448 termasuk dalam himpunan algoritma yang dibawa ISO/TS 32002 ke PDF, yang digest internalnya adalah SHAKE256 alih-alih SHA-2. Tidak ada satu pun keluarga ini di pustaka kriptografi Pascal yang umum dipakai, sehingga pustaka PDF yang menginginkannya harus memiliki sendiri

Argumen deployment-nya sama dengan yang berlaku bagi seluruh kriptografi pustaka ini: aplikasi yang mengirim satu binary tanpa dependensi kriptografis tidak punya provider untuk dideteksi, tidak punya versi untuk dicocokkan, dan tidak punya perilaku yang berubah ketika host di-patch. Penandatanganan justru area di mana Anda paling tidak menginginkan dependensi yang berpindah-pindah

Konstanta diambil dari teks spesifikasi, bukan dari ingatan

Percobaan pertama pada base point edwards448 ditulis dari ingatan dan keliru. Itu bukan kesalahan yang luar biasa, tetapi kesalahan yang sangat mahal, karena base point yang keliru menghasilkan sistem yang konsisten dengan dirinya sendiri: key generation, penandatanganan, dan verifikasi Anda semuanya saling sepakat dan berbeda dengan seluruh dunia

Prosedur yang benar adalah mengambil setiap parameter domain dari teks spesifikasi, lalu melakukan cross-verify. Untuk edwards448 itu berarti bilangan prima, konstanta kurva, order grup, dan kedua koordinat desimal base point dari RFC 8032, dikonversi ke representasi limb internal, lalu diperiksa terhadap vektor uji yang dipublikasikan pada dokumen yang sama. Untuk kurva Brainpool itu berarti parameter dari RFC 5639, sebuah implementasi independen yang ditulis untuk menghasilkan vektor, dan cross-check terhadap pustaka sistem di kedua arah sebelum satu baris Pascal pun dijalankan

Satu jalan pintas derivasi layak diberi peringatan karena tampak universal padahal tidak: memulihkan base point dari nilai y tetap bekerja untuk kurva 25519 dan tidak bekerja untuk edwards448, di mana nilai tersebut tidak punya akar kuadrat. Sebuah skrip membantahnya dalam hitungan detik, yang jauh lebih murah daripada menemukannya lewat debugger

Metodenya: mirror tingkat limb sebelum kode Pascal apa pun

Teknik yang membuat kedua unit tersebut terkendali adalah implementasi mirror dalam bahasa dengan integer tak terbatas, dibangun secara bottom-up. Pertama lapisan aritmetika saja: perkalian medan, pengurangan, dan propagasi carry, di-stress-test terhadap invarian aljabarnya pada beberapa ratus kasus acak. Lalu key generation lengkap di dalam mirror, di sanalah bug semantik bersemayat dan di sanalah mereka murah untuk ditemukan. Baru setelah itu transkripsi Pascal

Manfaatnya bersifat diagnostik, bukan pengembangan. Begitu mirror diketahui benar, setiap ketidakcocokan antara mirror dan Pascal adalah kekeliruan transkripsi, dan menyelidiki nilai antara yang sama di kedua implementasi langsung menemukannya. Hal itu mengubah kelas bug yang nyaris tidak bisa di-debug, satu limb yang keliru jauh di dalam perkalian skalar, menjadi perbandingan lima menit

Empat akar masalah di Ed448

Keempatnya ditemukan dengan menyelidiki nilai antara, dan keempatnya adalah jenis masalah yang menghasilkan output yang tampak valid

Yang pertama adalah jebakan notasi. Sebagian besar rumus unified Edwards addition yang dipublikasikan mengasumsikan konstanta kurva minus satu, sedangkan edwards448 punya plus satu. Jika dibawa begitu saja, pembilang koordinat y ditulis sebagai penjumlahan padahal seharusnya pengurangan. Solusinya bukan menambal tanda, melainkan menurunkan kembali bentuk produk bebas inversi dari hukum penjumlahan afinitas untuk kurva yang benar, yang menghasilkan keempat ekspresi koordinat dan tidak menyisakan ruang bagi tanda yang diwarisi dari sumber yang keliru

Yang kedua ada di point decompression. Memulihkan x afinitas dari koordinat projektif membutuhkan satu perkalian dengan invers dari Z. Mengalikan dengan kuadrat invers menghasilkan nilai yang masih merupakan representasi projektif yang valid tetapi merupakan koordinat afinitas yang keliru, sehingga gejalanya adalah y yang benar dengan x yang keliru. Kapan pun satu koordinat benar dan yang lain tidak, bug-nya ada di normalisasi, bukan di aritmetikanya

Yang ketiga adalah kebiasaan yang diimpor dari kurva yang lebih pendek. Baik skalar per tanda tangan maupun skalar challenge harus direduksi dari digest lengkap, yang untuk Ed448 adalah 114 byte, bukan dari 57 byte pertamanya. Kurva 32-byte juga menggunakan seluruh digest 64-byte-nya, jadi aturannya konsisten; yang keliru hanya asumsi bahwa "setengah digest adalah lebar skalar"

Yang keempat adalah urutan. Prefix domain separation datang lebih dulu, sebelum prefix konteks dan pesan, yang bukan urutan yang disarankan oleh pembacaan intuitif atas R dan A dalam spesifikasi. Keliru di sini menghasilkan tanda tangan yang terverifikasi terhadap implementasi Anda sendiri dan bukan apa pun yang lain, yang merupakan kegagalan paling menyesatkan yang mungkin

// Desain carry medan: propagasi semantik floor murni, sehingga limb
// positif maupun negatif sama-sama bekerja dan pengurangan tidak
// butuh bias. Carry teratas dilipat kembali melalui 2^448 = 2^224 + 1
// (mod p), yang menyentuh limb 0 dan limb 8. Terbatas empat ronde;
// dua ronde diamati dalam praktik
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, bukan truncation
      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;

Versi sebelumnya dari rutinitas tersebut menerapkan bias sebelum propagasi, dan pada input besar ia melipatkan carry semu dengan magnitudo yang keliru ke limb-limbah rendah. Skema carry berbasis bias adalah sumber defek kelas ini yang terus-menerus; semantik floor dengan loop repeat terbatas lebih mudah ditalar dan terukur cukup cepat

Dua akar masalah di Brainpool

Yang pertama sama sekali bukan kriptografi. Representasi yang dipakai adalah 33 limb, sehingga produk dua nilai membutuhkan 66, dan array produk dideklarasikan dengan 64. Penulisan melewati ujung array merusak memori tetangga, yang awalnya tampak sebagai hasil yang keliru dan baru menjadi crash setelah pemindaian yang lebih luas ditambahkan. Aturan yang lahir dari sana layak diterapkan pada setiap buffer numerik berukuran tetap: tentukan ukurannya dari lebar produk terburuk dan tambahkan margin, lalu jangan dipikirkan lagi. Array dalam kode yang dirilis berukuran 68 limb

Yang kedua adalah bentuk eksponensiasi yang tercampur. Ada dua bentuk square-and-multiply yang benar dan keduanya mengonsumsi eksponen ke arah yang berlawanan: bentuk kanan-ke-kiri mengalikan lalu menguadratkan basis dan harus membaca bit dari ujung least significant, sedangkan bentuk kiri-ke-kanan menguadratkan lalu mengalikan dan membaca dari ujung most significant. Loop inversi modular memiliki badan kanan-ke-kiri dengan penelusuran bit most-significant-first. Kedua bagian adalah bahan buku teks, kombinasinya bukan, dan hasilnya adalah invers yang keliru yang masih tampak seperti elemen medan yang masuk akal

// Doubling dan penjumlahan Jacobian ketika record tujuan bisa jadi
// variabel yang sama dengan sumber. Penyalinan seluruh record di
// awal adalah satu-satunya pertahanan yang andal: menulis limb milik
// R mencemari pembacaan P berikutnya
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // salin dulu, lalu hitung dari Pin saja
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dua pelajaran proses yang harganya lebih mahal daripada bug-nya

Hot-fixing inkremental tidak pernah konvergen pada unit kriptografi. Satu draf ditambal berulang kali sampai membawa 32 rutinitas yang terduplikasi dan struktur yang rusak, dan satu-satunya perbaikan adalah menulis ulangnya. Pola yang perlu diadopsi adalah menulisnya sekali dari mirror yang tervalidasi atau menulis ulang; rangkaian perbaikan lokal pada aritmetika yang belum Anda pahami menumpuk lebih cepat daripada memperbaiki

Dan periksa timestamp pada executable sebelum Anda percaya sebuah hasil uji. Build inkremental yang terkompilasi tetapi tidak me-relink menjalankan binary sebelumnya, yang memunculkan satu putaran penuh petunjuk palsu tentang probe yang hilang dan output yang terduplikasi. Ketika debugging kriptografi, hasil yang tidak bisa dijelaskan seharusnya memicu pertanyaan "apakah ini binary yang baru saja saya bangun" sebelum "apakah algoritmanya keliru"

Kinerja, cakupan, dan cara memanggilnya

Reduksi modular di unit Brainpool adalah shift-subtract bit-seri dari bit set tertinggi produk, sehingga satu perkalian berharga kira-kira sebesar orde lebar bitnya. Verifikasi P-256 berada di kisaran ratusan milidetik rendah, hal yang biasa saja untuk menandatangani atau memverifikasi dokumen dan tidak memadai untuk terminator TLS. Reduksi Barrett adalah peningkatan yang jelas dan membutuhkan nilai kerja yang lebih lebar daripada yang dibawa representasi saat ini, sehingga itu adalah perubahan yang dilakukan ketika workload memintanya, bukan secara antisipatif

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, SHAKE256 secara internal, kunci 57-byte
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: caller menyediakan nonce per tanda tangan, sehingga
  // kebijakan nonce tetap berada di tangan aplikasi
  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;

Perhatikan bahwa entry point penandatanganan Brainpool menerima nonce alih-alih membuatnya sendiri. Itu disengaja: pembuatan nonce adalah satu hal paling katastrofal yang bisa keliru di ECDSA, karena nilai yang berulang atau dapat diprediksi membongkar private key, dan keputusan tentang dari mana keacakan berasal adalah milik aplikasi dan rezim kepatuhannya, bukan milik pustaka PDF

Kurva-kurva ini berdiri berdampingan dengan pekerjaan post-quantum yang dijelaskan dalam artikel FIPS 204 ML-DSA, dan tersambung ke pipeline penandatanganan dan validasi yang sama yang dibahas dalam penandatanganan dan validasi PAdES. Untuk sertifikat uji pada kurva-kurva ini, jalur pembuatan lokal dijelaskan dalam sertifikat self-signed dengan CryptoAPI. Matriks algoritma lengkap tercantum di halaman produk losLab PDF Developer Library