Hash funkcije su obrazovna i znanstvena djelatnost anisimova vladimira Viktoroviča. Algoritmi za raspršivanje podataka

Napomena: U ovom predavanju formuliran je pojam hash funkcije, kao i kratak pregled algoritama za generiranje hash funkcija. Osim toga, razmatra se mogućnost korištenja algoritama blokovne enkripcije za formiranje hash funkcije.

Svrha predavanja: upoznati se s pojmom "hash funkcije", kao i s principima takvih funkcija.

Koncept hash funkcije

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

gdje je M izvorna poruka, koja se ponekad naziva prototip a h je rezultat koji se naziva hash vrijednost (i također hash kod ili sažeti poruke(iz engleskog. sažetak poruke)).

Smisao hash funkcije je odrediti karakterističnu značajku predslike – vrijednost hash funkcije. Ova vrijednost obično ima određenu fiksnu veličinu, kao što je 64 ili 128 bita. Hash kod se može dalje analizirati kako bi se riješio bilo koji problem. Tako se, na primjer, raspršivanje može koristiti za usporedbu podataka: ako dva niza podataka imaju različite hash kodove, zajamčeno je da su nizovi različiti; ako su isti, nizovi su najvjerojatnije isti. U općem slučaju, ne postoji korespondencija jedan-na-jedan između izvornih 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 se situacije nazivaju sudara). Vjerojatnost kolizija igra važnu ulogu u procjeni kvalitete hash funkcija.

Hash funkcije se široko koriste u modernoj kriptografiji.

Najjednostavnija hash funkcija može se konstruirati korištenjem operacije "sum modulo 2" na sljedeći način: dobivamo ulazni niz, zbrajamo sve bajtove po modulu 2 i vraćamo bajt rezultata kao vrijednost hash funkcije. Duljina hash vrijednosti u ovom slučaju bit će 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šimo bajtove jedan ispod drugog i dodajmo bitove u svaki stupac po modulu 2:

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

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

Međutim, takva hash funkcija ne može se koristiti u kriptografske svrhe, na primjer, za generiranje elektroničkog 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, a također ako izlaz funkcije ne ovisi eksplicitno 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;
• uz poznatu vrijednost hash funkcije, trebalo bi biti teško (gotovo nemoguće) pronaći prikladnu predsliku M;
• s poznatom porukom M, trebalo bi biti teško pronaći drugu poruku M 's istom hash vrijednošću kao izvorna poruka;
• trebalo bi biti teško pronaći bilo koji par nasumičnih različitih poruka s istom hash vrijednošću.

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

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

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

gdje je h i-1 rezultat dobiven pri izračunu 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 koja se temelji na njemu također biti pouzdana.

Najjednostavniji način korištenja blok algoritma za dobivanje hash koda je šifriranje poruke u CBC načinu. U ovom slučaju, poruka se prikazuje kao slijed blokova čija je duljina jednaka duljini bloka algoritma šifriranja. Ako je potrebno, zadnji blok s desne strane se dopunjava nulama kako bi se dobio blok željene duljine. Hash vrijednost bit će posljednji šifrirani blok teksta. Pod uvjetom da se koristi pouzdan algoritam za šifriranje blokova, rezultirajuća hash vrijednost imat će sljedeća svojstva:

• praktički je nemoguće bez poznavanja ključa za šifriranje izračunati hash vrijednost za dani otvoreni niz informacija;
• praktički je nemoguće odabrati otvorene podatke za danu vrijednost hash funkcije bez poznavanja ključa za šifriranje.

Hash vrijednost formirana na ovaj način obično se naziva imitacijski umetak ili autentifikator a koristi se za provjeru integriteta poruke. Stoga je lažno predstavljanje umetanjem kontrolna kombinacija koja ovisi o otvorenim podacima i informacijama o tajnom ključu. Svrha korištenja simuliranog umetanja je otkriti sve slučajne ili namjerne promjene u nizu informacija. Vrijednost dobivena hash funkcijom prilikom obrade ulazne poruke dodaje se poruci u trenutku kada se zna da je poruka točna. Primatelj provjerava integritet poruke tako što izračunava lažno predstavljanje primljene poruke i uspoređuje je s 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šiljatelja, tj. stvaranje potpisa. Također je moguće šifrirati primljeni hash kod simetričnim algoritmom za šifriranje ako pošiljatelj i primatelj 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, bilo koji blok može se koristiti za formiranje imitacije umetka. simetrični algoritam šifriranja.

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

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

