Adesea, atunci când descărcați torrente sau fișierele în sine, descrierea conține ceva de genul „ad33e486d0578a892b8vbd8b19e28754” (de exemplu, în ex.ua), adesea cu adăugarea „md5”. Acesta este un cod hash - rezultatul pe care funcția hash îl produce după procesarea datelor primite. Tradus din engleză, hash înseamnă confuzie, marijuana, iarbă sau un fel de mâncare din carne și legume tocate mărunt. foarte, foarte greu, putem spune că este aproape imposibil. Atunci apare întrebarea: „De ce avem nevoie de toate acestea, dau abracadabra de neînțeles, care încă nu poate fi descifrată?”. Acest lucru va fi discutat în acest articol.

Ce este o funcție hash și cum funcționează?

Această funcție este concepută pentru a transforma datele primite în orice fel marime mareîntr-un rezultat de lungime fixă. Procesul unei astfel de transformări se numește hashing, iar rezultatul se numește hash sau cod hash. Uneori sunt folosite și cuvintele „amprentă” sau „rezumat mesaj”, dar în practică sunt mult mai puțin frecvente. Există mulți algoritmi diferiți pentru cum puteți transforma orice matrice de date într-o anumită secvență de caractere de o anumită lungime. Cel mai utilizat algoritm se numește md5, care a fost dezvoltat încă din 1991. În ciuda faptului că astăzi md5 este oarecum învechit și nu este recomandat pentru utilizare, este încă în uz și adesea în loc de cuvântul „cod hash”, site-urile pur și simplu scriu md5 și indică codul în sine.

De ce este necesară o funcție hash?

Cunoscând rezultatul, este aproape imposibil să se determine datele originale, dar aceleași date de intrare dau același rezultat. Prin urmare, funcția hash (numită și funcție de convoluție) este adesea folosită pentru a stoca foarte Informații importante, cum ar fi parola, autentificarea, numărul de identificare și alte informații personale. În loc să compare informațiile introduse de utilizator cu ceea ce este stocat în baza de date, hashurile lor sunt comparate. Acest lucru asigură că, în cazul unei scurgeri accidentale de informații, nimeni nu va putea folosi datele importante în propriile scopuri. Prin compararea codului hash, este, de asemenea, convenabil să verificați corectitudinea descărcării fișierelor de pe Internet, mai ales dacă au existat întreruperi de comunicare în timpul descărcării.

Funcții hash: ce sunt T

O funcție hash poate fi unul din trei tipuri, în funcție de scopul ei:

1. Funcție de verificare a integrității informațiilor

Când se face prin rețea, hash-ul pachetului este calculat și acest rezultat este transmis și el împreună cu fișierul. La primire, codul hash este din nou calculat și comparat cu valoarea primită în rețea. Dacă codul nu se potrivește, atunci aceasta indică erori, iar pachetul corupt va fi transmis din nou. O astfel de funcție are o viteză rapidă de calcul, dar un număr mic de valori hash și o stabilitate slabă. Un exemplu de acest tip este CRC32, care are doar 232 de valori distincte.

2. Funcția criptografică

Folosit pentru a proteja împotriva (ND). Acestea vă permit să verificați dacă datele au fost corupte ca urmare a ND în timpul transferului de fișiere prin rețea. Hash-ul adevărat în acest caz este disponibil public, iar hash-ul fișierului rezultat poate fi calculat folosind setul diferite programe. Astfel de funcții au o viață lungă și stabilă, iar căutarea coliziunilor (posibile potriviri ale rezultatului din diferite date surse) este foarte complicată. Aceste funcții sunt folosite pentru a stoca parolele (SH1, SH2, MD5) și alte informații valoroase în baza de date.

3. O funcție concepută pentru a crea o structură de date eficientă

Scopul său este de a organiza informațiile într-o manieră compactă și destul de ordonată într-o structură specială numită tabel hash. Un astfel de tabel vă permite să adăugați informații noi, să eliminați informații și să căutați datele dorite la o viteză foarte mare.

hashing la rezolvarea problemelor în C++.

Procesul de căutare a datelor în volume mari de informații necesită timp, ceea ce se datorează necesității de a vizualiza și compara un număr semnificativ de elemente cu cheia de căutare. Căutarea poate fi scurtată prin localizarea ferestrei de vizualizare. De exemplu, sortați datele după cheia de căutare, împărțiți-le în blocuri care nu se suprapun în funcție de un atribut de grup sau potriviți datele reale cu un cod care va simplifica procedura de căutare.

