Haš funkcije su obrazovna i naučna aktivnost anisimova vladimira viktoroviča. Algoritmi heširanja podataka

Napomena: U ovom predavanju je formulisan koncept hash funkcije, kao i kratak pregled algoritama za generisanje hash funkcija. Uz to, razmatra se mogućnost korištenja algoritama blok šifriranja za formiranje hash funkcije.

Svrha predavanja: upoznati se sa konceptom "hash funkcije", kao i sa principima takvih funkcija.

Koncept hash funkcije

Hash funkcija je matematička ili druga funkcija koja, za niz proizvoljne dužine, izračunava neku cjelobrojnu vrijednost ili neki drugi niz fiksne dužine. Matematički se može napisati ovako:

gdje je M originalna poruka, koja se ponekad naziva prototip a h je rezultat koji se zove heš vrijednost (i također hash code ili digest poruke(sa engleskog. sažetak poruke)).

Značenje hash funkcije je da odredi karakterističnu osobinu predslike - vrijednost hash funkcije. Ova vrijednost obično ima određenu fiksnu veličinu, kao što je 64 ili 128 bita. Haš kod se može dalje analizirati kako bi se riješio bilo koji problem. Tako se, na primjer, heširanje može koristiti za poređenje podataka: ako dva niza podataka imaju različite hash kodove, garantirano je da su nizovi različiti; ako su isti, nizovi su najvjerovatnije isti. U opštem slučaju, ne postoji korespondencija jedan-na-jedan između originalnih podataka i hash koda zbog činjenice da je broj vrijednosti hash funkcija uvijek manji od broja varijanti ulaznih podataka. Stoga postoji mnogo ulaznih poruka koje daju iste hash kodove (takve situacije se nazivaju sudara). Vjerovatnoća kolizija igra važnu ulogu u procjeni kvaliteta hash funkcija.

Hash funkcije se široko koriste u modernoj kriptografiji.

Najjednostavnija hash funkcija se može konstruirati korištenjem operacije "suma modulo 2" na sljedeći način: dobijamo ulazni niz, dodajemo sve bajtove po modulu 2 i vraćamo rezultat bajta kao vrijednost hash funkcije. Dužina heš vrijednosti u ovom slučaju će biti 8 bita, bez obzira na veličinu ulazne poruke.

Na primjer, pretpostavimo da je originalna digitalizirana poruka bila sljedeća (u heksadecimalnom formatu):

Prevedimo poruku u binarni oblik, napišemo bajtove jedan ispod drugog i dodamo bitove u svaku kolonu po modulu 2:

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

Rezultat (0110 0101 (2) ili 65 (16)) će biti vrijednost hash funkcije.

Međutim, takva hash funkcija ne može se koristiti u kriptografske svrhe, na primjer, za generiranje elektronskog potpisa, jer je vrlo lako promijeniti sadržaj potpisane poruke bez promjene vrijednosti kontrolnog zbroja.

Stoga, razmatrana hash funkcija nije prikladna za kriptografske aplikacije. U kriptografiji, hash funkcija se smatra dobrom ako je teško stvoriti dvije predslike s istom hash vrijednošću, kao i ako izlaz funkcije eksplicitno ne ovisi o ulazu.

Formulirajmo osnovne zahtjeve za kriptografske hash funkcije:

• hash funkcija mora biti primjenjiva na poruke bilo koje veličine;
• izračunavanje vrijednosti funkcije treba obaviti dovoljno brzo;
• sa poznatom vrijednošću hash funkcije, trebalo bi biti teško (gotovo nemoguće) pronaći odgovarajuću predsliku M;
• sa poznatom porukom M, trebalo bi da bude teško pronaći drugu poruku M 'sa istom heš vrednošću kao originalna poruka;
• trebalo bi biti teško pronaći bilo koji par nasumičnih različitih poruka sa istom hash vrijednošću.

Kreiranje hash funkcije koja zadovoljava sve ove zahtjeve nije lak zadatak. Također treba imati na umu da se podaci proizvoljne veličine primaju na ulaz funkcije, a rezultat heširanja ne bi trebao biti isti za podatke različitih veličina.

Trenutno se u praksi koriste funkcije kao hash funkcije koje obrađuju ulaznu poruku blok po blok i izračunavaju hash vrijednost h i za svaki blok M i ulazne poruke prema zavisnostima oblika

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

gdje je h i-1 rezultat dobiven pri izračunavanju hash funkcije za prethodni blok ulaznih podataka.

Kao rezultat toga, izlaz hash funkcije h n je funkcija svih n blokova ulazne poruke.

Korištenje algoritama za šifriranje blokova za generiranje hash funkcije

Možete koristiti blok hash funkciju kao hash funkciju. Ako je korišteni blok algoritam kriptografski siguran, tada će i hash funkcija zasnovana na njemu također biti pouzdana.

Najjednostavniji način korištenja blok algoritma za dobivanje hash koda je šifriranje poruke u CBC modu. U ovom slučaju, poruka je predstavljena kao niz blokova čija je dužina jednaka dužini bloka algoritma šifriranja. Ako je potrebno, zadnji blok se nadopunjava s desne strane nulama kako bi se dobio blok željene dužine. Heš vrijednost će biti posljednji šifrirani blok teksta. Pod uslovom da se koristi pouzdan algoritam za šifrovanje bloka, rezultujuća heš vrednost će imati sledeća svojstva:

• praktično je nemoguće bez poznavanja ključa za šifrovanje izračunati heš vrijednost za dati otvoreni niz informacija;
• praktično je nemoguće odabrati otvorene podatke za datu vrijednost hash funkcije bez poznavanja ključa za šifriranje.

Heš vrijednost formirana na ovaj način se obično naziva umetak imitacije ili autentifikator i koristi se za provjeru integriteta poruke. Dakle, lažno predstavljanje umetanja je kontrolna kombinacija koja ovisi o otvorenim podacima i informacijama tajnog ključa. Svrha korištenja simuliranog umetanja je otkrivanje svih slučajnih ili namjernih promjena u nizu informacija. Vrijednost dobivena hash funkcijom prilikom obrade ulazne poruke dodaje se poruci u trenutku kada se zna da je poruka ispravna. Primalac provjerava integritet poruke tako što izračunava lažno predstavljanje primljene poruke i upoređuje je sa primljenim hash kodom, koji se mora prenijeti na siguran način. Jedna od takvih sigurnih metoda može biti šifriranje lažnog predstavljanja privatnim ključem pošiljaoca, tj. kreiranje potpisa. Također je moguće šifrirati primljeni hash kod simetričnim algoritmom šifriranja ako pošiljatelj i primalac imaju zajednički simetrični ključ za šifriranje.

