Kriptografska hash funkcija. Šta je hash ili heširanje

Šta je heš? Hash funkcija je matematička transformacija informacija u kratki niz određene dužine.

Zašto je ovo potrebno? Analiza pomoću hash funkcija često se koristi za kontrolu integriteta važnih datoteka operativnog sistema, važnih programa i važnih podataka. Monitoring se može vršiti i po potrebi i na redovnoj osnovi.

Kako se to radi? Prvo odredite integritet datoteka koje treba kontrolisati. Za svaku datoteku izračunava se vrijednost njenog hasha prema posebnom algoritmu, a rezultat se pohranjuje. Nakon potrebnog vremena, pravi se sličan proračun i upoređuju se rezultati. Ako su vrijednosti različite, tada su informacije sadržane u datoteci promijenjene.

Koje karakteristike treba da ima hash funkcija?

• mora biti u stanju da izvrši transformaciju podataka proizvoljne dužine u fiksnu;
• mora imati otvoren algoritam kako bi se mogla istražiti njegova kriptografska snaga;
• treba da bude jednostrana, odnosno ne bi trebalo da postoji matematička mogućnost da se iz rezultata odrede početni podaci;
• treba da se "opire" kolizijama, odnosno da ne proizvodi iste vrijednosti za različite ulazne podatke;
• ne bi trebalo da zahtevaju velike računarske resurse;
• uz najmanju promjenu ulaznih podataka, rezultat bi se trebao značajno promijeniti.

Koji su popularni algoritmi heširanja? Sljedeće hash funkcije su trenutno u upotrebi:

• CRC je skraćenica za ciklički redundantni kod ili kontrolni zbroj. Algoritam je vrlo jednostavan, ima veliki broj varijacija u zavisnosti od tražene izlazne dužine. Nije kriptografski!
• MD 5 je veoma popularan algoritam. Kao i njegova prethodna verzija, MD 4 je kriptografska funkcija. Veličina heša je 128 bita.
• SHA -1 je također vrlo popularna kriptografska funkcija. Veličina heša je 160 bita.
• GOST R 34.11-94 je ruski kriptografski standard za izračunavanje hash funkcije. Veličina heša je 256 bita.

Kada administrator sistema može koristiti ove algoritme?Često, prilikom preuzimanja bilo kojeg sadržaja, kao što su programi sa web stranice proizvođača, muzika, filmovi ili druge informacije, postoji vrijednost kontrolne sume koja se izračunava pomoću određenog algoritma. Iz sigurnosnih razloga, nakon preuzimanja, morate samostalno izračunati hash funkciju i uporediti vrijednost s onim što je naznačeno na web stranici ili u prilogu datoteke. Jeste li ikada ovo radili?

Šta je zgodnije za izračunavanje heša? Sada postoji veliki broj takvih uslužnih programa, plaćenih i besplatnih. Meni se lično svidio HashTab. Prvo, tokom instalacije, uslužni program je ugrađen kao kartica u svojstva datoteke, drugo, omogućava vam da odaberete veliki broj algoritama za raspršivanje, i treće, besplatan je za privatnu nekomercijalnu upotrebu.

Šta je ruski? Kao što je gore spomenuto, u Rusiji postoji standard heširanja GOST R 34.11-94, koji naširoko koriste mnogi proizvođači alata za sigurnost informacija. Jedan od ovih alata je program za popravljanje i kontrolu početnog stanja softverskog paketa FIX. Ovaj program je sredstvo za praćenje efikasnosti korišćenja sredstava informacione bezbednosti.

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

• Izračunavanje kontrolnih suma datih fajlova korišćenjem jednog od 5 implementiranih algoritama.
• Fiksiranje i naknadna kontrola početnog stanja softverskog paketa.
• Poređenje verzija softverskih paketa.
• Popravljanje i kontrola direktorija.
• Kontrola promjena u određenim datotekama (direktorijima).
• Generisanje izveštaja u TXT, HTML, SV formatima.
• Proizvod ima FSTEC sertifikat prema NDV 3 br. 913 do 01. juna 2013. godine.

A šta je sa ECP-om? Rezultat izračuna heš funkcije, zajedno sa tajnim ključem korisnika, ulazi na ulaz kriptografskog algoritma, gdje se izračunava digitalni potpis. Strogo govoreći, hash funkcija nije dio EDS algoritma, ali se to često radi namjerno, kako bi se isključio napad javnim ključem.