U svim ovim shemama, duljina generirane hash vrijednosti jednaka je duljini šifriranog bloka. Sve ove, kao i neke druge sheme za korištenje algoritma blok šifriranja za izračunavanje hash vrijednosti, mogu se primijeniti u praksi.

Glavni nedostatak hash funkcija dizajniranih na temelju 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 raspršivanje, dizajnirani samostalno, od nule, na temelju 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ćem slučaju, ne postoji korespondencija jedan-na-jedan između izvornih podataka i hash koda. Stoga postoji mnogo nizova podataka koji daju iste hash kodove – takozvane kolizije. Vjerojatnost kolizija igra važnu ulogu u procjeni "kvalitete" hash funkcija.

Kontrolni zbroji

Nekompliciran, iznimno brz i lako implementiran u hardverske algoritme koji se koriste za zaštitu od nenamjernog izobličenja, uključujući hardverske pogreške.

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

Plaćanje za tako veliku brzinu je nedostatak kriptografske snage - laka prilika za prilagodbu poruke na unaprijed određeni iznos. Također, obično je bitnost kontrolnih zbroja (tipičan broj: 32 bita) niža od kriptografskih hashova (tipični brojevi: 128, 160 i 256 bita), što znači mogućnost nenamjernih kolizija.

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

Obično je takav algoritam potreban za praćenje tipičnih hardverskih pogrešaka, kao što je nekoliko uzastopnih bitova pogreške do zadane duljine. Obitelj 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. Prije svega mora imati kriptografski jaku hash funkciju otpornost na sudar dvije vrste:

Korištenje hashiranja

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

• dobro miješanje podataka
• brzi algoritam izračuna

Usklađivanje podataka

Općenito, ova se aplikacija može opisati kao provjera nekih informacija za identitet izvornika, bez korištenja izvornika. Za provjeru se koristi hash vrijednost informacija koje se provjeravaju. Dva su glavna smjera ove aplikacije:

Provjera grešaka

Na primjer, kontrolni zbroj može se prenijeti komunikacijskim kanalom zajedno s glavnim tekstom. Na kraju prijema, kontrolni zbroj se može ponovno izračunati i usporediti s prenesenom vrijednošću. Ako se pronađe nepodudarnost, to znači da je tijekom prijenosa došlo do izobličenja 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 prtljage je njegov hash kod.

Provjera šifre

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

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

Ubrzavanje dohvaćanja podataka

Na primjer, prilikom pisanja tekstualnih polja u bazi podataka, njihov se hash kod 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 tražiti po cijeloj bazi, već samo u jednom od njegovih dijelova (to uvelike ubrzava pretragu).

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