O metodă utilizată pe scară largă este în prezent utilizată acces rapid la informațiile stocate în memorie externa- hashing.

Hashing(sau hashing, Engleză hashing) este transformarea unei matrice de date de intrare de un anumit tip și lungime arbitrară într-un șir de biți de ieșire cu o lungime fixă. Astfel de transformări mai sunt numite funcții hash sau funcții de convoluție, iar rezultatele lor sunt numite hash, hash code, hash table sau digera mesaje (engleză) rezumatul mesajului).

Tabel de hash- acest structură de date, care implementează interfața unui tablou asociativ, adică vă permite să stocați perechi cheie-valoare și să efectuați trei operații: operația de adăugare a unei noi perechi, operația de căutare și operația de ștergere a unei perechi cu cheie. Un tabel hash este un tablou format într-o anumită ordine de o funcție hash.

• funcția trebuie să fie simplă din punct de vedere computațional;
• funcția ar trebui să distribuie cheile în tabelul hash cât mai uniform posibil;
• funcția nu trebuie să mapeze nicio relație între valorile cheii cu o relație între valorile adresei;
• funcția ar trebui să minimizeze numărul de coliziuni - adică situații în care diferite chei corespund unei valori hash (cheile în acest caz sunt numite sinonime).

În acest caz, prima proprietate a unei bune funcții hash depinde de caracteristicile computerului, iar a doua depinde de valorile datelor.

Dacă toate datele ar fi aleatorii, atunci funcțiile hash ar fi foarte simple (cum ar fi câțiva biți dintr-o cheie). Cu toate acestea, în practică, datele aleatoare sunt destul de rare și trebuie să creați o funcție care ar depinde de întreaga cheie. Dacă funcția hash distribuie populația chei posibile uniform peste setul de indici, apoi hashingul împarte efectiv setul de chei. Cel mai rău caz este atunci când toate cheile sunt indexate într-un singur index.

Când apar coliziuni, este necesar să găsiți un nou loc pentru a stoca cheile care revendică aceeași celulă de tabel hash. În plus, dacă coliziunile sunt permise, atunci numărul acestora trebuie redus la minimum. În unele cazuri speciale este posibil să se evite complet coliziunile. De exemplu, dacă toate cheile elementului sunt cunoscute în avans (sau se schimbă foarte rar), atunci pentru ele este posibil să găsim o funcție hash injectivă care le va distribui printre celulele tabelului hash fără coliziuni. Tabelele hash care utilizează funcții hash similare nu au nevoie de un mecanism de rezoluție a coliziunilor și sunt numite tabele hash cu adresare directă.

Tabelele hash trebuie să se potrivească cu următoarele proprietăți.

• Executarea unei operații într-un tabel hash începe cu calcularea funcției hash a tastei. Valoarea hash rezultată este un index în tabloul original.
• Se numește numărul de elemente de matrice stocate împărțit la numărul de valori hash posibile factor de umplere a tabelului hash (factor de încărcare) si este parametru important, care determină timpul mediu de execuție al operațiunilor.
• Operațiunile de căutare, inserare și ștergere ar trebui să dureze în medie O(1). Cu toate acestea, această estimare nu ține cont de posibilele costuri hardware ale reconstrucției indexului tabelului hash asociat cu creșterea valorii dimensiunii matricei și adăugarea unei noi perechi la tabelul hash.
• Mecanismul de rezoluție a coliziunilor este o parte importantă a oricărui tabel hash.

Hashingul este util atunci când o gamă largă de valori posibile trebuie să fie stocată într-o cantitate mică de memorie și este nevoie de o metodă de acces rapid, aproape aleatoriu. Tabelele hash sunt adesea folosite în bazele de date și mai ales în procesoare de limbaj cum ar fi compilatoarele și asamblatorii în care cresc viteza de procesare a tabelului de identificatori. Ca o utilizare a hashing-ului Viata de zi cu zi putem da exemple de repartizarea cărților în bibliotecă după cataloage tematice, ordonarea în dicționare după primele litere ale cuvintelor, criptarea specialităților în universități etc.

Metode de rezolvare a coliziunilor

Coliziunile complică utilizarea tabelelor hash, deoarece întrerup corespondența unu-la-unu dintre codurile hash și date. Cu toate acestea, există modalități de a depăși dificultățile care apar:

• metoda lanțului (hashing extern sau deschis);
• metoda de adresare deschisă (hashing închis).

