Hash funkcije: koncept in osnove

V različnih vejah informacijske tehnologije se uporabljajo funkcije razpršitve. Oblikovani so po eni strani za bistveno poenostavitev izmenjave podatkov med uporabniki in obdelavo datotek, ki se uporabljajo za različne namene, na drugi strani za optimizacijo algoritmov za zagotavljanje nadzora dostopa do ustreznih virov. Funkcija razprševanja je eno od ključnih orodij za zagotavljanje zaščite podatkov z geslom ter organiziranje izmenjave dokumentov, podpisanih z digitalnim podpisom. Obstaja veliko število standardov, preko katerih je mogoče predpomniti datoteke. Mnoge izmed njih so razvili ruski strokovnjaki. Katere variacije lahko predstavljajo razpršene funkcije? Kateri so glavni mehanizmi za njihovo praktično uporabo?

Kaj je to?

Najprej raziščite koncept hash funkcije. Ta izraz se običajno razume kot algoritem za pretvorbo določene količine podatkov v krajše zaporedje simbolov s pomočjo matematičnih metod. Praktični pomen hash funkcije je mogoče zaslediti na različnih področjih. Torej jih lahko uporabite pri preverjanju celovitosti datotek in programov. Prav tako se v algoritmih šifriranja uporabljajo kriptografske razpršitvene funkcije.

Značilnosti

Razmislite o ključnih značilnostih preiskovanih algoritmov. Med temi: t

• prisotnost notranjih algoritmov za pretvorbo podatkov prvotne dolžine v krajše zaporedje znakov;
• odprtost za kriptografsko preverjanje;
• prisotnost algoritmov za zanesljivo šifriranje izvirnih podatkov;
• prilagoditev dešifriranju, kadar gre za majhne računalniške moči.

Med drugimi najpomembnejšimi lastnostmi hash funkcije:

• zmožnost obdelave začetnih podatkovnih polji poljubne dolžine;
• ustvarjanje hash blokov s fiksno dolžino;
• enakomerno porazdelite vrednosti funkcije na izhodu.

Obravnavani algoritmi prav tako predlagajo občutljivost za vhodne podatke na ravni 1 bita. To pomeni, da se, čeprav pogojno rečeno, vsaj ena črka v izvornem dokumentu spremeni, bo razpršena funkcija izgledala drugače.

Zahteve za heš

Obstajajo številne zahteve za razpršitvene funkcije, ki so zasnovane za praktično uporabo na določenem področju. Prvič, ustrezen algoritem mora biti občutljiv na spremembe v notranji strukturi razpršenih dokumentov. To pomeni, da je treba v funkciji razpršitve prepoznati, če govorimo o besedilni datoteki, permutacijah odstavkov, deljenju besed. Po eni strani se vsebina dokumenta ne spremeni, na drugi strani pa se njena struktura prilagodi, ta proces pa je treba prepoznati med zgoščevanjem. Drugič, obravnavani algoritem mora podatke pretvoriti tako, da je obratno delovanje (obračanje haše v izvirni dokument) praktično nemogoče. Tretjič, razpršilna funkcija bi morala vključevati uporabo takšnih algoritmov, ki praktično izključujejo verjetnost nastanka istega niza znakov v obliki hašiša, z drugimi besedami - pojavom tako imenovanih trkov. O njihovem bistvu bomo šli malo kasneje.

Označene zahteve, ki jih mora izpolnjevati hash funkcija, se lahko dosežejo predvsem z uporabo kompleksnih matematičnih pristopov.

Struktura

Preučimo, kakšna je lahko struktura obravnavanih funkcij. Kot smo že omenili, je med glavnimi zahtevami obravnavanih algoritmov zagotavljanje enosmernosti šifriranja. Oseba, ki ima na razpolago samo hašiš, bi težko pridobila izvorni dokument na njegovi podlagi.

V kateri strukturi lahko uporabimo funkcijo razpršitve za te namene? Primer njegove kompilacije je lahko: H (hash, tj. Hash) = f (T (besedilo), H1), kjer je H1 algoritem za obdelavo besedila T. Ta funkcija ima T tako, da ga brez poznavanja H1 odpre kot polno funkcijo datoteka bo skoraj nemogoča.

Uporaba hash funkcij v praksi: prenos datotek

Zdaj podrobneje preučimo možnosti uporabe hash funkcij v praksi. Uporabo ustreznih algoritmov lahko uporabimo pri pisanju scenarijev za prenos datotek iz internetnih strežnikov.

