Hash funkcije: koncept i osnove

U raznim granama informacijske tehnologije koriste se hash funkcije. One su, s jedne strane, osmišljene kako bi se znatno olakšala razmjena podataka između korisnika i obrada datoteka koje se koriste za različite namjene, as druge strane, optimizirati algoritme za osiguranje kontrole pristupa odgovarajućim resursima. Heš funkcija je jedan od ključnih alata za pružanje zaštite podataka lozinkom, kao i organiziranje razmjene dokumenata potpisanih digitalnim potpisom. Postoji velik broj standarda putem kojih se datoteke mogu pohraniti u predmemoriju. Mnoge od njih razvijaju ruski stručnjaci. Koje varijacije mogu predstavljati hash funkcije? Koji su glavni mehanizmi za njihovu praktičnu primjenu?

Što je to?

Prvo, istražite koncept hash funkcije. Taj se pojam obično shvaća kao algoritam za pretvaranje određene količine informacija u kraći slijed simbola pomoću matematičkih metoda. Praktični značaj hash funkcije može se pratiti u različitim područjima. Dakle, mogu se koristiti za provjeru integriteta datoteka i programa. Također, kriptografske hash funkcije se koriste u algoritmima šifriranja.

karakteristike

Razmotrite ključne karakteristike istraživanih algoritama. Među njima:

• prisutnost internih algoritama za pretvaranje podataka izvorne duljine u kraći slijed znakova;
• otvorenost za kriptografsku provjeru;
• prisutnost algoritama za pouzdano šifriranje izvornih podataka;
• prilagodba dešifriranju kada su uključene male računalne snage.

Među ostalim najvažnijim svojstvima hash funkcije:

• sposobnost obrade početnih nizova podataka proizvoljne duljine;
• generiraju hash-blokove fiksne duljine;
• ravnomjerno raspodijelite vrijednosti funkcije na izlazu.

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

Zahtjevi za raspršivanjem

Postoje brojni zahtjevi za hash funkcije dizajnirane za praktičnu uporabu u određenom području. Prvo, odgovarajući algoritam treba biti osjetljiv na promjene u unutarnjoj strukturi raspršenih dokumenata. To jest, u hash funkciji mora se prepoznati, ako govorimo o tekstualnoj datoteci, permutacijama paragrafa, crticama. S jedne strane, sadržaj dokumenta se ne mijenja, as druge - njegova struktura se prilagođava, a taj proces treba prepoznati tijekom heširanja. Drugo, razmatrani algoritam mora konvertirati podatke tako da je inverzna operacija (pretvaranje hash-a u izvorni dokument) praktički nemoguća. Treće, hash funkcija bi trebala uključivati ​​korištenje takvih algoritama, koji praktički isključuju vjerojatnost formiranja istog niza znakova u obliku hasha, drugim riječima - pojavu takozvanih sudara. Razmotrićemo njihovu bit malo kasnije.

Označeni zahtjevi, kojima se mora pridržavati hash funkcija, mogu se zadovoljiti uglavnom korištenjem složenih matematičkih pristupa.

struktura

Proučimo kakva može biti struktura razmatranih funkcija. Kao što smo napomenuli gore, među glavnim zahtjevima za razmatrane algoritme je osiguravanje jednosmjernosti enkripcije. Osoba koja ima samo hash na raspolaganju, teško bi mogla dobiti izvorni dokument na njegovoj osnovi.

U kojoj se strukturi može koristiti hash funkcija za takve svrhe? Primjer njezine kompilacije može biti: H (hash, to jest, hash) = f (T (tekst), H1), gdje je H1 algoritam za obradu teksta T. Ova funkcija ima T tako da bez poznavanja H1, otvori ga kao potpuno opremljenog datoteka će biti gotovo nemoguća.

Korištenje hash funkcija u praksi: preuzimanje datoteka

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

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

Hash funkcija i EDS

Uporaba hash funkcija je uobičajena kada se organizira razmjena dokumenata koji sadrže digitalni potpis. U tom slučaju, potpisana datoteka je raspršena tako da primatelj može provjeriti je li originalan. Iako formalno hash funkcija nije uključena u strukturu elektroničkog ključa, može se zabilježiti u flash memoriji hardvera s kojim su dokumenti potpisani, kao što je, na primjer, eToken.