Metoda lanțului. Tehnologia de cuplare a elementelor este aceea elemente de set, care corespund aceluiași valoare hash, sunt legate într-o listă de lanț. Numărul de poziție i stochează un pointer către capul listei acelor elemente a căror valoare hash a cheii este egală cu i ; daca nu exista astfel de elemente in multime, in pozitia i se scrie NULL. Pe fig. 38.1 demonstrează implementarea metodei lanțurilor în rezolvarea coliziunilor. Cheia 002 este revendicată de două valori, care sunt organizate într-o listă liniară.

Orez. 38.1.

Fiecare celulă de matrice este un pointer către o listă (lanț) legată de perechi cheie-valoare corespunzătoare aceleiași valori hash cheie. Ciocnirile au ca rezultat pur și simplu lanțuri care sunt mai lungi decât un element.

Operațiunile de căutare sau ștergere a datelor necesită căutarea tuturor elementelor lanțului corespunzător pentru a găsi un element cu o anumită cheie în el. Pentru a adăuga date, trebuie să adăugați un element la sfârșitul sau începutul listei corespunzătoare și, dacă factorul de umplere devine prea mare, măriți dimensiunea matricei și reconstruiți tabelul.

Presupunând că fiecare element poate cădea în orice poziție a tabelului cu probabilitate egală și indiferent de unde a ajuns orice alt element,

Hashingul este o metodă specială de adresare a datelor (un fel de algoritm de spațiere) prin cheile lor unice ( cheie ) pentru a găsi rapid informațiile de care aveți nevoie.

Noțiuni de bază

Tabel de hash

Un tabel hash este o matrice obișnuită cu o adresă specială dată de o anumită funcție (funcția Hash).

funcția hash

O funcție care convertește cheia unui element de date într-un index dintr-un tabel ( masa hash), se numește funcția hash sau funcția hash :

i = h (cheie );

Unde cheie- cheie convertibila, i- indicele tabelului rezultat, i.e. cheia este afișată într-un set de, de exemplu, numere întregi ( adrese hash ), care sunt ulterior folosite pentru a accesa datele.

Hashingul în acest fel este o tehnică care presupune utilizarea valorii unei chei pentru a determina poziția acesteia într-un tabel special.

Cu toate acestea, funcția de răspândire poate mai multe valorile cheilor unice dau aceeași valoare de poziție i în tabelul hash. Este apelată situația în care două sau mai multe chei primesc același index (adresă hash). coliziune (coliziune) în hashing.De aceea, schema de hashing trebuie să includă algoritm de rezolvare a conflictelor , definind ordinea actiunilor, daca pozitia i=h(cheie) este deja ocupată de o intrare cu o cheie diferită.

Există multe scheme de hashing care diferă în funcție de funcția de hash utilizată. h(cheie) și algoritmi de rezolvare a conflictelor.

Cea mai comună metodă de specificare a unei funcții hash este: metoda diviziunii.

Datele inițiale sunt: ​​- o cheie întreagă cheieși dimensiunea mesei m. Rezultatul acestei funcții este restul împărțirii acestei chei la dimensiunea tabelului. Forma generală a unei astfel de funcții în limbajul de programare C/C++:

int h (int cheie , int m ) {

Pentru m= 10 funcția hash returnează cifra cea mai puțin semnificativă a tastei.

Pentru m=100, funcția hash returnează cele două cifre cele mai puțin semnificative ale cheii.

În exemplele luate în considerare, funcția hash i=h(cheie) definește doar poziția din care să căutați (sau să plasați inițial în tabel) intrarea cu cheia cheie. Apoi, trebuie să utilizați un fel de schemă de hashing (algoritm).

Scheme de hashing

În majoritatea problemelor, două sau mai multe chei sunt indexate în același mod, dar nu pot ocupa aceeași celulă în tabelul hash. Sunt două opțiuni posibile: fie găsiți o poziție diferită pentru noua cheie, fie creați o listă separată pentru fiecare index de tabel hash, în care sunt plasate toate cheile mapate la acest index.

Aceste variante sunt cele două scheme clasice de hashing:

hashing prin adresare deschisă cu sondare liniară - liniar sondă deschis adresarea.

hashing în lanț (cu liste) sau așa-numitul hashing multidimensional - înlănţuire cu separa liste;

Metoda de adresare deschisă cu sondare liniară . Inițial, toate celulele tabelului hash, care este o matrice unidimensională normală, sunt marcate ca neocupate. Prin urmare, la adăugarea unei chei noi, se verifică dacă celula dată este ocupată. Dacă celula este ocupată, atunci algoritmul caută într-un cerc până când există un spațiu gol („adresă deschisă”).

Acestea. elementele cu chei omogene sunt plasate lângă indicele rezultat.

În viitor, efectuând o căutare, găsiți mai întâi poziția cu ajutorul tastei iîn tabel, iar dacă cheia nu se potrivește, atunci căutarea ulterioară se efectuează în conformitate cu algoritmul de rezolvare a conflictului, începând de la poziția i. .

Metoda lanțului este strategia dominantă . În acest caz i obţinut din funcţia hash selectată h(cheie)=i, este tratat ca un index într-un tabel hash de liste, de ex. mai întâi cheia cheie următoarea intrare este mapată la poziție i = h(cheie) Mese. Dacă poziția este liberă, atunci elementul cu cheia este plasat în ea. cheie, dacă este ocupat, atunci se elaborează un algoritm de rezolvare a conflictelor, în urma căruia astfel de chei sunt plasate într-o listă care începe la i-acea celula a tabelului hash. De exemplu

Ca rezultat, avem un tabel cu o serie de liste sau arbori legate.

Procesul de populare (citire) a unui tabel hash este simplu, dar accesarea elementelor necesită următoarele operații:

Calculul indicelui i;

Căutați în lanțul corespunzător.

Pentru a îmbunătăți căutarea atunci când adăugați un element nou, puteți utiliza algoritmul de inserare nu la sfârșitul listei, ci cu ordonare, adică adăugați elementul la locul potrivit.

Un exemplu de implementare a metodei de adresare directă cu sondare liniară . Datele inițiale sunt 7 înregistrări (pentru simplitate, partea informațională este formată doar din date întregi), de tip structural declarat:

intkey; // Cheie

intinfo; // Informație

(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9); dimensiunea tabelului hash m=10.

funcția hash i=h(date) =date.cheie%10; acestea. restul după împărțirea la 10 - i.

Pe baza datelor inițiale, completăm secvenţial tabelul hash.

Trimiterea prin hash a primelor cinci chei generează diverși indecși (adrese hash):

Prima ciocnire are loc între tastele 81 și 41 - locul cu indicele 1 este ocupat. Prin urmare, ne uităm prin tabelul hash pentru a găsi cel mai apropiat spațiu liber, în acest caz este i = 2.

Următoarea cheie 79 generează, de asemenea, o coliziune: poziția 9 este deja ocupată. Eficiența algoritmului scade brusc, deoarece a fost nevoie de 6 încercări (comparații) pentru a găsi un loc liber, indexul s-a dovedit a fi liber i= 4.

Numărul total de mostre ale acestei metode este de la 1 la n-1 eșantioane per element, unde n este dimensiunea tabelului hash.

Implementarea metodei de înlănțuire pentru exemplul anterior. Declaram un tip structural pentru un element de lista (unidirectional):

intkey; // Cheie

intinfo; // Informație

zap*Next; // Indicator la următorul element din listă

Pe baza datelor inițiale, completăm secvenţial tabelul hash, adăugând un nou element la sfârșitul listei dacă locul este deja ocupat.

Trimiterea prin hash a primelor cinci chei, ca în cazul precedent, oferă indici diferiți (adrese hash): 9, 0, 6, 1 și 3.

Când are loc o coliziune, noul element este adăugat la sfârșitul listei. Prin urmare, elementul cu cheia 41 este plasat după elementul cu cheia 81, iar elementul cu cheia 79 este plasat după elementul cu cheia 59.

Sarcini individuale

1. Arbori binari. Folosind programul generator de numere aleatoare, obțineți 10 valori de la 1 la 99 și construiți un arbore binar.

Faceți un ocol:

1.a Traversare de la stânga la dreapta: Stânga-Rădăcină-Dreapta: vizitați mai întâi subarborele din stânga, apoi rădăcina și, în final, subarborele din dreapta.

(Sau invers, de la dreapta la stânga: Dreapta-Rădăcină-Stânga)

1.b Traversare de sus în jos: Rădăcină-Stânga-Dreapta: vizitați rădăcina subarborilor.

1.în Traversare de jos în sus: Stânga-Dreapta-Rădăcină: vizitați rădăcina după subarbori

Adnotare: În această prelegere, conceptul de funcție hash este formulat și, de asemenea, dat scurtă recenzie algoritmi de generare a funcției hash. În plus, se ia în considerare posibilitatea utilizării algoritmilor de criptare bloc pentru a forma o funcție hash.

Scopul prelegerii: să se familiarizeze cu conceptul de „funcție hash”, precum și cu principiile de funcționare a unor astfel de funcții.

Conceptul de funcție hash

Funcția hash (funcția hash) este o funcție matematică sau de altă natură care, pentru un șir de lungime arbitrară, calculează o valoare întreagă sau un alt șir de lungime fixă. Din punct de vedere matematic, aceasta poate fi scrisă astfel:

unde M este mesajul original, uneori numit prototip, iar h este rezultatul, numit valoare hash (și, de asemenea cod hash sau rezumatul mesajului(din engleza. rezumatul mesajului)).

Semnificația funcției hash este de a determina trăsătura caracteristică a prototipului - valoarea funcției hash. Această valoare are de obicei o anumită marime fixa, de exemplu, 64 sau 128 de biți. Codul hash poate fi analizat în continuare pentru a rezolva o problemă. Deci, de exemplu, hashingul poate fi folosit pentru a compara datele: dacă două matrice de date au coduri hash diferite, matricele sunt garantate să difere; dacă sunt aceleași, matricele sunt cel mai probabil aceleași. În cazul general, nu există o corespondență unu-la-unu între datele sursă și codul hash datorită faptului că numărul de valori ale funcției hash este întotdeauna mai mic decât opțiunile de date de intrare. Prin urmare, există multe mesaje de intrare care dau aceleași coduri hash (astfel de situații sunt numite ciocniri). Probabilitatea de coliziuni joacă un rol important în evaluarea calității funcțiilor hash.

Funcțiile hash sunt utilizate pe scară largă în criptografia modernă.

Cea mai simplă funcție hash poate fi compusă folosind operația sum modulo 2, după cum urmează: obțineți șirul de intrare, adăugați toți octeții modulo 2 și returnați octetul rezultat ca valoare a funcției hash. Lungimea valorii hash în acest caz va fi de 8 biți, indiferent de dimensiunea mesajului de intrare.

De exemplu, lăsați mesajul original tradus în vizualizare digitală, a fost următorul (în hexazecimal):

Să traducem mesajul în formă binară, să scriem octeții unul sub altul și să adăugăm biții din fiecare coloană modulo 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Rezultatul (0110 0101 (2) sau 65 (16) ) va fi valoarea hash.

Cu toate acestea, o astfel de funcție hash nu poate fi utilizată în scopuri criptografice, de exemplu, pentru a forma semnatura electronica, deoarece este destul de ușor să schimbați conținutul unui mesaj semnat fără a modifica valoarea sumei de control.

Prin urmare, funcția hash considerată nu este potrivită pentru aplicații criptografice. În criptografie, o funcție hash este considerată bună dacă este dificil să se creeze două preimagini cu aceeași valoare hash și, de asemenea, dacă rezultatul funcției nu depinde în mod explicit de intrare.

Să formulăm cerințele de bază pentru funcțiile hash criptografice:

• funcția hash trebuie să fie aplicabilă unui mesaj de orice dimensiune;
• calculul valorii funcției ar trebui să fie suficient de rapid;
• având în vedere valoarea funcției hash, ar trebui să fie dificil (practic imposibil) să găsiți o pre-imagine adecvată a lui M ;
• dat fiind mesajul M, ar trebui să fie dificil să găsești un alt mesaj M' cu aceeași valoare hash ca și mesajul original;
• trebuie să fie greu să găsești vreo pereche de mesaje distincte aleatoriu cu aceeași valoare hash.

Crearea unei funcții hash care să îndeplinească toate aceste cerințe nu este o sarcină ușoară. De asemenea, trebuie amintit că intrarea funcției este date de dimensiuni arbitrare, iar rezultatul hash nu ar trebui să fie același pentru date de dimensiuni diferite.

În prezent, în practică, ca funcții hash, sunt utilizate funcții care procesează mesajul de intrare bloc cu bloc și calculează valoarea hash h i pentru fiecare bloc M i al mesajului de intrare în funcție de dependențele formei

h i =H(M i ,h i-1),

unde h i-1 este rezultatul obținut la calcularea funcției hash pentru blocul anterior de date de intrare.

Ca rezultat, ieșirea funcției hash h n este o funcție a tuturor n blocuri ale mesajului de intrare.

Utilizarea algoritmilor de criptare bloc pentru a forma o funcție Hash

Puteți utiliza o funcție hash de bloc. Dacă algoritmul de bloc utilizat este sigur din punct de vedere criptografic, atunci funcția hash bazată pe acesta va fi de încredere.

Cel mai simplu mod de a utiliza algoritmul de blocare pentru a obține un cod hash este criptarea mesajului în modul CBC. În acest caz, mesajul este reprezentat ca o secvență de blocuri, a căror lungime este egală cu lungimea blocului algoritmului de criptare. Dacă este necesar, ultimul bloc este captusit în dreapta cu zerouri pentru a obține un bloc de lungimea dorită. Valoarea hash va fi ultimul bloc de text criptat. Dacă se utilizează un algoritm puternic de criptare bloc, valoarea hash rezultată va avea următoarele proprietăți:

• este practic imposibil să se calculeze o valoare hash pentru o anumită matrice deschisă de informații fără a cunoaște cheia de criptare;
• este practic imposibil fără cunoașterea cheii de criptare pentru a selecta datele deschise sub valoarea stabilită funcții hash.

Valoarea hash astfel formată este de obicei numită inserție de imitație sau autentificatorși este folosit pentru a verifica integritatea mesajului. Astfel, o inserție de imitație este o combinație de control care depinde de datele deschise și informațiile cheii secrete. Scopul utilizării imitațiilor de inserție este de a detecta toate modificările accidentale sau intenționate ale șirului de informații. Valoarea obținută de funcția hash la procesarea mesajului de intrare este atașată mesajului în momentul în care se știe că mesajul este corect. Receptorul verifică integritatea mesajului calculând simulacul de inserare a mesajului primit și comparându-l cu codul hash primit, care trebuie transmis în mod sigur. Una dintre acestea căi sigure poate fi criptarea uzurparei identității cu cheia privată a expeditorului, de ex. crearea unei semnături. De asemenea, este posibilă criptarea codului hash primit cu un algoritm de criptare simetrică dacă expeditorul și destinatarul au o cheie de criptare simetrică comună.

Procesul specificat de obținere și utilizare a unei inserții de imitație este descris în standardul intern GOST 28147-89. Standardul propune utilizarea celor 32 de biți inferiori ai blocului obținuți la ieșirea operației de criptare a întregului mesaj în modul de înlănțuire a blocurilor de criptare pentru a controla integritatea mesajului transmis. În același mod, pentru a forma o inserție simulată, puteți folosi orice bloc algoritm de criptare simetric.

Alte cale posibilă Aplicarea unui cifru bloc pentru a genera un cod hash este următoarea. Mesajul original este procesat secvenţial în blocuri. Ultimul bloc, dacă este necesar, este umplut cu zerouri, uneori lungimea mesajului sub forma unui număr binar este atribuită ultimului bloc. În fiecare etapă, criptăm valoarea hash obținută în etapa anterioară, luând ca cheie blocul de mesaj curent. Ultima valoare criptată primită va fi rezultatul hash final.

De fapt, sunt posibile mai multe scheme pentru utilizarea unui cifru bloc pentru a forma o funcție hash. Fie M i blocul mesajului original, hi este valoarea funcției hash la etapa i-a, f este algoritmul de criptare a blocurilor utilizat în modul de înlocuire simplă, fie operația de adăugare modulo 2. Apoi, pentru de exemplu, sunt posibile următoarele scheme pentru generarea funcției hash:

În toate aceste scheme, lungimea valorii hash generată este egală cu lungimea blocului atunci când este criptat. Toate acestea și câteva alte scheme pentru utilizarea unui cifru bloc pentru a calcula valorile hash pot fi aplicate în practică.

Principalul dezavantaj al funcțiilor hash concepute pe baza algoritmilor bloc este viteza lor relativ scăzută. Puterea criptografică necesară poate fi atinsă și într-un număr mai mic de operații asupra datelor de intrare. Există algoritmi de hashing mai rapizi proiectați independent, de la zero, pe baza cerințelor de putere criptografică (cele mai comune dintre ei sunt MD5, SHA-1, SHA-2 și GOST R 34.11-94).

Hashing(uneori hashing, hashing englezesc) - conversia unei matrice de date de intrare de lungime arbitrară într-un șir de ieșire de lungime fixă. Astfel de transformări mai sunt numite funcții hash sau funcții de convoluție, matricea de intrare este prototip, și rezultatele transformării - hash, cod hash, imagine hash, amprentă sau rezumatul mesajului(Rezumat mesaj în engleză).

funcția hash este o funcție ușor de calculat, care convertește un mesaj inițial de lungime arbitrară (preimagine) într-un mesaj de lungime fixă ​​(imagine hash), pentru care nu există un algoritm eficient de detectare a coliziunilor.

coliziune pentru functie h se numește pereche de valori x, y, x ≠ y, astfel încât h(x) = h(y). Acea. Funcția hash trebuie să aibă următoarele proprietăți:

Pentru valoare dată h(x) nu poate găsi valoarea argumentului X. Aceste funcții hash sunt numite persistente în ceea ce privește manipularea sau persistentă în sens puternic;

Pentru argumentul dat X nu gasesc alt argument y astfel încât h(x) = h(y). Aceste funcții hash sunt numite persistente în sensul calculării coliziunilor sau persistentă în sens slab.

În cazul în care valoarea funcției hash depinde nu numai de preimagine, ci și de cheia privată, atunci această valoare se numește cod de autentificare a mesajului (Cod de autentificare a mesajelor, MAC), cod de autentificare a datelor (Codul de autentificare a datelor, DAC). ) sau inserție de imitație.