Trenutno, mnoge aplikacije za e-trgovinu omogućavaju vam da pohranite tajni ključ korisnika u privatnom području tokena (ruToken, eToken) bez tehničke mogućnosti da ga odatle izvučete. Sam token ima vrlo ograničeno memorijsko područje, mjereno u kilobajtima. Da biste potpisali dokument, ne postoji način da se dokument prenese na sam token, ali je vrlo lako prenijeti heš dokumenta u token i dobiti EDS na izlazu.

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

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

Koncept hash funkcije

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

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

Smisao hash funkcije je odrediti karakterističnu osobinu prototipa - vrijednost hash funkcije. Ova vrijednost obično ima određenu fiksnu veličinu, kao što je 64 ili 128 bita. Heš kod se može dalje analizirati kako bi se riješio neki problem. Tako se, na primjer, heširanje može koristiti za upoređivanje podataka: ako dva niza podataka imaju različite hash kodove, zajamčeno je da se nizovi razlikuju; ako su isti, nizovi su najvjerovatnije isti. U općenitom slučaju, ne postoji korespondencija jedan-na-jedan između izvornih podataka i hash koda zbog činjenice da je broj vrijednosti hash funkcije uvijek manji od opcija ulaznih podataka. Stoga postoji mnogo ulaznih poruka koje daju iste hash kodove (takve situacije se nazivaju sudara). Vjerovatnoća kolizija igra važnu ulogu u procjeni kvaliteta hash funkcija.

Hash funkcije se široko koriste u modernoj kriptografiji.

Najjednostavnija hash funkcija može se sastaviti korištenjem operacije zbroja po modulu 2 na sljedeći način: dobiti ulazni niz, dodati sve bajtove po modulu 2 i vratiti bajt rezultata kao vrijednost hash funkcije. Dužina heš vrijednosti u ovom slučaju će biti 8 bita, bez obzira na veličinu ulazne poruke.

Na primjer, neka originalna poruka, digitalizirana, bude sljedeća (heksadecimalno):

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

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

Rezultat (0110 0101 (2) ili 65 (16) ) će biti heš vrijednost.

Međutim, takva hash funkcija ne može se koristiti u kriptografske svrhe, na primjer, za generiranje elektronskog potpisa, jer je prilično 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 kreirati dvije predslike s istom hash vrijednošću, kao i ako izlaz funkcije nema eksplicitnu ovisnost o ulazu.

Formulirajmo osnovne zahtjeve za kriptografske hash funkcije:

• hash funkcija mora biti primjenjiva na poruku bilo koje veličine;
• izračunavanje vrijednosti funkcije treba biti dovoljno brzo;
• s obzirom na vrijednost hash funkcije, trebalo bi biti teško (praktički nemoguće) pronaći odgovarajuću predsliku M ;
• s obzirom na poruku M, trebalo bi biti teško pronaći drugu poruku M' sa istom hash vrijednošću kao originalna poruka;
• mora da je teško pronaći bilo koji par nasumično različitih poruka sa istom hash vrijednošću.

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

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

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

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

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

Korištenje algoritama blokovnog šifriranja za formiranje hash funkcije

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

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

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

Tako formirana heš vrijednost se obično naziva umetak imitacije ili autentifikator i koristi se za provjeru integriteta poruke. Dakle, imitacijski umetak je kontrolna kombinacija koja ovisi o otvorenim podacima i informacijama tajnog ključa. Svrha upotrebe imitacije umetanja je da se otkriju sve slučajne ili namjerne promjene u nizu informacija. Vrijednost dobivena hash funkcijom prilikom obrade ulazne poruke pridružuje se poruci u trenutku kada se zna da je poruka ispravna. Prijemnik provjerava integritet poruke tako što izračunava simulakrum umetanja primljene poruke i upoređuje ga sa primljenim hash kodom, koji se mora prenijeti na siguran način. Jedna takva sigurna metoda bila bi šifriranje lažnog umetka privatnim ključem pošiljaoca, tj. kreiranje potpisa. Također je moguće šifrirati primljeni hash kod simetričnim algoritmom za šifriranje ako pošiljatelj i primalac imaju zajednički simetrični ključ za šifriranje.

Navedeni proces dobivanja i korištenja imitacije umetka opisan je u domaćem standardu GOST 28147-89. Standard predlaže korištenje nižih 32 bita bloka dobivenih na izlazu operacije šifriranja cijele poruke u modu lančanja blokova šifre za kontrolu integriteta poslane poruke. Na isti način, da biste formirali simulirani umetak, možete koristiti bilo koji blok simetrični algoritam šifriranja.

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

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

