Aritmetika NIST krivulja u čistom Pascalu za potpis

HotPDF izvodi sporazum ključeva eliptičkih krivulja i provjeru potpisa za PDF u čistom Object Pascalu, bez OpenSSL vezivanja i bez platformskog kriptografskog davatelja na putu. To pokriva pet krivulja: P-256, P-384 i P-521 za NIST proste obitelji, plus X25519 i X448 za sporazum ključeva na Montgomery krivuljama. Razlog pisanja toga kôda umjesto povezivanja jest raspoređivanje, ne čistoća. Delphi ili Free Pascal aplikacija koja isporučuje jednu izvršnu datoteku i bez kriptografskog DLL-a nema odstupanja verzija za upravljanje, nema davatelja po platformi za otkriti, i nema ništa što mijenja ponašanje kada kupac zakrpi svoje sistemske biblioteke

Trošak je to što sada posjedujete aritmetiku. Modularno množenje velikih cijelih brojeva nemilosrdan je kôd: ili proizvodi rezultate identične bajtovima u odnosu na objavljene testne vektore ili proizvodi uvjerljivo izgledajuće smeće, a udaljenost između ta dva stanja može biti jedna usporedba. Ovo je priča o toj usporedbi, jer se oblik greške generalizira na bilo koji Pascal prijenos aritmetike polja

Zašto PDF knjižnica uopće treba aritmetiku krivulja?

Dvije značajke je povlače. Prva je šifriranje dokumenata javnim ključem: rukovatelj popisa primatelja ISO 32000 omotava ključ po dokumentu za imenovane certifikate, i kada primatelj drži EC ključ omotavanje ide kroz sporazum ključeva umjesto RSA prijenosa ključa. Bez ECDH-a nema načina otvoriti takav dokument. Druga je provjera valjanosti potpisa. Provjera ECDSA potpisa nad bajtovima /ByteRange treba množenje točaka na krivulji potpisnika, a P-384 je uobičajen u vladinim i profilima kvalificiranih potpisa gdje se P-256 smatra podom, a ne ciljem. HotPDF izlaže rezultate tog rada kroz put provjere ECDSA i CMS i kroz priključivi model davatelja potpisa

CIOS i jedno oduzimanje na kraju

Montgomery množenje izbjegava dijeljenje radeći u pretvorenoj domeni gdje je redukcija pomak. Varijanta koju HotPDF koristi jest grubo integrirano skeniranje operanada (CIOS), koja isprepliće množenje i redukciju limb po limb tako da međuprodukt nikad ne naraste dalje od širine modula plus jedan limb. Tijelo petlje je neposredno i lako za testirati. Rep nije: nakon isprepletenih prolaza akumulator može biti bilo gdje u rasponu do dvostrukog modula, pa algoritam završava uvjetnim oduzimanjem koje uklanja jedan primjerak prostog broja ako i samo ako je akumulator veći ili jednak njemu

Usporedba dvaju višelimbenih brojeva znači hodanje od najznačajnijeg limba prema dolje noseći posudbu. Očiti način pisanja jest usporediti limb akumulatora s limbom modula plus dolazećom posudbom. Taj izraz je pogrešan, i pogrešan je na način koji većina krivulja skriva

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

// Ispravno: usporedite bez ikakvog zbrajanja na limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Kako zapravo izgleda omotavanje posudbe?

Izgleda kao krivulja koja radi svugdje osim u produkciji. Prosti brojevi za P-384 i P-521 sadrže limbove koji su posve jedinice, pa P[I] jednako je $FFFFFFFFFFFFFFFF. Dodajte dolazeću posudbu jedan tome i 64-bitni bezpredznačni omota se u nulu. Usporedba zatim pita je li limb akumulatora manji od nule, odlučuje da nije, i zaključuje da posudba nije potrebna. Jedan limb rezultata odstupio je za jedan

P-256 izbjegava to jer nijedan njegov limb nije svih jedinica, pa zbrajanje nikad ne prelijeva i pogrešan izraz slučajno se slaže s ispravnim. To je najgori mogući ishod za testni skup: najviše testirana krivulja prolazi, manje testirane padaju povremeno ovisno o vrijednostima operanada, a neuspjeh pokazuje se kao rezultat provjere "nevaljan potpis" na dokumentima koji su savršeno valjani. HotPDF je nosio izričitu granu na P-384 upravo iz tog razloga, vraćajući stanje nedostupno umjesto pogrešnog odgovora, sve dok aritmetika nije bila dokazana u odnosu na referentne vektore

Kako je greška stvarno locirana