În practică, funcțiile hash sunt utilizate în următoarele scopuri:

Pentru a accelera căutarea datelor în baza de date;

Accelerează recuperarea datelor. De exemplu, atunci când scrieți câmpuri de text într-o bază de date, codul hash al acestora poate fi calculat și datele pot fi plasate într-o secțiune corespunzătoare acestui cod hash. Apoi, la căutarea datelor, va fi mai întâi necesar să se calculeze codul hash al textului și se va ști imediat în ce secțiune ar trebui căutate, adică. va fi necesar să căutați nu în întreaga bază de date, ci doar într-una dintre secțiunile acesteia (acest lucru accelerează foarte mult căutarea).

În acest caz, analogul de uz casnic al hashingului poate fi plasarea cuvintelor într-un dicționar în ordine alfabetică. Prima literă a unui cuvânt este codul lui hash, iar atunci când căutăm, nu ne uităm prin întreg dicționarul, ci doar secțiunea cu litera dorită.

Procedura de calcul ( schema standard algoritm) funcția hash este prezentată în figura următoare.

Fig.10.1. Procedura de calcul al valorii hash

1) Înapoi la postarea inițială T sunt adăugate informații auxiliare (de exemplu, lungimea preimaginei, simboluri auxiliare etc.) astfel încât lungimea preimaginei X devenit multiplu al L bl, definit de specificația (standard) a funcției hash.