Popis algoritama

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tigar (Whirlpool
• IP internetski kontrolni zbroj (RFC 1071)

Linkovi

Zaklada Wikimedia. 2010.

• Hashan Moheyan
• Hash kod

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

Hash funkcija- funkcija koja hashira niz podataka preslikavanjem vrijednosti iz (vrlo) velikog skupa vrijednosti u (značajno) manji skup vrijednosti. Na engleskom: Hash funkcija Vidi također: Cryptographic Algorithms Financial ... ... Financijski rječnik

kriptografska hash funkcija- Funkcija koja pretvara tekst proizvoljne duljine u tekst fiksne (u većini slučajeva kraće) duljine. Glavna primjena hash funkcije nalazi se u shemi 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 Financijski rječnik Finam ... Financijski rječnik

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

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

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čunalima. Tiger nema patentnih ograničenja, može se slobodno koristiti kao s ... ... Wikipedijom

funkcija raspršivanja- hash funkcija 1. Funkcija koja kontrolira proces unosa podataka u hash tablicu, definirajući (adrese slobodnih ćelija. 2. Funkcija koja predstavlja preslikavanje fragmenta otvorene poruke u šifrirani niz fiksne duljine. U . ... ... Vodič za tehničkog prevoditelja

Hash tablica- U programiranju je hash tablica struktura podataka koja implementira sučelje asocijativnog niza, naime omogućuje vam pohranjivanje parova (ključ, vrijednost) i izvođenje tri operacije: operaciju dodavanja novog para, operaciju pretraživanja i operacija brisanja ... Wikipedia

Hash kod- Hashing (ponekad raspršivanje) pretvaranje niza ulaznih podataka proizvoljne duljine u izlazni niz bitova fiksne duljine. Takve transformacije nazivaju se i hash funkcijama ili funkcijama preklapanja, a njihovi rezultati ... ... Wikipedia

Sudar funkcije hash- Kolizija hash funkcije H su 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

Ili Hash funkcija je funkcija, pretvara ulazne podatke bilo koje (obično velike) veličine u podatke fiksne veličine. Haširanje(ponekad G yeshuvannya, eng. hashiranje)- pretvaranje niza ulaznih podataka proizvoljne duljine u izlazni niz bitova fiksne duljine. Takve se transformacije također nazivaju hash funkcije ili funkcije konvolucije, a njihovi rezultati se nazivaju hash, hash kod, hash zbroj, ili sažeti poruke(engl. Sažetak poruke).

Hash 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 tablica i baza podataka tako što imaju iste hash vrijednosti u istim zapisima. Ovaj pristup pronalaženja duplikata učinkovit je u velikim datotekama. Primjer ovog nalaza sličnih mjesta u DNK sekvencama. Kriptografska hash funkcija olakšava provjeru da je neki ulaz uparen s danom hash vrijednošću, ali ako je ulaz nepoznat, namjerno je teško rekonstruirati ulaznu vrijednost (ili ekvivalentnu alternativu) znajući pohranjenu hash vrijednost. Ovo se koristi za osiguravanje integriteta prenesenih podataka i temeljni je blok za HMAC-ove koji osiguravaju provjeru autentičnosti poruke.

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

Povijest

Donald Knuth pripisuje prvu sustavnu ideju heširanja zaposleniku IBM-a Hansu Peteru Lohnu, koji je predložio hash u siječnju 1953.

Godine 1956. Arnold Dumy je u svojoj knjizi Računala i automatizacija prvi uveo koncept raspršivanja kakvog ga većina programera danas poznaje. Duma je smatrao raspršivanje kao 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 Wesleyja Petersona u IBM Journal of Research and Development 1957. u kojoj je definirao otvoreno oslovljavanje, a također je ukazao na degradaciju performansi kada se briše. Šest godina kasnije objavljen je rad Wernera Buchholza koji je uvelike istraživao hash funkcije. Tijekom sljedećih nekoliko godina, raspršivanje je bilo naširoko korišteno, ali nije objavljen nijedan značajan rad.

Godine 1967. hashiranje u modernom smislu spominje se u knjizi Herbert Hellerman Principles of Digital Computing. Godine 1968. Robert Morris je objavio u Komunikacije ACM-a sjajan pregled o hashiranju. Ovaj rad se smatra publikacijom koja u znanstveni promet uvodi pojam haširanja i konačno konsolidira pojam "haš" među stručnjacima.

Početkom 1990-ih, ekvivalent izrazu "haširanje", zahvaljujući radovima Andreja Eršova, bila je riječ "konstelacija" u izdanju knjige Niklausa Wirtha "Algoritmi i strukture podataka" (1989) na ruskom jeziku. korišteno.) Međutim, nijedna od ovih opcija nije uspjela, a u literaturi se uglavnom koristi izraz "haširanje".

Opis

Hashing se koristi za izgradnju asocijativnih nizova, traženje duplikata u nizu skupova podataka, izgradnju jedinstvenih identifikatora za skupove podataka, kontrolni zbroj za identificiranje slučajnih ili namjernih pogrešaka tijekom pohrane ili prijenosa, za pohranu lozinki u sigurnosnim sustavima (u ovom slučaju, pristup memorijsko područje " memorija, gdje se nalaze lozinke, ne dopušta vraćanje same lozinke), pri generiranju elektroničkog potpisa (u praksi se često ne potpisuje sama poruka, već njezina hash slika).

U općem slučaju, ne postoji korespondencija jedan-na-jedan između izvornih podataka i hash koda zbog činjenice da je broj vrijednosti hash funkcija manji od broja varijanti vrijednosti ulaza niz. Postoji mnogo nizova s ​​različitim sadržajem, ali daju iste hash kodove – tzv. kolizije. Vjerojatnost kolizija igra važnu ulogu u procjeni kvalitete hash funkcija.

Postoji mnogo algoritama za raspršivanje s 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čunajte 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 deseteroznamenkastim prirodnim brojem s tri znamenke odabrane iz sredine dvadesetznamenkastog kvadrata broja. Čini se da bi vrijednost hash kodova trebala biti ravnomjerno raspoređena između "000" i "999", ali za stvarne podatke ova je metoda 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 temelje mnoge hash funkcije.

Hash funkcije temeljene na podjelu

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

Pritom je očito da je s parom način štednje uparen, s parom. I neparan - s neparnim, što može dovesti do značajnog pomaka u podacima u datotekama. Također, ne biste trebali koristiti numerički sustav računala kao bazu, jer će hash ovisiti o samo nekoliko znamenki broja koji se nalazi desno, što će dovesti do mnogo kolizija. U praksi se obično bira onaj jednostavni - u većini slučajeva ovaj izbor je sasvim zadovoljavajući.

Treba reći i o metodi raspršivanja koja se temelji na dijeljenju s log modulom 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 stupnjem polinoma uzimaju se kao hash kod:

Uz pravi izbor, ova metoda jamči da nema sudara između gotovo identičnih ključeva.

Multiplikativna shema raspršivanja

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

U ovom slučaju, na računalu s binarnim brojevnim sustavom, to je stepen dvojke, a sastoji se od najznačajnijih bitova desne polovice proizvoda.

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

Jedna od varijacija ove metode je Fibonaccijevo raspršivanje, temeljeno na svojstvima zlatnog omjera. Ovdje je cijeli broj najbliži, koprimeran s

Hashing nizove promjenjive duljine

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

Pearsonovo raspršivanje je algoritam koji je predložio Peter Pearson. Peter Pearson) za procesore s 8-bitnim registrima, čiji je zadatak brzo izračunati hash kod za niz proizvoljne duljine. 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 znaku ulazne riječi.

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

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

Među prednostima algoritma treba istaknuti:

• jednostavnost izračuna;
• nema ulaznih podataka za koje je vjerojatnost sudara najveća;
• mogućnost modifikacije u idealnu hash funkciju.

Kao alternativni način raspršivanja ključeva koji se sastoje od simbola (), mogu se predložiti izračuni

Korištenje hash funkcija

Hash funkcije se široko koriste u kriptografiji, kao i u mnogim strukturama podataka kao što su hash tablice, Bloomovi filtri i kartezijanska stabla.

Kriptografske hash funkcije

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

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

Ovi zahtjevi ovise jedan o drugom:

• 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 istina.

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

Rođendanski napad omogućuje vam da pronađete kolizije za hash funkciju s vrijednostima duljine n bitova u prosjeku za grubo hash računanje. Zato n - bit hash funkcija smatra se zagonetnom 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 (efekt lavine). Konkretno, hash vrijednost ne smije propuštati informacije, čak ni o pojedinačnim bitovima argumenta. Ovaj zahtjev je ključ kriptografske snage algoritama za raspršivanje koji hashiraju korisničku lozinku za dobivanje ključa.

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

Geometrijsko raspršivanje

Geometrijsko raspršivanje (eng. geometrijsko raspršivanje)- metoda koja se široko koristi u računalnoj grafici i računskoj geometriji za rješavanje problema na ravnini ili u trodimenzionalnom prostoru, na primjer, za pronalaženje najbližih parova u skupu točaka ili traženje identičnih slika. Hash funkcija u ovoj metodi obično uzima metrički prostor kao ulaz i dijeli ga, stvarajući mrežu ćelija. Tablica je u ovom slučaju niz s dva ili više indeksa i naziva se grid datoteka (eng. Mrežna datoteka). Geometrijsko raspršivanje također se koristi u telekomunikacijama kada se radi s višedimenzionalnim signalima.

Ubrzavanje dohvaćanja podataka

Hash tablica je struktura podataka koja vam omogućuje pohranjivanje parova oblika (ključ, hash kod) i podržava operacije za pretraživanje, umetanje i brisanje elemenata. Zadatak hash tablica je ubrzanje pretraživanja, na primjer, u slučaju zapisa u tekstualnim poljima u bazi podataka, njihov se hash kod 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 saznati u kojem dijelu je potrebno pretraživati, odnosno neće biti potrebno pretraživati ​​po cijeloj bazi, već samo u jednom njegovom dijelu (to uvelike ubrzava pretragu).

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

Algoritmi za raspršivanje nizova mogu vam pomoći u rješavanju mnogih problema. Ali oni imaju veliki nedostatak: najčešće nisu 100%, budući da postoji mnogo nizova čiji se hashovi podudaraju. Druga stvar je da u većini zadataka to možete zanemariti, jer je vjerojatnost podudaranja hashova još uvijek vrlo mala.

Hash definicija i izračun

Jedan od najboljih načina za određivanje hash funkcije 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 se nizovi trebaju 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 koristit će P = 31.

Samu hash vrijednost poželjno je pohraniti u najveći brojčani tip - int64, aka long long. Očito, s duljinom niza od oko 20 znakova, već će doći do prekoračenja vrijednosti. Ključna stvar je da ne obraćamo pažnju na ove preljeve, kao da uzimamo hash po modulu 2 ^ 64.

Primjer izračunavanja hasha ako su dopuštena 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 tražene potencije P u nekom nizu.

Primjer zadatka. Potražite duple nizove

Već smo u poziciji da učinkovito riješimo ovaj problem. Dobivate popis nizova S, duljine ne više od M znakova. Recimo da želite pronaći sve duplicirane retke i podijeliti ih u grupe tako da svaka grupa sadrži samo iste retke.

Normalnim sortiranjem nizova dobili bismo algoritam složenosti O (N M log N), dok bismo korištenjem hashova dobili O (N M + N log N).

Algoritam. Izračunajmo hash iz svakog retka i sortirajmo retke prema ovom hashu.

Vektor s n); // ... čitanje nizova ... // broji sve potencije p, recimo, do 10000 - maksimalna duljina nizova const int p = 31; vektor p_pow (10000); p_pow = 1; za (veličina_t i = 1; i > hashevi (n); za (int i = 0; i

