Aritmetika NIST krivih u čistom Pascalu za potpis PDF-a

HotPDF izvodi dogovor ključeva eliptičkih krivih i verifikaciju potpisa za PDF u čistom Object Pascalu, bez OpenSSL vezivanja i bez platformskog kripto provajdera na putu. To pokriva pet krivih: P-256, P-384 i P-521 za NIST proste familije, plus X25519 i X448 za dogovor ključeva na Montgomery krivama. Razlog da se taj kod napiše umesto da se poveže jeste raspoređivanje, ne čistota. Delphi ili Free Pascal aplikacija koja isporučuje jednu izvršnu datoteku i bez kriptografskog DLL-a nema odstupanje verzija za upravljanje, nema provajdera po platformi za otkrivanje, i ništa što menja ponašanje kada kupac zakrpi svoje sistemske biblioteke

Cena je da sada vi posedujete aritmetiku. Modularno množenje velikih celih brojeva je neumoljiv kod: ili proizvodi rezultate identične bajtovima u odnosu na objavljene test vektore ili proizvodi smeće koje deluje uverljivo, i razdaljina između ta dva stanja može biti jedno poređenje. Ovo je priča o tom poređenju, jer se oblik greške uopštava na svaki Pascal port aritmetike polja

Zašto PDF biblioteka uopšte treba aritmetiku krivih?

Dve funkcije ga privlače. Prva je enkripcija dokumenata javnim ključem: ISO 32000 rukovaoc popisa primalaca omotava ključ po dokumentu za imenovane sertifikate, i kada primalac drži EC ključ omotavanje ide kroz dogovor ključeva umesto RSA prenosa ključa. Bez ECDH-a nema načina da se takav dokument otvori. Druga je validacija potpisa. Verifikacija ECDSA potpisa preko bajtova /ByteRange traži množenje tačke na krivi potpisnika, i P-384 je čest u vladinim i profilima kvalifikovanih potpisa gde se P-256 smatra podom, a ne ciljem. HotPDF izlaže rezultate tog rada kroz put ECDSA i CMS verifikacije i kroz model priključivih provajdera potpisa

CIOS, i jedno oduzimanje na kraju

Montgomery množenje izbegava deljenje radeći u transformisanom domenu gde je redukcija pomeranje. Varijanta koju HotPDF koristi je Coarsely Integrated Operand Scanning, koja isprepliće množenje i redukciju limb po limb pa međuprodukt nikad ne raste preko širine modula plus jedan limb. Telo petlje je jednostavno i lako za testiranje. Rep nije: posle isprepletenih prolaza akumulator može biti bilo gde u opsegu do dva puta modula, pa se algoritam završava uslovnim oduzimanjem koje uklanja jedan primerak prostog broja ako i samo ako je akumulator veći ili jednak njemu

Poređenje dva višelimbova broja znači hodanje od najznačajnijeg limba nadole noseći zajam. Očigledan način da se napiše jeste uporediti limb akumulatora sa limbom modula plus dolazni zajam. Taj izraz je pogrešan, i pogrešan je na način koji većina krivih krije

// Pogrešno: P[I] + Borrow može se saviti kada je P[I] $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Ispravno: poredite bez ikad dodavanja limb-u
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Kako zapravo izgleda prekoračenje zajma?

Izgleda kao kriva koja radi svuda osim u produkciji. Prosti brojevi za P-384 i P-521 sadrže limbove koji su svi jedinice, pa je P[I] jednako $FFFFFFFFFFFFFFFF. Dodajte dolazni zajam od jedan tome i 64-bitni bezznakovan broj savija se u nulu. Poređenje zatim pita da li je limb akumulatora manji od nule, odlučuje da nije, i zaključuje da zajam nije potreban. Jedan limb rezultata odstupa za jedan

P-256 izmiče zato što nijedan njegov limb nije svih jedinica, pa dodavanje nikad ne prelazi i pogrešan izraz slučajno se slaže sa ispravnim. To je najgori mogući ishod za test skup: najviše testirana kriva prolazi, manje testirane otkazuju povremeno zavisno od vrednosti operanada, i otkazivanje ispoljava se kao rezultat verifikacije "nevažeći potpis" na dokumentima koji su savršeno valjani. HotPDF je nosio eksplicitnu kapiju na P-384 upravo iz ovog razloga, vraćajući status nedostupan umesto pogrešan odgovor, dok aritmetika nije dokazana protiv referentnih vektora

Kako je greška zapravo locirana