U svim ovim šemama, dužina generirane heš vrijednosti jednaka je dužini bloka kada je šifriran. Sve ove i neke druge sheme za korištenje blok šifre za izračunavanje hash vrijednosti mogu se primijeniti u praksi.

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

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

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

Kontrolne sume

Jednostavni, izuzetno brzi i laki za implementaciju hardverski algoritmi koji se koriste za zaštitu od nenamjernih izobličenja, uključujući hardverske greške.

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

Cijena za tako veliku brzinu je nedostatak kriptografske snage - laka prilika da se poruka uklopi u unaprijed poznatu količinu. Takođe je uobičajeno da su kontrolni sumi (tipični broj: 32 bita) manji od kriptografskih heševa (tipični brojevi: 128, 160 i 256 bita), što znači da može doći do nenamjernih kolizija.

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

Po pravilu, takav algoritam je neophodan za praćenje tipičnih hardverskih grešaka, kao što je nekoliko uzastopnih pogrešnih bitova do date dužine. Porodica algoritama tzv. "ciklički redundantni kodovi" zadovoljavaju ove zahtjeve. To uključuje, na primjer, CRC32, koji se koristi u ZIP opremi.

Kriptografske hash funkcije

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

Primjena heširanja

Hash funkcije se također koriste u nekim strukturama podataka - hash tablicama i kartezijanskim stablima. Zahtjevi za hash funkciju u ovom slučaju su različiti:

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

Usklađivanje podataka

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

Provjera greške

Na primjer, kontrolni zbroj se može prenijeti preko komunikacijskog kanala zajedno sa osnovnim tekstom. Na prijemnoj strani, kontrolni zbir se može ponovo izračunati i uporediti sa prenesenom vrednošću. Ako se pronađe neslaganje, to znači da je prijenos oštećen i da se može zatražiti ponavljanje.

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

Provjera šifre

U većini slučajeva, pristupne fraze se ne pohranjuju na ciljeve, već se pohranjuju samo njihove hash vrijednosti. Nije preporučljivo pohranjivati ​​pristupne fraze, jer će u slučaju neovlaštenog pristupa datoteci sa frazama napadač saznati sve pristupne fraze i moći će ih odmah koristiti, a prilikom pohranjivanja hash vrijednosti naučit će samo hash vrijednosti koji nisu reverzibilni na originalne podatke, u ovom slučaju, pristupnu frazu. Tokom postupka autentifikacije, heš vrijednost unesene šifre se izračunava i upoređuje sa pohranjenom.

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

Ubrzavanje preuzimanja podataka

Na primjer, kada pišete tekstualna polja u bazi podataka, njihov hash kod se može izračunati i podaci se mogu smjestiti u odjeljak koji odgovara ovom hash kodu. Zatim, prilikom pretraživanja podataka, prvo će biti potrebno izračunati hash kod teksta i odmah će postati poznato u kojem dijelu ih treba pretraživati, odnosno neće biti potrebno pretraživati ​​cijelu bazu podataka, već samo jedan od njegovih odjeljaka (ovo uvelike ubrzava pretragu).

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

Lista algoritama

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

Linkovi

Wikimedia fondacija. 2010 .

Pogledajte šta je "Hash kod" u drugim rječnicima:

Hash kod- rezultat aritmetičke kombinacije sa svim bajtovima programskog koda ili skupa podataka. Rezultat algoritma heširanja uključuje samo neke bajtove, a algoritam je dizajniran na način da svaka modifikacija programskog koda ili podataka sa ... ... Zvanična terminologija

Hash kod- rezultat aritmetičke kombinacije sa svim bajtovima programskog koda ili skupa podataka. Rezultat algoritma heširanja uključuje samo neke bajtove, a algoritam je dizajniran na način da svaka modifikacija programskog koda ili podataka sa ... ...

kod za autentifikaciju poruke koristeći hash funkciju- (ITU T H.235.3, ITU T H.235.1). Telekomunikacijske teme, osnovni koncepti EN raspršeni kod za autentifikaciju porukeHMAC ... Priručnik tehničkog prevodioca

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

MAC (kod za autentifikaciju poruke, kod za autentifikaciju poruke) je sredstvo za pružanje imitacije zaštite u protokolima za autentifikaciju poruka sa učesnicima koji međusobno vjeruju, poseban skup znakova koji se dodaje u ... ... Wikipedia

Haširanje (ponekad heširanje, eng. hashing) je transformacija niza ulaznih podataka proizvoljne dužine u izlazni niz bitova fiksne dužine. Takve transformacije se nazivaju i hash funkcije ili funkcije konvolucije, a njihovi rezultati ... ... Wikipedia