Hash podniza i njegovo brzo izračunavanje

Pretpostavimo da nam je dan niz S i dani su indeksi I i J. Želite pronaći hash 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

Ovo svojstvo je vrlo važno.

Doista, ispada da, znajući samo hashove iz svih prefiksa niza S, možemo dobiti hash bilo kojeg podniza u O (1).

Jedini problem koji se pojavljuje je taj što morate biti u mogućnosti podijeliti s P [I]. Zapravo, nije to tako lako. Budući da izračunavamo hash po modulu 2 ^ 64, tada za dijeljenje s P [I] moramo pronaći njegov inverz u polju (na primjer, korištenjem proširenog Euklidovog algoritma) i izvršiti množenje s tim inverzom.

Međutim, postoji lakši način. U većini slučajeva, umjesto dijeljenja hasheva s potencijama P, možete ih, naprotiv, pomnožiti s ovim potencijama.

Recimo da imate dva hasha: jedan pomnožen s P [I], a drugi pomnožen s P [J]. Ako ja< J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

Na primjer, kod koji izračunava hasheve 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štenje hashiranja

Neke tipične upotrebe za raspršivanje 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 zadan niz S duljine 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 naizmjence: L = 1 .. N.

Za svaki L ćemo konstruirati niz hashova podnizova duljine L, i smanjiti hasheve na jedan stupanj i sortirati ovaj niz. Odgovoru se dodaje broj različitih elemenata u ovom nizu.