V večini primerov se za vsako datoteko določi določena kontrolna vsota - to je hash. Enak mora biti za objekt, ki se nahaja na strežniku in prenesti na uporabniški računalnik. V nasprotnem primeru se datoteka morda ne bo odprla ali se morda ne bo pravilno zagnala.

Hash funkcija in EDS

Uporaba razpršitvenih funkcij je pogosta pri organiziranju izmenjave dokumentov, ki vsebujejo digitalni podpis. V tem primeru se podpisana datoteka razprši, tako da lahko prejemnik preveri, ali je pristna. Čeprav formalno hash funkcija ni vključena v strukturo elektronskega ključa, se lahko zabeleži v pomnilniku flash strojne opreme, s katero so podpisani dokumenti, kot je npr. EToken.

Elektronski podpis je šifriranje datotek z uporabo javnih in zasebnih ključev. To pomeni, da je sporočilo, šifrirano z zasebnim ključem, povezano z izvorno datoteko, EDS pa se preverja z javnim ključem. Če je funkcija razpršitve obeh dokumentov enaka, je datoteka, ki jo ima prejemnik, prepoznana kot verodostojna, podpis podpisnika pa je priznan kot veljaven.

Hashing, kot smo že omenili, ni neposredno sestavni del EDS, vendar omogoča zelo učinkovito optimizacijo algoritmov za aktiviranje elektronskih podpisov. Torej lahko šifriramo samo razpršeno, ne pa samega dokumenta. Zaradi tega se hitrost obdelave datotek znatno poveča, hkrati pa je mogoče zagotoviti učinkovitejše mehanizme za zaščito EDS, saj bo poudarek v računskih operacijah v tem primeru postavljen ne na obdelavo izvirnih podatkov, temveč na zagotavljanje kriptografske moči podpisa. Funkcija razprševanja omogoča tudi podpisovanje različnih podatkovnih tipov in ne samo besedilo.

Preverjanje gesla

Drugo možno področje uporabe razprševanja je organizacija algoritmov za preverjanje gesel, ki so določeni za omejitev dostopa do določenih datotečnih virov. Kako lahko v reševanje takšnih problemov sodelujejo določene vrste razpršenih funkcij? Zelo preprosto.

Dejstvo je, da so na večini strežnikov, do katerih je dostop omejen, gesla shranjena v obliki zgoščenih vrednosti. To je povsem logično - če so bila gesla predstavljena v izvirnem besedilu, bi lahko hekerji, ki so pridobili dostop do njih, zlahka prebrali tajne podatke. V zameno, na podlagi hash za izračun gesla ni enostavno.

Kako se preverja dostop uporabnika pri uporabi obravnavanih algoritmov? Geslo, ki ga vnese uporabnik, se preveri glede na to, kaj je shranjeno v razpršeni funkciji, ki je shranjena na strežniku. Če so vrednosti besedilnih blokov enake, dobi uporabnik potreben dostop do virov.

Najpreprostejšo razpršilno funkcijo lahko uporabite kot orodje za preverjanje gesel. V praksi pa strokovnjaki za informacijsko tehnologijo najpogosteje uporabljajo kompleksne večstopenjske kriptografske algoritme. Praviloma se dopolnjujejo z uporabo standardov prenos podatkov prek varnega kanala - tako da hekerji ne morejo zaznati ali izračunati gesla, ki ga prenaša računalnik uporabnika na strežnik - preden ga preverijo z razpršenim blokom besedila.

Hašni trki

V teoriji hash funkcij je takšen pojav zagotovljen kot trčenje. Kaj je njeno bistvo? Hašiš trk je situacija, v kateri imata dve različni datoteki isto razpršilno kodo. To je mogoče, če je dolžina ciljnega zaporedja znakov majhna. V tem primeru je verjetnost, da bo tekma razpršena, višja.

Da bi se izognili trčenju, je priporočljivo zlasti uporabljati dvojni algoritem, imenovan "razpršitev hash funkcije". Vključuje oblikovanje odprte in zaprte kode. Mnogi programerji pri reševanju pomembnih problemov priporočajo, da ne uporabljate funkcij razpršitve v primerih, ko ni potrebno in vedno preizkusite ustrezne algoritme za najboljšo združljivost z določenimi ključi.

Zgodovina videza

Ustanovitelji teorije hash funkcij se lahko obravnavajo kot raziskovalci Carter, Wegman, Simonson, Bierbrauer. V prvih različicah so bili uporabljeni ustrezni algoritmi kot orodje za oblikovanje edinstvenih slik zaporedij znakov poljubne dolžine z naknadnim ciljem identifikacije in preverjanja pristnosti. Po drugi strani pa mora imeti razpršitev po določenih merilih dolžino 30-512 bitov. Kot posebno uporabna značilnost ustreznih funkcij je bila upoštevana njegova primernost za uporabo vira kot hitro iskanje datotek ali njihovo razvrščanje.