Ne čitanjem koda. Plodna sekvenca bila je mehanička, i ponovo je upotrebljiva. Prvo, eliminisati konstante: svaki limb p, R i R^2 regenerisan je nezavisno i poređen limb po limb, što isključuje jedan najčešći izvor grešaka krivih. Drugo, instrumentisati aritmetiku umesto API-ja: privremena dump procedura ispisala je međuvrednosti Montgomery množenja od R^2, od x^3, i od y^2 za poznatu tačku, pa su mogle biti proverene protiv nezavisno izračunate istine

To poređenje ukazalo je pravo na krivca. Lanac x bio je ispravan od kraja do kraja, dok se y^2 razlikovao u tačno jednom limb-u za tačno jedan. Razlika jednog limba za jedan nije greška množenja, greška propagacije prenosa, niti greška konstante; to je greška lanca zajma, i jedini lanac zajma u rutini je konačno uslovno oduzimanje. Jedan detalj skoro je to iskrao: referentna konstanta korišćena za dump bila je sama napisana u pogrešnom redosledu bajtova pri prvom pokušaju, što je proizvelo neslaganje u vrednosti y i kratko sugestiralo drugi, nepostojeći defekt. Proverite endianness vaše osnovne istine pre nego što joj poverujete da optuži vaš kod

Susedne zamke u istoj rutini

Tri režima otkazivanja više žive unutar nekoliko linija od tog poređenja, i sva tri bila su živa u nekom trenutku tokom razvoja

// 1. Akumulator ima jedan limb iznad širine modula. Poređenje samo
//    donjih L limbova propušta slučaj gde je T tačno p plus 2^(64*L),
//    što se dešava za znatan udeo slučajnih ulaza jer 2p
//    prelazi 2^256 za P-256 i 2^384 za P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Opšte višelimbovno oduzimanje ima istu opasnost savijanja: kada
//    je Y[I] $FFFFFFFFFFFFFFFF, Y[I] + Borrow savija se u nulu i
//    zajam mora preživeti u sledeći limb umesto da bude obrisan
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Treći nije kod, to je poreklo. Prosti broj za P-521 prvobitno prepisan je sa 130 heksadecimalnih cifara umesto 131, jedan F kratak, i Montgomery konstante su potom izračunate iz tog pogrešnog prostog broja, pa su konstante bile samo-konzistentne i zajednički pogrešne. Parametri krive moraju se izvoditi, nikada kucati: izračunajte R kao (1 shl (64 * L)) mod p iz prostog broja koji zapravo koristite, pa unakrsno proverite R * R mod p protiv vrednosti koju vaša R^2 konstanta tvrdi. Par konstanti koji se slažu međusobno ne dokazuje ništa o nijednoj

Strategija verifikacije koja se skalira van jedne krive

Tehnika koja je učinila X25519 i X448 obvladivim bila je pisanje ogledalne implementacije u jeziku sa neograničenim celim brojevima i prepisivanje Pascal kontrolnog toka u nju liniju po liniju. Kada ogledalo proizvede ispravan odgovor a Pascal ne, defekt je promašaj u prepisivanju i ispitivanje iste međuvrednosti u obe implementacije ga nalazi u sekundama. Sve tri klasične RFC 7748 lestvice greške uhvaćene su ovako: zamena konstantnog vremena čija je druga linija ponovo koristila već zamenjenu vrednost, konačna inverzija koja je vratila z na stepen minus jedan umesto da ga pomnoži u X, i množenje malom konstantom koje je sklapalo polurečne proizvode bitovskim ili i izgubilo prenos

Za test materijal, uzimajte vektore kao bajtove umesto kao tekst. Izvlačenje privatnog ključa tekstualnim obrazcem način je na koji ispravna implementacija biva optužena za grešku od jednog bajta koja živi u potpunosti u koraku izvlačenja. Isecite heksa iz DER kodiranja na poznatim ofsetima i uporedite nizove bajtova

Sa ispravljenim lancem zajma, svih pet krivih poklapa objavljene referentne vektore bajt po bajt, i HotPDF više ne postavlja kapiju na nijednu. Ako integrišete potpisivanje zasnovano na sertifikatima ili enkripciju popisa primalaca, praktični zaključak je da je izbor krive sada odluka politike, a ne pitanje mogućnosti; profili i zamke redosleda bajtova strane potpisivanja pokriveni su u objašnjenju PAdES potpisivanja. Detalji komponente i podržana matrica algoritama nalaze se na stranici proizvoda HotPDF Delphi PDF component