Navedeni postupak za dobivanje i korištenje simuliranog umetka opisan je u domaćem standardu GOST 28147-89. Standard predlaže korištenje najmanje značajnih 32 bita bloka primljenog na izlazu operacije šifriranja cijele poruke u načinu spajanja blokova šifre za kontrolu integriteta poslane poruke. Na isti način, da biste formirali simulirani umetak, možete koristiti bilo koji blok simetrični algoritam šifriranja.

Drugi mogući način korištenja blok šifre za generiranje hash koda je sljedeći. Originalna poruka se obrađuje sekvencijalno u blokovima. Zadnji blok je dopunjen nulama, ako je potrebno, ponekad se dužina poruke dodaje posljednjem bloku kao binarni broj. U svakoj fazi šifriramo heš vrijednost dobivenu u prethodnoj fazi, uzimajući trenutni blok poruke kao ključ. Posljednja primljena šifrirana vrijednost bit će konačni rezultat heširanja.

U stvari, postoji još nekoliko mogućih shema za korištenje blok šifre za formiranje hash funkcije. Neka je M i - blok originalne poruke, hi - vrijednost hash funkcije u i-toj fazi, f - algoritam šifriranja bloka koji se koristi u načinu jednostavne zamjene, - operacija sabiranja po modulu 2. Zatim, za na primjer, moguće su sljedeće šeme za formiranje hash funkcije:

U svim ovim šemama, dužina generirane heš vrijednosti jednaka je dužini šifriranog bloka. Sve ove, kao i neke druge šeme za korišćenje algoritma blok šifrovanja za izračunavanje heš vrednosti, mogu se primeniti u praksi.

Glavni nedostatak hash funkcija dizajniranih na bazi blok algoritama je relativno mala brzina rada. Potrebna kriptografska snaga može se postići manjim brojem operacija na ulaznim podacima. Postoje brži algoritmi za heširanje, dizajnirani samostalno, od nule, na osnovu zahtjeva kriptografske snage (najčešći od njih su MD5, SHA-1, SHA-2 i GOST R 34.11-94).

itd.). Izbor određene hash funkcije određen je specifičnostima problema koji se rješava. Najjednostavniji primjeri hash funkcija su kontrolni zbroj ili CRC.

U opštem slučaju, ne postoji korespondencija jedan-na-jedan između originalnih podataka i hash koda. Stoga postoji mnogo nizova podataka koji daju iste hash kodove - takozvane kolizije. Vjerovatnoća kolizija igra važnu ulogu u procjeni "kvaliteta" hash funkcija.

Kontrolne sume

Nekomplikovano, izuzetno brzo i lako implementirano u hardverske algoritme koji se koriste za zaštitu od nenamjernog izobličenja, uključujući hardverske greške.

Što se tiče brzine računanja, desetine i stotine puta je brža od kriptografskih hash funkcija i mnogo jednostavnija u hardverskoj implementaciji.

Plaćanje za tako veliku brzinu je nedostatak kriptografske snage - laka prilika da se poruka prilagodi unaprijed određenom iznosu. Takođe, obično je bitnost kontrolnih suma (tipičan broj: 32 bita) niža od kriptografskih heševa (tipični brojevi: 128, 160 i 256 bita), što znači mogućnost nenamjernih kolizija.

Najjednostavniji slučaj takvog algoritma je podjela poruke na 32- ili 16-bitne riječi i njihovo sabiranje, što se koristi, na primjer, u TCP / IP.

Tipično, takav algoritam je potreban za praćenje tipičnih hardverskih grešaka, kao što je nekoliko uzastopnih bitova greške do date dužine. Porodica algoritama tzv. "Ciklični redundantni kodovi" zadovoljavaju ove zahtjeve. To uključuje, na primjer, CRC32 koji se koristi u ZIP hardveru.

Kriptografske hash funkcije

Među mnogim postojećim hash funkcijama, uobičajeno je razlikovati kriptografski jake one koje se koriste u kriptografiji. Kriptografski jaka hash funkcija prije svega mora imati otpornost na sudar dvije vrste:

Korišćenje heširanja

Hash funkcije se također koriste u nekim strukturama podataka kao što su hash tablice i kartezijanska stabla. Zahtjevi za hash funkciju u ovom slučaju su različiti:

• dobro mešanje podataka
• brzi algoritam proračuna

Usklađivanje podataka

Općenito, ova aplikacija se može opisati kao provjera nekih informacija za identitet originala, bez korištenja originala. Za verifikaciju se koristi hash vrijednost informacija koje se provjeravaju. Postoje dva glavna pravca ove aplikacije:

Provjera grešaka

Na primjer, kontrolni zbroj se može prenijeti preko komunikacijskog kanala zajedno s glavnim tekstom. Na prijemnoj strani, kontrolni zbir se može ponovo izračunati i uporediti sa prenesenom vrednošću. Ako se pronađe neslaganje, to znači da je bilo izobličenja tokom prenosa i možete zatražiti ponovni pokušaj.

U ovom slučaju, kućni analog haširanja može biti tehnika kada se, prilikom kretanja, broj komada prtljage čuva u memoriji. Zatim, da biste provjerili, ne morate se sjećati svakog kofera, već ih je dovoljno prebrojati. Utakmica će značiti da nijedan kofer nije izgubljen. Odnosno, broj komada prtljaga je njegov hash kod.

Provjera šifre

U većini slučajeva, pristupne fraze se ne pohranjuju na ciljne objekte, već se pohranjuju samo njihove hash vrijednosti. Nepraktično je pohranjivati ​​pristupne fraze, jer će u slučaju neovlaštenog pristupa datoteci sa frazama napadač saznati sve pristupne fraze i moći će ih odmah koristiti, a prilikom pohranjivanja hash vrijednosti znat će samo hash vrijednosti ​​koji nisu reverzibilni u originalne podatke, u ovom slučaju, u pristupnoj frazi. Tokom postupka autentifikacije, heš vrijednost unesene šifre se izračunava i upoređuje sa pohranjenom.

Primjer u ovom slučaju je GNU / Linux OS i Microsoft Windows XP. Oni pohranjuju samo hash vrijednosti pristupnih fraza s korisničkih računa.

Ubrzavanje preuzimanja podataka

Na primjer, prilikom pisanja tekstualnih polja u bazu podataka, njihov hash kod se može izračunati i podaci se mogu smjestiti u odjeljak koji odgovara ovom hash kodu. Zatim, kada tražite podatke, prvo ćete morati izračunati hash kod teksta i odmah će se znati u kojem dijelu ih trebate tražiti, odnosno nećete morati pretraživati ​​po cijeloj bazi, već samo u jednom od njegovih odjeljaka (ovo uvelike ubrzava pretragu).

