Algoritmi pretraživanja koje smo razmatrali obično se temelje na operaciji apstraktne usporedbe. Iz ove serije bitno se izdvaja metoda distribucije pretraživanja, opisana u "Tablicama simbola i binarnim stablima pretraživanja", u kojoj je element s ključem i pohranjen na i-tom položaju tablice, što vam omogućuje da obratite se direktno na to. Distribucija pretraživanja koristi vrijednosti ključeva kao indekse niza, a ne operande operacije usporedbe; sama metoda oslanja se na činjenicu da su ključevi različiti cijeli brojevi iz istog raspona kao i indeksi tablice. U ovom poglavlju ćemo pogledati heširanje, napredno distribucijsko pretraživanje koje se koristi u tipičnijim aplikacijama za pretraživanje gdje ključevi nemaju tako prikladna svojstva. Krajnji rezultat aplikacije ovaj pristup nimalo ne liče na metode zasnovane na usporedbi-umjesto da prelazimo strukture podataka rječnika usporedbom ključeva za pretraživanje s ključevima u elementima, pokušavamo pristupiti elementima u tablici izvođenjem aritmetičke pretvorbe ključeva u adrese tablice.

Algoritmi pretraživanja koji koriste raspršivanje sastoje se od dva odvojeni delovi... Prvi korak je izračunavanje hash funkcije koja pretvara ključ za pretraživanje u adresu u tablici. U idealnom slučaju, različiti ključevi bi se mapirali na različite adrese, ali često dva ili više različitih ključeva mogu dati istu adresu u tablici. Stoga je drugi dio pretraživanja raspršivanja proces rješavanja sudara koji rukuje takvim ključevima. Jedna od tehnika rješavanja sukoba koju ćemo pogledati u ovom poglavlju koristi povezane liste, pa se nalazi u direktnoj upotrebi u dinamičkim situacijama u kojima je teško predvidjeti broj ključeva za pretraživanje unaprijed. Druge dvije metode rješavanja sudara postižu visoke rezultate performanse pretražujte jer su elementi pohranjeni u fiksnom nizu. Pogledat ćemo kako se ove metode mogu poboljšati kako bi se mogle koristiti čak i u slučajevima kada se veličina tablice ne može unaprijed predvidjeti.

Heširanje - dobar primjer balans između vremena i memorije. Da nema ograničenja u količini korištene memorije, bilo koje pretraživanje moglo bi se izvršiti samo s jednim pristupom memoriji, jednostavno pomoću ključa kao memorijske adrese, kao u dodijeljenom pretraživanju. Međutim, ovaj idealni slučaj obično je nedostižan, jer dugi ključevi mogu zahtijevati ogromnu količinu memorije. S druge strane, ako ne postoje ograničenja vodeće vrijeme, moglo bi se proći s minimalnom količinom memorije korištenjem metode uzastopnog pretraživanja. Heširanje je način korištenja prihvatljive količine memorije i vremena, i postizanje ravnoteže između ove dvije krajnosti. Konkretno, bilo koja ravnoteža može se održati jednostavnom promjenom veličine tablice, a ne prepisivanjem koda ili odabirom drugih algoritama.

Heširanje je jedan od klasičnih problema u računarstvu: njegovi različiti algoritmi detaljno su proučeni i široko se koriste. Vidjet ćemo da se sa labavim pretpostavkama možemo nadati da ćemo podržati operacije pronalaženja i umetanja u tablice simbola konstantnog vremena, bez obzira na veličinu tablice.

Ova očekivana vrijednost je teoretski optimum performansi za bilo koju implementaciju tablice simbola, ali heširanje još uvijek nije lijek iz dva glavna razloga. Prvo, vodeće vrijeme ovisi o dužini ključa, što može biti značajno u stvarnim aplikacijama koje koriste dugačke tipke. Drugo, heširanje ne pruža efikasne implementacije drugih operacija tablice simbola, poput odabira ili sortiranja. U ovom poglavlju ćemo detaljnije razmotriti ova i druga pitanja.

Hash funkcije

Prije svega, potrebno je riješiti problem izračunavanja hash funkcije koja pretvara ključeve u adrese tablica. Obično implementacija ovog aritmetičkog izračuna nije teška, ali ipak morate biti oprezni da ne naiđete na razne suptilne podvodne stijene... Ako imate tablicu koja može sadržavati M elemenata, potrebna vam je funkcija koja pretvara ključeve u cijele brojeve u rasponu. Idealna hash funkcija trebala bi se lako izračunati i nalikovati slučajnoj funkciji: za bilo koji argument, rezultati bi u određenom smislu trebali biti podjednako vjerovatni.

Raspršena funkcija ovisi o vrsti ključa. Strogo govoreći, za svaku moguću vrstu ključeva potrebna je zasebna funkcija raspršivanja. Da bi se poboljšala efikasnost, obično je poželjno izbjegavati eksplicitne pretvorbe tipova, a umjesto toga preći na ideju da se pogleda binarna reprezentacija ključeva u mašinska reč kao cijeli broj koji se može koristiti u aritmetičkim proračunima. Heširanje je došlo prije jezika visoki nivo- na ranim računarima bilo je uobičajeno da se vrijednost tretira kao ključ niza ili kao cijeli broj. U nekim jezicima na visokom nivou teško je stvoriti programe koji zavise od zastupljenosti ključeva na određenom računaru, budući da su takvi programi inherentno strojno ovisni i stoga ih je teško prenijeti na drugo računalo. Funkcije raspršivanja obično ovise o procesu konverzije ključ u cijeli broj, pa može biti teško postići neovisnost stroja i učinkovitost u implementacijama raspršivanja. Obično se jednostavni cijeli ili ključevi s pomičnim zarezom mogu pretvoriti samo jednom mašinskom operacijom, ali ključevi sa nizovima i drugi tipovi složenih ključeva su skuplji i posvećuju više pažnje efikasnosti.

Vjerojatno najjednostavnija situacija je kada su tipke brojevi s pomičnim zarezom iz fiksnog raspona. Na primjer, ako su ključevi brojevi veći od 0 i manji od 1, možete ih jednostavno pomnožiti s M, zaokružiti rezultat na niži cijeli broj i dobiti adresu u rasponu između 0 i M - 1; takav primjer prikazan je na sl. 14.1. Ako su ključevi veći od s i manji od t, oni se mogu skalirati oduzimanjem s i dijeljenjem sa ts, dovodeći ih u raspon vrijednosti između 0 i 1, a zatim množeći s M da bi se adresa u tablici .

Pirinač. 14.1.

Za pretvaranje brojeva s pomičnim zarezom u rasponu između 0 i 1 u indekse tablice čija je veličina 97, ti se brojevi pomnože sa 97. U ovom primjeru dogodila su se tri sudara: za indekse 17, 53 i 76. Vrijednosti raspršivanja Su određeni najvećim bitovima ključa, a najmanje bitni ne igraju nikakvu ulogu. Jedan od ciljeva razvoja hash funkcije je ispraviti ovu neravnotežu tako da se svaki bit uzima u obzir prilikom izračuna.

Ako su ključevi w-bitni cijeli brojevi, mogu se pretvoriti u brojeve s pomičnim zarezom i podijeliti s 2 w kako bi se dobili brojevi s pomičnim zarezom između 0 i 1, a zatim pomnožiti s M kao u prethodnom odlomku. Ako operacije s pomičnim zarezom traju dugo, a brojevi nisu dovoljno veliki da izazovu prelijevanje, isti se rezultat može postići korištenjem cijeli broj aritmetičkih operacija: ključ morate pomnožiti s M, a zatim izvršiti pomak udesno sa w znamenkama za dijeljenje sa 2 w (ili, ako se množenje prelije, izvedite pomak, a zatim i množenje). Takve metode su beskorisne za heširanje, osim ako su ključevi ravnomjerno raspoređeni po rasponu, budući da je vrijednost raspršivanja određena samo početnim znamenkama ključa.

Jednostavnije i efikasna metoda za w -bitne cijele brojeve - jednu od, možda, najčešće korištenih metoda raspršivanja - odabir tablice prostih brojeva kao veličine M i izračunavanje ostatka k pomoću M, tj. h (k) = k mod M za bilo koji cijeli broj ključa k. Ova funkcija se naziva modularna hash funkcija. Vrlo je jednostavno izračunati (k% M u C ++) i efikasno je za postizanje ravnomjerne raspodjele ključnih vrijednosti između vrijednosti manjih od M. Mali primjer prikazan je na Sl. 14.2.

Pirinač. 14.2.

Tri desne kolone prikazuju rezultat heširanja 16-bitnih ključeva navedenih s lijeve strane pomoću sljedećih funkcija:

v% 97 (lijevo)