Priljubljeni Hash standardi

Sedaj upoštevamo priljubljene standarde, v katerih je mogoče predstaviti razpršene funkcije. Med njimi - CRC. Ta algoritem je ciklična koda, imenovana tudi kontrolna vsota. Ta standard se odlikuje po preprostosti in obenem univerzalnosti - preko njega lahko razpršite najširši spekter podatkov. CRC je eden najpogostejših nekriptografskih algoritmov.

Po drugi strani se pri šifriranju pogosto uporabljajo standardi MD4 in MD5. Drug priljubljen kriptografski algoritem je SHA-1. Zlasti je značilna razpršenost 160 bitov, ki je večja od MD5 - ta standard podpira 128 bitov. Obstajajo ruski standardi, ki urejajo uporabo hash funkcij, - GOST R 34.11-94, kot tudi ga nadomestiti z GOST R 34.11-2012. Ugotovimo lahko, da je vrednost razpršitve, ki jo zagotavljajo algoritmi, sprejeti v Ruski federaciji, 256 bitov.

Zadevni standardi se lahko razvrstijo iz različnih razlogov. Na primer, obstajajo tisti, ki uporabljajo blok in specializirane algoritme. Enostavnost izračunov, ki temeljijo na standardih prvega tipa, pogosto spremlja njihova nizka hitrost. Zato lahko kot alternativo blokovnim algoritmom sodelujejo tisti, ki vključujejo manjšo količino računalniških operacij. Običajno je treba standardom visoke hitrosti pripisati zlasti zgoraj omenjeni MD4, MD5 in SHA. Podrobneje obravnavamo posebnosti posebnih algoritmov razprševanja na primeru SHA.

Značilnosti algoritma SHA

Uporaba razpršilnih funkcij, ki temeljijo na standardu SHA, se najpogosteje izvaja na področju razvoja orodij za digitalno podpisovanje dokumentov DSA. Kot smo že omenili, algoritem SHA podpira 160-bitno razpršitev (ki zagotavlja tako imenovano "digest" zaporedja znakov). Prvotno obravnavani standard deli niz podatkov na bloke 512 bitov. Če je potrebno, če dolžina zadnjega bloka ne doseže določene številke, se struktura datoteke dopolni z 1 in s potrebnim številom ničel. Tudi na koncu ustreznega bloka ustreza koda, ki določa dolžino sporočila. Obravnavani algoritem vključuje 80 logičnih funkcij, s katerimi se obdelajo 3 besede, predstavljene v 32 bitih. Tudi pri standardni uporabi SHA so na voljo 4 konstante.

Primerjava algoritmov razpršitve

Poglejmo, kako so lastnosti razpršenih funkcij, ki se nanašajo na različne standarde, primerljive, na primer primerjava značilnosti ruskega standarda GOST R 34.11-94 in ameriškega SHA, ki smo jih obravnavali zgoraj. Najprej je treba opozoriti, da algoritem, razvit v Ruski federaciji, vključuje izvajanje 4 operacij šifriranja na 1 cikel. To ustreza 128 krogom. Po drugi strani pa se za 1 krog pri aktiviranju SHA predpostavlja, da se izračuna približno 20 ukazov, skupno število krogov pa je 80. Tako uporaba SHA omogoča obdelavo 512 bitov izvornih podatkov v enem ciklu. Hkrati je ruski standard sposoben izvajati operacije na cikel 256 bitov podatkov.

Posebnosti najnovejšega ruskega algoritma

Zgoraj smo ugotovili, da je standard GOST R 34.11-94 nadomestil novejši - GOST R 34.11-2012 "Stribog". Podrobneje preučujemo njene posebnosti.

S tem standardom se lahko izvajajo kriptografske razpršitvene funkcije, kot v primeru zgoraj opisanih algoritmov. Ugotovimo lahko, da zadnji ruski standard podpira blok vhodnih podatkov v višini 512 bitov. Glavne prednosti GOST R 34.11-2012:

• visoka stopnja varnosti pred razpokami šifer;
• zanesljivost, podprta z uporabo dokazanih struktur;
• operativni izračun hash funkcije, pomanjkanje transformacij v algoritmu, ki otežujejo konstrukcijo funkcije in upočasnjujejo izračun.

