Aritmetika Kurva NIST Pascal Murni untuk Tanda Tangan PDF

HotPDF menjalankan kesepakatan kunci kurva eliptik dan verifikasi tanda tangan untuk PDF dalam Object Pascal murni, tanpa binding OpenSSL dan tanpa platform crypto provider di jalurnya. Itu mencakup lima kurva: P-256, P-384, dan P-521 untuk keluarga prima NIST, plus X25519 dan X448 untuk kesepakatan kunci kurva Montgomery. Alasan menulis kode itu alih-alih me-link-nya adalah deployment, bukan kemurnian. Aplikasi Delphi atau Free Pascal yang mengirim satu executable tanpa DLL kriptografis tidak punya gesekan versi untuk dikelola, tidak punya provider per platform untuk dideteksi, dan tidak punya apa pun yang berubah perilaku ketika pelanggan mem-patch pustaka sistemnya

Biayanya adalah Anda kini memiliki aritmetika itu. Perkalian modular big-integer adalah kode yang tidak kenal ampun: ia menghasilkan hasil yang identik byte terhadap vektor uji yang dipublikasikan atau menghasilkan sampah yang tampak masuk akal, dan jarak antara kedua keadaan itu bisa satu perbandingan. Ini adalah kisah perbandingan itu, karena bentuk bug-nya tergeneralisasi ke porting Pascal apa pun dari aritmetika medan

Mengapa pustaka PDF butuh aritmetika kurva sama sekali?

Dua fitur menariknya masuk. Yang pertama adalah enkripsi kunci publik dokumen: handler recipient-list ISO 32000 membungkus kunci per dokumen untuk sertifikat yang dinamai, dan ketika penerima memegang kunci EC pembungkusannya berjalan melalui kesepakatan kunci alih-alih transport kunci RSA. Tanpa ECDH tidak ada cara membuka dokumen semacam itu. Yang kedua adalah validasi tanda tangan. Memverifikasi tanda tangan ECDSA atas byte /ByteRange membutuhkan perkalian titik pada kurva penandatangan, dan P-384 umum di profil pemerintahan dan tanda tangan terkualifikasi di mana P-256 dianggap batas bawah, bukan target. HotPDF memaparkan hasil kerja itu melalui jalur verifikasi ECDSA dan CMS dan melalui model signature-provider yang dapat dipasang

CIOS, dan satu pengurangan di akhir

Perkalian Montgomery menghindari pembagian dengan bekerja di domain tertransformasi di mana reduksi adalah shift. Varian yang dipakai HotPDF adalah Coarsely Integrated Operand Scanning, yang menyelingi perkalian dan reduksi limb demi limb sehingga nilai antara tidak pernah tumbuh melewati lebar modulus plus satu limb. Badan loop-nya lugas dan mudah diuji. Ekorinya tidak: setelah lintasan terselang, akumulator bisa berada di mana saja dalam rentang hingga dua kali modulus, sehingga algoritma berakhir dengan pengurangan kondisional yang menghapus satu salinan prima jika dan hanya jika akumulator lebih besar atau sama dengannya

Membandingkan dua bilangan multi-limb berarti berjalan dari limb paling signifikan ke bawah sambil membawa borrow. Cara menulis yang jelas adalah membandingkan limb akumulator dengan limb modulus plus borrow yang masuk. Ekspresi itu keliru, dan kelirunya dengan cara yang disembunyikan oleh sebagian besar kurva

// Keliru: P[I] + Borrow bisa wrap ketika P[I] berisi $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Benar: membandingkan tanpa pernah menambah ke sebuah limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Bagaimana sebenarnya wujud wrap-around borrow?

Ia tampak seperti kurva yang bekerja di mana-mana kecuali di produksi. Prima untuk P-384 dan P-521 memuat limb yang seluruhnya berisi satu, sehingga P[I] sama dengan $FFFFFFFFFFFFFFFF. Tambahkan borrow masuk bernilai satu ke situ dan unsigned 64-bit wrap ke nol. Perbandingan itu lalu menanyakan apakah limb akumulator kurang dari nol, memutuskan tidak, dan menyimpulkan tidak perlu borrow. Satu limb hasil meleset satu

P-256 lolos karena tidak ada limb-nya yang berisi satu semua, sehingga penjumlahan tidak pernah overflow dan ekspresi yang berbuga kebetulan sepakat dengan yang benar. Itu hasil terburuk yang mungkin bagi test suite: kurva yang paling banyak diuji lolos, yang kurang diuji gagal selang-seling tergantung nilai operand, dan kegagalannya muncul sebagai hasil verifikasi "tanda tangan tidak valid" pada dokumen yang sepenuhnya valid. HotPDF membawa gerbang eksplisit pada P-384 justru karena alasan ini, mengembalikan status tidak tersedia alih-alih jawaban yang salah, sampai aritmetikanya dibuktikan terhadap vektor acuan