Implementacija:

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

Hash funkcije se koriste u raznim industrijama informacijske tehnologije. Namjena im je, s jedne strane, uvelike pojednostaviti razmjenu podataka između korisnika i obradu datoteka koje se koriste u različite svrhe, s druge strane optimizirati algoritme za osiguranje kontrole pristupa odgovarajućim resursima. Hash funkcija je jedan od ključnih alata za osiguravanje zaštite podataka lozinkom, kao i organiziranje razmjene dokumenata potpisanih korištenjem EDS-a. Postoji veliki broj standarda prema kojima se može izvesti predmemorija datoteka. Mnoge od njih razvili su ruski stručnjaci. Koje okuse mogu imati hash funkcije? Koji su glavni mehanizmi njihove praktične primjene?

Što je?

Prvo, istražimo koncept hash funkcije. Ovaj se pojam obično shvaća 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 u raznim područjima. Dakle, mogu se koristiti pri provjeravanju integriteta datoteka i programa. Također, kriptografske hash funkcije se koriste u algoritmima šifriranja.

Tehnički podaci

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

• prisutnost internih algoritama za pretvaranje podataka izvorne duljine u kraći niz znakova;
• otvorenost za kriptografsku provjeru;
• prisutnost algoritama koji vam omogućuju pouzdano šifriranje izvornih podataka;
• prilagodljivost dešifriranju pri korištenju male računalne snage.