v% 100 (centar) i

(int) (a * v)% 100 (desno),

gdje je a = .618033. Veličine tablica za ove funkcije su 97, 100 i 100. Vrijednosti izgledaju slučajno (budući da su tipke nasumične). Druga funkcija (v% 100) koristi samo dvije krajnje desne znamenke tipki i stoga može pokazati loše performanse za ključeve koji nisu slučajni.

Modularno heširanje primjenjuje se i na ključeve s pomičnim zarezom. Ako su ključevi u malom rasponu, možete ih skalirati na brojeve između 0 i 1,2 w da biste dobili w-bitne cijele brojeve, a zatim upotrijebiti modularnu hash funkciju. Druga je mogućnost jednostavno koristiti binarni prikaz ključa kao operand modularne hash funkcije (ako je dostupna).

Modularno raspršivanje koristi se u svim slučajevima kada postoji pristup bitovima koji čine ključeve, bez obzira na to jesu li to cijeli brojevi predstavljeni mašinskom riječi, nizom znakova upakovanih u mašinsku riječ ili bilo kojim drugim. moguća opcija... Niz nasumičnih znakova upakovanih u mašinsku riječ nije potpuno isti kao ključevi nasumičnih cijelih brojeva, jer se svi kodovi ne koriste za kodiranje. Ali oba ova tipa (i bilo koji drugi tip ključa kodiranog tako da stane u mašinsku riječ) mogu biti napravljeni da izgledaju kao slučajni indeksi na maloj tablici.

Glavni razlog odabira primarne tablice raspršivanja kao veličine M za modularno raspršivanje prikazan je na Sl. 14.3. Ovaj primjer 7-bitnih podataka o znakovima tretira ključ kao osnovni 128 broj-jednu znamenku za svaki znak u ključu. Riječ sada odgovara broju 1816567, koji se također može napisati kao

jer u ASCII znakovima n, o i w odgovaraju brojevima 1568 = 110, 1578 = 111 i 1678 = 119. Izbor veličine tablice M = 64 za ovu vrstu ključa je neuspješan, jer dodavanjem vrijednosti koje su višestruke od 64 (ili 128) u x ne mijenja se vrijednost x mod 64 - za bilo koji ključ, vrijednost raspršivanja je vrijednost posljednjih 6 bitova ovog ključa. Naravno, dobra funkcija raspršivanja treba uzeti u obzir sve znamenke ključa, posebno za znakovne ključeve. Slične se situacije mogu pojaviti kada M sadrži faktor snage 2. Najjednostavniji način da biste to izbjegli, odaberite prost broj kao M.

Pirinač. 14.3.

Svaki red ove tablice sadrži: riječ od 3 slova, ASCII prikaz te riječi kao 21-bitnog broja u oktalnom i decimalnom zapisu i standardne modularne hash funkcije za veličine tablice 64 i 31 (dvije krajnje desne kolone). Veličina tablice 64 dovodi do neželjenih rezultata jer se samo krajnji desni bitovi ključa koriste za dobivanje hash vrijednosti, a slova u riječima zajedničkog jezika su neravnomjerno raspoređena. Na primjer, sve riječi koje završavaju slovom y imaju hash vrijednost 57. Nasuprot tome, jednostavna vrijednost 31 uzrokuje manje sudara u tablici koja je više od polovice veličine.