Ne čitanjem kôda. Plodni niz bio je mehanički, i višekratno je upotrebljiv. Prvo, eliminirajte konstante: svaki limb od p, R i R^2 ponovno je generiran neovisno i uspoređen limb po limb, što isključuje jedan najčešći izvor grešaka krivulja. Drugo, opremite aritmetiku umjesto API-ja: privremena procedura ispuštanja ispisala je međuvrijednosti Montgomery množenja od R^2, od x^3 i od y^2 za poznatu točku, tako da se mogle provjeriti u odnosu na neovisno izračunatu istinu

Ta je usporedba uputila ravno na krivca. Lanac x bio je ispravan od početka do kraja, dok se y^2 razlikovao u točno jednom limb za točno jedan. Razlika jednog limba za jedan nije greška množenja, greška propagacije prijenosa ni greška konstante; to je greška lanca posudbe, a jedini lanac posudbe u rutini jest konačno uvjetno oduzimanje. Jedna pojedinost gotovo je izvela ovo s puta: referentna konstanta korištena za ispuštanje bila je sama zapisana u pogrešnom redoslijedu bajtova pri prvom pokušaju, što je proizvelo nepodudarnost u vrijednosti y i nakratko sugeriralo drugi, nepostojeći defekt. Provjerite endiannost vaše temeljne istine prije nego joj povjerite optužbu vašeg kôda

Susjedne zamke u istoj rutini

Još tri načina kvara žive unutar nekoliko redaka od te usporedbe, i sva tri su bila živa u nekom trenutku tijekom razvoja

// 1. Akumulator ima jedan limb iznad širine modula. Usporedba samo
//    niskih L limbova promašuje slučaj gdje je T točno p plus 2^(64*L),
//    što se događa za znatan udio slučajnih ulaza jer 2p
//    premašuje 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će višelimbeno oduzimanje ima istu opasnost omotavanja: kada
//    je Y[I] $FFFFFFFFFFFFFFFF, Y[I] + Borrow omota se u nulu i
//    posudba mora preživjeti u sljedeći limb umjesto da se obriše
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Treća nije kôd, nego podrijetlo. Prosti broj za P-521 inicijalno je prepisan sa 130 heksadecimalnih znamenki umjesto 131, jedan F manje, i Montgomery konstante su zatim izračunate iz toga pogrešnog prostog broja, pa su konstante bile samokonzistentne i zajednički pogrešne. Parametri krivulja moraju se izvoditi, nikad tipkati: izračunajte R kao (1 shl (64 * L)) mod p iz prostog broja koji stvarno koristite, zatim unakrsno provjerite R * R mod p u odnosu na vrijednost koju vaša konstanta R^2 tvrdi. Par konstanti koje se slažu jedna s drugom ne dokazuje ništa o nijednoj

Strategija provjere koja raste izvan jedne krivulje

Tehnika koja je X25519 i X448 učinila savladivim bila je pisanje zrcalne implementacije u jeziku s neograničenim cjelobrojnim vrijednostima i prepisivanje Pascal toka upravljanja u nju redak po redak. Kada zrcalo proizvodi ispravan odgovor, a Pascal ne, defekt je promašaj u prijepisu i ispitivanje iste međuvrijednosti u obje implementacije pronalazi ga u sekundama. Sve tri klasične greške ljestvice RFC 7748 uhvaćene su ovako: zamjena konstantnog vremena čija je druga linija ponovno koristila već zamijenjenu vrijednost, konačna inverzija koja je vratila z na potenciju minus jedan umjesto množenja u X, i množenje malom konstantom koje je sastavljalo polu-riječne produkte s bitovskim ili i izgubilo prijenos

Za testni materijal, uzimajte vektore kao bajtove, ne kao tekst. Izdvajanje privatnog ključa tekstualnim obrazacem način je na koji ispravna implementacija biva optužena za grešku od jednog bajta koja u potpunosti živi u koraku izdvajanja. Izrežite heksadecimalne brojeve iz DER kodiranja na poznatim pomacima i usporedite polja bajtova

S ispravljenim lancem posudbe, svih pet krivulja poklapa objavljene referentne vektore bajt po bajt, i HotPDF više ne ograničava nijednu. Ako integrirate potpisivanje na temelju certifikata ili šifriranje popisa primatelja, praktičan zaključak jest da je izbor krivulje sada odluka politike umjesto pitanje mogućnosti; profili i zamke redoslijeda bajtova na strani potpisivanja pokriveni su u vodiču kroz PAdES potpisivanje. Pojedinosti komponente i podržana matrica algoritama su na stranici proizvoda HotPDF Delphi PDF component