Aritmetică NIST de curbe în Pascal pur pentru semnare PDF

HotPDF efectuează acord de chei pe curbe eliptice și verificare de semnături pentru PDF în Object Pascal pur, fără binding OpenSSL și fără furnizor criptografic de platformă în cale. Aceasta acoperă cinci curbe: P-256, P-384 și P-521 pentru familiile prime NIST, plus X25519 și X448 pentru acord de chei pe curbe Montgomery. Motivul de a scrie acel cod în loc să îl legați este implementarea, nu puritatea. O aplicație Delphi sau Free Pascal care livrează un singur executabil și niciun DLL criptografic nu are decalaj de versiuni de gestionat, nu are furnizor per platformă de detectat și nimic care să schimbe comportamentul când un client patchuiește bibliotecile lui de sistem

Costul este că acum dețineți aritmetica. Înmulțirea modulară cu întregi mari este cod nemilos: produce fie rezultate identice octet cu octet față de vectorii de test publicați, fie gunoi cu aspect plauzibil, iar distanța dintre cele două stări poate fi o singură comparație. Aceasta este povestea acelei comparații, deoarece forma erorii se generalizează la orice portare Pascal a aritmeticii de corp

De ce are deloc nevoie o bibliotecă PDF de aritmetică de curbe?

Două funcții o trag înăuntru. Prima este criptarea cu cheie publică a documentelor: handlerul de listă de destinatari din ISO 32000 înfășoară o cheie per document pentru certificate numite, iar când un destinatar deține o cheie EC, înfășurarea rulează prin acord de chei, nu prin transport de chei RSA. Fără ECDH nu există modalitate de a deschide un asemenea document. A doua este validarea semnăturilor. Verificarea unei semnături ECDSA peste octeții /ByteRange cere o înmulțire de puncte pe curba semnatarului, iar P-384 este comună în profilurile guvernamentale și de semnătură calificată, unde P-256 este considerată podeaua, nu ținta. HotPDF expune rezultatele acestei munci prin calea de verificare ECDSA și CMS și prin modelul conectabil de furnizori de semnătură

CIOS și scăderea unică de la final

Înmulțirea Montgomery evită împărțirea lucrând într-un domeniu transformat în care reducerea este o deplasare. Varianta folosită de HotPDF este Coarsely Integrated Operand Scanning, care împletește înmulțirea și reducerea membru cu membru, astfel încât intermediarul nu crește niciodată peste lățimea modulului plus un membru. Corpul buclei este direct și ușor de testat. Coada nu este: după trecerile împletite acumulatorul poate fi oriunde în intervalul până la dublul modulului, deci algoritmul se termină cu o scădere condițională care îndepărtează o copie a numărului prim dacă și numai dacă acumulatorul este mai mare sau egal cu el

Compararea a două numere cu mai mulți membri înseamnă parcurgerea de la cel mai semnificativ membru în jos purtând un borrow. Modul evident de a o scrie este să comparați membrul acumulatorului cu membrul modulului plus borrow-ul de intrare. Expresia aceea este greșită, și este greșită într-un mod pe care majoritatea curbelor îl ascund

// Greșit: P[I] + Borrow poate face wrap când P[I] este $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Corect: comparați fără să adăugați vreodată la un membru
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Cum arată efectiv o depășire de borrow?

Arată ca o curbă care funcționează oriunde în afară de producție. Numerele prime pentru P-384 și P-521 conțin membri care sunt integral unu, deci P[I] este egal cu $FFFFFFFFFFFFFFFF. Adăugați borrow-ul de intrare de unu la asta și un întreg pe 64 de biți fără semn se suprascrie la zero. Comparația întreabă apoi dacă membrul acumulatorului este mai mic decât zero, decide că nu este și concluzionează că nu este nevoie de borrow. Un membru al rezultatului este greșit cu unu

P-256 scapă deoarece niciunul dintre membrii ei nu este integral unu, deci adunarea nu produce niciodată depășire, iar expresia eronată se întâmplă să fie de acord cu cea corectă. Acesta este cel mai rău rezultat posibil pentru o suită de test: cea mai testată curbă trece, cele mai puțin testate eșuează intermitent în funcție de valorile operanzilor, iar eșecul iese la suprafață ca rezultat de verificare „semnătură invalidă" pe documente perfect valide. HotPDF a purtat o poartă explicită pe P-384 exact din acest motiv, returnând o stare de indisponibilitate în loc de un răspuns greșit, până când aritmetica a fost dovedită contra vectorilor de referință

Cum a fost localizată efectiv eroarea