Elektronički potpis je šifriranje datoteka uz korištenje javnih i privatnih ključeva. To znači da je poruka šifrirana privatnim ključem povezana s izvornom datotekom, a EDS se provjerava pomoću javnog ključa. Ako je hash funkcija oba dokumenta ista, datoteka koju je primatelj primio prepoznaje se kao autentična, a potpis pošiljatelja se prepoznaje kao valjan.

Hashing, kao što smo već napomenuli, nije izravno sastavni dio EDS-a, ali omogućuje vrlo učinkovito optimiziranje algoritama za aktiviranje elektroničkog potpisa. Dakle, samo se hash može šifrirati, a ne sam dokument. Kao rezultat toga, brzina obrade datoteka se značajno povećava, a istodobno postaje moguće osigurati učinkovitije mehanizme za zaštitu EDS-a, budući da će naglasak u računalnim operacijama u ovom slučaju biti stavljen ne na obradu izvornih podataka, već na osiguravanje kriptografske snage potpisa. Heš funkcija također omogućuje potpisivanje raznih vrste podataka a ne samo tekst.

Provjera zaporke

Još jedno moguće područje primjene hashinga je organizacija algoritama za provjeru lozinke postavljenih da ograniče pristup određenim resursima datoteka. Kako određene vrste hash funkcija mogu biti uključene u rješavanje takvih problema? Vrlo jednostavno.

Činjenica je da su na većini poslužitelja, kojima je pristup ograničen, lozinke pohranjene u obliku raspršenih vrijednosti. To je sasvim logično - ako su lozinke predstavljene u izvornom obliku, hakeri koji su im pristupili mogli su lako čitati tajne podatke. S druge strane, na temelju hash za izračun lozinke nije lako.

Kako se provjerava pristup korisnika kada se koriste razmatrani algoritmi? Lozinka koju je unio korisnik provjerava se s onim što je pohranjeno u hash funkciji koja je pohranjena na poslužitelju. Ako su vrijednosti tekstualnih blokova iste, korisnik dobiva potreban pristup resursima.

Najjednostavnija hash funkcija može se koristiti kao alat za provjeru lozinke. No, u praksi, IT-stručnjaci najčešće koriste složene kriptografske algoritme s više stupnjeva. U pravilu se dopunjuju primjenom standarda prijenos podataka preko sigurnog kanala - tako da hakeri ne mogu otkriti ili izračunati zaporku prenesenu s korisnikovog računala na poslužitelj - prije nego što je provjere sa blokiranim tekstom.

Sudari sudara

U teoriji hash funkcija takav je fenomen osiguran kao sudar. U čemu je njezina bit? Hašišni sudar je situacija u kojoj dvije različite datoteke imaju istu šifru. To je moguće ako je duljina ciljnog niza znakova mala. U tom slučaju vjerojatnost hash-podudaranja bit će veća.

Kako bi se izbjegli sudari, posebno se preporučuje korištenje dvostrukog algoritma nazvanog "hash-hashing function". To uključuje formiranje otvorenog i zatvorenog koda. Mnogi programeri u rješavanju važnih problema preporučuju da ne koristite hash funkcije u slučajevima kada to nije potrebno i uvijek testirati odgovarajuće algoritme za najbolju kompatibilnost s određenim ključevima.

Povijest izgleda

Osnivači teorije hash funkcija mogu se smatrati istraživačima Carter, Wegman, Simonson, Bierbrauer. U prvim verzijama, odgovarajući algoritmi korišteni su kao alat za formiranje jedinstvenih slika sekvenci znakova proizvoljne duljine s naknadnim ciljem identificiranja i provjere autentičnosti. S druge strane, hash, prema zadanim kriterijima, treba imati duljinu od 30-512 bita. Kao posebno korisna značajka odgovarajućih funkcija, razmatrana je njezina prikladnost za korištenje kao resursa za brzo pretraživanje datoteka ili njihovo razvrstavanje.

Popularni Hash standardi

