Trec prin semnătura unică Lamport Diffie.
Ca o notă secundară; această lucrare este un efort timpuriu care a culminat cu ceea ce este cunoscut ca „Metode de semnătură bazate pe hash cu stare”; modelele moderne includ XMSS și LMS, și sunt surprinzător de aproape de ceea ce este în ziarul Merkle. Puteți găsi linkul Wiki mai accesibil...
În orice caz, pentru a vă adresa întrebărilor:
- Cum pot fi mapate mesajele lungi (mai mare de 100 de biți) în mesaje scurte (100 de biți) printr-o funcție unidirecțională și doar mesajul scurt semnat?
Ca să nu sune prea simplist:
Luăm mesajul lung pentru a semna
Folosim asta ca intrare la o „funcție unică” (terminologie modernă: o funcție hash), care generează o ieșire de dimensiune fixă (în acest exemplu, 100 de biți)
Luăm acea ieșire de 100 de biți și îi aplicăm algoritmul de semnătură.
Acest lucru nu este specific semnăturilor bazate pe hash; în esență, toți algoritmii de semnătură (cel puțin, oricare despre care am auzit) folosesc o variantă a acestuia ca prim pas. Singura diferență este că 100 de biți nu ar fi considerați suficient de lungi; în general, insistăm pe ieșiri hash mult mai lungi (deoarece capacitățile atacatorului au crescut foarte mult din 1979, de aceea trebuie să ne facem sistemele mai puternice).
Întrebarea neevidentă este „de ce este acest lucru sigur”? Ei bine, dacă presupunem că atacatorul nu poate găsi un alt mesaj pe care funcția unidirecțională se mapează la aceiași 100 de biți și atacatorul nu poate genera o semnătură pentru acel set diferit de 100 de biți la care se mapează mesajul atacatorului, atunci este sigur. .
De fapt, în practică, ne facem griji cu privire la atacurile de coliziune, în care atacatorul deține controlul asupra mesajului valid care este semnat (dar încă trebuie să producă un fals, adică o semnătură validă pentru un mesaj care nu a fost semnat); Merkle ia în considerare acest lucru, totuși să păstrăm lucrurile simple pentru moment.
- „mesajul poate fi criptat cu o cheie aleatoare nou generată...” Poate cineva să-mi explice asta?
Ei bine, această parte poate fi probabil sărită - aceasta este o secțiune a lucrării pe care cripto-ul modern nu o urmează.
Merkle încearcă să definească o „funcție de criptare certificată” și utilizează ipoteze specifice pentru a face acest lucru, inclusiv o intrare randomizată; mesajele semnate nu sunt randomizate, așa că el introduce o funcție de criptare (cu o cheie aleatorie) pentru a se potrivi cu ipotezele sale.
În cripto-ul modern, nu facem acest lucru - în general folosim o funcție hash disponibilă (cum ar fi SHA-2 sau SHAKE) și o folosim - acestea au fost proiectate (și criptoanalizate) pentru a îndeplini diferitele ipoteze pentru criptografie. funcții hash; prin urmare, noi (ca designer de semnături) nu trebuie să ne facem griji pentru asta.
Pentru a fi corect cu Merkle, aceasta poate fi prima dată când cineva încearcă să descopere cum ar arăta o „funcție hash rezistentă la coliziune” și a făcut o încercare destul de decentă - pur și simplu nu este direcția în care au luat-o criptografii de mai târziu.
- „Metoda descrisă până acum suferă de defectul că B poate modifica m prin schimbarea biților care sunt 1 în 0...” Poate cineva să explice cum rezolvă problema.
Ei bine, să luăm în considerare cel mai simplu caz; semnând un singur bit. În „metoda descrisă până acum”, pentru a genera o cheie privată, am alege o valoare aleatorie $x$, și aplicați o funcție aleatorie $F$ acestuia, generând valoarea publică $F(x)$. Apoi, pentru a semna un bit „1”, vom produce ca semnătură $x$ (pe care verificatorul l-ar putea valida $F$ mapează asta la cheia publică). Totuși, pentru a semna un bit „0”, nu am dezvălui nimic. Este evident că cineva care vede semnătura validă de „1” ar putea să o transforme într-o semnătură de „0” (sau, de altfel, să genereze o semnătură de „0” fără să vadă nimic).
În schema Lamport, pentru a semna un singur bit, generăm două valori aleatorii $x$ și $x'$și publică valorile ca cheie publică $F(x)$ și $F(x')$. Pentru a semna 0, producem $x$; pentru a semna un 1, producem $x'$; cineva cu semnătura de 1 nu poate genera o semnătură de 0 (pentru că ar trebui să producă $x$, și ei nu știu asta).
Acum, acest lucru funcționează, dar este destul de costisitor (sfârșiți prin a avea nevoie de o cheie publică care are de două ori mai multe ieșiri hash decât biți pe care funcția dvs. de hash îi produce - de exemplu, dacă funcția dvs. de hash iese 100 de biți, aceasta are o cheie publică care constă de 200 de hashes). Lucrarea continuă să arate modalități de reducere a acesteia, așa cum se menționează în secțiunile 4 și 5 ale lucrării (care sunt cele folosite în practică).