Modularno raspršivanje je vrlo jednostavno implementirati, osim što veličina tablice mora biti prost broj. Za neke aplikacije možete biti zadovoljni malim poznatim prostim brojevima ili potražiti na popisu poznatih prostih brojeva onaj koji je blizu potrebne veličine tablice. Na primjer, brojevi jednaki 2 t - 1 su prosti kada t = 2, 3, 5, 7, 13, 17, 19 i 31(i bez ikakvih drugih vrijednosti t< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не jedini razlog, pomoću koje veličina tablice treba biti prost broj; drugi razlog je opisan u odjeljku 14.4.

Pirinač. 14.4.

Ova tablica najvećih prostih brojeva manjih od 2 n za , može se koristiti za dinamičku dodjelu hash tablice kada želite da veličina tablice bude prost broj. Za bilo koju datu pozitivnu vrijednost u obuhvaćenom rasponu, ova se tablica može koristiti za određivanje prostih brojeva koji se manje od 2 puta razlikuju od njega.

Drugi način rukovanja cjelobrojnim ključevima je kombiniranje multiplikativnih i modularnih metoda: ključ pomnožite s konstantom između 0 i 1, a zatim podijelite po modulu M. Drugim riječima, morate koristiti funkciju. Postoji odnos između vrijednosti, M i efektivnog radijusa ključa koji bi teoretski mogao dovesti do abnormalnog ponašanja, ali ako koristite proizvoljnu vrijednost a, u stvarna aplikacija teško da postoji neki problem. Često se vrijednost φ = 0,618033 ... (zlatni omjer) bira kao a.

Istražene su mnoge druge varijacije na ovu temu, posebno hash funkcije koje se mogu implementirati koristeći učinkovite strojne upute, poput pomaka i maskiranog isticanja (vidi odjeljak veza).

U mnogim aplikacijama koje koriste tablice simbola ključevi nisu brojevi i nisu nužno kratki; češće su to alfanumerički nizovi koji mogu biti prilično dugi. Dakle, kako izračunati hash funkciju za riječ poput averylongkey?

U 7-bitnom ASCII kodu, ova riječ odgovara 84-bitnom broju \ begin (align *) 97 \ cdot 128 ^ (11) & + 118 \ cdot 128 ^ (10) + 101 \ cdot 128 ^ (9) + 114 \ cdot 128 ^ (8) + 121 \ cdot 128 ^ (7) \\ & + 108 \ cdot 128 ^ (6) + 111 \ cdot 128 ^ (5) + 110 \ cdot 128 ^ (4) + 103 \ cdot 128 ^ (3) \\ & + 107 \ cdot 128 ^ (2) + 101 \ cdot 128 ^ (1) + 121 \ cdot 128 ^ (0), \ end (align *),

koji je prevelik za obavljanje normalnih aritmetičkih funkcija na većini računara. Često morate da rukujete mnogo dužim ključevima.

Da bi se izračunala modularna hash funkcija za dugačke ključeve, oni se pretvaraju komad po dio. Možete koristiti aritmetička svojstva funkcije modula i koristiti Hornerov algoritam (pogledajte odjeljak 4.9 "Apstraktni tipovi podataka"). Ova metoda se temelji na drugom načinu pisanja brojeva koji odgovaraju tipkama. Za ovaj primjer napišite sljedeći izraz: \ begin (align *) (((((((((((97 \ cdot 128 ^ (11) & + 118) \ cdot 128 ^ (10) + 101) \ cdot 128 ^) (9) + 114) \ cdot 128 ^ (8) + 121) \ cdot 128 ^ (7) \\ & + 108) \ cdot 128 ^ (6) + 111) \ cdot 128 ^ (5) + 110) \ cdot 128 ^ (4) + 103) \ cdot 128 ^ (3) \\ & + 107) \ cdot 128 ^ (2) + 101) \ cdot 128 ^ (1) + 121. \ end (align *)

Tj decimalni broj, koji odgovara kodiranju znakova niza, može se izračunati gledajući ga slijeva nadesno, množeći akumuliranu vrijednost sa 128, a zatim dodajući vrijednost koda sljedećeg znaka. U slučaju dugačkog niza, ovaj način izračunavanja će na kraju dovesti do broja većeg od onoga što računar može zamisliti. Međutim, ovaj broj nije potreban jer je potreban samo (mali) ostatak ako se podijeli s M. Rezultat se može dobiti čak i bez pohranjivanja velike akumulirane vrijednosti, budući da u bilo kojem trenutku u izračunu možete odbaciti višekratnik M - svaki put kada izvršite množenje i sabiranje, trebate samo pohraniti ostatak dijeljenja po modulu M. Rezultat će biti isti kao da smo imali priliku izračunati dugačak broj, a zatim izvršite podjelu (vidi. Vježba 14.10). Ovo zapažanje vodi do jednostavnog aritmetičkog načina izračunavanja modularnih hash funkcija za duge nizove - vidi Program 14.1. Ovaj program koristi posljednji trik: umjesto baze 128, koristi prost broj 127. Razlog za ovu promjenu se govori u sljedećem odlomku.

Postoji mnogo načina za izračunavanje hash funkcija po približno istoj cijeni kao modularno heširanje pomoću Hornerove metode (jedan ili dva aritmetičke operacije za svaki znak u ključu). Za nasumične ključeve ove su metode praktički iste, ali pravi ključevi rijetko su slučajni. Mogućnost randomiziranja stvarnih ključeva po niskoj cijeni dovodi do razmatranja randomiziranih algoritama heširanja, budući da su nam potrebne hash funkcije koje generiraju nasumične indekse na tablici bez obzira na distribuciju ključeva. Randomizacija je jednostavna, jer se ne morate doslovno pridržavati definicije modularnog heširanja - samo trebate koristiti sve znamenke ključa za izračunavanje cijelog broja manjeg od M.

M = 96 i a = 128 (gore),

M = 97 i a = 128 (središte) i

M = 96 i a = 127 (dolje)

Neravnomjerna raspodjela u prvom slučaju rezultat je neravnomjerne upotrebe slova i postojanosti nejednakosti zbog činjenice da su i veličina tablice i faktor višekratnici 32. Druga dva primjera izgledaju nasumično jer veličina tablice i faktor su relativno prosti brojevi.

Program 14.1 prikazuje jedan način za to: korištenje jednostavne osnove umjesto snage 2 i cijelog broja koji odgovara ASCII predstavljanju niza. Na sl. 14.5 sl. Slika 14.5 prikazuje kako ova promjena poboljšava distribuciju tipičnih ključeva niza. U teoriji, hash vrijednosti generirane programom 14.1 mogu dati loše rezultate za veličine tablica koje su višestruke od 127 (iako će u praksi to vjerojatno biti gotovo nevidljivo); da bismo stvorili randomizirani algoritam, mogli smo nasumično odabrati vrijednost množitelja. Još učinkovitiji pristup je korištenje slučajnih vrijednosti koeficijenata u proračunu i različitih slučajnih vrijednosti za svaku ključnu znamenku. Ovaj pristup daje randomizirani algoritam koji se naziva univerzalno heširanje.

U teoriji, idealna univerzalna hash funkcija je ona za koju je vjerojatnost sudara između dva različita ključa u tablici veličine M točno 1 / M. Može se dokazati da upotrebom koeficijenta a u Programu 14.1, ne fiksne proizvoljne vrijednosti, već sekvence slučajno različitih vrijednosti, pretvara modularno heširanje u univerzalnu hash funkciju. Međutim, troškovi generiranja novog slučajnog broja za svaki znak u ključu obično su neprihvatljivi. U praksi, kompromis prikazan u Programu 14.1 može se postići ne pohranjivanjem niza različitih slučajnih brojeva za svaki simbol ključa, već promjenom koeficijenata generiranjem jednostavnog pseudo-slučajnog niza.

Ukratko, da biste koristili raspršivanje za implementaciju tablice sa apstraktnim simbolima, prvo morate proširiti sučelje apstraktnog tipa tako da uključi operaciju raspršivanja, koja preslikava ključeve na negativne cijele brojeve manje od veličine tablice M.

Kao dio ovog članka reći ću vam šta je hash, zašto je potreban, gdje i kako se koristi, kao i najpoznatiji primjeri.

Mnogi zadaci informacijske tehnologije vrlo su kritični za podatke. Na primjer, ako trebate uporediti dvije datoteke od po 1 KB i dvije datoteke od po 10 GB, ovo je potpuno drugo vrijeme. Stoga se algoritmi koji vam omogućuju rad s kraćim i prostranijim vrijednostima smatraju vrlo popularnima.

Jedna od ovih tehnologija je Hashing, koja je svoju primjenu našla u rješavanju mnogih problema. Ali, mislim da vama, kao običnom korisniku, još uvijek nije jasno o kakvoj se vrsti životinje radi i čemu služi. Stoga ću dalje pokušati objasniti sve najjednostavnijim riječima.

Bilješka: Materijal je namijenjen običnim korisnicima i ne sadrži mnogo tehničkih aspekata, međutim više je nego dovoljan za osnovno upoznavanje.

Šta je hash ili hashing?

Počeću sa uslovima.

Hash funkcija, funkcija konvolucije je posebna vrsta funkcije koja vam omogućuje pretvaranje tekstova proizvoljne dužine u kôd fiksne duljine (obično kratki alfanumerički zapis).

Heširanje je proces konverzije samog izvornog teksta.

Hash, Hash Code, Hash Value, Hash Sum je izlazna vrijednost Hash funkcije, odnosno rezultirajući blok fiksne duljine.

Kao što vidite, pojmovi imaju donekle figurativan opis, iz kojeg je teško shvatiti čemu sve ovo služi. Stoga ću odmah navesti mali primjer (o ostalim aplikacijama ću govoriti kasnije). Recimo da imate 2 datoteke od 10 GB. Kako možete brzo saznati koja vam je potrebna? Naziv datoteke se može koristiti, ali ga je lako preimenovati. Možete gledati datume, ali nakon kopiranja datoteka, datumi mogu biti isti ili u drugom slijedu. Veličina, kao što i sami razumijete, može malo pomoći (pogotovo ako su veličine iste ili niste pogledali tačne vrijednosti bajtova).

Ovdje je potreban ovaj Hash, koji je kratki blok formiran od izvornog teksta datoteke. Ove dvije datoteke od 10 GB imat će dva različita, ali kratka hash koda (nešto poput "ACCAC43535" i "BBB3232A42"). Pomoću njih možete brzo saznati željeni fajl, čak i nakon kopiranja i promjene imena.

Bilješka: Zbog činjenice da je Hash vrlo poznat koncept u svijetu računara i na Internetu, često se sve što se odnosi na Hash skraćuje na ovu riječ. Na primjer, izraz "koristim MD5 raspršivanje" u prijevodu znači da web mjesto ili negdje drugdje koristi algoritam heširanja standarda MD5.

Svojstva funkcije raspršivanja

Sada ću govoriti o svojstvima Hash funkcija, kako biste lakše razumjeli gdje se Hash koristi i za što je potrebno. No, prvo, još jedna definicija.

Collision- ovo je situacija kada se dobije isti hash zbir za dva različita teksta. Kao što i sami razumijete, budući da je blok fiksne duljine, tada ima ograničen broj mogućih vrijednosti, pa su stoga moguća ponavljanja.

A sada na sama svojstva Hash funkcija:

1. Ulaz može biti tekst bilo koje veličine, a izlaz je blok podataka fiksne dužine. To proizlazi iz definicije.

2. Heš-zbir istih tekstova mora biti isti. Inače su takve funkcije jednostavno beskorisne - analogne su slučajnom broju.

3. Lijepa funkcija vijuge moraju imati dobru distribuciju. Slažete se da ako je veličina izlaznog Hash -a, na primjer, 16 bajtova, onda ako funkcija vraća samo 3 različite vrijednosti za bilo koji tekst, onda nema smisla u takvoj funkciji i ovih 16 bajtova (16 bajtova je 2 ^ 128 opcija, što je približno 3, 4 * 10 ^ 38 stepeni).

4. Koliko dobro funkcija reagira na najmanje promjene izvornog teksta. Jednostavan primjer. Promijenjeno 1 slovo u datoteci od 10 GB, vrijednost funkcije bi trebala biti drugačija. Ako to nije slučaj, tada je korištenje takve funkcije vrlo problematično.

5. Vjerovatnoća sudara. Vrlo složen parametar izračunat pod određenim uvjetima. Ali, njegova suština je u tome što je poenta hash funkcije ako se rezultirajući hash zbir često podudara.

6. Brzina izračunavanja Hash -a. Koja je upotreba funkcije konvolucije ako je potrebno puno vremena za izračunavanje? Ništa, jer je tada lakše usporediti podatke datoteke ili koristiti drugačiji pristup.

7. Složenost oporavka izvornih podataka iz vrijednosti hasha. Ova je karakteristika specifičnija od opće, jer to nije uvijek potrebno. Međutim, za najpoznatije algoritme ova se karakteristika procjenjuje. Na primjer, teško možete dobiti izvornu datoteku iz ove funkcije. Međutim, ako postoji problem sudara (na primjer, morate pronaći bilo koji tekst koji odgovara takvom Hash -u), tada takva karakteristika može biti važna. Na primjer, lozinke, ali o njima kasnije.

8. Otvoreni ili zatvoreni izvorni kod takve funkcije. Ako kôd nije otvorenog koda, složenost oporavka podataka, odnosno kriptografska snaga, ostaje upitna. Ovo je djelomično problem s šifriranjem.

Sada možete prijeći na pitanje "čemu služi sve to?"

Zašto je potreban Hash?

Postoje samo tri glavna cilja hash funkcija (ili bolje rečeno, njihova svrha).

1. Provera integriteta podataka. IN ovaj slučaj sve je jednostavno, takvu funkciju treba brzo izračunati i omogućiti jednako brzo provjeru da, na primjer, datoteka preuzeta s interneta nije oštećena tijekom prijenosa.

2. Povećanje brzine preuzimanja podataka. Fiksna veličina bloka omogućuje vam da dobijete mnoge prednosti u rješavanju problema pretraživanja. U ovom slučaju, stvar je u tome da, tehnički, korištenje hash funkcija može imati pozitivan učinak na performanse. Za takve funkcije vjerojatnost sudara i dobra raspodjela vrlo su važni.

3. Za kriptografske potrebe. Ovaj pogled funkcije konvolucije koriste se u onim područjima sigurnosti gdje je važno da se rezultati teško zamjenjuju ili gdje je potrebno učiniti zadatak dobijanja što je moguće težim korisne informacije od Hash.

Gdje i kako se koristi hash?

Kao što ste vjerojatno već pretpostavili, Hash se koristi u mnogim zadacima. Evo nekoliko njih:

1. Lozinke se obično ne čuvaju u čistom tekstu, već u obliku heš-suma, što omogućava veći stepen sigurnosti. Uostalom, čak i ako napadač dobije pristup takvoj bazi podataka, i dalje će morati potrošiti puno vremena da pronađe odgovarajuće tekstove za ove hash kodove. Ovdje je važna karakteristika "složenost oporavka izvornih podataka iz vrijednosti hasha".

Bilješka: Savjetujem vam da pročitate ovaj članak za nekoliko savjeta za poboljšanje sigurnosti lozinkom.

2. U programiranju, uključujući baze podataka. Naravno, najčešće govorimo o strukturama podataka koje to dopuštaju brza pretraga... Čisto tehnički aspekt.

3. Prilikom prijenosa podataka putem mreže (uključujući Internet). Mnogi protokoli, poput TCP / IP -a, uključuju posebna polja za provjeru koja sadrže raspršivanje izvorne poruke, tako da ako negdje dođe do kvara, to neće utjecati na prijenos podataka.

4. Za različite algoritme vezane za sigurnost. Na primjer, Hash se koristi u elektroničkim digitalnim potpisima.

5. Provjerite integritet datoteka. Ako ste obratili pažnju, često na Internetu možete pronaći datoteke (na primjer, arhive) dodatni opisi sa hash kodom. Ova se mjera koristi ne samo da ne biste slučajno pokrenuli datoteku koja je oštećena prilikom preuzimanja s interneta, već i jednostavno dolazi do grešaka u hostingu. U takvim slučajevima možete brzo provjeriti Hash i, ako je potrebno, ponovo učitati datoteku.

6. Ponekad se hash funkcije koriste za kreiranje jedinstvenih identifikatora (kao dio). Na primjer, prilikom spremanja slika ili samo datoteka, oni obično koriste Hash u imenima zajedno s datumom i vremenom. Time se izbjegava prepisivanje datoteka istog imena.

U stvari, što idete dalje, češće se koriste funkcije raspršivanja informacione tehnologije... Uglavnom zbog činjenice da je količina podataka i snaga najviše jednostavni računari mnogo su porasle. U prvom slučaju radi se više o pretraživanju, a u drugom o sigurnosnim pitanjima.

Značajne hash funkcije

Najpoznatije su sljedeće tri hash funkcije.

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

Svrha predavanja: upoznati se sa pojmom "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 cijelu vrijednost ili neki drugi niz fiksne dužine. Matematički se to može napisati ovako:

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

Značenje hash funkcije je da se odredi karakteristična karakteristika slike - vrijednost hash funkcije. Ova vrijednost obično ima određenu fiksnu veličinu, poput 64 ili 128 bita. Heš kod se može dalje analizirati kako bi se riješio bilo koji problem. Tako se, na primjer, heširanje može upotrijebiti za usporedbu podataka: ako dva polja podataka imaju različite hash kodove, zagarantirano je da će biti različiti; ako su isti, nizovi su najvjerovatnije isti. U opštem slučaju, nema međusobne korespondencije 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 situacije se nazivaju sudari). Vjerojatnost sudara igra važnu ulogu u procjeni kvalitete hash funkcija.