Opažene prednosti novega ruskega standarda kriptografskega šifriranja omogočajo uporabo pri organiziranju toka dokumentov, ki izpolnjuje najstrožja merila, ki so določena v določbah regulativne zakonodaje.

Specifičnost kriptografskih razpršilnih funkcij

Oglejmo si podrobneje, kako se lahko vrste algoritmov, ki jih proučujemo, uporabljajo na področju kriptografije. Ključna zahteva za ustrezne funkcije je odpornost na trke, ki smo jih omenili zgoraj. To pomeni, da podvojene vrednosti hash funkcije ne bi smele biti oblikovane, če so te vrednosti že prisotne v strukturi sosednjega algoritma. Druga zgoraj navedena merila morajo izpolnjevati tudi kriptografske funkcije. Jasno je, da vedno obstaja teoretična možnost obnovitve izvorne datoteke, ki temelji na razpršitvi, še posebej, če je dostopno močno računalniško orodje. Vendar pa naj bi bil ta scenarij po zaslugi robustnih algoritmov šifriranja čim manjši. Zato bo zelo težko izračunati hash funkcijo, če njena računska moč ustreza formuli 2 ^ {n / 2}.

Še en pomemben kriterij kriptografskega algoritma je sprememba razpršitve v primeru popravka prvotnega podatkovnega niza. Zgoraj smo ugotovili, da morajo imeti standardi za šifriranje občutljivost 1 bit. Torej je ta lastnost ključni dejavnik pri zagotavljanju zanesljivega zaščite dostopa do datotek z geslom.

Iterativne sheme

Zdaj preučimo, kako lahko zgradimo algoritme kriptografskega razprševanja. Med najpogostejšimi rešitvami za reševanje tega problema je uporaba iterativnega zaporednega modela. Temelji na uporabi tako imenovane funkcije stiskanja, pri kateri je število vhodnih bitov bistveno večje od števila zapisanih na izhodu.

Seveda mora funkcija stiskanja izpolnjevati potrebna merila za kriptografsko moč. V interaktivni shemi je prva operacija za obdelavo vhodnega podatkovnega toka razdeljena na bloke, katerih velikost se izračuna v bitih. Ustrezni algoritem vključuje tudi časovne spremenljivke danega števila bitov. Prva vrednost uporablja dobro znano številko, poznejše podatkovne bloke pa kombiniramo z vrednostjo zadevne funkcije na izhodu. Vrednost razpršitve postane izhodni bit za zadnjo iteracijo, ki upošteva celoten vhodni tok, vključno s prvo vrednostjo. Zagotavlja se tako imenovani "plazovit učinek" zgoščevanja.

Glavna težava, ki označuje zgoščevanje, ki se izvaja kot iterativna shema, je, da je včasih težko zgraditi hash funkcije, če vhodni tok ni enak velikosti bloka, v katerega je razdeljeno začetno podatkovno polje. Toda v tem primeru je mogoče razčlenjevati algoritme, s katerimi lahko izvorni tok razširimo na tak ali drugačen način.

V nekaterih primerih lahko v obdelavo podatkov v iterativni shemi sodelujejo tako imenovani algoritmi z več prehodi. Predlagajo nastanek še bolj intenzivnega "plazovitega učinka". Tak scenarij predvideva nastanek ponavljajočih se podatkovnih nizov in samo sekundarno je razširitev.

Blok algoritem

Funkcija stiskanja lahko temelji tudi na blokovnem algoritmu, s katerim se izvaja šifriranje. Torej, da bi povečali stopnjo varnosti, lahko uporabite podatkovne bloke, ki jih je treba pri trenutni iteraciji razpršiti, kot ključ in rezultat operacij, pridobljenih med izvajanjem funkcije stiskanja pred tem - kot vhod. Posledično bo zadnja ponovitev zagotovila izhod algoritma. Hash varnost bo korelirala z robustnostjo vključenega algoritma.

Vendar, kot smo že omenili zgoraj, ob upoštevanju različnih vrst razpršilnih funkcij, blokovni algoritmi pogosto spremlja potreba po uporabi velikih računskih moči. Če niso na voljo, hitrost obdelave datotek morda ne bo zadostovala za reševanje praktičnih problemov, povezanih z uporabo hash funkcij. Istočasno je mogoče zahtevano kripto-odpornost uresničiti z majhnim številom operacij z izvornimi podatkovnimi tokovi, predvsem pa so algoritmi, ki smo jih obravnavali, prilagojeni za reševanje teh problemov - MD5, SHA, ruski kriptografski šifrirni standardi.