Nu citind codul. Secvența productivă a fost mecanică și este reutilizabilă. În primul rând, eliminați constantele: fiecare membru al lui p, R și R^2 a fost regenerat independent și comparat membru cu membru, ceea ce exclude cea mai comună sursă unică de erori de curbă. În al doilea rând, instrumentați aritmetica, nu API-ul: o procedură temporară de dump tipărea valorile intermediare ale înmulțirii Montgomery a lui R^2, a lui x^3 și a lui y^2 pentru un punct cunoscut, astfel încât să poată fi verificate contra unui adevăr calculat independent

Comparația aceea a indicat direct vinovatul. Lanțul x era corect de la un capăt la altul, în timp ce y^2 diferea exact într-un membru cu exact unu. O diferență de unu într-un singur membru nu este o eroare de înmulțire, de propagare a reportului sau de constantă; este o eroare de lanț de borrow, iar singurul lanț de borrow din rutină este scăderea condițională finală. Un detaliu a aproape deraiat aceasta: constanta de referință folosită pentru dump fusese scrisă ea însăși în ordine de octeți greșită la prima încercare, ceea ce a produs o nepotrivire în valoarea y și a sugerat pe scurt un al doilea defect inexistent. Verificați endianitatea adevărului dumneavoastră fundamental înainte să vă bazați pe el pentru a acuza codul

Capcanele vecine din aceeași rutină

Încă trei moduri de eșec trăiesc la câteva linii de comparația aceea, iar toate trei au fost active la un moment dat în timpul dezvoltării

// 1. Acumulatorul are un membru peste lățimea modulului. Compararea doar
//    a celor L membri de jos ratează cazul în care T este exact p plus 2^(64*L),
//    ceea ce se întâmplă pentru o parte semnificativă din intrările aleatorii
//    deoarece 2p depășește 2^256 pentru P-256 și 2^384 pentru P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. O scădere generică cu mai mulți membri are același pericol de wrap: când
//    Y[I] este $FFFFFFFFFFFFFFFF, Y[I] + Borrow se suprascrie la zero și
//    borrow-ul trebuie să supraviețuiască în membrul următor, nu să fie curățat
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

A treia nu este cod, este proveniența. Numărul prim pentru P-521 a fost inițial transcris cu 130 de cifre hexazecimale în loc de 131, lipsind un F, iar constantele Montgomery au fost apoi calculate din acel prim greșit, astfel încât constantele erau autoconsistente și greșite împreună. Parametrii de curbă trebuie derivați, niciodată tastați: calculați R ca (1 shl (64 * L)) mod p din numărul prim pe care îl folosiți efectiv, apoi verificați încrucișat R * R mod p contra valorii pe care o pretinde constanta dumneavoastră R^2. O pereche de constante care sunt de acord între ele nu dovedește nimic despre niciuna

Strategie de verificare care scalează dincolo de o curbă

Tehnica care a făcut X25519 și X448 gestionabile a fost scrierea unei implementări-oglindă într-un limbaj cu întregi nelimitați și transcrierea fluxului de control Pascal în ea linie cu linie. Când oglinda produce răspunsul corect, iar Pascalul nu, defectul este o alunecare de transcriere, iar sondarea aceleiași valori intermediare în ambele implementări o găsește în secunde. Toate cele trei greșeli clasice de scară RFC 7748 au fost prinse astfel: un swap în timp constant a cărui a doua linie refolosea valoarea deja inversată, o inversare finală care returna z la puterea minus unu în loc să îl înmulțească în X, și o înmulțire cu constantă mică care asambla produse de semi-cuvânt cu un or pe biți și pierdea reportul

Pentru material de test, luați vectorii ca octeți, nu ca text. Extragerea unei chei private cu un tipar textual este felul în care o implementare corectă este acuzată de o eroare de un octet care trăiește integral în pasul de extragere. Tăiați hex-ul din codificarea DER la offset-uri cunoscute și comparați vectori de octeți

Cu lanțul de borrow corectat, toate cele cinci curbe se potrivesc cu vectorii de referință publicați octet cu octet, iar HotPDF nu mai filtrează niciuna. Dacă integrați semnare bazate pe certificate sau criptare cu listă de destinatari, concluzia practică este că alegerea curbei este acum o decizie de politică, nu o întrebare de capacitate; profilele și capcanele de ordine a octeților ale părții de semnare sunt tratate în ghidul de semnare PAdES. Detaliile componentei și matricea de algoritmi suportați sunt pe pagina de produs HotPDF Delphi PDF component