Ce este un hash? O funcție hash este o transformare matematică a informațiilor într-un șir scurt de o anumită lungime.
De ce este nevoie de asta? Analiza funcției hash este adesea folosită pentru a verifica integritatea fișierelor importante sistem de operare, programe importante, date importante. Monitorizarea poate fi efectuată atât la nevoie, cât și în mod regulat.
Cum se face? Mai întâi, determinați integritatea fișierelor care trebuie controlate. Pentru fiecare fișier, valoarea hash-ului său este calculată conform unui algoritm special, iar rezultatul este salvat. După timpul necesar, se face un calcul similar și se compară rezultatele. Dacă valorile sunt diferite, atunci informațiile conținute în fișier au fost modificate.
Ce caracteristici ar trebui să aibă o funcție hash?
- trebuie să poată efectua transformări de date de lungime arbitrară într-una fixă;
- trebuie să aibă un algoritm deschis, astfel încât puterea sa criptografică să poată fi investigată;
- ar trebui să fie unilateral, adică nu ar trebui să existe o posibilitate matematică de a determina datele inițiale din rezultat;
- ar trebui să „reziste” la coliziuni, adică să nu producă aceleași valori pentru diferite date de intrare;
- nu ar trebui să necesite resurse de calcul mari;
- cu cea mai mică modificare a datelor de intrare, rezultatul ar trebui să se schimbe semnificativ.
Care sunt algoritmii de hashing populari? Următoarele funcții hash sunt utilizate în prezent:
- CRC înseamnă cod de redundanță ciclică sau sumă de control. Algoritmul este foarte simplu, are un numar mare de variaţii în funcţie de lungimea de ieşire dorită. Nu este criptografic!
- MD 5 este un algoritm foarte popular. Ca el versiunea anterioara MD 4 este o funcție criptografică. Dimensiunea hash este de 128 de biți.
- SHA -1 este, de asemenea, o funcție criptografică foarte populară. Dimensiunea hash este de 160 de biți.
- GOST R 34.11-94 este un standard criptografic rusesc pentru calcularea unei funcții hash. Dimensiunea hash este de 256 de biți.
Când poate un administrator de sistem să folosească acești algoritmi? Adesea, atunci când descărcați orice conținut, cum ar fi programe de pe site-ul producătorului, muzică, filme sau alte informații, există o valoare a sumei de control calculată folosind un anumit algoritm. Din motive de securitate, după descărcare, trebuie să calculați independent funcția hash și să comparați valoarea cu ceea ce este indicat pe site sau în atașamentul la fișier. Ai făcut asta vreodată?
Ce este mai convenabil pentru a calcula hash-ul? Acum există un număr mare de astfel de utilități, atât plătite, cât și gratuite. Mie personal mi-a plăcut HashTab. În primul rând, în timpul instalării, utilitarul este încorporat ca o filă în proprietățile fișierului, în al doilea rând, vă permite să selectați un număr mare de algoritmi de hashing și, în al treilea rând, este gratuit pentru uz privat necomercial.
Ce este rusa? După cum am menționat mai sus, în Rusia există un standard de hashing GOST R 34.11-94, care este utilizat pe scară largă de mulți producători de instrumente de securitate a informațiilor. Unul dintre aceste instrumente este programul de fixare și control. stare initiala Pachetul software FIX. Acest program este un mijloc de monitorizare a eficacității utilizării facilităților de securitate a informațiilor.
FIX (versiunea 2.0.1) pentru Windows 9x/NT/2000/XP
- Calculul sumelor de control ale fișierelor date folosind unul dintre cei 5 algoritmi implementați.
- Fixarea și controlul ulterior al stării inițiale a pachetului software.
- Comparația versiunilor de pachete software.
- Fixarea și controlul directoarelor.
- Controlul modificărilor în fișierele specificate (directoare).
- Generarea de rapoarte în formate TXT, HTML, SV.
- Produsul are certificat FSTEC conform NDV 3 Nr. 913 până la 01 iunie 2013
Și cum rămâne cu ECP? Rezultatul calculului funcției hash, împreună cu cheia secretă a utilizatorului, intră în intrarea algoritmului criptografic, unde se calculează semnătura digitală. Strict vorbind, funcția hash nu face parte din algoritmul EDS, dar adesea acest lucru este făcut intenționat, pentru a exclude un atac cu cheia publică.
În prezent, multe aplicații de comerț electronic vă permit să stocați cheia privată a utilizatorului în zona privată a jetonului (ruToken, eToken) fără fezabilitate tehnică extragandu-l de acolo. Token-ul în sine are o zonă de memorie foarte limitată, măsurată în kilobytes. Pentru a semna un document, nu există nicio modalitate de a transfera documentul în simbolul în sine, dar este foarte ușor să transferați hash-ul documentului pe token și să obțineți un EDS la ieșire.
De exemplu, putem alimenta un roman Lev Tolstoi în formă hexazecimală sau numărul 1 ca intrare într-o funcție hash de 128 de biți. Ca rezultat, în ambele cazuri vom obține seturi diferite de cifre hexazecimale pseudoaleatoare de forma: „”.
Dacă textul sursă este modificat chiar și cu un caracter, rezultatul funcției hash se schimbă complet.
Această proprietate a funcțiilor hash le permite să fie utilizate în următoarele cazuri:
- la construirea de tablouri asociative;
- când se caută duplicate într-o serie de seturi de date;
- la construirea de identificatori unici pentru seturile de date;
- la calcularea sumelor de control din date (semnal) pentru depistarea ulterioară a erorilor din acestea (survenite accidental sau introduse intenționat) care apar în timpul stocării și/sau transmiterii datelor;
- la salvarea parolelor în sistemele de protecţie sub forma unui cod hash (pentru a recupera o parolă folosind un cod hash, este necesară o funcție care este inversa funcției hash utilizată);
- la generarea unei semnături electronice (în practică, adesea nu mesajul în sine este semnat, ci „imaginea hash” a acestuia);
- si etc.
Tipuri de „funcții hash”
O funcție hash „bună” trebuie să satisfacă două proprietăți:
- calcul rapid;
- numărul minim de „coliziuni”.
Să introducem notația:
∀ k ∈ (0 ; K) : h (k)< M {\displaystyle \forall k\in (0;\,K):h(k)Un exemplu de funcție hash „rea” este o funcție cu M = 1000 (\displaystyle M=1000), care este un număr natural de zece cifre K (\displaystyle K) compară Trei cifre selectate din mijlocul pătratului de douăzeci de cifre al numărului K (\displaystyle K). S-ar părea că valorile „codurilor hash” ar trebui uniform fi distribuit între 000 " Și " 999 ", dar pentru " real» date, acest lucru este adevărat numai dacă « chei' nu au un număr „mare” de zerouri în stânga sau în dreapta.
Să luăm în considerare câteva implementări simple și fiabile ale „funcțiilor hash”.
„Funcții hash” bazate pe diviziune
1. „Cod hash” ca restul împărțirii după numărul tuturor „hash-urilor” posibile
Funcția hash poate calcula „hash” ca restul împărțirii intrării la M (\displaystyle M):
h (k) = k mod M (\displaystyle h(k)=k\mod M),Unde M (\displaystyle M)- numărul tuturor „hash-urilor” posibile (date de ieșire).
În acest caz, este evident că pentru un par M (\displaystyle M) valoarea funcţiei va fi chiar dacă k (\displaystyle k)și impar - cu impar k (\displaystyle k). De asemenea, nu trebuie folosit ca M (\displaystyle M) gradul de bază al sistemului de numere al computerului, deoarece „codul hash” va depinde numai de mai multe cifrele unui număr k (\displaystyle k) situat în dreapta, ceea ce va duce la un număr mare de ciocniri. În practică, de obicei se alege un simplu M (\displaystyle M); în majoritatea cazurilor această alegere este destul de satisfăcătoare.
2. „Cod hash” ca un set de coeficienți ai polinomului rezultat
O funcție hash poate efectua modul doi împărțirea datelor de intrare printr-un polinom. În această metodă M (\displaystyle M) trebuie să fie o putere de doi, iar cheile binare ( K = k n − 1 k n − 2 . . . k 0 (\displaystyle K=k_(n-1)k_(n-2)...k_(0))) sunt prezentate sub formă polinomiale, ca „cod hash” sunt „luate” valorile coeficienților polinom, obținut ca rest din împărțirea intrării K (\displaystyle K) la un polinom preselectat P (\displaystyle P) grade m (\displaystyle m):
K (x) mod P (x) = hm − 1 xm − 1 + ⋯ + h 1 x + h 0 (\displaystyle K(x)\mod P(x)=h_(m-1)x^(m- 1)+\dots +h_(1)x+h_(0)) h (x) = h m − 1 . . . h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0))Cu alegerea corectă P (x) (\displaystyle P(x)) garantat că nu există ciocniri între taste aproape identice.
„Funcții hash” bazate pe înmulțire
Se notează prin simbol w (\displaystyle w) numărul de numere care pot fi reprezentate printr-un cuvânt mașină. De exemplu, pentru computerele compatibile IBM PC pe 32 de biți, w = 2 32 (\displaystyle w=2^(32)).
Să alegem o constantă A (\displaystyle A) astfel încât A (\displaystyle A) a fost coprime cu w (\displaystyle w). Atunci o funcție hash care utilizează înmulțirea ar putea arăta astfel:
h (K) = [ M ⌊ A w ∗ K ⌋ ] (\displaystyle h(K)=\left)În acest caz, pe un computer cu un sistem de numere binar M (\displaystyle M) este o putere a doi și h (K) (\displaystyle h(K)) va consta din biții înalți din jumătatea dreaptă a produsului A ∗ K (\displaystyle A*K).
Printre avantajele funcțiilor hash bazate pe împărțire și înmulțire, este de remarcat utilizarea avantajoasă a non-aleatoriei cheilor reale. De exemplu, dacă cheile sunt o progresie aritmetică (de exemplu, succesiunea de nume „Nume 1”, „Nume 2”, „Nume 3”), o funcție hash care utilizează înmulțirea va mapa progresia aritmetică la o progresie aproximativ aritmetică de diferite valori hash, ceea ce va reduce numărul de coliziuni în comparație cu o situație aleatorie.
Una dintre funcțiile hash care utilizează înmulțirea este funcția hash care utilizează hashingul Fibonacci. Hashingul Fibonacci se bazează pe proprietățile raportului de aur. Ca o constantă A (\displaystyle A) aici numărul întreg cel mai apropiat de φ − 1 ∗ w (\displaystyle \varphi ^(-1)*w) si coprime cu w (\displaystyle w), Unde φ (\displaystyle \varphi ) este raportul de aur.
Hashing șiruri de lungime variabilă
Metodele de mai sus sunt aplicabile și atunci când este necesar să se ia în considerare chei formate din mai multe cuvinte sau chei de lungime variabilă.
De exemplu, puteți combina cuvinte într-unul singur folosind adăugarea modulo w (\displaystyle w) sau operația XOR. Unul dintre algoritmii care funcționează pe acest principiu este funcția hash Pearson.
Hashing universal
Metode de abordare a coliziunilor
O coliziune (uneori un conflict sau o coliziune) este un caz în care o funcție hash pentru diferite blocuri de intrare returnează aceleași coduri hash.
Metode de tratare a coliziunilor în tabelele hash
Cele mai multe dintre primele lucrări care descriu hashingul s-au ocupat de metode de tratare a coliziunilor în tabelele hash. Apoi au fost folosite funcțiile hash la căutarea textului în fișiere mari. Există două metode principale pentru a trata coliziunile în tabelele hash:
- metoda lanțului (metoda legăturii directe);
- metoda adresei deschise.
Când utilizați metoda de înlănțuire, tabelul hash stochează perechi de „listă de chei conectate” - „cod hash”. Pentru fiecare cheie, un cod hash este calculat de funcția hash; dacă codul hash a fost obținut mai devreme (pentru o altă cheie), cheia este adăugată la lista existentă de chei asociate cu codul hash; în caz contrar, o nouă pereche „listă de chei” - „cod hash” este creată, iar cheia este adăugată la lista creată. În general, dacă există N (\displaystyle N) chei și M (\displaystyle M) liste, dimensiunea medie a tabelului hash este N M (\displaystyle (\frac (N)(M))). În acest caz, la căutarea prin tabel, comparativ cu cazul în care căutarea se efectuează secvenţial, cantitatea medie de muncă va scădea cu aproximativ M (\displaystyle M) o singura data.
Când utilizați metoda de adresare deschisă, tabelul hash stochează perechile „cheie” - „cod hash”. Pentru fiecare cheie, un cod hash este calculat de funcția hash; perechea „cheie” - „codul hash” este stocată în tabel. În acest caz, la căutarea prin tabel, în comparație cu cazul în care se folosesc liste legate, nu se folosesc legături, se efectuează o enumerare secvențială a perechilor „cheie” - „cod hash”, enumerarea se oprește după cheia necesară e gasit. Secvența în care celulele unui tabel sunt scanate se numește secvență de sondă.
Sarea criptografică
Aplicarea funcțiilor hash
Funcțiile hash sunt utilizate pe scară largă în criptografie.
Hash-ul este folosit ca o cheie în multe structuri de date - tabele hash, filtre Bloom și arbori cartezieni.
Funcții hash criptografice
Printre numeroasele funcții hash existente, se obișnuiește să le evidențiem pe cele sigure din punct de vedere criptografic utilizate în criptografie, deoarece le sunt impuse cerințe suplimentare. Pentru funcția hash H (\displaystyle H) considerat sigur din punct de vedere criptografic, trebuie să satisfacă trei cerințe de bază pe care se bazează majoritatea aplicațiilor funcțiilor hash din criptografie:
Aceste cerințe nu sunt independente.
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.
În prezent, o metodă utilizată pe scară largă pentru a oferi acces rapid la informațiile stocate în memoria externă este hashingul.
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 de 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 posibile chei 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) și este un parametru important de care depinde 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. Exemple de utilizare a hashing-ului în viața de zi cu zi sunt distribuirea cărților în bibliotecă pe 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 aceleiași valori 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 elementul cu cheia dată î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,
etc.). Alegerea uneia sau alteia funcții hash este determinată de specificul problemei care se rezolvă. Cele mai simple exemple de funcții hash sunt suma de control sau CRC.
În cazul general, nu există o corespondență unu-la-unu între datele originale și codul hash. Prin urmare, există multe matrice de date care dau aceleași coduri hash - așa-numitele coliziuni. Probabilitatea de coliziuni joacă un rol important în evaluarea „calității” funcțiilor hash.
Sume de control
Algoritmi hardware simpli, extrem de rapid și ușor de implementat, utilizați pentru a proteja împotriva distorsiunilor neintenționate, inclusiv a erorilor hardware.
În ceea ce privește viteza de calcul, este de zeci și sute de ori mai rapidă decât funcțiile hash criptografice și mult mai simplă în implementarea hardware.
Prețul pentru o viteză atât de mare este lipsa puterii criptografice - o oportunitate ușoară de a potrivi un mesaj la o sumă precunoscută. De asemenea, este obișnuit ca sumele de control (număr tipic: 32 de biți) să fie mai mici decât hashurile criptografice (numerele tipice: 128, 160 și 256 de biți), ceea ce înseamnă că pot apărea coliziuni neintenționate.
Cel mai simplu caz al unui astfel de algoritm este împărțirea unui mesaj în cuvinte de 32 sau 16 biți și însumarea acestora, care este folosită, de exemplu, în TCP/IP.
De regulă, un astfel de algoritm este necesar pentru a urmări erorile hardware tipice, cum ar fi mai mulți biți eronați consecutivi până la o anumită lungime. Familia de algoritmi așa-numiți. „coduri de redundanță ciclică” îndeplinește aceste cerințe. Acestea includ, de exemplu, CRC32, utilizat în echipamentele ZIP.
Funcții hash criptografice
Printre numeroasele funcții hash existente, se obișnuiește să le evidențiem pe cele sigure criptografic utilizate în criptografie. O funcție hash puternică din punct de vedere criptografic trebuie să aibă în primul rând rezistenta la ciocniri doua tipuri:
Aplicarea hashingului
Funcțiile hash sunt, de asemenea, folosite în unele structuri de date - tabele hash și arbori cartezieni. Cerințele pentru funcția hash în acest caz sunt diferite:
- amestecare bună a datelor
- algoritm de calcul rapid
Reconcilierea datelor
În general, această aplicație poate fi descrisă ca verificarea unor informații pentru identitatea originalului, fără a utiliza originalul. Pentru verificare, se folosește valoarea hash a informațiilor care sunt verificate. Există două domenii principale ale acestei aplicații:
Eroare la verificare
De exemplu, suma de control poate fi transmisă prin canalul de comunicare împreună cu textul corpului. La capătul de recepție, suma de control poate fi recalculată și comparată cu valoarea transmisă. Dacă se găsește o discrepanță, aceasta înseamnă că transmisia a fost coruptă și poate fi solicitată o repetare.
În acest caz, un analog de uz casnic al hashingului poate fi o tehnică atunci când, la mutare, numărul de bagaje este păstrat în memorie. Apoi, pentru verificare, nu trebuie să vă amintiți despre fiecare valiză, ci doar să le numărați. Un meci ar însemna că nu s-a pierdut nicio valiză. Adică, numărul de bagaje este codul său hash.
Verificarea frazei de acces
În cele mai multe cazuri, frazele de acces nu sunt stocate pe ținte, sunt stocate doar valorile hash ale acestora. Nu este indicat să stocați fraze de acces, deoarece în cazul accesului neautorizat la un fișier cu fraze, un atacator va afla toate frazele de acces și le va putea folosi imediat, iar la stocarea valorilor hash, va învăța doar valorile hash. care nu sunt reversibile la datele originale, în acest caz, expresie de acces. În timpul procedurii de autentificare, valoarea hash a frazei de acces introduse este calculată și comparată cu cea stocată.
Exemple în acest caz sunt GNU/Linux și Microsoft Windows XP. Ele stochează numai valori hash ale frazelor de acces din conturile de utilizator.
Accelerarea recuperării 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, mai întâi va fi necesar să se calculeze codul hash al textului și se va ști imediat în ce secțiune ar trebui căutate, adică nu va fi necesară căutarea în întreaga bază de date, ci doar una dintre secțiunile sale (acest lucru accelerează foarte mult căutarea).
În acest caz, analogul de uz casnic al hashingului poate fi plasarea cuvintelor în dicționar în ordine alfabetică. Prima literă a unui cuvânt este codul său hash, iar atunci când căutăm, nu ne uităm prin întregul dicționar, ci doar litera dorită.
Lista de algoritmi
- SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
- RIPEMD-160
- RIPEMD-320
- Snefru
- Tigru (Vârtej
- Sumă de verificare IP Internet (RFC 1071)
Legături
Fundația Wikimedia. 2010 .
Vedeți ce este „funcția Hash” în alte dicționare:
funcția hash- O funcție care, având în vedere diferite dimensiuni ale valorii de intrare, are o ieșire cu dimensiune fixă. funcția hash - Tehnologia informației în ... ... Manualul Traducătorului Tehnic Wikipedia
Un tabel hash este o structură de date care implementează o interfață matrice asociativă, și anume, 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. o pereche de ...... Wikipedia
O coliziune cu funcția hash este două blocuri de date de intrare diferite și astfel încât există coliziuni pentru majoritatea funcțiilor hash, dar pentru funcțiile hash „bune”, frecvența apariției lor este aproape de minimul teoretic. În unele cazuri speciale... Wikipedia
Hashing (uneori hashing, ing. hashing) este transformarea unei matrice de date de intrare de lungime arbitrară într-un șir de biți de ieșire de lungime fixă. Astfel de transformări sunt numite și funcții hash sau funcții de convoluție, iar rezultatele lor ... ... Wikipedia
Funcția hash Tiger dezvoltată de Ros Anderson și Eli Biham în 1995. Tiger a fost conceput pentru a rula foarte rapid pe computere pe 64 de biți. Tiger nu are restricții de brevet, poate fi folosit în mod liber ca și cu ... ... Wikipedia
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 o 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 său hash, iar atunci când căutăm, nu ne uităm prin întregul dicționar, ci doar secțiunea cu litera dorită.
Procedura de calcul (schema standard de algoritm) a funcției 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, 4 variabile cu o dimensiune de 32 de biți sunt inițializate ș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: "", "", "".