Ostala važna svojstva hash funkcije uključuju:

• sposobnost obrade početnih nizova podataka proizvoljne duljine;
• generirati raspršene blokove fiksne duljine;
• ravnomjerno rasporediti vrijednosti funkcije na izlazu.

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

Zahtjevi za hash

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 unutarnje strukture raspršenih dokumenata. Odnosno, hash funkcija treba biti prepoznata, kada je riječ o tekstualnoj datoteci, permutaciji pasusa, hifeniranju. S jedne strane, sadržaj dokumenta se ne mijenja, s druge strane, njegova je struktura prilagođena, a taj se proces mora prepoznati tijekom raspršivanja. Drugo, razmatrani algoritam mora transformirati podatke tako da je obrnuta operacija (pretvaranje hasha u izvorni dokument) nemoguća u praksi. Treće, hash funkcija treba pretpostaviti korištenje algoritama koji praktički isključuju vjerojatnost formiranja istog slijeda znakova u obliku hasha, drugim riječima, pojavu tzv. Njihovu bit ćemo razmotriti malo kasnije.

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

Struktura

Pogledajmo kakva može biti struktura razmatranih funkcija. Kao što smo već spomenuli, među glavnim zahtjevima za algoritme koji se razmatraju je osiguravanje jednosmjerne enkripcije. Osoba koja ima na raspolaganju samo hash praktički ne bi trebala moći iz njega dobiti originalni dokument.

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

Korištenje hash funkcija u praksi: preuzimanje datoteka

Proučimo sada detaljnije mogućnosti korištenja hash funkcija u praksi. Korištenje odgovarajućih algoritama može se koristiti prilikom pisanja skripti za preuzimanje datoteka s internetskih poslužitelja.

U većini slučajeva za svaku se datoteku određuje određeni kontrolni zbroj - to je hash. Mora biti isti za objekt koji se nalazi na poslužitelju i preuzet na računalo korisnika. Ako to nije slučaj, datoteka se možda neće otvoriti ili se neće pokrenuti sasvim ispravno.

Hash funkcija i digitalni potpis

Upotreba hash funkcija je raširena pri organiziranju razmjene dokumenata koji sadrže digitalni potpis. U ovom slučaju, datoteka koju treba potpisati se raspršuje kako bi primatelj mogao provjeriti je li originalna. Iako hash funkcija formalno nije dio strukture elektroničkog ključa, može se uhvatiti u flash memoriju hardvera kojim su dokumenti potpisani, kao što je, na primjer, eToken.

Elektronički potpis je šifriranje datoteke pomoću javnih i privatnih ključeva. Odnosno, poruka šifrirana privatnim ključem prilaže se izvornoj datoteci, a EDS se provjerava javnim ključem. Ako je hash funkcija oba dokumenta ista, datoteka u posjedu primatelja priznaje se kao autentična, a potpis pošiljatelja ispravan.