Hash funkcije se široko koriste u modernoj kriptografiji.

Najjednostavnija hash funkcija može se konstruirati pomoću operacije "zbir modulo 2" na sljedeći način: dobivamo ulazni niz, dodajemo sve bajtove po modulu 2 i vraćamo rezultatni bajt kao vrijednost hash funkcije. Dužina 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, upišemo bajtove jedan ispod drugog i dodamo 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 raspršivanja.

Međutim, takva se funkcija raspršivanja ne može koristiti u kriptografske svrhe, poput generiranja elektronski potpis, jer je prilično lako promijeniti sadržaj potpisane poruke bez promjene vrijednosti kontrolne sume.

Stoga razmatrana hash funkcija nije prikladna za kriptografske aplikacije. U kriptografiji, hash funkcija se smatra dobrom ako je teško stvoriti dvije predslike istu vrijednost hash funkciju, a također i ako izlaz funkcije ne ovisi izričito o ulazu.

Formulirajmo osnovne zahtjeve za kriptografske hash funkcije:

• hash funkcija mora biti primjenjiva na poruke bilo koje veličine;
• proračun vrijednosti funkcije mora se obaviti dovoljno brzo;
• s poznatom vrijednošću hash funkcije, trebalo bi biti teško (gotovo nemoguće) pronaći odgovarajuću sliku M;
• s poznatom porukom M trebalo bi biti teško pronaći drugu poruku M 's istom vrijednošću raspršenja kao originalna poruka;
• trebalo bi biti teško pronaći bilo koji par nasumično različitih poruka s istom vrijednošću raspršivanja.

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

Trenutno se u praksi funkcije koriste kao hash funkcije koje obrađuju ulaznu poruku blok po blok i izračunavaju vrijednost raspršivanja 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čunavanju hash funkcije za prethodni blok ulazne podatke.

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

Korištenje algoritama blok enkripcije za generiranje hash funkcije

Kao hash funkciju možete koristiti hash funkciju bloka. Ako je korišteni blok algoritam kriptografski siguran, tada će i hash funkcija zasnovana na njemu 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 niz blokova čija je dužina jednaka dužini bloka algoritma za šifriranje. Ako je potrebno, zadnji blok se s desne strane nadopunjuje nulama kako bi se dobio blok željene dužine. Vrijednost raspršivanja bit će posljednji šifrirani blok teksta. Pod uvjetom da se koristi pouzdan algoritam za šifriranje blokova, rezultirajuća vrijednost raspršivanja imat će sljedeća svojstva:

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

Ovako formirana hash vrijednost se obično naziva imitacija umetka ili autentifikator i koristi se za provjeru integriteta poruke. Dakle, umetanje imitacije je kontrolna kombinacija koja ovisi o otvorenim podacima i tajnim ključnim podacima. Svrha korištenja simuliranog umetka je otkrivanje svih slučajnih ili namjernih promjena u informacijskom nizu. Vrijednost dobivena hash funkcijom pri obradi ulazne poruke dodaje se poruci kada se zna da je poruka tačna. Primalac provjerava integritet poruke izračunavajući lažno predstavljanje primljene poruke i upoređujući je sa primljenim heš kodom, koji se mora prenijeti na siguran način. Jedan od ovih sigurne načine možda postoji umetak koji imitira enkripciju privatni ključ pošiljalac, tj. stvaranje potpisa. Također je moguće šifrirati primljeni hash kod pomoću simetričnog algoritma za šifriranje, ako pošiljatelj i primatelj imaju zajednički simetrični ključ za šifriranje.

Navedeni postupak dobijanja i korištenja simuliranog umetka opisan je u domaćem standardu GOST 28147-89. Standard predlaže korištenje najmanjih 32 bita bloka primljenih na izlazu operacije šifriranja cijele poruke u načinu spajanja blokova šifri za kontrolu integriteta prenesene poruke. Na isti način, za formiranje simuliranog umetka, možete koristiti bilo koji blok simetrični algoritam šifriranja.

Drugi moguć način Primjena blok šifre za generiranje hash koda je sljedeća. Originalna poruka se obrađuje sekvencijalno u blokovima. Posljednji blok se prema potrebi dodaje nulama, ponekad se dužina poruke dodaje posljednjem bloku kao binarni broj. U svakoj fazi šifriramo vrijednost raspršivanja dobivenu u prethodnoj fazi, uzimajući trenutni blok poruke kao ključ. Posljednja primljena šifrirana vrijednost bit će konačni rezultat raspršivanja.

U stvari, 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 jednostavnom načinu zamjene, - rad sabiranja po modulu 2. Zatim, za na primjer, moguće su sljedeće sheme za generiranje hash funkcije:

U svim ovim shemama, dužina generirane hash vrijednosti jednaka je dužini šifriranog bloka. Sve ove, kao i neke druge sheme za korištenje algoritma blok -šifre za izračunavanje hash vrijednosti, mogu se primijeniti u praksi.

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