Sada razmatramo popularne standarde u kojima se mogu prikazati hash funkcije. Među njima - CRC. Ovaj algoritam je ciklički kod, koji se naziva i kontrolni zbroj. Ovaj standard karakterizira jednostavnost, a istovremeno i univerzalnost - kroz njega možete hash najširi spektar podataka. CRC je jedan od najčešćih ne-kriptografskih algoritama.

Zauzvrat, kod šifriranja, standardi MD4 i MD5 su široko korišteni. Još jedan popularni kriptografski algoritam je SHA-1. Konkretno, karakterizira ga hash veličina od 160 bita, što je veće od MD5 - ovaj standard podržava 128 bita. Postoje ruski standardi koji reguliraju korištenje hash funkcija, - GOST R 34.11-94, kao i zamjenjujući ga s GOST R 34.11-2012. Može se primijetiti da hash-vrijednost koju pružaju algoritmi usvojeni u Ruskoj Federaciji je 256 bita.

Spomenuti standardi mogu se klasificirati iz različitih razloga. Na primjer, postoje oni koji koriste blok i specijalizirane algoritme. Jednostavnost proračuna temeljena na standardima prvog tipa često je praćena njihovom malom brzinom. Stoga, kao alternativa blokiranju algoritama, mogu biti uključeni oni koji uključuju manju količinu računalnih operacija. Uobičajeno je da se standardima visoke brzine pripisuju, prije svega, gore spomenuti MD4, MD5, kao i SHA. Razmotrite detaljnije specifičnosti posebnih algoritama raspršivanja na primjeru SHA.

Značajke SHA algoritma

Korištenje hash funkcija temeljenih na SHA standardu najčešće se provodi u području razvoja alata za digitalni potpis za DSA dokumente. Kao što smo napomenuli gore, SHA algoritam podržava 160-bitni hash (osiguravajući takozvani "digest" niza znakova). Početno razmatrani standard dijeli niz podataka na blokove od 512 bita. Ako je potrebno, ako duljina posljednjeg bloka ne dosegne zadanu znamenku, strukturu datoteke nadopunjujemo s 1 i potrebnim brojem nula. Na kraju odgovarajućeg bloka odgovara i kod koji fiksira duljinu poruke. Razmatrani algoritam uključuje 80 logičkih funkcija, pomoću kojih se obrađuje 3 riječi, prikazane u 32 bita. Također, u standardnom SHA korištenju 4 konstante.

Usporedba algoritama hasha

Pogledajmo kako su svojstva hash funkcija vezanih za različite standarde korelirala, primjerice, uspoređujući karakteristike ruskog standarda GOST R 34.11-94 i američkog SHA, o čemu smo raspravljali gore. Prije svega, treba napomenuti da je algoritam razvijen u Ruskoj Federaciji uključuje provedbu 4 operacije šifriranja po 1 ciklusu. To odgovara 128 rundi. Zauzvrat, za 1 krug, kada se aktivira SHA, pretpostavlja se da se izračunava oko 20 naredbi, dok je ukupan broj rundi 80. Dakle, korištenjem SHA možete obraditi 512 bita izvornih podataka tijekom 1 ciklusa. Istodobno, ruski standard je sposoban obavljati operacije po ciklusu od 256 bita podataka.

Specifičnosti najnovijeg ruskog algoritma

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

Kroz ovaj standard mogu se implementirati kriptografske hash funkcije, kao što je to slučaj s gore opisanim algoritmima. Može se primijetiti da najnoviji ruski standard podržava blok ulaznih podataka u iznosu od 512 bita. Glavne prednosti GOST R 34.11-2012:

• visoka razina sigurnosti od pucanja šifri;
• pouzdanost, podržana uporabom dokazanih struktura;
• operativni izračun heš funkcije, nedostatak transformacija u algoritmu, koji kompliciraju konstrukciju funkcije i usporavaju izračun.

Uočene prednosti novog ruskog standarda kriptografskog šifriranja omogućuju mu da se koristi pri organiziranju toka dokumenata koji zadovoljava najstrože kriterije koji su navedeni u odredbama regulatornog zakonodavstva.

Specifičnost kriptografskih heš funkcija