Hashing, kao što smo gore napomenuli, nije izravna komponenta EDS-a, međutim, omogućuje vam vrlo učinkovitu optimizaciju algoritama za korištenje elektroničkog potpisa. Dakle, zapravo se može šifrirati samo hash, a ne i sam dokument. Kao rezultat toga, brzina obrade datoteka značajno se povećava, a istodobno postaje moguće osigurati učinkovitije mehanizme za zaštitu digitalnog potpisa, budući da naglasak u računalnim 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ćuje potpisivanje širokog spektra tipova podataka, a ne samo teksta.

Provjera lozinke

Drugo moguće područje primjene raspršivanja 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? Jako jednostavno.

Činjenica je da se na većini poslužitelja, čiji je pristup podložan diferencijaciji, lozinke pohranjuju kao raspršene vrijednosti. To je sasvim logično – da su lozinke predstavljene u izvornom tekstualnom obliku, hakeri koji su im dobili pristup lako bi mogli pročitati tajne podatke. Zauzvrat, nije lako izračunati lozinku na temelju hash-a.

Kako se provjerava pristup korisnika pri korištenju algoritama 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 poslužitelju. Ako se vrijednosti tekstualnih blokova podudaraju, korisnik dobiva potreban pristup resursima.

Najjednostavnija hash funkcija može se koristiti kao alat za provjeru lozinke. No u praksi IT stručnjaci najčešće koriste složene višestupanjske kriptografske algoritme. U pravilu se nadopunjuju primjenom standarda za prijenos podataka preko sigurnog kanala – tako da hakeri ne mogu pronaći niti izračunati lozinku koja se prenosi s računala korisnika na poslužitelj – prije nego što se provjeri u odnosu na raspršene tekstualne blokove.

Hash kolizije

Teorija hash funkcija predviđa takav fenomen kao što je kolizija. Koja je njegova bit? Hash kolizija je situacija u kojoj dvije različite datoteke imaju isti hash kod. To je moguće ako je duljina ciljnog niza znakova kratka. U ovom slučaju, vjerojatnost da će se hash podudarati bit će veća.

Kako bi se izbjegle kolizije, posebno se preporuča 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.

Povijest izgleda

Utemeljiteljima teorije hash funkcija mogu se smatrati istraživači Carter, Wegman, Simonson, Bierbrauer. U prvim verzijama odgovarajući algoritmi korišteni su kao alati za formiranje jedinstvenih slika nizova znakova proizvoljne duljine s naknadnom svrhom njihove identifikacije i provjere autentičnosti. Zauzvrat, hash, u skladu s navedenim kriterijima, trebao bi imati duljinu od 30-512 bita. Kao posebno korisno svojstvo odgovarajućih funkcija, smatrali smo njegovu prikladnost za korištenje kao resurs za brzo traženje datoteka ili njihovo sortiranje.

Popularni standardi raspršivanja

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

Zauzvrat, standardi MD4 i MD5 se široko koriste u šifriranju. Drugi popularni 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 reguliraju korištenje 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 pružaju 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 izračuna na temelju standarda prvog tipa često je poprać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 pozivati ​​se na standarde velike brzine, posebno na gore spomenute MD4, MD5, a također i na SHA. Razmotrimo specifičnosti posebnih algoritama za raspršivanje koristeći SHA kao primjer.

Značajke SHA algoritma

Korištenje hash funkcija temeljenih 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 (pružajući takozvani "digest" niza znakova). U početku, standard koji se razmatra dijeli niz podataka u blokove od 512 bita. Ako je potrebno, ako duljina zadnjeg bloka ne dosegne navedenu znamenku, struktura datoteke se nadopunjuje s 1 i potrebnim brojem nula. Također, na kraju odgovarajućeg bloka umetnut je kod koji fiksira duljinu 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.

Usporedba algoritama za raspršivanje

Proučimo kako se povezuju svojstva hash funkcija povezanih s različitim standardima, koristeći primjer usporedbe karakteristika ruskog standarda GOST R 34.11-94 i američkog SHA, o kojem smo gore raspravljali. Prije svega, treba napomenuti da algoritam razvijen u Ruskoj Federaciji uključuje provedbu 4 operacije šifriranja po 1 ciklusu. To odgovara 128 rundi. Zauzvrat, tijekom 1 runde pri korištenju SHA-a treba izračunati oko 20 naredbi, a ukupno ih ima 80. Dakle, korištenje SHA omogućuje obradu 512 bitova početnih podataka unutar 1 ciklusa. Dok je ruski standard sposoban obavljati operacije 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". Istražimo njegove specifičnosti detaljnije.