Šta je hash? Raspršena funkcija je matematička transformacija informacija u kratki niz specifične dužine.

Zašto je ovo potrebno? Hash analiza često se koristi za provjeru integriteta važnih datoteka. operativni sistem, važni programi, važni podaci. Kontrola se može vršiti po potrebi i redovno.

Kako se to radi? Prvo, oni određuju integritet datoteka koje treba nadzirati. Za svaku datoteku se njena hash vrijednost izračunava pomoću posebnog algoritma, pri čemu se rezultat sprema. Nakon potrebnog vremena napravi se sličan izračun i rezultati se uporede. Ako se vrijednosti razlikuju, podaci u datoteci su promijenjeni.

Koje karakteristike treba imati hash funkcija?

• moraju biti u stanju pretvoriti podatke proizvoljne dužine u fiksne;
• mora imati otvoren algoritam kako biste mogli istražiti njegovu kriptografsku snagu;
• treba biti jednostran, odnosno ne bi trebalo postojati matematička mogućnost određivanja početnih podataka prema rezultatu;
• treba "odoljeti" sudarima, odnosno ne bi trebao proizvoditi iste vrijednosti za različite ulazne podatke;
• ne bi trebali zahtijevati velike računarske resurse;
• pri najmanjoj promjeni ulaznih podataka rezultat bi se trebao značajno promijeniti.

Koji su popularni algoritmi heširanja? Trenutno se koriste sljedeće hash funkcije:

• CRC - Kôd cikličkog viška ili kontrolni zbroj. Algoritam je prilično jednostavan, ima veliki broj varijacije u zavisnosti od potrebne izlazne dužine. Nije kriptografsko!
• MD 5 je vrlo popularan algoritam. Kao on prethodna verzija MD 4 je kriptografska funkcija. Veličina hasha je 128 bita.
• SHA -1 je također vrlo popularna kriptografska funkcija. Veličina hasha je 160 bita.
• GOST R 34.11-94 - Ruski kriptografski standard za izračunavanje hash funkcija. Veličina raspršivanja je 256 bita.

Kada administrator sistema može koristiti ove algoritme?Često pri preuzimanju bilo kojeg sadržaja, na primjer, programa s web stranice proizvođača, glazbe, filmova ili drugih podataka, postoji vrijednost kontrolne sume izračunati prema određenom algoritmu. Iz sigurnosnih razloga, nakon preuzimanja, morate samostalno izračunati hash funkciju i usporediti vrijednost s onim što je navedeno na web stranici ili u privitku datoteke. Jeste li ikada ovo radili?

Zašto je prikladnije izračunati hash? Sada postoji veliki broj takvih alata, i plaćenih i besplatnih za korištenje. Meni lično se dopao HashTab. Prvo, tokom instalacije, uslužni program je ugrađen kao kartica u svojstvima datoteke, drugo, omogućava vam odabir velikog broja algoritama za heširanje, i treće, besplatan je za privatnu nekomercijalnu upotrebu.

Šta je ruski? Kao što je gore spomenuto, u Rusiji postoji standard za mješanje GOST R 34.11-94, koji naširoko koriste mnogi proizvođači proizvoda za zaštitu informacija. Jedan od ovih alata je program fiksacije i kontrole početnog stanja. softverski paket FIX. Ovaj program je sredstvo praćenja efikasnosti korištenja informaciono -sigurnosnih sistema.

FIX (verzija 2.0.1) za Windows 9x / NT / 2000 / XP

• Izračunavanje kontrolnih suma navedenih datoteka pomoću jednog od 5 implementiranih algoritama.
• Fiksiranje i naknadna kontrola početnog stanja programskog paketa.
• Poređenje verzija softverskog paketa.
• Popravljanje i kontrola direktorija.
• Kontrola promjena u navedenim datotekama (direktorijima).
• Formiranje izvještaja u TXT, HTML, SV formatima.
• Proizvod ima FSTEC certifikat za NDV 3 br. 913 do 01. juna 2013. godine.

A šta je sa digitalnim potpisom? Rezultat izračunavanja hash funkcije, zajedno s korisnikovim tajnim ključem, ide na ulaz kriptografskog algoritma, gdje se izračunava digitalni potpis. Strogo govoreći, hash funkcija nije dio EDS algoritma, ali se često radi namjerno kako bi se isključio napad pomoću javnog ključa.

U današnje vrijeme mnoge aplikacije za e-trgovinu omogućuju vam da pohranite tajni ključ korisnika u privatno područje tokena (ruToken, eToken) bez tehničke mogućnosti da ga odande izvučete. Sam token ima vrlo ograničenu memorijsku površinu, mjerenu u kilobajtima. Za potpisivanje dokumenta ne postoji način da se dokument prenese na sam token, ali je vrlo lako prenijeti hash dokumenta u token i primiti EDS na izlazu.

Pitanja:

1. Koncept hash funkcije.

2. Korištenje algoritama blok enkripcije za formiranje hash funkcije.

3. Pregled algoritama za formiranje hash funkcija.

1. Koncept hash funkcije

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

h = H (M) ,

gdje M - originalna poruka, ponekad nazvana prototip , ali h - rezultat, nazvan vrijednost hash funkcije (i također hash kod ili sažete poruke(sa engleskog. sažetak poruka)).

Značenje hash funkcije je da se odredi karakteristična karakteristika slike - vrijednost hash funkcije. Ova vrijednost obično ima određenu fiksnu veličinu, poput 64 ili 128 bita. Heš kod se može dalje analizirati kako bi se riješio bilo koji problem. Tako se, na primjer, heširanje može upotrijebiti za usporedbu podataka: ako dva polja podataka imaju različite hash kodove, zagarantirano je da će biti različiti; ako su isti, nizovi su najvjerovatnije isti. U opštem slučaju, nema međusobne korespondencije 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 situacije se nazivaju sudari ). Vjerojatnost sudara igra važnu ulogu u procjeni kvalitete hash funkcija.

Hash funkcije se široko koriste u modernoj kriptografiji.

Najjednostavnija hash funkcija može se konstruirati pomoću operacije "zbir modulo 2" na sljedeći način: dobivamo ulazni niz, dodajemo sve bajtove po modulu 2 i vraćamo rezultatni bajt kao vrijednost hash funkcije. Dužina 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):

2 B1 4 A9 5 FE4

Prevedimo poruku u binarni oblik, upišemo bajtove jedan ispod drugog i dodamo bitove u svaki stupac po modulu 2:

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

Rezultat: 0010 1101 ili 2 D i bit će vrijednost hash funkcije.

Međutim, takva se funkcija raspršivanja ne može koristiti u kriptografske svrhe, na primjer, za generiranje elektroničkog potpisa, jer je prilično lako promijeniti sadržaj potpisane poruke bez promjene vrijednosti kontrolne sume.

Stoga razmatrana hash funkcija nije prikladna za kriptografske aplikacije. U kriptografiji se hash funkcija smatra dobrom ako je teško stvoriti dvije predslike sa istom hash vrijednošću, a također i ako izlaz funkcije ne ovisi izričito o ulazu.

Formulirajmo osnovne zahtjeve za kriptografske hash funkcije:

· Funkcija raspršivanja mora biti primjenjiva na poruku bilo koje veličine;

· Izračun vrijednosti funkcije treba obaviti dovoljno brzo;

Uz poznatu vrijednost hash funkcije, trebalo bi biti teško (gotovo nemoguće) pronaći odgovarajuću predodžbu M ;

Sa poznatom porukom M trebalo bi biti teško pronaći drugu poruku M ' sa istom hash vrednošću kao originalna poruka;

· Trebalo bi biti teško pronaći bilo koji par nasumično različitih poruka sa istom vrijednošću raspršivanja.

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

Trenutno se u praksi funkcije koriste kao hash funkcije koje obrađuju ulaznu poruku blok po blok i izračunavaju vrijednost raspršivanja h i za svaki blok M i ulazna poruka prema ovisnostima obrasca

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

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

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

2. Korištenje algoritama blok enkripcije za generiranje hash funkcije.

Simetrični algoritam šifriranja blokova može se koristiti kao hash funkcija. Ako je korišteni algoritam blokova kriptografski siguran, tada će i hash funkcija zasnovana na njemu biti pouzdana.

Najjednostavniji način korištenja blok algoritma za dobivanje hash koda je šifriranje poruke u CBC načinu ( Lanac blokova šifriranja - Lančavanje blokova šifriranog teksta). U ovom slučaju poruka se prikazuje kao niz blokova čija je dužina jednaka dužini bloka algoritma za šifriranje. Ako je potrebno, zadnji blok se s desne strane nadopunjuje nulama kako bi se dobio blok željene dužine. Vrijednost raspršivanja bit će zadnji šifrirani blok teksta. Pod uvjetom da se koristi pouzdan algoritam za šifriranje blokova, rezultirajuća vrijednost raspršivanja imat će sljedeća svojstva:

· Praktično je nemoguće bez znanja o ključu za šifriranje izračunati vrijednost raspršivanja za dati otvoreni niz informacija;

· Praktično je nemoguće odabrati otvorene podatke za datu vrijednost hash funkcije bez poznavanja ključa za šifriranje.

Ovako formirana hash vrijednost se obično naziva imitacija umetka ili autentifikator i koristi se za provjeru integriteta poruke. Dakle, umetanje imitacije je kontrolna kombinacija koja ovisi o otvorenim podacima i tajnim ključnim podacima. Svrha korištenja simuliranog umetka je otkrivanje svih slučajnih ili namjernih promjena u informacijskom nizu. Vrijednost dobivena hash funkcijom pri obradi ulazne poruke dodaje se poruci kada se zna da je poruka tačna. Primalac provjerava integritet poruke izračunavajući lažno predstavljanje primljene poruke i upoređujući je sa primljenim heš kodom, koji se mora prenijeti na siguran način. Jedna od ovih 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 pomoću simetričnog algoritma za šifriranje, ako pošiljatelj i primatelj imaju zajednički simetrični ključ za šifriranje.

Navedeni postupak dobijanja i korištenja simuliranog umetka opisan je u domaćem standardu GOST 28147-89. Standard predlaže korištenje najmanje značajnih 32 bita bloka dobivenih na izlazu operacije šifriranja cijele poruke u načinu spajanja blokova šifri za kontrolu integriteta prenesene poruke. Na isti način, bilo koji blok simetrični algoritam šifriranja može se koristiti za generiranje imitiranog umetka.

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

Dakle, ako je uobičajena shema šifriranja poruka M pomoću blok šifre f na ključu TO snimili smo kao E = f (M, K) , zatim shemu za dobivanje hash koda h prema gore opisanom algoritmu može se predstaviti kao

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

Kao početni hash kod h 0 uzeti neku konstantu. Šifriranje se izvodi u jednostavnom načinu prepisivanja. Upotreba ovom metodom veličina bloka je ista kao i dužina ključa, a veličina hash vrijednosti bit će dužina bloka.

Moguć je i drugi način korištenja blok šifre u jednostavnom načinu zamjene: elementi poruke su šifrirani s hash vrijednostima dobivenim u prethodnom koraku:

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

U stvari, postoji još nekoliko mogućih shema za korištenje blok šifre za formiranje hash funkcije. Neka bude M i - blok originalne poruke, h i - vrijednost hash funkcije uključena i -prva faza, f - algoritam za šifriranje blokova koji se koristi u jednostavnom načinu zamjene; ​​- operacija dodavanja po modulu 2. Tada su, na primjer, sljedeće sheme za generiranje hash funkcije moguće:

U svim ovim shemama, dužina generirane hash vrijednosti jednaka je dužini šifriranog bloka. Sve ove, kao i neke druge sheme za korištenje algoritma blok -šifre 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 heširanja (najčešći od njih su MD5, SHA-1, SHA-2 i GOST R 34.11-94).

3. Pregled algoritama za formiranje hash funkcija.

Trenutno su predloženi i praktično se koriste različiti posebni algoritmi za izračunavanje hash funkcije. Najpoznatiji algoritmi su MD5, SHA-1, SHA-2 i druge verzije SHA, kao i domaći algoritam postavljen u GOST R 34.11-94.

Algoritam MD5 pojavio se početkom 90 -ih godina dvadesetog stoljeća kao rezultat poboljšanja algoritma za generiranje MD4 hash funkcije. Znakovi u imenu "MD" označavaju Sažetak poruke - sažetak poruke. Autor algoritama MD4 i MD5 je R. Rivest. Kao rezultat korištenja MD5, 128-bitna hash vrijednost se generira za proizvoljnu poruku. Ulazni podaci se obrađuju u blokovima od 512 bita. Algoritam koristi elementarno logičke operacije(inverzija, konjukcija, mod sabiranja 2, ciklični pomaci itd.), kao i obično aritmetičko sabiranje. Složeno ponavljanje ovih elementarne funkcije algoritam osigurava da je rezultat nakon obrade dobro izmiješan. Stoga je malo vjerojatno da dvije nasumično odabrane poruke imaju isti hash kod. MD5 algoritam ima sljedeće svojstvo: svaki bit primljene hash vrijednosti je funkcija svakog bita ulaza. MD5 se smatra najjačom hash funkcijom za 128-bitnu hash vrijednost.

Algoritam SHA Algoritam sigurnog raspršivanja (Secure Hash Algorithm) razvio je američki Nacionalni institut za standarde i tehnologiju (NIST) i objavljen kao Federalni informacijski standard SAD -a 1993. SHA-1 je, kao i MD5, baziran na MD4 algoritmu. SHA-1 generira 160-bitnu hash vrijednost na temelju obrade izvorne poruke u blokovima od 512 bita. Algoritam SHA-1 također koristi jednostavne logičke i aritmetičke operacije. Najvažnija razlika između SHA-1 i MD5 je u tome što je SHA-1 hash 32 bita duži od MD5 hasha. Ako pretpostavimo da su oba algoritma iste složenosti za kriptoanalizu, tada je SHA-1 robusniji algoritam. Koristeći brute force napad (frontalni napad), teže je stvoriti proizvoljnu poruku koja ima dati hash kod, a također je teže stvoriti dvije poruke koje imaju isti hash kod.

2001. Nacionalni institut za standarde i tehnologiju Sjedinjenih Država usvojio je tri hash funkcije kao standard sa dužom dužinom hash koda od SHA-1. Ove se hash funkcije često nazivaju SHA-2 ili SHA-256, SHA-384 i SHA-512 (naziv označava dužinu hash koda generiranog algoritmima). Ovi se algoritmi razlikuju ne samo po dužini generiranog hash koda, već i po korištenim internim funkcijama i dužini obrađenog bloka (za SHA-256, dužina bloka je 512, a za SHA-384 i SHA-512, dužina bloka je 1024 bita). Postupno poboljšanje SHA algoritma dovodi do povećanja njegove kriptografske snage. Unatoč međusobnim razlikama razmatranih algoritama, svi su oni daljnji razvoj SHA-1 i MD4 i imaju sličnu strukturu.

U Rusiji je usvojen GOST R34.11-94, što je domaći standard za funkcije raspršivanja. Njegova struktura se prilično razlikuje od strukture SHA-1,2 ili MD5 algoritama, koji su zasnovani na MD4 algoritmu. Dužina hash koda generiranog algoritmom GOST R 34.11-94 je 256 bita. Algoritam sekvencijalno obrađuje originalnu poruku u blokovima od 256 bita zdesna nalijevo. Parametar algoritma je početni vektor heširanja - proizvoljna fiksna vrijednost s dužinom od 256 bita. Algoritam GOST R 34.11-94 koristi operacije permutacije, pomaka, aritmetičkog sabiranja, sabiranja po modulu 2. Kao pomoćna funkcija u GOST 34.11-94, algoritam prema GOST 28147-89 koristi se u načinu jednostavne zamjene.

4. Zahtjevi za hash

Raspršena funkcija je jednosmjerna funkcija dizajnirana za preuzimanje sažetka ili "otiska prsta" datoteke, poruke ili nekog bloka podataka.

Heš kod generira funkcija H :

h = H (M)

Gde M je poruka proizvoljne dužine i h je hash kod fiksne dužine.

Razmotrite zahtjeve koje hash funkcija mora ispuniti da bi se mogla koristiti kao autentifikator poruke. Pogledajmo vrlo jednostavan primjer hash funkcije. Zatim ćemo analizirati nekoliko pristupa izgradnji hash funkcije.

Hash funkcija H koji se koriste za provjeru autentičnosti poruka moraju imati sljedeća svojstva:

1. Hash funkcija H mora se primijeniti na blok podataka bilo koje dužine.

2. Hash funkcija H stvara izlaz fiksne dužine.

3. H (M) relativno lako (u polinomskom vremenu) izračunava se za bilo koju vrijednost M .

4. Za bilo koju vrijednost hash koda h računski nemoguće pronaći M takav da H (M) = h .

5. Za bilo koje dato NS računski je nemoguće to pronaći

H (y) = H (x).

6. Računarski je nemoguće pronaći proizvoljan par ( NS , y ) takav da H (y) = H (x) .

Prva tri svojstva zahtijevaju hash funkciju za generiranje hash koda za bilo koju poruku.