Ovaj članak je o kodu. Za metodu brainstorminga, pogledajte CRC mapu. Ciklična provjera redundancije (CRC) je algoritam za izračunavanje kontrolne sume dizajniran za provjeru integriteta ... ... Wikipedia

- (skraćenica za autentifikacioni kod poruke zasnovan na heš, autentifikacioni kod heš poruke). Posjedovanje načina da se provjeri integritet informacija koje se prenose ili pohranjuju u nepouzdanom okruženju je sastavni i neophodan dio svijeta ... ... Wikipedia

MI 2891-2004: Preporuka. GSOEI. Opšti zahtjevi za softver mjernih instrumenata- Terminologija MI 2891 2004: Preporuka. GSOEI. Opšti zahtevi za softver mernih instrumenata: Podaci su merne informacije predstavljene u obliku pogodnom za prenos, interpretaciju ili obradu. Definicije pojma iz ... ... Rječnik-priručnik pojmova normativne i tehničke dokumentacije

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

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

Kontrolne sume

Jednostavni, izuzetno brzi i laki za implementaciju hardverski algoritmi koji se koriste za zaštitu od nenamjernih izobličenja, uključujući hardverske greške.

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

Cijena za tako veliku brzinu je nedostatak kriptografske snage - laka prilika da se poruka uklopi u unaprijed poznatu količinu. Takođe je uobičajeno da su kontrolni sumi (tipični broj: 32 bita) manji od kriptografskih heševa (tipični brojevi: 128, 160 i 256 bita), što znači da može doći do nenamjernih kolizija.

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

Po pravilu, takav algoritam je neophodan za praćenje tipičnih hardverskih grešaka, kao što je nekoliko uzastopnih pogrešnih bitova do date dužine. Porodica algoritama tzv. "ciklički redundantni kodovi" zadovoljavaju ove zahtjeve. To uključuje, na primjer, CRC32, koji se koristi u ZIP opremi.

Kriptografske hash funkcije

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

Primjena heširanja

Hash funkcije se također koriste u nekim strukturama podataka - hash tablicama i kartezijanskim stablima. Zahtjevi za hash funkciju u ovom slučaju su različiti:

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

Usklađivanje podataka

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

Provjera greške

Na primjer, kontrolni zbroj se može prenijeti preko komunikacijskog kanala zajedno sa osnovnim tekstom. Na prijemnoj strani, kontrolni zbir se može ponovo izračunati i uporediti sa prenesenom vrednošću. Ako se pronađe neslaganje, to znači da je prijenos oštećen i da se može zatražiti ponavljanje.

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

Provjera šifre

U većini slučajeva, pristupne fraze se ne pohranjuju na ciljeve, već se pohranjuju samo njihove hash vrijednosti. Nije preporučljivo pohranjivati ​​pristupne fraze, jer će u slučaju neovlaštenog pristupa datoteci sa frazama napadač saznati sve pristupne fraze i moći će ih odmah koristiti, a prilikom pohranjivanja hash vrijednosti naučit će samo hash vrijednosti koji nisu reverzibilni na originalne podatke, u ovom slučaju, pristupnu frazu. Tokom postupka autentifikacije, heš vrijednost unesene šifre se izračunava i upoređuje sa pohranjenom.

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

Ubrzavanje preuzimanja podataka

Na primjer, kada pišete tekstualna polja u bazi podataka, njihov hash kod se može izračunati i podaci se mogu smjestiti u odjeljak koji odgovara ovom hash kodu. Zatim, prilikom pretraživanja podataka, prvo će biti potrebno izračunati hash kod teksta i odmah će postati poznato u kojem dijelu ih treba pretraživati, odnosno neće biti potrebno pretraživati ​​cijelu bazu podataka, već samo jedan od njegovih odjeljaka (ovo uvelike ubrzava pretragu).

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

Lista algoritama

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

Linkovi

Wikimedia fondacija. 2010 .

• Heshang Moheyan
• Hash kod

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

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

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

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

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

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

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