Razmotrimo detaljnije kako se vrste algoritama koje istražujemo mogu koristiti u području kriptografije. Ključni zahtjev za odgovarajuće funkcije je otpor prema sudarima, što smo već spomenuli. To znači da vrijednosti duple hash funkcije ne bi trebale biti formirane ako su te vrijednosti već prisutne u strukturi susjednog algoritma. Drugi gore navedeni kriteriji također bi trebali zadovoljiti kriptografske funkcije. Jasno je da uvijek postoji teoretska mogućnost vraćanja izvorne datoteke na temelju hash-a, osobito ako postoji moćan računski alat u pristupu. Međutim, ovaj scenarij trebao bi biti minimiziran zahvaljujući robusnim algoritmima šifriranja. Dakle, bit će vrlo teško izračunati hash-funkciju ako njezina računska snaga odgovara formuli 2 ^ {n / 2}.

Drugi važan kriterij kriptografskog algoritma je promjena u hash-u u slučaju korekcije početnog skupa podataka. Iznad smo primijetili da standardi enkripcije trebaju imati osjetljivost od 1 bita. Dakle, ovo svojstvo je ključni čimbenik u osiguravanju pouzdane zaštite lozinkom pristupa datotekama.

Iterativne sheme

Sada ispitujemo kako se kriptografski algoritmi raspršivanja mogu graditi. Među najčešćim shemama za rješavanje ovog problema je upotreba iterativnog sekvencijalnog modela. Temelji se na korištenju tzv. Funkcije kompresije, u kojoj je broj ulaznih bitova znatno veći od onih zabilježenih na izlazu.

Naravno, funkcija kompresije mora zadovoljiti potrebne kriterije za kriptografsku snagu. U interaktivnoj shemi, prva operacija za obradu ulaznog toka podataka je podijeljena na blokove, čija se veličina izračunava u bitovima. Odgovarajući algoritam također uključuje vremenske varijable određenog broja bitova. Prva vrijednost koristi dobro poznati broj, dok se sljedeći blokovi podataka kombiniraju s vrijednošću dotične funkcije na izlazu. Vrijednost hash-a postaje izlazni bit za posljednju iteraciju, koja uzima u obzir cijeli ulazni tok, uključujući prvu vrijednost. Takozvani "lavinski učinak" hasinga je osiguran.

Glavna poteškoća koja karakterizira hash implementirana kao iterativna shema je da je ponekad teško izgraditi hash funkcije ako ulazni tok nije identičan veličini bloka u koji je podijeljena početna podatkovna polja. Ali u ovom slučaju, standard raspršivanja može biti izrađen algoritmima pomoću kojih se izvorni tok može proširiti na ovaj ili onaj način.

U nekim slučajevima, takozvani algoritmi s više prolaza mogu biti uključeni u obradu podataka unutar iterativne sheme. Oni sugeriraju stvaranje još intenzivnijeg "lavinskog učinka". Takav scenarij pretpostavlja stvaranje ponovljenih nizova podataka, a samo sekundarno postoji ekspanzija.

Blok algoritam

Funkcija kompresije također se može temeljiti na blokovskom algoritmu kojim se izvodi enkripcija. Dakle, kako bi se povećala razina sigurnosti, možete koristiti podatkovne blokove koji će se raspršiti na trenutnoj iteraciji, kao ključ, a rezultat operacija dobivenih tijekom izvršenja funkcije kompresije prije toga - kao ulaz. Kao posljedica toga, posljednja iteracija osigurava izlaz algoritma. Hash sigurnost korelira s robusnošću uključenog algoritma.

Međutim, kao što smo već napomenuli, s obzirom na različite tipove hash funkcija, blokovski algoritmi često su popraćeni potrebom korištenja velikih računskih snaga. Ako nisu dostupni, brzina obrade datoteka možda neće biti dovoljna za rješavanje praktičnih problema povezanih s korištenjem hash funkcija. Istodobno se tražena kripto-otpornost može ostvariti s malim brojem operacija s izvorima izvornih podataka, a posebno su razmatrani algoritmi prilagođeni za rješavanje takvih problema - MD5, SHA, ruski kriptografski enkripcijski standardi.