Četvrto svojstvo definira zahtjev jednosmjerne hash funkcije: lako je stvoriti hash kod iz date poruke, ali je nemoguće oporaviti poruku iz datog hash koda. Ovo svojstvo je važno ako hash provjera autentičnosti uključuje tajnu vrijednost. Tajna vrijednost se možda neće poslati, međutim, ako hash funkcija nije jednosmjerna, protivnik može lako otkriti tajnu vrijednost na sljedeći način. Kada se prijenos presretne, napadač prima poruku M i hash kod C = H (SAB || M) ... Ako napadač može preokrenuti hash funkciju, onda može dobiti SAB || M = H-1 (C) ... Pošto napadač sada zna i M i SAB || M , get SAB sasvim jednostavno.

Peto svojstvo osigurava da se ne može pronaći druga poruka čija vrijednost raspršivanja odgovara vrijednosti raspršivanja. ove poruke... Ovo sprječava miješanje autentifikatora pri korištenju šifriranog hash koda. U ovom slučaju, protivnik može pročitati poruku i stoga generirati svoj hash kod. Ali budući da protivnik ne posjeduje tajni ključ, nema načina da promijeni poruku tako da je primatelj ne pronađe. Ako ovo svojstvo nije ispunjeno, napadač može izvršiti sljedeći slijed radnji: presresti poruku i njen šifrirani hash kod, izračunati hash kod poruke, stvoriti alternativnu poruku s istim hash kodom, zamijeniti originalnu poruku lažnom . Budući da su kodovi raspršivanja ovih poruka isti, primatelj neće otkriti lažiranje.

Raspršena funkcija koja zadovoljava prvih pet svojstava naziva se jednostavna ili slaba funkcija raspršivanja. Ako je, osim toga, zadovoljeno šesto svojstvo, tada se takva funkcija naziva jaka hash funkcija. Šesta imovina štiti od klase napada poznate kao rođendanski napad.

5. Jednostavne hash funkcije

Sve hash funkcije izvode se na sljedeći način. Ulazna vrijednost (poruka, datoteka itd.) Tretira se kao niz n -bitni blokovi. Ulazna vrijednost se sekvencijalno obrađuje blok po blok i stvara m -bitna vrijednost hash koda.

Jedan od najjednostavnijih primjera hash funkcije je bitovni XOR svakog bloka:

C i - i bit hash koda, 1 <= i <= n .

k - broj n -bitni blokovi unosa.

b ij – i ujeo se j th block.

Tada se cijela poruka šifrira, uključujući i hash kod, u CBC načinu za stvaranje šifriranih blokova Y1, Y2, ..., YN + 1. Po definiciji SHS imamo: Ali XN + 1 je hash kod: Budući da se izrazi u prethodnoj jednakosti mogu izračunati bilo kojim redoslijedom, stoga se hash kod neće mijenjati ako se šifrirani blokovi preurede. Originalni standard koji je predložio NIST koristio je jednostavan XOR, koji je primijenjen na 64-bitne blokove poruka, a zatim je cijela poruka šifrirana pomoću CBC načina. "Rođendanski paradoks" Prije nego pogledamo složenije hash funkcije, postoji jedan poseban napad na jednostavne hash funkcije koje je potrebno analizirati. Takozvani "rođendanski paradoks" je sljedeći. Pretpostavimo da je broj izlaznih vrijednosti hash funkcije H jednako n ... Koji bi trebao biti broj k tako da za određenu vrijednost X i vrednosti Y1, , Yk vjerovatnoća da barem jedan Yi zadovoljava jednakost H (X) = H (Y) bila veća od 0,5. Za jedan Y verovatnoća da H (X) = H (Y) , je jednako sa 1 / n . Prema tome, vjerovatnoća da , je jednako sa 1 - 1 / n . Ako kreirate k vrijednosti, tada je vjerojatnost da neće postojati slučajnosti ni za jednu od njih jednaka umnošku vjerovatnoća koje odgovaraju jednoj vrijednosti, tj. (1 - 1 / n) k . Stoga je vjerovatnoća barem jednog podudaranja jednaka 1 - (1 - 1 / n) k Tako smo saznali da za m -bitni hash kod je dovoljan za odabir 2m-1 poruka tako da je vjerojatnost podudaranja hash kodova veća od 0,5. Sada razmotrite sljedeći problem: označite P (n, k) vjerovatnoća da će u skupu k elemenata, od kojih svaki može uzeti n vrijednosti, postoje najmanje dvije s istim vrijednostima. Šta bi trebalo biti jednako k , do P (n, k) bilo bi više 0,5 ? Broj različitih načina odabira elemenata na takav način da nema duplikata je n (n-1) ... (n-k + 1) = n! / (n-k)! Ukupan broj mogućih načina odabira elemenata je n k Vjerojatnost da nema duplikata je n! / (n-k)! n k Vjerovatnoća postojanja duplikata je 1 - n! / (N -k)! Nk P (n, k) = 1 - n! / ((n-k)! x nk) = 1-(n x (n-1) x ... x (n-k-1)) / nk = 1-[(n-1) / n x (n-2) / n x ... x (n-k + 1) / n] = 1 - [(1- 1 / n) x (1 - 2 / n) x ... x (1 - (k -1) / n)] Ako je hashcode dugačak m bit tj. uzima 2m vrednosti, dakle Ovaj rezultat naziva se "rođendanski paradoks" jer, prema gore navedenom obrazloženju, kako bi dvije osobe imale više od 0,5 vjerojatnosti da se rođendani podudaraju, moraju biti samo 23 osobe u grupi. Ovaj rezultat izgleda iznenađujuće, možda zato što je za svakog pojedinca u grupi vjerovatnoća da će se njihov rođendan poklopiti s rođendanom nekog drugog u grupi prilično mala. Vratimo se na razmatranje svojstava hash funkcija. Pretpostavimo da se koristi 64-bitni hash kod. Može se smatrati da je to sasvim dovoljno i, prema tome, sigurna dužina za hash kod. Na primjer, ako je šifrirani hash kod WITH prenosi sa odgovarajućom nešifriranom porukom M , tada će neprijatelj morati pronaći M ' takav da H (M ") = H (M) , kako bi prevarili poruku i prevarili primaoca. U prosjeku, protivnik mora proći kroz 263 poruke kako bi pronašao poruku čiji je hash kod jednak presretnutoj poruci. Međutim, moguće su različite vrste napada zasnovane na "rođendanskom paradoksu". Moguća je sljedeća strategija: 1. Neprijatelj stvara 2 m / 2 opcije poruka, od kojih svaka ima određeno značenje. Protivnik priprema isti broj poruka, od kojih je svaka lažna i namjerava zamijeniti stvarnu poruku. 2. Dva seta poruka se uspoređuju kako bi se pronašao par poruka koje imaju isti hash kod. Vjerovatnoća uspjeha prema "rođendanskom paradoksu" veća je od 0,5. Ako nije pronađen odgovarajući par, generiraju se dodatne izvorne i lažne poruke dok se ne pronađe podudaranje. 3. Napadač nudi pošiljatelju originalnu poruku na potpis. Ovaj potpis se tada može priložiti lažnoj varijanti za prijenos primatelju. Budući da obje opcije imaju isti hash kod, bit će generiran isti potpis. Protivnik će biti siguran u uspjeh čak i bez poznavanja ključa za šifriranje. Dakle, ako se koristi 64-bitni hash kod, tada je potrebna računska složenost reda veličine 232. Zaključno, napominjemo da dužina hash koda mora biti dovoljno velika. Dužina od 64 bita se trenutno ne smatra sigurnom. Po mogućnosti, dužina je reda veličine 100 bita. Korištenje šifriranog lančanog bloka Postoje različite funkcije raspršivanja zasnovane na stvaranju lanca šifriranih blokova, ali bez upotrebe tajnog ključa. Jednu takvu hash funkciju predložio je Rabin. Poruka M razbijeni na blokove fiksne dužine M1, M2 ,. ... ... , MN i koristi simetrični algoritam šifriranja poput DES -a za izračunavanje hash koda G na sledeći način: H 0 - početna vrijednost H i = E Mi G = H N Ovo je slično korištenju šifriranja u CBC načinu rada, ali u ovom slučaju nema tajnog ključa. Kao i kod svake jednostavne hash funkcije, i ovaj je algoritam podložan "rođendanskom napadu", a ako je algoritam šifriranja DES i generira se samo 64-bitni hash kod, tada se sistem smatra prilično ranjivim. Mogu se izvesti i drugi napadi, poput "rođendana", koji su mogući čak i ako protivnik ima pristup samo jednoj poruci i odgovarajućem šifriranom hash kodu te ne može dobiti nekoliko parova poruka i šifriranih hash kodova. Mogući je sljedeći scenarij: pretpostavimo da je protivnik presreo poruku s autentifikatorom u obliku šifriranog hash koda, a poznato je da nešifrirani hash kod ima dužinu m bitovi. Dalje, neprijatelj mora izvršiti sljedeće radnje: Koristeći gore opisani algoritam, izračunajte nešifrirani hash kod G . Kreirajte lažnu poruku kao Q1, Q2 ,. ... ... , QN-2 . Izračunati H i = E Qi for 1 <= i <= N-2 . · Stvoriti 2 m / 2 nasumični blokovi NS i za svaki takav blok NS izračunati E X ... Kreirajte dodatni 2 m / 2 nasumični blok Y i za svaki blok Y izračunati D Y [G] , gdje D - odgovarajuća funkcija dešifriranja E ... Na temelju "rođendanskog paradoksa" možemo reći da će s velikim stupnjem vjerojatnosti ovaj niz sadržavati blokove NS i Y takav da E X = D Y [Y] . Kreiraj poruku Q1, Q2 ,. ... ... , QN-2, X, Y ... Ova poruka ima hash kod G i stoga se može koristiti zajedno sa šifriranim autentifikatorom. Ovaj oblik napada poznat je kao napad susretom u sredini. Različite studije su predložile sofisticiranije metode za jačanje blockchain pristupa. Na primjer, Davis i Price opisali su sljedeću opciju: Moguća je i druga opcija: Međutim, obje ove sheme su također osjetljive na različite napade. Općenito, može se pokazati da je neki oblik "rođendanskog napada" uspješan sa bilo kojim hash algoritmom koji uključuje upotrebu šifriranog bloka bez upotrebe tajnog ključa. Daljnje istraživanje bilo je usmjereno na pronalaženje drugih pristupa stvaranju funkcija raspršivanja. Hash funkcija MD5 Razmotrite MD5 (RFC 1321) algoritam za sažetak poruka koji je razvio Ron Rivest iz MIT -a. Logika izvođenja MD5 Algoritam prima poruku proizvoljne dužine kao ulaz i stvara 128-bitni sažetak poruke kao izlaz. Algoritam se sastoji od sljedećih koraka: Pirinač. 8.1. Logika izvođenja MD5 Korak 1: dodavanje nedostajućih bitova Poruka se dopunjava tako da njena dužina postaje 448 po modulu 512 (). To znači da je dužina dodane poruke 64 bita manja od višekratnika od 512. Dodavanje se uvijek vrši, čak i ako je poruka željene dužine. Na primjer, ako je poruka duga 448 bita, ona je dopunjena sa 512 bita do 960 bita. Stoga se broj dodanih bitova kreće od 1 do 512. Sabiranje se sastoji od jedne iza koje slijedi potreban broj nula. Korak 2: dodavanje dužine 64-bitni prikaz izvorne (prije dodavanja) dužine poruke u bitovima dodaje se rezultatu prvog koraka. Ako je originalna dužina veća od 2 64, tada se koriste samo posljednja 64 bita. Dakle, polje sadrži dužinu izvorne poruke po modulu 64. Prva dva koraka stvaraju poruku koja je višekratna od 512 bita. Ova proširena poruka predstavljena je kao niz 512-bitnih blokova Y 0, Y 1 ,. ... ., Y L-1, dok je ukupna dužina proširene poruke L * 512 bita. Dakle, dužina primljene proširene poruke je više od šesnaest 32-bitnih riječi. Pirinač. 8.2. Proširena struktura poruke Korak 3: inicijalizacija MD bafera 128-bitni međuspremnik koristi se za spremanje srednjih i konačnih rezultata hash funkcije. Međuspremnik se može predstaviti kao četiri 32-bitna registra (A, B, C, D). Ovi registri se inicijaliziraju sljedećim heksadecimalnim brojevima: A = 01234567 B = 89ABCDEF C = FEDCBA98 D = 76543210 Korak 4: obrada niza 512-bitnih (16 riječi) blokova Osnova algoritma je modul koji se sastoji od četiri ciklične obrade, označene kao HMD5. Četiri petlje imaju sličnu strukturu, ali svaka petlja koristi svoju vlastitu atomsku logičku funkciju, označenu f F, f G, f H i f I, respektivno. Pirinač. 8.3. Obrada sljedećeg 512-bitnog bloka Svaki ciklus uzima kao ulaz trenutni 512-bitni blok Y q, koji se trenutno obrađuje, i 128-bitnu vrijednost međuspremnika ABCD, koja je srednja sažeta vrijednost, i mijenja sadržaj ovog međuspremnika. Svaka petlja koristi i četvrti dio tablice T sa 64 elementa na osnovu funkcije sin. I-ti element T, označen sa T [i], ima vrijednost jednaku cijelom dijelu od 2 32 * abs (sin (i)), i je u radijanima. Budući da je abs (sin (i)) broj između 0 i 1, svaki element T je cijeli broj koji se može predstaviti s 32 bita. Tablica pruža "slučajni" skup 32-bitnih vrijednosti koje bi trebale ukloniti svaku pravilnost u unosu. Da bi se dobio MD q + 1, izlaz četiri ciklusa se dodaje modulo 2 32 sa MD q. Dodavanje se vrši nezavisno za svaku od četiri riječi u međuspremniku.