2) Pentru a inițializa procedura de hashing, se folosește un mesaj de sincronizare y 0.

3) prototip X se descompune în n blocuri x i(i = 1 .. n) lungime fixă L bl, peste care se execută aceeași procedură de hashing de tip f(y i-1, x i), în funcție de rezultatul hash al blocului anterior y i-1.

4) Din punct de vedere al hashului h(T) mesaj original T va fi rezultatul procedurii de hashing y n, obtinut in urma procesarii ultimului bloc x n.

10.2. MD5

MD5(Message Digest 5) este un algoritm de hashing pe 128 de biți dezvoltat de profesorul Ronald L. Rivest de la Massachusetts Institute of Technology (MIT) în 1991. Este o versiune îmbunătățită a MD4 în ceea ce privește securitatea.

Mai jos este algoritmul de calcul hash.

1. Alinierea fluxului.

Până la sfârșitul mesajului original, lungime L, adăugați un bit, apoi numărul necesar de zero biți, astfel încât noua dimensiune L" a fost comparabil cu 448 modulo 512 (L' mod 512 = 448). Adăugarea de biți zero este efectuată chiar dacă noua lungime, inclusiv un bit, este deja comparabilă cu 448.

2. Adăugarea lungimii mesajului.

O reprezentare pe 64 de biți a lungimii datelor (numărul de biți din mesaj) este atașată mesajului modificat. Acestea. lungimea mesajului T devine multiplu de 512 (T mod 512 = 0). Dacă lungimea mesajului original depășește 2 64 - 1, atunci numai cei 64 de biți inferiori sunt adăugați. În plus, pentru reprezentarea specificată a lungimii de 64 de biți, cei 32 de biți inferiori sunt scrieți mai întâi, iar apoi cei 32 de biți superiori.

