Puncte:1

Un verificator SHA în format CNF

drapel br

Poate cineva să vă spună cum să generați un verificator 3-CNF pentru SHA-256 care:

  1. iese 1 dacă valoarea SHA-256 calculată a mesajului/intrarilor se potrivește cu hash-ul pre-furnizat
  2. În caz contrar, iese 0.

Având în vedere că mesajul poate fi arbitrar lung, putem presupune că are o lungime finită (să zicem 2 MB) pentru a ne simplifica sarcina.

fgrieu avatar
drapel ng
Cu excepția dimensiunii CNF, nu pare să existe nicio dificultate semnificativă. Vedeți cum ați proceda având în vedere o implementare 3-CNF a SHA-256 pentru mesaje de dimensiune fixă? Cum ați construi acest lucru având în vedere o implementare 3-CNF a unei compresii SHA-256? Cum să construiți acest lucru dintr-o implementare 3-CNF a unei runde SHA-256? Cum să mai despart asta în 3-CNF? Începeți să o faceți și, dacă rămâneți blocat, spuneți unde.
J.Doe avatar
drapel br
mulțumesc. doar o interogare ulterioară. Puteți sugera un limbaj bun și un program de ieșire a circuitului, în sensul că, având în vedere operațiile binare de nivel înalt, acesta scoate în esență o expresie booleană care implementează logica. VHDL sau altele par a fi pentru proiectarea circuitelor, dar nu sunt sigur cum putem obține logica binară [ȘI, SAU, NU] ieșire bazată pe porți care implementează același lucru. P.S. Nou în acest sens, așadar, oarecum necunoscut.
fgrieu avatar
drapel ng
Îmi pare rău, nu pot recomanda un instrument. Odată (2004) am vrut să convertesc în CNF o problemă legată de cripto ([VMPC](http://www.vmpcfunction.com/vmpc.pdf)), am încercat să găsesc instrumente ușor de utilizat, am eșuat și am ajuns să scriu [ un scurt program C](https://pastebin.com/WbDaYxWP). Benchmark-urile pe care le generează sunt încă folosite în competițiile SAT. Totul a început să funcționeze într-o singură seară, IIRC.
J.Doe avatar
drapel br
nu o problemă. Mulțumesc mult.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.