Pomoću ovog standarda mogu se implementirati kriptografske hash funkcije, kao što je slučaj s 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:

• visoka razina zaštite od probijanja šifri;
• pouzdanost potkrijepljena korištenjem dokazanih dizajna;
• on-line izračunavanje hash funkcije, odsutnost u algoritmu transformacija koje kompliciraju konstrukciju funkcije i usporavaju izračun.

Zapažene prednosti novog ruskog standarda za kriptografsko šifriranje omogućuju njegovu upotrebu pri organiziranju cirkulacije dokumenata koja zadovoljava najstrože kriterije, koji su navedeni u odredbama regulatornog zakonodavstva.

Specifičnost kriptografskih hash funkcija

Razmotrimo detaljnije kako se vrste algoritama koje istražujemo mogu koristiti u području kriptografije. Ključni zahtjev za odgovarajuće funkcije je otpornost na koliziju, što smo već spomenuli. Odnosno, ponovljene vrijednosti hash funkcije ne bi se trebale formirati 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 izvorne datoteke na temelju hash-a, pogotovo ako je dostupan moćan računalni alat. Međutim, takav scenarij bi trebao biti minimiziran zbog pouzdanih algoritama šifriranja. Dakle, bit će vrlo teško izračunati hash funkciju ako njezina računska snaga odgovara formuli 2 ^ (n / 2).

Drugi važan kriterij za kriptografski algoritam je promjena u hashu ako je izvorni skup podataka prilagođen. Gore smo napomenuli da standardi šifriranja trebaju imati osjetljivost od 1 bita. Stoga je ovo svojstvo ključni čimbenik u pružanju pouzdane zaštite lozinkom za pristup datotekama.

Iterativne sheme

Pogledajmo sada kako se mogu izgraditi algoritmi za kriptografsko raspršivanje. Među najčešćim shemama za rješavanje ovog problema je korištenje iterativnog sekvencijalnog modela. Temelji se na korištenju tzv. funkcije kompresije, u kojoj je broj ulaznih bitova znatno veći od onih koji su fiksni na izlazu.

Naravno, funkcija kompresije mora zadovoljiti potrebne kriterije kriptografske čvrstoće. S interaktivnom shemom, prva operacija za obradu ulaznog toka podataka podijeljena je u blokove čija se veličina izračunava u bitovima. Odgovarajući algoritam također koristi privremene varijable s zadanim brojem bitova. Kao prva vrijednost koristi se dobro poznati broj, dok se sljedeći blokovi podataka na izlazu kombiniraju s vrijednošću dotične funkcije. Hash vrijednost je izlazna brzina prijenosa za posljednju iteraciju, koja uključuje cijeli ulazni tok, uključujući prvu vrijednost. Osiguran je takozvani "efekt lavine" haširanja.

Glavna poteškoća koja karakterizira raspršivanje 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 izvorni niz podataka. Ali u ovom slučaju, algoritmi se mogu napisati u standardu raspršivanja pomoću kojih se izvorni tok može proširiti na ovaj ili onaj način.

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

Blok algoritam

Funkcija kompresije također se može temeljiti na blok algoritmu kojim se izvodi šifriranje. Dakle, kako biste povećali razinu sigurnosti, možete koristiti blokove podataka koji su podložni hashiranju u trenutnoj iteraciji, kao ključ, a rezultat operacija dobivenih tijekom izvršavanja funkcije kompresije prije toga - kao ulaz. Kao rezultat, posljednja iteracija će dati izlaz algoritma. Sigurnost raspršivanja bit će u korelaciji s robusnošću algoritma koji se koristi.

Međutim, kao što smo već napomenuli, s obzirom na različite vrste hash funkcija, blok algoritme često prati potreba za korištenjem velike računalne snage. Ako nisu dostupni, brzina obrade datoteke može biti nedovoljna za rješavanje praktičnih problema povezanih s korištenjem hash funkcija. Istodobno, potrebna kriptografska snaga može se ostvariti čak i s 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.