Bagaimana bug itu sebenarnya ditemukan

Bukan dengan membaca kodenya. Rangkaian yang produktif bersifat mekanis, dan dapat dipakai ulang. Pertama, eliminasi konstanta: setiap limb dari p, R, dan R^2 diregenerasi secara independen dan dibandingkan limb demi limb, yang menyisihkan sumber bug kurva paling umum. Kedua, instrumenasi aritmetikanya, bukan API-nya: satu procedure dump sementara mencetak nilai antara perkalian Montgomery dari R^2, dari x^3, dan dari y^2 untuk satu titik yang diketahui, sehingga semuanya bisa diperiksa terhadap kebenaran yang dihitung secara independen

Perbandingan itu menunjuk langsung ke pelakunya. Rantai x benar dari ujung ke ujung, sementara y^2 berbeda tepat di satu limb sebesar tepat satu. Perbedaan satu limb sebesar satu bukan bug perkalian, bug propagasi carry, atau bug konstanta; itu bug rantai borrow, dan satu-satunya rantai borrow di rutinitas itu adalah pengurangan kondisional terakhir. Satu detail nyaris menggelincirkan ini: konstanta acuan yang dipakai untuk dump ternyata sendiri ditulis dengan urutan byte yang salah pada percobaan pertama, yang menghasilkan ketidakcocokan pada nilai y dan sesaat menyarankan defek kedua yang tidak ada. Verifikasi endianness ground truth Anda sebelum Anda mempercayainya untuk menuduh kode Anda

Jebakan tetangga di rutinitas yang sama

Tiga mode kegagalan lagi bersemayat dalam beberapa baris dari perbandingan itu, dan ketiganya pernah hidup pada suatu titik selama pengembangan

// 1. Akumulator punya satu limb di atas lebar modulus. Membandingkan hanya
//    L limb rendah melewatkan kasus ketika T tepat sama dengan p plus
//    2^(64*L), yang terjadi pada porsi acak input yang berarti karena 2p
//    melebihi 2^256 untuk P-256 dan 2^384 untuk P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Pengurangan multi-limb generik punya bahaya wrap yang sama: ketika
//    Y[I] berisi $FFFFFFFFFFFFFFFF, Y[I] + Borrow wrap ke nol dan
//    borrow harus bertahan ke limb berikutnya alih-alih dihapus
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Yang ketiga bukan kode, melainkan asal-usulnya. Prima untuk P-521 mula-mula ditranskrip dengan 130 digit heksadesimal alih-alih 131, kurang satu F, dan konstanta Montgomery kemudian dihitung dari prima yang salah itu, sehingga konstanta-konstantanya konsisten dengan dirinya sendiri dan bersama-sama salah. Parameter kurva harus diturunkan, tidak pernah diketik: hitung R sebagai (1 shl (64 * L)) mod p dari prima yang benar-benar Anda pakai, lalu cross-check R * R mod p terhadap nilai yang diklaim konstanta R^2 Anda. Sepasang konstanta yang sepakat satu sama lain tidak membuktikan apa pun tentang keduanya

Strategi verifikasi yang berskala melampaui satu kurva

Teknik yang membuat X25519 dan X448 terkendali adalah menulis implementasi mirror dalam bahasa dengan integer tak terbatas dan mentranskripsikan alur kontrol Pascal ke dalamnya baris demi baris. Ketika mirror menghasilkan jawaban yang benar dan Pascal tidak, defeknya adalah kekeliruan transkripsi dan menyelidiki nilai antara yang sama di kedua implementasi menemukannya dalam hitungan detik. Ketiga kesalahan klasik ladder RFC 7748 tertangkap dengan cara ini: swap constant-time yang baris keduanya memakai ulang nilai yang sudah di-swap, inversi akhir yang mengembalikan z ke pangkat minus satu alih-alih mengalikannya ke dalam X, dan perkalian konstanta kecil yang merakit produk half-word dengan bitwise or dan kehilangan carry

Untuk materi uji, ambil vektor sebagai byte, bukan sebagai teks. Mengekstrak private key dengan pola teks adalah cara implementasi yang benar dituduh melakukan error meleset satu byte yang sepenuhnya bersemayat di langkah ekstraksinya. Iris hex dari encoding DER pada offset yang diketahui dan bandingkan array byte

Dengan rantai borrow yang diperbaiki, kelima kurva cocok dengan vektor acuan yang dipublikasikan byte demi byte, dan HotPDF tidak lagi melakukan gating pada salah satunya. Jika Anda mengintegrasikan penandatanganan berbasis sertifikat atau enkripsi recipient-list, pelajaran praktisnya adalah pilihan kurva kini menjadi keputusan kebijakan alih-alih pertanyaan kemampuan; profil dan jebakan urutan byte di sisi penandatanganan dibahas dalam panduan penandatanganan PAdES. Detail komponen dan matriks algoritma yang didukung ada di halaman produk HotPDF Delphi PDF component