3. Inițializarea bufferului.

Pentru calcule, sunt inițializate 4 variabile cu o dimensiune de 32 de biți și valorile inițiale sunt setate (reprezentare hexazecimală):

A = 67 45 23 01;
B= EF CD AB 89;
C= 98 VA DC FE;
D = 10 32 54 76.

Aceste variabile vor stoca rezultatele calculelor intermediare. Stare initiala ABCD se numește vector de inițializare.

4. Calculul hashului într-un ciclu.

Mesajul original este împărțit în blocuri T, 512 biți lungime. Pentru fiecare bloc din ciclu se efectuează procedura prezentată în Fig. 10.2. Rezultatul procesării tuturor blocurilor mesajului original ca o uniune de valori variabile pe 32 de biți ABCDși va fi un haș.

Fig.10.2. Pasul buclei principale de calcul hash

În fiecare rundă peste variabile ABCDși bloc de text sursă Tîntr-un ciclu (16 iterații), transformările de același tip sunt efectuate conform următoarei scheme.

Fig.10.3. O iterație a buclei rotunde

Denumirile conventionale.

1) RF- functie rotunda, determinata conform tabelului urmator.

Tabelul 10.1. Funcții RF rotunde

2) tj- j-a parte de 32 de biți a blocului de mesaj original T cu ordine inversă a octetilor;

