dat un algoritm al unei funcții hash, cum se transformă într-un circuit?
Cel mai important, mai întâi dorim să expunem mai bine problema
- Ce funcție hash?
- Dorim un circuit pentru funcția hash completă și o intrare cu lungime fixă [care pare să se potrivească cel mai bine cu întrebarea] sau pentru o parte a hashului [cum ar fi o rundă a funcției hash cu introducerea unui bloc de mesaj captusit în material legat, dacă am citit corect]?
- De ce vrem „un circuit”? Acest lucru va afecta natura a ceea ce producem.
- O dovadă de zero cunoștințe care implică hash ca în exemplul legat? Aceasta se va îndrepta către o expresie ca un lung lanț de porți limitat la unele soiuri (aici XOR, ȘI, și INV)
- Testarea cât de pură Rezolvator SAT se ocupă de rezolvarea unei probleme legate de hash (cum ar fi preimagine)? Expresia va fi de obicei și mai restrânsă (fără XOR), pe de altă parte, negația este de obicei liberă.
- Realizare optimizată în silicon sau FPGA? De obicei, o puritate prea profundă Expresie booleană va fi inutil, vom avea nevoie de zăvoare intermediare și, cu excepția cazului în care totul este profund canalizat sau hash-ul teribil de neregulat, vom avea o anumită logică reutilizată în runde. Nu voi acoperi asta.
- În ce formă vrem rezultatul? Pentru un circuit pur boolean, majoritatea formatelor vor numerota variabile. Presupun că exemplu are 512 intrări numerotate de la 0 la 511, 116246 porți (una pe linie) fiecare producând o nouă variabilă pentru un total de 116758 variabile și 256 ieșiri (ar putea fi variabile de la 116502 la 116757, nu sunt sigur), cu aceasta descrisă în primele două rânduri după o convenție simplă. Mai jos sunt câte o poartă pe linie, cred că pentru fiecare
- numărul de intrări [1 pentru NOT și 2 pentru altele din exemplu]
- numărul de ieșiri [1 în exemplu]
- lista de intrări
- lista cu [unul] ieșiri
- numele porții [XOR, AND, INV în exemplu]
Restul urmează în linii mari tehnica omului cavernelor de a mânca un mamut (o bucată la un moment dat) și progresul de acolo (instrumente).
Luăm algoritmul pas cu pas, derulând fiecare buclă și exprimăm fiecare pas ca ecuații booleene. De exemplu, dacă toate variabilele sunt pe 32 de biți (ca în SHA-256):
- o afirmatie ca
C = A ^ B poate fi tradus în 32 de variabile noi pentru C, ieșite de 32 de porți XOR, necesitând 32 de linii. Trebuie să ținem evidența numerelor care desemnează noile variabile cărora le sunt atribuite C.
E = C + D necesită variabile intermediare, deci mai multe linii. Avem nevoie de 30 sumatori plini, și apoi două simplificate (fără executare pentru bitul de înaltă calitate care se reduce astfel la un XOR; fără transfer pentru primul care se reduce astfel la un XOR și un AND).F = (E<<3)|(E>>29) nu ar necesita nicio linie, doar o reatribuire a variabilelor pentru E.
Există câteva trucuri care pot obține uneori expresii mai simple, dar pentru hashe-uri de interes criptografic expresia va rămâne lungă. Dacă nu ar fi, hașul ar fi slab.
Este destul de ușor să faci un program care să facă asta de la zero și, din experiența mea, este mai ușor decât să găsești și să stăpânești ceva adecvat. Instrumentele existente pot fi utile pentru a simplifica automat expresiile, dar pentru majoritatea hashurilor criptografice o mică analiză a ecuațiilor hash-ului va obține cele mai multe simplificări posibile și ar putea oferi rezultate mai bune decât instrumentele automate.