Svakodnevni analog heširanja u ovom slučaju može biti smještanje riječi u rječnik po abecednom redu. Prvo slovo riječi je njen hash kod, a prilikom pretraživanja ne pregledavamo cijeli rječnik, već samo traženo slovo.

Lista algoritama

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tigar (Whirlpool
• IP internet kontrolna suma (RFC 1071)

Linkovi

Wikimedia fondacija. 2010.

• Hashan Moheyan
• Hash kod

Pogledajte šta je "hash funkcija" u drugim rječnicima:

Hash funkcija- funkcija koja hashira niz podataka mapiranjem vrijednosti iz (veoma) velikog skupa vrijednosti u (značajno) manji skup vrijednosti. Na engleskom: Hash funkcija Vidi također: Kriptografski algoritmi Financijski ... ... Finansijski vokabular

kriptografska hash funkcija- Funkcija koja pretvara tekst proizvoljne dužine u tekst fiksne (u većini slučajeva kraće) dužine. Glavna primjena hash funkcije nalazi se u šemi digitalnog potpisa. Budući da se hash funkcija izračunava brže od digitalnog potpisa, umjesto ... ...

Jednosmjerna hash funkcija- hash funkcija, koja je računski nepovratna funkcija. Na engleskom: Jednosmjerna hash funkcija Vidi također: Kriptografski algoritmi Finansijski rječnik Finam ... Finansijski vokabular

TIGER - hash funkcija- TIGER hash funkcija, koju su razvili Ros Anderson i Eli Biham 1996. godine. TIGER hash funkcija je nova brza heš funkcija koja je dizajnirana da bude veoma brza na modernim računarima, posebno na 64-bitnim računarima. TIGAR ... ... Wikipedia

jednosmjerna hash funkcija- Za jednosmjernu funkciju, računski je nemoguće pronaći dva različita argumenta za koje su njene vrijednosti iste. [] Teme informaciona sigurnost EN jednosmjerna hash funkcija ... Vodič za tehničkog prevodioca

tigar (hash funkcija)- Tiger hash funkcija, koju su razvili Ros Anderson i Eli Biham 1995. godine. Tiger je dizajniran da radi posebno brzo na 64-bitnim računarima. Tiger nema patentnih ograničenja, može se slobodno koristiti kao sa ... ... Wikipedia

funkcija heširanja- hash funkcija 1. Funkcija koja kontrolira proces unosa podataka u hash tablicu, definirajući (adrese slobodnih ćelija. 2. Funkcija koja predstavlja mapiranje fragmenta otvorene poruke u šifrirani niz fiksne dužine. U . ... ... Vodič za tehničkog prevodioca

Hash tablica- U programiranju, hash tablica je struktura podataka koja implementira sučelje asocijativnog niza, naime, omogućava vam da pohranite parove (ključ, vrijednost) i izvršite tri operacije: operaciju dodavanja novog para, operaciju pretraživanja i operacija brisanja... Wikipedia

Hash kod- Haširanje (ponekad heširanje) pretvaranje niza ulaznih podataka proizvoljne dužine u izlazni niz bitova fiksne dužine. Takve transformacije se također nazivaju hash funkcije ili fold funkcije, a njihovi rezultati ... ... Wikipedia

Sudar funkcije hash- Kolizija heš funkcije H je dva različita ulazna bloka podataka x i y tako da je H (x) = H (y). Kolizije postoje za većinu hash funkcija, ali za "dobre" hash funkcije učestalost njihovog pojavljivanja je blizu teorijskog minimuma. U ... ... Wikipediji

Or Haš funkcija je funkcija, pretvara ulazne podatke bilo koje (obično velike) veličine u podatke fiksne veličine. Hashing(ponekad G yeshuvannya, eng. heširanje)- konverzija niza ulaznih podataka proizvoljne dužine u izlazni niz bitova fiksne dužine. Takve transformacije se još nazivaju hash funkcije ili funkcije konvolucije, a njihovi rezultati se nazivaju hash, hash kod, hash suma, ili digest poruke(eng. Sažetak poruke).

Haš funkcija se posebno koristi u strukturama podataka - hash tablicama, široko se koristi u softveru za brzo pronalaženje podataka. Hash funkcije se koriste za optimizaciju tabela i baza podataka tako što imaju iste hash vrijednosti u istim zapisima. Ovaj pristup pronalaženja duplikata je efikasan u velikim datotekama. Primjer ovog nalaza sličnih mjesta u sekvencama DNK. Kriptografska hash funkcija olakšava verifikaciju da je neki ulaz uparen sa datom heš vrednošću, ali ako je ulaz nepoznat, namerno je teško rekonstruisati ulaznu vrednost (ili ekvivalentnu alternativu) znajući pohranjenu heš vrednost. Ovo se koristi da bi se osigurao integritet prenesenih podataka i predstavlja gradivni blok za HMAC-ove, koji obezbjeđuju autentifikaciju poruke.

Hash funkcije su povezane (i često se brkaju) sa zbrojima, kontrolnim znamenkama, otiscima prstiju, randomizacijom funkcija, kodovima, ispravljanjem grešaka i šiframa. Iako se ovi koncepti u određenoj mjeri preklapaju, svaki ima svoj obim i zahtjeve i dizajniran je i optimiziran na različite načine.

Priča

Donald Knuth pripisuje prvu sistematsku ideju heširanja zaposleniku IBM-a Hansu Peteru Lohnu, koji je predložio heš u januaru 1953. godine.

Godine 1956. Arnold Dumy je u svojoj knjizi Computers and Automation prvi uveo koncept heširanja kakav većina programera danas poznaje. Duma je smatrao da je heširanje rješenje "problema s rječnikom", a također je predložio korištenje ostatka dijeljenja prostim brojem kao hash adrese.

Prvi značajan rad vezan za pretraživanje velikih datoteka bio je članak Wesleya Petersona u IBM Journal of Research and Development 1957. u kojoj je definisao otvoreno adresiranje, a takođe je ukazao na degradaciju u performansama prilikom brisanja. Šest godina kasnije objavljen je rad Wernera Buchholza, koji je u velikoj mjeri istraživao hash funkcije. U narednih nekoliko godina, heširanje je bilo naširoko korišćeno, ali nijedan značajan rad nije objavljen.

Godine 1967. heširanje u modernom smislu spominje se u knjizi Herbert Hellerman Principles of Digital Computing. Godine 1968. Robert Morris je objavio u Komunikacije ACM-a odličan pregled o heširanju. Ovaj rad se smatra publikacijom koja uvodi koncept heširanja u naučnu cirkulaciju i konačno konsoliduje pojam "haš" među stručnjacima.

Do ranih 1990-ih, ekvivalent izrazu "haširanje", zahvaljujući radovima Andreja Eršova, bila je reč "sazvežđe" u izdanju knjige Niklausa Virta "Algoritmi i strukture podataka" (1989) na ruskom jeziku. korišćeno.) Međutim, nijedna od ovih opcija nije se uhvatila, a u literaturi se uglavnom koristi termin "haširanje".

Opis

Haširanje se koristi za izgradnju asocijativnih nizova, traženje duplikata u nizu skupova podataka, izgradnju jedinstvenih identifikatora za skupove podataka, kontrolnu sumu za identifikaciju slučajnih ili namjernih grešaka tokom skladištenja ili prijenosa, za pohranjivanje lozinki u sigurnosnim sistemima (u ovom slučaju, pristup memorijsko područje " memorija, u kojoj se nalaze lozinke, ne dozvoljava vraćanje same lozinke), prilikom generisanja elektronskog potpisa (u praksi se često ne potpisuje sama poruka, već njena hash slika).

U općenitom slučaju, ne postoji korespondencija jedan-na-jedan između originalnih podataka i hash koda zbog činjenice da je broj vrijednosti hash funkcija manji od broja varijanti vrijednosti ulaza niz. Postoji mnogo nizova sa različitim sadržajem, ali daju iste hash kodove - takozvane kolizije. Vjerovatnoća kolizija igra važnu ulogu u procjeni kvaliteta hash funkcija.

Postoji mnogo algoritama za heširanje sa različitim svojstvima (dubina bita, složenost računanja, kriptografska snaga, itd.). Izbor određene hash funkcije određen je specifičnostima problema koji se rješava. Najjednostavniji primjeri hash funkcija su kontrolni zbroj ili CRC.

Vrste hash funkcija

Dobra hash funkcija mora zadovoljiti dva svojstva:

• Izračunaj brzo;
• Minimizirajte broj sudara

Recimo, radi određenosti, broj ključeva i hash funkcija imaju samo različite vrijednosti:

Primjer "loše" hash funkcije je funkcija c, koja odgovara desetocifrenim prirodnim brojem sa tri cifre odabrane iz sredine dvadesetcifrenog kvadrata broja. Čini se da bi vrijednost heš kodova trebala biti ravnomjerno raspoređena između "000" i "999", ali za stvarne podatke ova metoda je prikladna samo ako ključevi nemaju veliki broj nula s lijeve ili desne strane.

Međutim, postoji nekoliko drugih jednostavnih i pouzdanih metoda na kojima se zasnivaju mnoge hash funkcije.

Haš funkcije zasnovane na podjelu

Prva metoda je ono što koristimo kao hash - ostatak dijeljenja po, gdje je broj svih mogućih hashova:

Istovremeno, očigledno je da je sa parom način štednje uparen, sa parom. I neparan - sa neparnim, što može dovesti do značajnog pomaka u podacima u datotekama. Takođe, ne bi trebalo da koristite numerički sistem računara kao osnovu, jer će heš zavisiti od samo nekoliko cifara broja koji se nalazi desno, što će dovesti do mnogo kolizija. U praksi se obično bira onaj jednostavan - u većini slučajeva ovaj izbor je sasvim zadovoljavajući.

Treba reći i o metodi heširanja, koja se zasniva na podjeli sa log po modulu dva. U ovoj metodi također mora biti stepen dvojke, a binarni ključevi () imaju oblik polinoma. U ovom slučaju, vrijednosti koeficijenata polinoma dobivene kao ostatak dijeljenja unaprijed odabranim stepenom polinoma uzimaju se kao hash kod:

Uz pravi izbor, ova metoda garantuje da nema kolizija između gotovo identičnih ključeva.

Šema multiplikativnog heširanja

Druga metoda se sastoji u odabiru neke cjelobrojne konstante, relativno jednostavne sa, gdje je broj mogućih varijanti vrijednosti u obliku računalne riječi (u IBM PC računarima). Tada možemo uzeti hash funkciju u obliku:

U ovom slučaju, na računaru sa binarnim brojevnim sistemom, to je stepen dvojke, a sastoji se od najznačajnijih bitova desne polovine proizvoda.

Među prednostima ove dvije metode, vrijedi napomenuti da one iskorištavaju činjenicu da pravi ključevi nisu nasumični. Na primjer, ako ključevi predstavljaju aritmetičku progresiju (recimo niz imena "name1", "name2", "name3"). Multiplikativna metoda će prikazati aritmetičku progresiju u približnu aritmetičku progresiju različitih heš vrijednosti, smanjujući broj sudara u poređenju sa slučajnom situacijom.

Jedna od varijacija ove metode je Fibonačijevo heširanje, zasnovano na svojstvima zlatnog preseka. Ovdje je cijeli broj najbliži, koprost sa

Haširanje nizova promjenjive dužine

Gore navedene metode se također koriste kada trebamo uzeti u obzir ključeve koji se sastoje od nekoliko riječi ili ključeva promjenjive dužine. Na primjer, možete kombinirati riječi u jednu koristeći modulo sabiranje ili modulo 2 sabiranje. Jedan od algoritama koji radi na ovom principu je Pearsonova hash funkcija.

Pearsonovo heširanje je algoritam koji je predložio Peter Pearson. Peter Pearson) za procesore sa 8-bitnim registrima, čiji je zadatak da brzo izračunaju hash kod za niz proizvoljne dužine. Funkcija prima riječ koja se sastoji od znakova, svaki veličine 1 bajt, i vraća vrijednost u rasponu od 0 do 255. Vrijednost hash koda ovisi o svakom karakteru ulazne riječi.

Algoritam se može opisati sljedećim pseudokodom, koji uzima niz kao ulaz i koristi tablicu permutacije

h: = 0 Za svaki c in W petlja indeks: = h xor ch: = T Završna petlja Povratak h

Među prednostima algoritma treba napomenuti:

• jednostavnost izračunavanja;
• nema ulaznih podataka za koje je vjerovatnoća kolizije najveća;
• mogućnost modifikacije u idealnu hash funkciju.

Kao alternativni način heširanja ključeva koji se sastoje od simbola (), mogu se predložiti proračuni

Korištenje hash funkcija

Haš funkcije se široko koriste u kriptografiji, kao iu mnogim strukturama podataka kao što su hash tablice, Bloom filteri i kartezijanska stabla.

Kriptografske hash funkcije

Među mnogim postojećim hash funkcijama, uobičajeno je razlikovati kriptografski jake one koje se koriste u kriptografiji, jer im se nameću dodatni zahtjevi. Da bi se hash funkcija smatrala kriptografski sigurnom, mora zadovoljiti tri osnovna zahtjeva na kojima se zasniva većina upotreba hash funkcija u kriptografiji:

• Nepovratnost: za datu hash vrijednost m mora biti kompjuterski nemoguće pronaći blok podataka za koji.
• Održivost sudari prve vrste: za datu poruku M mora biti kompjuterski nemoguće pokupiti drugu poruka N za koji.
• Održivost To sudara druga vrsta: mora biti kompjuterski nemoguće pronaći par poruka koje imaju isti hash.

Ovi zahtjevi zavise jedni od drugih:

• Reverzna funkcija nije otporna na sudare prve i druge vrste.
• Funkcija koja nije otporna na sudare prve vrste, nije otporna na sudare druge vrste; obrnuto nije tačno.

Treba napomenuti da postojanje ireverzibilnih hash funkcija nije dokazano, za koje je teoretski nemoguće izračunati bilo kakvu predsliku date hash vrijednosti. Obično je pronalaženje recipročne vrijednosti samo računski težak zadatak.

Rođendanski napad vam omogućava da pronađete kolizije za hash funkciju s vrijednostima dužine n bitova u prosjeku za grubo hash računanje. Dakle n - bitna heš funkcija se smatra kriptičnom ako je računska složenost pronalaženja kolizija za nju blizu.

Za kriptografske hash funkcije također je važno da se pri najmanjoj promjeni argumenta vrijednost funkcije jako promijeni (efekat lavine). Posebno, heš vrijednost ne bi trebala propuštati informacije, čak ni o pojedinačnim bitovima argumenta. Ovaj zahtjev je ključ za kriptografsku snagu algoritama za heširanje koji heširaju korisničku lozinku za dobivanje ključa.

Haširanje se često koristi u algoritmima digitalnog potpisa, gdje nije šifrirana sama poruka, već njen hash, što smanjuje vrijeme računanja i povećava kriptografsku snagu. Također, u većini slučajeva, umjesto lozinki, pohranjuju se vrijednosti njihovih hash kodova.

Geometrijsko heširanje

Geometrijsko heširanje (eng. Geometrijsko heširanje)- metoda koja se široko koristi u kompjuterskoj grafici i računarskoj geometriji za rješavanje problema na ravni ili u trodimenzionalnom prostoru, na primjer, za pronalaženje najbližih parova u skupu tačaka ili traženje identičnih slika. Haš funkcija u ovoj metodi obično uzima metrički prostor kao ulaz i dijeli ga, stvarajući mrežu ćelija. Tabela je u ovom slučaju niz sa dva ili više indeksa i naziva se grid datoteka (eng. Grid fajl). Geometrijsko heširanje se također koristi u telekomunikacijama kada se radi o višedimenzionalnim signalima.

Ubrzavanje preuzimanja podataka

Haš tabela je struktura podataka koja vam omogućava da pohranite parove forme (ključ, hash kod) i podržava operacije za pretraživanje, umetanje i brisanje elemenata. Zadatak hash tabela je ubrzanje pretraživanja, na primjer, u slučaju zapisa u tekstualnim poljima u bazi podataka, njihov hash kod se može izračunati i podaci se mogu smjestiti u odjeljak koji odgovara ovom hash kodu. Tada će pri traženju podataka biti potrebno prvo izračunati hash teksta i odmah će se znati u kojem dijelu je potrebno pretraživati, odnosno neće biti potrebno pretraživati ​​po cijeloj bazi, već samo jedan od njegovih odjeljaka (ovo uvelike ubrzava pretragu).

Svakodnevni analog heširanja u ovom slučaju može biti smještanje riječi u rječnik po abecednom redu. Prvo slovo riječi je njen hash kod, a prilikom pretraživanja ne pregledavamo cijeli rječnik, već samo traženo slovo.

Algoritmi za heširanje nizova mogu vam pomoći da riješite mnoge probleme. Ali oni imaju veliki nedostatak: najčešće nisu 100%, jer postoji mnogo nizova čiji se hešovi podudaraju. Druga stvar je da u većini zadataka ovo možete zanemariti, jer je vjerovatnoća da se hešovi podudaraju još uvijek vrlo mala.

Hash definicija i izračun

Jedan od najboljih načina da se odredi hash funkcija iz niza S je sljedeći:

H (S) = S + S * P + S * P ^ 2 + S * P ^ 3 + ... + S [N] * P ^ N

gdje je P neki broj.

Razumno je odabrati prost broj za P, približno jednak broju znakova u ulaznoj abecedi. Na primjer, ako bi se nizovi trebali sastojati samo od malih latiničnih slova, onda bi dobar izbor bio P = 31. Ako slova mogu biti i velika i mala, onda, na primjer, možete P = 53.

Svi dijelovi koda u ovom članku će koristiti P = 31.

Poželjno je pohraniti samu heš vrijednost u najveći numerički tip - int64, aka long long. Očigledno, sa dužinom stringa od oko 20 karaktera, već će doći do prekoračenja vrijednosti. Ključna stvar je da ne obraćamo pažnju na ova prelivanja, kao da uzimamo heš po modulu 2 ^ 64.

Primjer izračunavanja heša ako su dozvoljena samo mala latinična slova:

Const int p = 31; long long hash = 0, p_pow = 1; za (veličina_t i = 0; i

U većini problema, ima smisla prvo izračunati sve potrebne snage P u nekom nizu.

Primer zadatka. Potražite duple nizove

Već smo u poziciji da efikasno riješimo ovaj problem. Dobijate listu nizova S, dužine svakog od najviše M karaktera. Recimo da želite pronaći sve duple redove i podijeliti ih u grupe tako da svaka grupa sadrži samo iste redove.

Normalnim sortiranjem stringova dobili bismo algoritam složenosti O (N M log N), dok bismo upotrebom hešova dobili O (N M + N log N).

Algoritam. Izračunajmo heš iz svake linije i sortirajmo redove prema ovom hešu.

Vector s (n); // ... čitanje nizova ... // brojanje svih potencija p, recimo, do 10000 - maksimalna dužina nizova const int p = 31; vektor p_pow (10000); p_pow = 1; za (veličina_t i = 1; i > heševi (n); za (int i = 0; i

Haš podniza i njegovo brzo računanje

Pretpostavimo da nam je dat niz S i dati indeksi I i J. Želite da pronađete heš iz podniza S.

Po definiciji imamo:

H = S [I] + S * P + S * P ^ 2 + ... + S [J] * P ^ (J-I)

H * P [I] = S [I] * P [I] + ... + S [J] * P [J], H * P [I] = H - H

Ova nekretnina je veoma važna.

Zaista, ispostavilo se da, znajući samo hešove iz svih prefiksa niza S, možemo dobiti hash bilo kojeg podniza u O (1).

Jedini problem koji se pojavljuje je da morate biti u mogućnosti podijeliti sa P [I]. U stvari, to nije tako lako. Pošto računamo heš po modulu 2 ^ 64, onda da bismo podijelili sa P [I] moramo pronaći njegov inverz u polju (na primjer, korištenjem proširenog Euklidovog algoritma), i izvršiti množenje ovim inverzom.

Međutim, postoji lakši način. U većini slučajeva, umjesto da dijelite hešove sa potencijama P, možete ih, naprotiv, pomnožiti sa ovim potencijama.

Pretpostavimo da su vam data dva heša: jedan pomnožen sa P [I], a drugi pomnožen sa P [J]. Ako ja< J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

Na primjer, kod koji izračunava hešove svih prefiksa i zatim uspoređuje dva podniza u O (1):

String s; int i1, i2, len; // ulazni podaci // brojimo sve potencije p const int p = 31; vektor i2 && h1 == h2 * p_pow) cout<< "equal"; else cout << "different";

Korišćenje heširanja

Neke tipične upotrebe za heširanje uključuju:

• Određivanje broja različitih podnizova u O (N ^ 2 log N) (vidi dolje)
• Određivanje broja palindroma unutar niza

Određivanje broja različitih podnizova

Neka je dat niz S dužine N, koji se sastoji samo od malih latiničnih slova. Želite pronaći broj različitih podnizova u ovom nizu.

Da bismo riješili, ponavljamo dužinu podniza redom: L = 1 .. N.

Za svaki L, napravićemo niz heševa podnizova dužine L, i smanjiti hešove na jedan stepen i sortirati ovaj niz. Broj različitih elemenata u ovom nizu se dodaje odgovoru.

Implementacija:

String s; // ulazni niz int n = (int) s.length (); // brojimo sve potencije p const int p = 31; vektor p_pow (s.length ()); p_pow = 1; za (veličina_t i = 1; i H (dužina ()); za (veličina_t i = 0; i hs (n-l + 1); za (int i = 0; i

Haš funkcije se koriste u širokom spektru industrija informacionih tehnologija. Namijenjeni su, s jedne strane, da u velikoj mjeri pojednostave razmjenu podataka između korisnika i obradu fajlova koji se koriste u različite svrhe, as druge da optimiziraju algoritme za osiguranje kontrole pristupa odgovarajućim resursima. Haš funkcija je jedan od ključnih alata za osiguranje lozinkom zaštite podataka, kao i organizovanje razmjene dokumenata potpisanih korištenjem EDS-a. Postoji veliki broj standarda po kojima se može izvesti keširanje datoteka. Mnoge od njih razvili su ruski stručnjaci. Koje vrste mogu imati hash funkcije? Koji su glavni mehanizmi njihove praktične primjene?

Šta je to?

Prvo, istražimo koncept hash funkcije. Ovaj termin se obično shvata kao algoritam za pretvaranje određene količine informacija u kraći niz znakova pomoću matematičkih metoda. Praktična važnost hash funkcije može se pratiti do širokog spektra područja. Dakle, mogu se koristiti prilikom provjere integriteta datoteka i programa. Također, kriptografske hash funkcije se koriste u algoritmima za šifriranje.

Specifikacije

Razmotrimo ključne karakteristike algoritama koji se proučavaju. među njima:

• prisutnost internih algoritama za pretvaranje podataka originalne dužine u kraći niz znakova;
• otvorenost za kriptografsku verifikaciju;
• prisutnost algoritama koji vam omogućuju pouzdano šifriranje originalnih podataka;
• prilagodljivost dešifriranju pri korištenju male računarske snage.

Ostala važna svojstva hash funkcije uključuju:

• sposobnost obrade početnih nizova podataka proizvoljne dužine;
• generirati heširane blokove fiksne dužine;
• ravnomjerno rasporedite vrijednosti funkcije na izlazu.

Razmatrani algoritmi takođe pretpostavljaju osjetljivost na podatke na ulazu na nivou od 1 bita. To jest, čak i ako se, relativno govoreći, promijeni barem 1 slovo u originalnom dokumentu, hash funkcija će izgledati drugačije.

Hash zahtjevi

Postoji niz zahtjeva za hash funkcije dizajnirane za praktičnu upotrebu u određenom području. Prvo, odgovarajući algoritam mora biti osjetljiv na promjene u internoj strukturi heširanih dokumenata. Odnosno, treba prepoznati hash funkciju kada je riječ o tekstualnoj datoteci, permutaciji pasusa, stavljanju crtica. S jedne strane, sadržaj dokumenta se ne mijenja, s druge strane njegova struktura je prilagođena, a ovaj proces mora biti prepoznat tokom heširanja. Drugo, razmatrani algoritam mora transformisati podatke tako da je obrnuta operacija (pretvaranje heša u originalni dokument) nemoguća u praksi. Treće, hash funkcija treba da pretpostavi upotrebu algoritama koji praktično isključuju vjerovatnoću formiranja istog niza znakova u obliku heša, drugim riječima, pojavu tzv. Njihovu suštinu ćemo razmotriti malo kasnije.

Navedeni zahtjevi koje algoritam hash funkcije mora ispuniti mogu se zadovoljiti uglavnom korištenjem složenih matematičkih pristupa.

Struktura

Hajde da ispitamo kakva može biti struktura funkcija koje se razmatraju. Kao što smo već napomenuli, među glavnim zahtjevima za algoritme koji se razmatraju je obezbjeđivanje jednosmjerne enkripcije. Osoba koja ima na raspolaganju samo heš praktično ne bi trebala moći da dobije originalni dokument od njega.

U kojoj strukturi može biti predstavljena hash funkcija koja se koristi u takve svrhe? Primjer njegove kompilacije može biti sljedeći: H (heš, odnosno hash) = f (T (tekst), H1), gdje je H1 algoritam za obradu teksta T. Ova funkcija hešira T na način da bez znanja H1, otvoriti ga kao punopravnu datoteku će biti gotovo nemoguće.

Korištenje hash funkcija u praksi: preuzimanje datoteka

Proučimo sada detaljnije opcije za korištenje hash funkcija u praksi. Korištenje odgovarajućih algoritama može se koristiti prilikom pisanja skripti za preuzimanje datoteka sa internet servera.

U većini slučajeva, određena kontrolna suma se određuje za svaku datoteku - ovo je hash. Mora biti isti za objekat koji se nalazi na serveru i preuzet na računar korisnika. Ako to nije slučaj, onda se datoteka možda neće otvoriti ili možda neće početi sasvim ispravno.

Hash funkcija i digitalni potpis

Upotreba hash funkcija je široko rasprostranjena pri organizaciji razmjene dokumenata koji sadrže digitalni potpis. U ovom slučaju, datoteka koju treba potpisati se hešira kako bi primalac mogao provjeriti da je originalna. Iako hash funkcija formalno nije dio strukture elektroničkog ključa, može se uhvatiti u fleš memoriju hardvera kojim su dokumenti potpisani, kao što je, na primjer, eToken.

Elektronski potpis je šifriranje datoteke korištenjem javnih i privatnih ključeva. Odnosno, poruka šifrovana privatnim ključem je priložena originalnom fajlu, a EDS se verifikuje korišćenjem javnog ključa. Ako je hash funkcija oba dokumenta ista, datoteka u posjedu primatelja prepoznaje se kao autentična, a potpis pošiljaoca ispravan.

Haširanje, kao što smo gore napomenuli, nije direktno komponenta EDS-a, međutim, omogućava vam da vrlo efikasno optimizirate algoritme za korištenje elektronskog potpisa. Dakle, u stvari, samo heš može biti šifrovan, a ne i sam dokument. Kao rezultat toga, brzina obrade datoteka se značajno povećava, a istovremeno postaje moguće obezbijediti efikasnije mehanizme za zaštitu digitalnog potpisa, jer naglasak u računskim operacijama u ovom slučaju neće biti stavljen na obradu početnih podataka, već o osiguranju kriptografske snage potpisa. Hash funkcija također omogućava potpisivanje širokog spektra tipova podataka, ne samo teksta.

Provjera lozinke

Još jedno moguće polje primjene heširanja je organizacija algoritama za provjeru lozinki uspostavljenih za razgraničenje pristupa određenim resursima datoteke. Kako ove ili druge vrste hash funkcija mogu biti uključene u rješavanje takvih problema? Veoma jednostavno.

Činjenica je da se na većini servera, čiji je pristup podložan diferencijaciji, lozinke pohranjuju kao heširane vrijednosti. Ovo je sasvim logično – ako bi lozinke bile predstavljene u originalnom tekstualnom obliku, hakeri koji su im pristupili mogli bi lako pročitati tajne podatke. Zauzvrat, nije lako izračunati lozinku na osnovu hash-a.

Kako se provjerava pristup korisnika kada se koriste algoritmi koji se razmatraju? Lozinka koju je unio korisnik provjerava se u odnosu na ono što je zabilježeno u hash funkciji, koja je pohranjena na serveru. Ako se vrijednosti tekstualnih blokova poklapaju, korisnik dobiva neophodan pristup resursima.

Najjednostavnija hash funkcija može se koristiti kao alat za provjeru lozinke. Ali u praksi IT stručnjaci najčešće koriste složene višestepene kriptografske algoritme. U pravilu se dopunjuju primjenom standarda za prijenos podataka preko sigurnog kanala - tako da hakeri ne mogu pronaći ili izračunati lozinku koja se prenosi sa računara korisnika na server - prije nego što se provjeri u odnosu na heširane tekstualne blokove.

Hash kolizije

Teorija hash funkcija predviđa takav fenomen kao što je kolizija. Šta je njegova suština? Hash kolizija je situacija u kojoj dvije različite datoteke imaju isti hash kod. Ovo je moguće ako je dužina ciljnog niza znakova kratka. U ovom slučaju, vjerovatnoća da će se hash podudarati bit će veća.

Kako bi se izbjegle kolizije, posebno se preporučuje korištenje dvostrukog algoritma koji se zove hash funkcija. Uključuje formiranje otvorenog i zatvorenog koda. Prilikom rješavanja kritičnih problema, mnogi programeri preporučuju ne korištenje hash funkcija u slučajevima kada to nije potrebno i uvijek testiraju odgovarajuće algoritme za najbolju kompatibilnost s određenim ključevima.

Istorija izgleda

Osnivačima teorije hash funkcija mogu se smatrati istraživači Carter, Wegman, Simonson, Bierbrauer. U prvim verzijama, odgovarajući algoritmi su korišteni kao alati za formiranje jedinstvenih slika nizova znakova proizvoljne dužine sa naknadnom svrhom njihove identifikacije i provjere autentičnosti. Zauzvrat, heš, u skladu sa navedenim kriterijumima, treba da ima dužinu od 30-512 bita. Kao posebno korisno svojstvo odgovarajućih funkcija, smatrali smo njegovu pogodnost da se koristi kao resurs za brzo traženje datoteka ili njihovo sortiranje.

Popularni standardi heširanja

Razmotrimo sada u kojim popularnim standardima heš funkcije mogu biti predstavljene. Među njima je i CRC. Ovaj algoritam je ciklički kod, koji se naziva i kontrolni zbroj. Ovaj standard karakteriše jednostavnost i istovremeno univerzalnost - može se koristiti za heširanje najšireg spektra podataka. CRC je jedan od najčešćih nekriptografskih algoritama.

Zauzvrat, standardi MD4 i MD5 se široko koriste u enkripciji. Još jedan popularan kriptografski algoritam je SHA-1. Konkretno, karakterizira ga heš veličina od 160 bita, što je veće od one kod MD5 - ovaj standard podržava 128 bita. Postoje ruski standardi koji regulišu upotrebu hash funkcija - GOST R 34.11-94, kao i GOST R 34.11-2012, koji ga je zamijenio. Može se primijetiti da je hash vrijednost koju daju algoritmi usvojeni u Ruskoj Federaciji 256 bita.

Standardi o kojima je riječ mogu se klasificirati po različitim osnovama. Na primjer, postoje oni koji koriste blok i specijalizirane algoritme. Jednostavnost proračuna zasnovana na standardima prvog tipa često je praćena njihovom malom brzinom. Stoga se kao alternativa blok algoritmima mogu koristiti oni koji uključuju manju količinu potrebnih računskih operacija. Uobičajeno je da se pozivaju na standarde velike brzine, posebno na gore spomenute MD4, MD5, a također i na SHA. Razmotrimo specifičnosti posebnih algoritama za heširanje koristeći SHA kao primjer.

Karakteristike SHA algoritma

Upotreba hash funkcija baziranih na SHA standardu najčešće se provodi u razvoju alata za digitalni potpis za DSA dokumente. Kao što smo gore napomenuli, SHA algoritam održava 160-bitni hash (obezbeđujući takozvani "dižet" niza znakova). U početku, standard koji se razmatra dijeli niz podataka na blokove od 512 bita. Ako je potrebno, ako dužina posljednjeg bloka ne dostigne navedenu cifru, struktura datoteke se dopunjava sa 1 i potrebnim brojem nula. Takođe, na kraju odgovarajućeg bloka ubacuje se kod koji fiksira dužinu poruke. Algoritam koji se razmatra koristi 80 logičkih funkcija, kroz koje se obrađuju 3 riječi, predstavljene u 32 bita. Također, SHA standard predviđa korištenje 4 konstante.

Poređenje algoritama heširanja

Proučimo kako se svojstva hash funkcija povezanih s različitim standardima odnose, koristeći primjer poređenja karakteristika ruskog standarda GOST R 34.11-94 i američkog SHA, o kojem smo gore govorili. Prije svega, treba napomenuti da algoritam razvijen u Ruskoj Federaciji uključuje implementaciju 4 operacije šifriranja po 1 ciklusu. Ovo odgovara 128 rundi. Zauzvrat, tokom 1 runde pri korištenju SHA-a, treba izračunati oko 20 komandi, dok ih ima ukupno 80. Dakle, korištenje SHA omogućava obradu 512 bitova početnih podataka u 1 ciklusu. Dok je ruski standard sposoban za obavljanje operacija po ciklusu od 256 bitova podataka.

Specifičnost najnovijeg ruskog algoritma

Iznad smo primijetili da je standard GOST R 34.11-94 zamijenjen novijim - GOST R 34.11-2012 "Stribog". Hajde da detaljnije istražimo njegove specifičnosti.

Pomoću ovog standarda mogu se implementirati kriptografske hash funkcije, kao što je slučaj sa algoritmima o kojima smo gore govorili. Može se primijetiti da najnoviji ruski standard podržava 512-bitni blok ulaznih podataka. Glavne prednosti GOST R 34.11-2012:

• visok nivo zaštite od razbijanja šifri;
• pouzdanost podržana upotrebom dokazanih dizajna;
• on-line izračunavanje hash funkcije, odsustvo u algoritmu transformacija koje kompliciraju konstrukciju funkcije i usporavaju izračunavanje.

Uočene prednosti novog ruskog standarda za kriptografsko šifrovanje omogućavaju njegovu upotrebu pri organizaciji cirkulacije dokumenata koja ispunjava najstrože kriterijume, koji su navedeni u odredbama regulatornog zakonodavstva.

Specifičnost kriptografskih hash funkcija

Razmotrimo detaljnije kako se vrste algoritama koje istražujemo mogu koristiti u polju kriptografije. Ključni zahtjev za odgovarajuće funkcije je otpornost na koliziju, koju smo spomenuli gore. Odnosno, ponovljene vrijednosti hash funkcije ne bi trebale biti formirane ako su te vrijednosti već prisutne u strukturi susjednog algoritma. Ostale gore navedene kriterije također moraju zadovoljiti kriptografske funkcije. Jasno je da uvijek postoji neka teoretska mogućnost oporavka originalne datoteke na osnovu hash-a, posebno ako je dostupan moćan računarski alat. Međutim, takav scenarij bi trebao biti minimiziran zbog pouzdanih algoritama šifriranja. Dakle, bit će vrlo teško izračunati hash funkciju ako njena računska snaga odgovara formuli 2 ^ (n / 2).

Još jedan važan kriterij za kriptografski algoritam je promjena heša ako je originalni skup podataka prilagođen. Gore smo napomenuli da standardi šifriranja trebaju imati osjetljivost od 1 bit. Stoga je ovo svojstvo ključni faktor u pružanju pouzdane zaštite lozinkom za pristup datotekama.

Iterativne šeme

Hajde sada da ispitamo kako se mogu izgraditi algoritmi kriptografskog heširanja. Među najčešćim šemama za rješavanje ovog problema je korištenje iterativnog sekvencijalnog modela. Zasniva se na upotrebi tzv. funkcije kompresije, u kojoj je broj ulaznih bitova znatno veći od onih koji su fiksirani na izlazu.

Naravno, funkcija kompresije mora zadovoljiti potrebne kriterije kriptografske snage. Sa interaktivnom shemom, prva operacija za obradu ulaznog toka podataka podijeljena je na blokove, čija se veličina izračunava u bitovima. Odgovarajući algoritam takođe koristi privremene varijable sa datim brojem bitova. Kao prva vrijednost koristi se dobro poznati broj, dok se naredni blokovi podataka kombiniraju s vrijednošću dotične funkcije na izlazu. Heš vrijednost je izlazna brzina bitova za posljednju iteraciju, koja uključuje cijeli ulazni tok, uključujući prvu vrijednost. Obezbeđen je takozvani "efekat lavine" heširanja.

Glavna poteškoća koja karakterizira heširanje implementirano kao iterativna shema je da je ponekad teško konstruirati hash funkcije ako ulazni tok nije identičan veličini bloka u koji je podijeljen originalni niz podataka. Ali u ovom slučaju, algoritmi se mogu napisati u heš standardu pomoću kojih se originalni tok može proširiti na ovaj ili onaj način.

U nekim slučajevima, u procesu obrade podataka u okviru iterativne šeme, mogu se koristiti takozvani algoritmi više prolaza. Oni sugeriraju stvaranje još intenzivnijeg "efekta lavine". Takav scenario pretpostavlja formiranje ponovljenih skupova podataka, a tek u drugoj fazi dolazi do proširenja.

Blok algoritam

Funkcija kompresije također može biti zasnovana na blok algoritmu kojim se šifriranje izvodi. Dakle, da biste povećali nivo sigurnosti, možete koristiti blokove podataka koji su podložni heširanju u trenutnoj iteraciji, kao ključ, a rezultat operacija dobijenih tokom izvršavanja funkcije kompresije prije toga - kao ulaz. Kao rezultat, posljednja iteracija će dati izlaz algoritma. Sigurnost heširanja će biti u korelaciji sa robusnošću algoritma koji se koristi.

Međutim, kao što smo već napomenuli, s obzirom na različite tipove hash funkcija, blok algoritme su često praćeni potrebom za korištenjem velike računarske snage. Ako nisu dostupni, brzina obrade datoteke može biti nedovoljna za rješavanje praktičnih problema povezanih s korištenjem hash funkcija. Istovremeno, potrebna kriptografska snaga se može ostvariti malim brojem operacija s početnim tokovima podataka, a posebno su algoritmi koje smo razmatrali prilagođeni rješavanju takvih problema - MD5, SHA, ruski standardi kriptografskog šifriranja.