3) k i- partea întreagă a constantei determinată de formulă

k i = 2 32 * | sin(i + 16 * (r - 1)) |, (10.1)

unde i este numărul de iterație al buclei (i = 1..16);
r – număr rotund (r = 1..4).

Argumentul funcției sin este măsurat în radiani.

4) ⊞ – adunare modulo 2 32 .

5) <<< s i– deplasare ciclică la stânga cu s i biți.

Porțiunea folosită pe 32 de biți a blocului de mesaj original tjși cantitatea de deplasare ciclică la stânga s i depind de numărul de iterație și sunt prezentate în tabelul următor.

Tabelul 10.2. Valori utilizate în pasul buclei rotunde

numărul de iterație		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Runda 1	tj	t1	t2	t3	t4	t5	t6	t7	t8	t9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
	s i	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
Runda 2	tj	t2	t7	t 12	t1	t6	t 11	t 16	t5	t 10	t 15	t4	t9	t 14	t3	t8	t 13
	s i	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
Runda 3	tj	t6	t9	t 12	t 15	t2	t5	t8	t 11	t 14	t1	t4	t7	t 10	t 13	t 16	t3
	s i	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
Runda 4	tj	t1	t8	t 15	t6	t 13	t4	t 11	t2	t9	t 16	t7	t 14	t5	t 12	t3	t 10
	s i	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

După 4 runde, noua valoare (modificată) a fiecăreia dintre variabile ABCD se adaugă (⊞ ) cu valoarea inițială (valoarea variabilei înainte de prima rundă).

5. Permutarea octeților în variabilele ABCD. După procesarea tuturor blocurilor mesajului original, se efectuează o schimbare inversă de octeți pentru fiecare variabilă.

Găsirea coliziunilor.

În 2004, cercetătorii chinezi Wang Xiaoyun, Feng Dengguo, Lai Xuejia și Yu Hongbo au anunțat o vulnerabilitate pe care au descoperit-o într-un algoritm care le-a permis ca IBM p690) să găsească coliziuni.

10.3. Utilizarea criptării pentru a obține o imagine Hash

Pentru a dezvolta o imagine hash rezistentă la coliziuni, pot fi utilizate moduri speciale furnizate în cifrurile bloc (de exemplu, concatenarea blocurilor de cifră y), sau în funcția hash în sine, ca parte integrantă, poate fi utilizat unul dintre modurile de cifrare bloc. (de exemplu, componenta hash -functions conform GOST 34.11-94 1 este modul de înlocuire simplă a algoritmului de conversie criptografică cu 2).

Amintiți-vă că, în cazul în care valoarea funcției hash depinde nu numai de preimagine, ci și de cheia privată, atunci imaginea hash se numește cod de autentificare a mesajului (Message Authentication Code, MAC), cod de autentificare a datelor (Data Authentication). Cod, DAC) sau inserție de imitație.

De exemplu, să luăm un mod (înlănțuire blocuri de criptare - Cipher Block Chaining).

Fig.10.4. Schema algoritmului DES în modul de înlănțuire a blocurilor de criptare

Ultimul bloc criptat C nși există o imagine hash a mesajului T = (T 1 , T 2 , …, T n ).

1 GOST 34.11-94 „Tehnologia informației. Protecția criptografică a informațiilor. funcția de hashing.

2 GOST 28147-89 „Sisteme de procesare a informațiilor. Protecție criptografică. Algoritmul de transformare criptografică”.

Întrebări pentru autoexaminare

1. Definiți conceptele: "", "", "".