Grynojo Pascal NIST kreivių aritmetika PDF pasirašymui

HotPDF atlieka elipsinių kreivių rakto suderinimą ir parašų tikrinimą PDF gryname Object Pascal, be OpenSSL susiejimo ir be platformos kripto teikėjo kelyje. Tai dengia penkias kreives: P-256, P-384 ir P-521 NIST pirminėms šeimoms, plus X25519 ir X448 Montgomery kreivių rakto suderinimui. Priežastis rašyti tą kodą, o ne jį susieti, yra diegimas, o ne grynumas. Delphi arba Free Pascal programa, išsiunčiama kaip vienas vykdomasis failas be kriptografinės DLL, neturi versijų skirtumo, kurį valdyti, neturi platformos teikėjo, kurį aptikti, ir neturi nieko, kas pakeistų elgseną, kai klientas lopina savo sistemos bibliotekas

Kaina ta, kad dabar aritmetika priklauso jums. Didelių sveikųjų skaičių modulinė daugyba yra neleniantis kodas: ji arba duoda baitais identiškus rezultatus pagal paskelbtus testinius vektorius, arba duoda tikėtinai atrodančias šiukšles, ir atstumas tarp tų dviejų būsenų gali būti vienas palyginimas. Tai to palyginimo istorija, nes klaidos forma apibendrinama į bet kurį lauko aritmetikos Pascal perkeliamąjį variantą

Kodėl PDF bibliotekai apskritai reikia kreivių aritmetikos?

Dvi savybės jį traukia vidun. Pirma yra viešojo rakto dokumentų šifravimas: ISO 32000 gavėjų sąrašo apdorotojas apvynioja dokumento raktą įvardytiems sertifikatams, o kai gavėjas turi EC raktą, apvyniojimas eina per rakto suderinimą, o ne per RSA rakto perdavimą. Be ECDH tokio dokumento atidaryti nėra kaip. Antra yra parašų tikrinimas. ECDSA parašo tikrinimas ant /ByteRange baitų reikalauja taškų daugybos pasirašiusiojo kreive, o P-384 įprasta valstybinėse ir kvalifikuoto parašo profiliuose, kur P-256 laikoma grindim, o ne taikiniu. HotPDF to darbo rezultatus atveria per ECDSA ir CMS tikrinimo kelią ir per keičiamąjį parašų teikėjų modelį

CIOS ir viena atimtis pabaigoje

Montgomery daugyba išvengia dalybos dirbdama transformuotoje srityje, kur redukcija yra poslinkis. HotPDF naudojamas variantas yra Coarsely Integrated Operand Scanning, kuris supina daugybą ir redukciją limb po limb, kad tarpinė niekada neužaugtų už modulio pločio plus vieno limb. Ciklo kūnas paprastas ir lengvai testuojamas. Uodega — ne: po supintų ejimų akumuliatorius gali būti bet kurioje iki dviejų modulių srityje, todėl algoritmas baigiasi sąlygine atimtimi, pašalinančia vieną pirminio kopiją tada ir tik tada, kai akumuliatorius yra didesnis arba lygus jam

Dviejų kelių limb skaičių palyginimas reiškia ėjimą nuo reikšmingiausio limb žemyn, nešant skolą. Akivaizdus būdas tai rašyti — lyginti akumuliatoriaus limb su modulio limb plus atkeliaujančia skola. Tas reiškinys yra neteisingas, ir jis neteisingas taip, kad dauguma kreivių tai slepia

// Neteisinga: P[I] + Borrow gali apsivynioti, kai P[I] yra $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Teisinga: lyginti niekada nesudėjus į limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Kaip iš tikrųjų atrodo skolos apsivyniojimas?

Jis atrodo kaip kreivė, veikianti visur, išskyrus gamyboje. P-384 ir P-521 pirminiai turi limb, visus iš vienetų, todėl P[I] lygus $FFFFFFFFFFFFFFFF. Sudėjus atkeliaujančią vieneto skolą, 64 bitų beženklis apsiverčia į nulį. Tada palyginimas klauso, ar akumuliatoriaus limb mažesnis už nulį, nusprendžia, kad ne, ir daro išvadą, kad skolos nereikia. Vienas rezultato limb nuokrypa vienetu

P-256 ištrūksta, nes nė vienas jo limb nėra visi vienetai, todėl sudėtis niekada neužlieja ir klaidingas reiškinys atsitiktinai sutampa su teisingu. Tai blogiausias galimas testų rinkinio rezultatas: labiausiai testuota kreivė išlaiko, mažiau testuotos periodiškai nepavyksta priklausomai nuo operandų reikšmių, o nesėkmė pasirodo kaip tikrinimo rezultatas „negaliojantis parašas“ ant dokumentų, kurie visiškai teisėti. HotPDF dėl būtent to nešė aiškią užtvarą ant P-384, grąžindamas neprieinamą būseną vietoj neteisingo atsakymo, kol aritmetika nebuvo įrodyta pagal atskaitos vektorius

Kaip klaida iš tikrųjų buvo rasta