hash funkcija- hash funkcija 1. Funkcija koja kontrolira proces unosa podataka u hash tablicu, određivanje (adrese slobodnih ćelija. 2. Funkcija koja predstavlja prikaz fragmenta otvorene poruke u šifriranom nizu fiksne dužine. U ... ... Priručnik tehničkog prevodioca

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

Hash kod- Hashing (ponekad heširanje, eng. hashing) konverzija niza ulaznih podataka proizvoljne dužine u izlazni niz bitova fiksne dužine. Takve transformacije se nazivaju i hash funkcije ili funkcije konvolucije, 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

Algoritmi pretraživanja koje smo razmatrali obično su zasnovani na apstraktnoj operaciji poređenja. Iz ove serije izdvaja se metoda distributivnog pretraživanja opisana u "Tabele simbola i binarna stabla pretraživanja", u kojoj je element sa ključem i pohranjen na i-toj poziciji tabele, što vam omogućava direktan pristup. U distributivnom traženju, vrijednosti ključa se koriste kao indeksi niza, a ne kao operandi operacije poređenja; sama metoda je zasnovana na činjenici da su ključevi različiti cijeli brojevi iz istog raspona kao i indeksi tablice. U ovom poglavlju ćemo pogledati heširanje, proširenje distributivnog pretraživanja koje se koristi u tipičnijim aplikacijama za pretraživanje gdje ključevi nemaju tako zgodna svojstva. Krajnji rezultat ovog pristupa se prilično razlikuje od metoda zasnovanih na usporedbi - umjesto da prelazimo preko struktura podataka rječnika upoređujući ključeve za pretraživanje sa ključevima u elementima, pokušavamo pristupiti elementima u tablici direktno izvodeći aritmetičku konverziju ključeva u adrese tablice.

Algoritmi pretraživanja koji koriste heširanje sastoje se od dva različita dijela. Prvi korak je izračunavanje hash funkcije (hash funkcija) koja pretvara ključ za pretraživanje u adresu u tabeli. 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 tabeli. Dakle, drugi dio hash pretraživanja je proces rješavanja kolizije, koji rukuje tim ključevima. Jedna od tehnika rješavanja sukoba koju ćemo pokriti u ovom poglavlju koristi povezane liste, tako da ima direktnu upotrebu u dinamičkim situacijama u kojima je teško unaprijed predvidjeti broj ključeva za pretraživanje. Druge dvije metode rezolucije sudara postižu visoku razinu performanse potražite jer su elementi pohranjeni u fiksnom nizu. Razmotrićemo način da poboljšamo ove metode, omogućavajući im da se koriste iu slučajevima kada je nemoguće unapred predvideti veličinu tabele.

Haširanje je dobar primjer ravnoteže između vremena i memorijskog prostora. Da nije bilo ograničenja u količini korištene memorije, bilo koje pretraživanje bi se moglo obaviti samo jednim pristupom memoriji, jednostavnim korištenjem ključa kao memorijske adrese, kao u alokativnom pretraživanju. Međutim, ovo idealno kućište obično nije ostvarivo jer dugi ključevi mogu zahtijevati ogromnu količinu memorije. S druge strane, da nije bilo ograničenja na vodeće vrijeme, bilo bi moguće proći s minimalnom količinom memorije koristeći metodu sekvencijalnog pretraživanja. Haširanje je način da se iskoristi prihvatljiva količina i memorije i vremena, te uspostavi ravnoteža između ova dva ekstrema. Konkretno, bilo koja ravnoteža se može održati jednostavnim promjenom veličine tablice umjesto ponovnim pisanjem koda ili odabirom različitih algoritama.

Haširanje je jedan od klasičnih problema kompjuterske nauke: njeni različiti algoritmi su detaljno proučavani i široko se koriste. Videćemo da se, pod labavim pretpostavkama, možemo nadati da ćemo podržati operacije pronalaženja i umetanja u tabele simbola sa konstantnim vremenom izvršenja, bez obzira na veličinu tabele.

Ova očekivana vrijednost je teoretski optimalna izvedba za bilo koju implementaciju tablice simbola, ali heširanje još uvijek nije lijek iz dva glavna razloga. prvo, vodeće vrijeme zavisi od dužine ključa, što može biti značajno u stvarnim aplikacijama koje koriste duge ključeve. Drugo, heširanje ne pruža efikasne implementacije drugih operacija tabele znakova, kao što su odabir ili sortiranje. U ovom poglavlju ćemo detaljno 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 ovo aritmetičko izračunavanje nije teško implementirati, ali se mora paziti da ne naiđete na razne suptilne zamke. S obzirom na tablicu koja može sadržavati M elemenata, potrebna vam je funkcija koja pretvara ključeve u cijele brojeve u rasponu. Idealnu hash funkciju trebalo bi lako izračunati i izgledati kao nasumična funkcija: za bilo koji dati argument, rezultati bi u nekom smislu trebali biti jednako vjerojatni.

Haš funkcija ovisi o vrsti ključa. Strogo govoreći, svaka moguća vrsta ključa zahtijeva posebnu hash funkciju. Da bi se poboljšala efikasnost, obično je poželjno izbjeći eksplicitne konverzije tipova, umjesto da se pribjegne ideji da se binarni prikaz ključeva u strojnoj riječi smatra cijelim brojem koji se može koristiti u aritmetičkim proračunima. Haširanje je prethodilo jezicima visokog nivoa - na ranim računarima bilo je uobičajeno tretirati vrijednost ili kao string ključ ili kao cijeli broj. U nekim jezicima visokog nivoa, teško je kreirati programe koji zavise od prikaza ključeva na određenom računaru, jer su takvi programi, u stvari, zavisni od mašine i stoga ih je teško preneti na drugi računar. Tipično, heš funkcije zavise od procesa pretvaranja ključeva u cijele brojeve, tako da može biti teško da implementacije heširanja budu i neovisne o stroju i efikasne u isto vrijeme. Općenito, jednostavni ključevi s cijelim brojem ili ključevi s pomičnim zarezom mogu se pretvoriti samo jednom mašinskom operacijom, ali string ključevi i drugi tipovi kompozitnih ključeva su skuplji i zahtijevaju više pažnje na efikasnost.

Vjerojatno najjednostavnija situacija je kada su ključevi brojevi s pomičnim zarezom iz fiksnog raspona. Na primjer, ako su ključevi brojevi veći od 0 i manji od 1, mogu se jednostavno pomnožiti sa M, zaokružiti na najbliži cijeli broj i dati adresu između 0 i M - 1; takav primjer je prikazan na sl. 14.1. Ako su ključevi veći od s i manji od t, mogu se skalirati oduzimanjem s i dijeljenjem sa t-s tako da padaju između 0 i 1, a zatim pomnoženim sa M da bi se dobila adresa u tabeli.

Rice. 14.1.

Da biste pretvorili brojeve s pomičnim zarezom između 0 i 1 u indekse u tabeli veličine 97, ovi brojevi se množe sa 97. U ovom primjeru, došlo je do tri kolizije: za indekse jednake 17, 53 i 76. Haš vrijednosti ​Određene su višim znamenkama ključa, niže cifre ne igraju nikakvu ulogu. Jedan od ciljeva dizajna hash funkcije je eliminisati takvu neravnotežu tako da se svaki bit uzima u obzir tokom izračunavanja.

Ako su ključevi w-bit cijeli brojevi, mogu se pretvoriti u float i podijeliti sa 2 w da bi se dobili floatovi između 0 i 1, a zatim pomnoženi sa M kao u prethodnom paragrafu. Ako operacije s pomičnim zarezom traju dugo i brojevi nisu dovoljno veliki da izazovu prelijevanje, isti rezultat se može dobiti korištenjem cjelobrojnih aritmetičkih operacija: trebate pomnožiti ključ s M, a zatim pomaknuti desno za w bitova da biste podijelili sa 2 w (ili, ako se množenje prekorači, izvršite pomak, a zatim množenje). Takve metode su beskorisne za heširanje osim ako ključevi nisu ravnomjerno raspoređeni u rasponu, budući da je heš vrijednost određena samo vodećim znamenkama ključa.

Jednostavnija i efikasnija metoda za w-bitne cijele brojeve - jedna od možda najčešće korištenih metoda heširanja - je da odaberete veličinu tabele M jednostavnog broja i izračunate ostatak nakon dijeljenja k sa M, tj. h(k) = k mod M za bilo koji cjelobrojni ključ k. Takva funkcija se naziva modularna hash funkcija. Veoma je lako izračunati (k % M u C++) i efikasan je za postizanje ujednačene distribucije ključnih vrednosti između vrednosti manjih od M. Mali primer je prikazan na slici 1-2. 14.2.

Tri desna kolona prikazuju hash rezultat 16-bitnih ključeva prikazanih na lijevoj strani koristeći sljedeće funkcije:

v % 97 (lijevo)

v % 100 (u sredini) i

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

gdje je a = .618033 . Veličine tablica za ove funkcije su 97, 100, odnosno 100. Vrijednosti izgledaju nasumično (jer su ključevi nasumični). Druga funkcija (v % 100) koristi samo dvije krajnje desne cifre ključeva i stoga može pokazati loše performanse za nenasumične tipke.

Modularno heširanje se odnosi 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 cjelobrojne vrijednosti, a zatim upotrijebite modularnu hash funkciju. Druga opcija je jednostavno koristiti binarni prikaz ključa (ako je dostupan) kao operand modularne hash funkcije.

Modularno heširanje se koristi u svim slučajevima kada postoji pristup bitovima koji čine ključeve, bez obzira na to da li su cijeli brojevi predstavljeni mašinskom riječi, nizom znakova upakovanih u strojnu riječ ili predstavljeni bilo kojom drugom mogućom opcijom. Niz nasumičnih znakova upakovanih u mašinsku riječ nije potpuno isti kao nasumični cjelobrojni ključevi, budući da se svi bitovi ne koriste za kodiranje. Ali oba ova tipa (i bilo koji drugi tip ključa koji je kodiran da stane u mašinsku riječ) mogu se učiniti da izgledaju kao nasumični indeksi na maloj tablici.

Glavni razlog za odabir veličine heš tabele M da bude prost broj za modularno heširanje prikazan je na Sl. 14.3. U ovom primjeru podataka 7-bitno kodiranih znakova, ključ se tretira kao broj u bazi 128, jedna cifra za svaki znak u ključu. Riječ sada odgovara broju 1816567, koji se također može napisati kao

jer u ASCII kodu znakovi n, o i w odgovaraju brojevima 1568 = 110 , 1578 = 111 i 1678 = 119 . Izbor veličine tabele M = 64 za ovu vrstu ključa je nesrećan, jer dodavanje višekratnika od 64 (ili 128) na x ne menja vrednost x mod 64 - za bilo koji ključ, vrednost heš funkcije je vrednost od zadnjih 6 bitova ovog ključa. Naravno, dobra hash funkcija treba da uzme u obzir sve bitove ključa, posebno za znakovne ključeve. Slične situacije mogu nastati kada M sadrži faktor koji je stepen 2. Najjednostavniji način da se to izbjegne je da odaberete prost broj za M.

Svaki red ove tablice sadrži: riječ od 3 slova, ASCII reprezentaciju te riječi kao 21-bitni broj u oktalnom i decimalnom obliku i standardne modularne funkcije raspršivanja za veličine tablice 64 i 31 (dvije krajnje desne kolone) . Veličina tabele od 64 dovodi do neželjenih rezultata jer se samo krajnje desne cifre ključa koriste za izvođenje hash vrijednosti, a slova u riječima uobičajenog jezika su neravnomjerno raspoređena. Na primjer, sve riječi koje se završavaju slovom y imaju heš vrijednost 57. Suprotno tome, jednostavna vrijednost od 31 uzrokuje manje kolizija u tabeli koja je više od polovine veličine.

Modularno heširanje je vrlo lako implementirati, osim što veličina tabele mora biti prost broj. Za neke aplikacije, neko može biti zadovoljan malim poznatim prostim brojem ili može pretraživati ​​listu poznatih prostih brojeva za onim koji je blizu potrebnoj veličini tabele. Na primjer, brojevi jednaki 2 t - 1 su prosti kada t = 2, 3, 5, 7, 13, 17, 19 i 31(i ni za jednu drugu vrijednost t< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.

Ova tablica najvećih prostih brojeva manjih od 2n for , može se koristiti za dinamičko dodjeljivanje hash tablice kada želite da veličina hash tablice bude prost broj. Za bilo koju datu pozitivnu vrijednost unutar pokrivenog raspona, ova tabela se može koristiti za određivanje prostog broja koji je manji od 2 puta od njegovog vlastitog.

Druga opcija za rukovanje cjelobrojnim ključevima je kombiniranje multiplikativne i modularne metode: trebate pomnožiti ključ konstantom u rasponu između 0 i 1, a zatim izvršiti dijeljenje po modulu M. Drugim riječima, trebate koristiti . Postoji odnos između vrijednosti , M i efektivnog radiksa ključa koji bi teoretski mogao dovesti do anomalnog ponašanja, ali ako se koristi proizvoljna vrijednost a, malo je vjerovatno da će biti problema u stvarnoj primjeni. Često se vrijednost a bira kao f = 0,618033 ... (zlatni presjek).

Istražene su mnoge druge varijacije na ovu temu, posebno hash funkcije koje se mogu implementirati pomoću efikasnih mašinskih instrukcija kao što su pomak i izbor maske (pogledajte odjeljak veza).

U mnogim aplikacijama koje koriste tabele znakova, tasteri nisu brojevi i nisu nužno kratki; češće su to alfanumerički nizovi koji mogu biti prilično dugi. Kako onda izračunati hash funkciju za riječ kao što je averylongkey?

U 7-bitnom ASCII-u, 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. I često je potrebno obraditi mnogo duže ključeve.

Za izračunavanje modularne hash funkcije za dugačke ključeve, oni se pretvaraju dio po dio. Možete iskoristiti prednosti aritmetičkih svojstava funkcije modula i koristiti Hornerov algoritam (pogledajte odjeljak 4.9 "Apstraktni tipovi podataka"). Ova metoda se zasniva na drugom načinu pisanja brojeva koji odgovaraju ključevima. Za ovaj primjer pišemo 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*)

To jest, decimalni broj koji odgovara kodiranju znakova niza može se izračunati gledanjem s lijeva na desno, množenjem akumulirane vrijednosti sa 128, a zatim dodavanjem vrijednosti koda sljedećeg znaka. U slučaju dugog niza, ova metoda izračunavanja će na kraju dovesti do broja većeg od onoga što se uopće može predstaviti u kompjuteru. Međutim, ovaj broj nije potreban, jer je potreban samo (mali) ostatak kada se dijeli sa M. Rezultat se može dobiti čak i bez pohranjivanja velike akumulirane vrijednosti, jer u bilo kom trenutku u izračunavanju, možete odbaciti višekratnik M - svaki put kada izvodite množenje i sabiranje, morate pohraniti samo ostatak dijeljenja po modulu M. Rezultat će biti isti kao da smo imali priliku izračunati dugi broj, a zatim izvršite dijeljenje (vidi vježbu 14.10). Ovo zapažanje vodi do direktnog aritmetičkog načina izračunavanja modularnih heš funkcija za dugačke nizove - vidi program 14.1. Ovaj program koristi posljednji trik: umjesto osnove 128, koristi prost broj 127. Razlog za ovu promjenu je razmatran u sljedećem paragrafu.

Postoji mnogo načina za izračunavanje hash funkcija po približno istoj cijeni kao i modularno heširanje korištenjem Hornerove metode (jedna ili dvije aritmetičke operacije za svaki znak u ključu). Za nasumične ključeve, ove metode su praktički iste, ali pravi ključevi su rijetko nasumični. 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 tablice bez obzira na distribuciju ključeva. Randomizaciju nije teško organizirati, jer uopće nije potrebno striktno se pridržavati definicije modularnog heširanja - potrebno je samo da se svi bitovi ključa koriste u izračunavanju cijelog broja manjeg od M.

Program 14.1. Hash funkcija za string ključeve

M = 96 i a = 128 (gore),

M = 97 i a = 128 (centar) i

M = 96 i a = 127 (dole)

Neravnomjerna raspodjela u prvom slučaju rezultat je neravnomjerne upotrebe slova i postojanosti neravnomjernosti zbog činjenice da su i veličina tablice i množitelj višestruki od 32. Druga dva primjera izgledaju nasumično jer veličina tablice i množitelj su međusobno prosti brojevi.

Program 14-1 pokazuje jedan način da se to uradi: korišćenje jednostavne baze umesto stepena 2 i celog broja koji odgovara ASCII prikazu niza. Na sl. 14.5 sl. Slika 14.5 pokazuje kako ova promjena poboljšava distribuciju tipičnih string ključeva. Teoretski, heš vrijednosti koje proizvodi Program 14.1 mogu dati loše rezultate za veličine tablica koje su višestruke od 127 (iako je u praksi to vjerovatno gotovo neprimjetno); da bi se kreirao randomizirani algoritam, može se nasumično odabrati vrijednost množitelja. Još efikasniji pristup je korištenje nasumičnih vrijednosti koeficijenta 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.

Teoretski, idealna univerzalna heš funkcija je ona za koju je vjerovatnoća kolizije između dva različita ključa u tabeli veličine M tačno 1/M. Može se dokazati da korištenje ne fiksne proizvoljne vrijednosti kao koeficijenta a u programu 14.1, već niza nasumičnih različitih vrijednosti, transformiše modularno heširanje u univerzalnu hash funkciju. Međutim, cijena generiranja novog slučajnog broja za svaki znak u ključu je obično neprihvatljiva. U praksi se može postići kompromis prikazan u Programu 14.1 tako što se ne pohranjuje niz različitih slučajnih brojeva za svaki simbol ključa, već variranjem koeficijenata generiranjem jednostavnog pseudo-slučajnog niza.

Da rezimiramo, da biste koristili raspršivanje za implementaciju tablice apstraktnih simbola, prvo morate proširiti interfejs apstraktnog tipa kako biste uključili heš operaciju koja mapira ključeve u nenegativne cijele brojeve manje od veličine tablice M.