CLS s - kružni pomak ulijevo za s bitova 32 -bitnog argumenta.

X [k]-M je k-ta 32-bitna riječ u q-tom 512 bloku poruka.

T [i]-i-ta 32-bitna riječ u matrici T.

+ - dodatak mod 2 32.

U svakom od četiri ciklusa algoritma koristi se jedna od četiri osnovne logičke funkcije. Svaka atomska funkcija uzima tri 32-bitne riječi kao ulaz i stvara jednu 32-bitnu riječ na izlazu. Svaka funkcija je skup bitnih logičkih operacija, tj. N -ti bit izlaza je funkcija n -tog bita od tri ulaza. Osnovne funkcije su sljedeće:

Niz 32-bitnih riječi X sadrži vrijednost trenutnog 512-bitnog ulaznog bloka koji se trenutno obrađuje. Svaki ciklus se izvršava 16 puta, a budući da se svaki blok ulazne poruke obrađuje u četiri ciklusa, svaki blok ulazne poruke se obrađuje prema shemi prikazanoj na Sl. 4, 64 puta. Ako ulazni 512-bitni blok predstavimo u obliku šesnaest 32-bitnih riječi, tada se svaka ulazna 32-bitna riječ koristi četiri puta, jednom u svakom ciklusu, a svaki element tablice T sastoji se od 64 32-bitne riječi riječi, koristi se samo jednom. Nakon svakog koraka petlje, četiri riječi A, B, C i D. se ciklično pomiču ulijevo. U svakom koraku mijenja se samo jedna od četiri riječi međuspremnika ABCD. Stoga se svaka riječ u međuspremniku mijenja 16 puta, a zatim 17. put na kraju kako bi se dobio konačni izlaz tog bloka.

digest.

2. Brzina: softverska implementacija algoritma trebala bi biti dovoljno brza. Konkretno, algoritam bi trebao biti dovoljno brz na 32-bitnoj arhitekturi. Stoga se algoritam temelji na jednostavnom skupu elementarnih operacija na 32-bitnim riječima.

3. Jednostavnost i kompaktnost: algoritam bi trebao biti jednostavan za opisivanje i lako programiran, bez velikih programa ili tabela za pretraživanje. Ove karakteristike nemaju samo očigledne softverske prednosti, već su i poželjne sa sigurnosnog stanovišta, jer je bolje imati jednostavan algoritam za analizu mogućih slabosti.

4. Poželjna arhitektura sa malim endijanima: neke arhitekture procesora (kao što je linija Intel 80xxx) skladište leve bajtove reči na mestu adresa najmanjih krajnjih bajtova. Drugi (poput SUN Sparcstation) pohranjuju desne bajtove riječi na mjesto najmanje značajnih adresa bajtova (velika dodatna konstanta MD4 u prvoj petlji se ne primjenjuje. Slična dodatna konstanta koristi se za svaki od koraka u drugoj petlja. Još jedna dodatna konstanta se koristi za svaki od koraka u trećoj petlji. hash kod je funkcija svakog bita ulaza. Složeno ponavljanje atomskih funkcija f F, f G, f H i f I osigurava da rezultat je dobro izmiješan; to jest, malo je vjerojatno da su dvije poruke odabrane nasumično, čak i ako imaju naizgled slične obrasce, imaju iste sažetke koji proizvode istu izlaznu vrijednost, što znači da pokretanje MD5 na jednom 512-bitnom bloku rezultirat će istim izlazom za dva različita ulaza u međuspremniku ABCD.ne postoji na MD5.