Ne skaitant kodo. Vaisinga seka buvo mechaninė, ir ji pakartotinai naudojama. Pirma, panaikinkite konstantas: kiekvienas p, R ir R^2 limb buvo persigeneruotas nepriklausomai ir palygintas limb po limb, kas atmeta vieną dažniausią kreivių klaidų šaltinį. Antra, instrumentuokite aritmetiką, o ne API: laikina išmetimo procedūra spausdino Montgomery R^2, x^3 ir y^2 žinomo taško daugybos tarpines reikšmes, kad jas būtų galima patikrinti pagal nepriklausomai apskaičiuotą tiesą

Tas palyginimas rodė tiesiai į kaltininką. x grandinė buvo teisinga nuo galo iki galo, o y^2 skyrėsi tiksliai viename limb tiksliai vienetu. Vieno limb skirtumas vienetu nėra daugybos klaida, pernešimo plitimo klaida ar konstantos klaida; tai skolos grandinės klaida, ir vienintelė skolos grandinė procedūroje yra galutinė sąlyginė atimtis. Viena detalė beveik nukėlė tai nuo bėgių: atskaitos konstanta, naudota išmetimui, pati buvo parašyta neteisinga baitų tvarka pirmuoju bandymu, kas davė nesutapimą y reikšme ir trumpai siūlė antrą, neegzistuojantį defektą. Patikrinkite savo etaloninės tiesos baitų eiliškumą, prieš leisdami jai kaltinti savo kodą

Kaimyniniai spąstai toje pačioje procedūroje

Trys daugiau gedimo režimai gyvena keliomis eilutėmis nuo to palyginimo, ir visi trys kadaise buvo gyvi kūrimo metu

// 1. Akumuliatorius turi vieną limb virš modulio pločio. Lyginant tik
//    žemutinius L limb praleidžiamas atvejis, kai T lygus tiksliai
//    p plus 2^(64*L), kuris pasitaiko reikšmingai daliai atsitiktinių
//    įvečių, nes 2p viršija 2^256 P-256 ir 2^384 P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Bendro pobūdžio kelių limb atimtis turi tą patį apsivyniojimo
//    pavojų: kai Y[I] yra $FFFFFFFFFFFFFFFF, Y[I] + Borrow apsiverčia
//    į nulį, o skola privalo išgyventi iki kito limb, o ne būti išvalyta
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Trečiasis nėra kodas — tai kilmė. P-521 pirminis pradžioje buvo perrašytas su 130 šešioliktainių skaitmenų vietoj 131, vienu F trumpiau, o Montgomery konstantos tada buvo apskaičiuotos iš to neteisingo pirminio, todėl konstantos buvo savi susitarusios ir kartu neteisingos. Kreivės parametrai privalo būti išvesti, niekada ne surinkti ranka: apskaičiuokite R kaip (1 shl (64 * L)) mod p iš pirminio, kurį iš tikrųjų naudojate, tada kryžmiškai patikrinkite R * R mod p pagal reikšmę, kurią teigia jūsų R^2 konstanta. Konstantų pora, sutampanti tarp savęs, nieko neįrodo apie nė vieną

Tikrinimo strategija, besiplečianti už vienos kreivės

Technika, padariusi X25519 ir X448 valdomus, buvo veidrodinės realizacijos rašymas kalba su neribotais sveikaisiais skaičiais ir Pascal valdymo srauto perrašymas į ją eilutė po eilutės. Kai veidrodis duoda teisingą atsakymą, o Pascal ne, defektas yra perrašymo klaidelė, ir tos pačios tarpinės reikšmės ištyrinėjimas abiejose realizacijose randa ją per sekundes. Visos trys klasikinės RFC 7748 kopėčių klaidos buvo pagautos tokiu būdu: pastovaus laiko apsikeitimas, kurio antra eilutė naudojo jau apsukeistą reikšmę, galutinė inversija, grąžinusi z laipsniu minus vienetas vietoj jo dauginimo į X, ir mažos konstantos daugyba, sudėliojusi pusaikščio sandaugas su bitiniu ar ir praradusi pernešimą

Testinei medžiagai imkite vektorius kaip baitus, o ne kaip tekstą. Privataus rakto ištraukimas teksto šablonu yra būdas, kuriuo teisinga realizacija būna kaltinama už vieno baito nuokrypos klaidą, kuri visiškai gyvena ištraukimo žingsnyje. Išpjaukite šešioliktainę iš DER koduotės žinomuose poslinkiuose ir palyginkite baitų masyvus

Ištaisius skolos grandinę, visos penkios kreivės sutampa su paskelbtais atskaitos vektoriais baitas po baito, ir HotPDF daugiau neužtveria nė vienos. Jeigu integruojate sertifikatais paremtą pasirašymą arba gavėjų sąrašo šifravimą, praktinė išvada tokia, kad kreivės pasirinkimas dabar yra politikos sprendimas, o ne galimybių klausimas; pasirašymo pusės profiliai ir baitų eiliškumo spąstai dengiami PAdES pasirašymo apžvalgoje. Komponentės detalės ir palaikomų algoritmų matrica yra HotPDF Delphi PDF component produkto puslapyje