Domnievam sa, že mnohí vedia, že od roku 2007 americký Národný inštitút pre štandardy a technológie (NIST) organizuje súťaž o vývoj hašovacieho algoritmu, ktorý nahradí SHA-1, a rodinu algoritmov SHA-2. Táto téma je však z nejakého dôvodu na stránke zbavená pozornosti. To je vlastne to, čo ma k vám priviedlo. Dávam do pozornosti sériu článkov o hašovacích algoritmoch. V tomto cykle si spoločne preštudujeme základy hašovacích funkcií, zvážime najznámejšie hašovacie algoritmy, ponoríme sa do atmosféry súťaže SHA-3 a zvážime algoritmy, ktoré tvrdia, že ju vyhrajú, určite ich otestujeme. Ak je to možné, zohľadnia sa aj ruské hašovacie štandardy.

O sebe

Študentka Katedry informačnej bezpečnosti.

O hašovaní

V súčasnosti takmer žiadna kryptografická aplikácia nie je úplná bez použitia hashovania.
Hašovacie funkcie sú funkcie určené na „komprimovanie“ ľubovoľnej správy alebo súboru údajov, zvyčajne zapísaných v binárnej abecede, do nejakej kombinácie bitov s pevnou dĺžkou, ktorá sa nazýva konvolúcia. Hash funkcie majú rôzne aplikácie v štatistických experimentoch, pri testovaní logických zariadení, pri vytváraní algoritmov na rýchle vyhľadávanie a kontrolu integrity záznamov v databázach. Hlavnou požiadavkou na hašovacie funkcie je jednotnosť rozloženia ich hodnôt s náhodným výberom hodnôt argumentov.
Kryptografická hašovacia funkcia je akákoľvek hašovacia funkcia, ktorá je kryptograficky bezpečná, to znamená, že spĺňa množstvo požiadaviek špecifických pre kryptografické aplikácie. V kryptografii sa hašovacie funkcie používajú na riešenie nasledujúcich problémov:
- budovanie systémov kontroly integrity údajov počas ich prenosu alebo uchovávania,
- autentifikácia zdroja údajov.

Hašovacia funkcia je akákoľvek funkcia h:X -> Y, ľahko vypočítateľný a taký, že pre akúkoľvek správu M význam h(M) = H (konvolúcia) má pevnú dĺžku bitu. X- súbor všetkých správ, Y- súbor binárnych vektorov pevnej dĺžky.

Hašovacie funkcie sú spravidla postavené na základe takzvaných jednokrokových kontrakčných funkcií y \u003d f (x 1, x 2) dve premenné, kde x 1, x2 a r- binárne dĺžkové vektory m, n a n respektíve, a n je dĺžka konvolúcie a m- dĺžka bloku správ.
Ak chcete získať hodnotu h(M) správa je najprv rozdelená na bloky dĺžky m(zároveň, ak dĺžka správy nie je násobkom m potom sa posledný blok nejakým špeciálnym spôsobom doplní k úplnému bloku) a potom k prijatým blokom M1, M2,.., M N na výpočet konvolúcie použite nasledujúci postupný postup:

H o \u003d v,
Hi = f(Mi,Hi-1), i = 1,.., N,
h(M) = HN

Tu v- nejaká konštanta, často sa nazýva inicializačný vektor. Ona sa dostane von
z rôznych dôvodov a môže to byť tajná konštanta alebo súbor náhodných údajov (napríklad výber dátumu a času).
Pri tomto prístupe sú vlastnosti hašovacej funkcie úplne určené vlastnosťami funkcie jednokrokovej kontrakcie.

Existujú dva dôležité typy kryptografických hašovacích funkcií – kľúčové a bezkľúčové. Kľúčové hašovacie funkcie sa nazývajú overovacie kódy správ. Umožňujú bez dodatočných prostriedkov zaručiť správnosť zdroja údajov a integritu údajov v systémoch so vzájomne dôveryhodnými používateľmi.
Bezkľúčové hašovacie funkcie sa nazývajú kódy detekcie chýb. Umožňujú pomocou dodatočných prostriedkov (napríklad šifrovanie) zaručiť integritu údajov. Tieto hašovacie funkcie možno použiť v systémoch s dôveryhodnými aj nedôverčivými používateľmi.

O štatistických vlastnostiach a požiadavkách

Ako som povedal, hlavnou požiadavkou na hašovacie funkcie je rovnomerné rozloženie ich hodnôt s náhodným výberom hodnôt argumentov. Pre kryptografické hašovacie funkcie je tiež dôležité, že pri najmenšej zmene argumentu sa hodnota funkcie výrazne zmení. Toto sa nazýva lavínový efekt.

Komu kľúčové funkcie hashovanie má nasledujúce požiadavky:
- nemožnosť výroby,
- nemožnosť úpravy.

Prvá požiadavka znamená, že je veľmi ťažké priradiť správu so správnou hodnotou zloženia. Druhým je vysoká zložitosť porovnávania pre danú správu so známou hodnotou zloženia inej správy so správnou hodnotou zloženia.

Požiadavky na bezkľúčové funkcie sú:
- jednosmerný,
- odolnosť voči nárazom,
- odolnosť voči nájdeniu druhého prototypu.

Jednosmernosť sa chápe ako vysoká zložitosť nájdenia správy podľa danej konvolučnej hodnoty. Treba poznamenať, že na tento moment nepoužívajú sa žiadne hašovacie funkcie s osvedčeným jednosmerným prístupom.
Odolnosť voči kolízii sa chápe ako obtiažnosť nájsť pár správ s rovnakými násobnými hodnotami. Zvyčajne je to práve nájdenie spôsobu, ako zostrojiť zrážky kryptoanalytikmi, čo slúži ako prvý signál zastaranosti algoritmu a potreby jeho rýchlej výmeny.
Odolnosť voči nájdeniu druhého predobrazu sa chápe ako obtiažnosť nájsť druhú správu s rovnakou násobnou hodnotou pre danú správu so známou násobnou hodnotou.

Toto bola teoretická časť, ktorá sa nám bude hodiť v budúcnosti...

O populárnych hašovacích algoritmoch

Algoritmy CRC16/32- kontrolný súčet (nie kryptografická konverzia).

Algoritmy MD2/4/5/6. Sú výtvorom Rona Rivesta, jedného z autorov algoritmu RSA.
Algoritmus MD5 bol kedysi veľmi populárny, ale prvé predpoklady pre hackovanie sa objavili koncom deväťdesiatych rokov a teraz jeho popularita rýchlo klesá.
Algoritmus MD6 je z konštruktívneho hľadiska veľmi zaujímavý algoritmus. Bol nominovaný do súťaže SHA-3, ale autorom sa ho, žiaľ, nepodarilo uviesť do štandardu a tento algoritmus nie je v zozname kandidátov, ktorí postúpili do druhého kola.

Algoritmy pravítka SHA Algoritmy, ktoré sú dnes široko používané. Existuje aktívny prechod zo štandardov verzie SHA-1 na SHA-2. SHA-2 je súhrnný názov pre algoritmy SHA224, SHA256, SHA384 a SHA512. SHA224 a SHA384 sú v podstate analógy SHA256 a SHA512, až po vypočítaní konvolúcie sú niektoré informácie v nej vyradené. Mali by sa používať iba na zabezpečenie kompatibility so staršími modelmi zariadení.

ruský štandard - GOST 34.11-94.

V ďalšom článku

Prehľad MD algoritmov (MD4, MD5, MD6).

Literatúra

A. P. Alferov, Základy kryptografie.

Bruce Schneier, Aplikovaná kryptografia.

Hašovanie je špeciálna metóda adresovania údajov (nejaký druh rozstupového algoritmu) pomocou ich jedinečných kľúčov ( kľúč ) aby ste rýchlo našli informácie, ktoré potrebujete.

Základné pojmy

Tabuľka hash

Hašovacia tabuľka je pravidelné pole so špeciálnou adresou danou nejakou funkciou (Hash funkcia).

hašovacia funkcia

Funkcia, ktorá konvertuje kľúč údajovej položky na nejaký index v tabuľke ( hash tabuľka), sa nazýva hašovacia funkcia alebo hašovacia funkcia :

i = h (kľúč );

kde kľúč- konvertibilný kľúč, i- výsledný tabuľkový index, t.j. kľúč sa zobrazuje v množine napríklad celých čísel ( hash adresy ), ktoré sa neskôr použijú na prístup k údajom.

Hašovanie týmto spôsobom je technika, ktorá zahŕňa použitie hodnoty kľúča na určenie jeho pozície v špeciálnej tabuľke.

Funkcia spread však môže niekoľko jedinečné hodnoty kľúča dávajú rovnakú hodnotu pozície i v hašovacej tabuľke. Zavolá sa situácia, v ktorej dva alebo viac kľúčov dostane rovnaký index (hash adresu). Zrážka (kolízia) v hašovaní. Preto musí hašovacia schéma zahŕňať Algoritmus riešenia konfliktov , definujúce poradie úkonov, ak je pozícia i=h(kľúč) je už obsadený záznamom s iným kľúčom.

Existuje mnoho hašovacích schém, ktoré sa líšia v použitej hašovacej funkcii. h(kľúč) a algoritmy riešenia konfliktov.

Najbežnejšia metóda na určenie hašovacej funkcie je: metóda delenia.

Počiatočné údaje sú: - nejaký celočíselný kľúč kľúč a veľkosť stola m. Výsledkom tejto funkcie je zvyšok vydelenia tohto kľúča veľkosťou tabuľky. Všeobecná forma takejto funkcie v programovacom jazyku C/C++:

int h (int kľúč , int m ) {

Pre m= 10 hašovacia funkcia vráti najmenej významnú číslicu kľúča.

Pre m=100 vráti hašovacia funkcia dve najmenej významné číslice kľúča.

V uvažovaných príkladoch hašovacia funkcia i=h(kľúč) definuje iba pozíciu, z ktorej sa má hľadať (alebo na začiatku umiestniť do tabuľky) záznam s kľúčom kľúč. Ďalej musíte použiť nejaký typ hašovacej schémy (algoritmus).

Hašovacie schémy

Vo väčšine problémov sú dva alebo viac kľúčov hashované rovnakým spôsobom, ale nemôžu zaberať rovnakú bunku v tabuľke hash. Existujú dva možné možnosti: buď nájdite inú pozíciu pre nový kľúč, alebo vytvorte samostatný zoznam pre každý index hašovacej tabuľky, v ktorom sú umiestnené všetky kľúče namapované na tento index.

Tieto varianty sú dve klasické hašovacie schémy:

hašovanie otvoreným adresovaním s lineárnym snímaním - lineárne sonda OTVORENÉ adresovanie.

reťazové hašovanie (so zoznamami), alebo takzvané viacrozmerné hašovanie - reťazenie s oddelené zoznamy;

Otvorená metóda adresovania s lineárnym snímaním . Na začiatku sú všetky bunky hašovacej tabuľky, čo je normálne jednorozmerné pole, označené ako neobsadené. Pri pridávaní nového kľúča sa teda kontroluje, či je daná bunka obsadená. Ak je bunka obsadená, algoritmus hľadá v kruhu, kým nezostane prázdne miesto („otvorená adresa“).

Tie. prvky s homogénnymi kľúčmi sú umiestnené blízko výsledného indexu.

V budúcnosti pri vyhľadávaní najskôr nájdite pozíciu pomocou kľúča i v tabuľke a ak sa kľúč nezhoduje, následné vyhľadávanie sa vykoná v súlade s algoritmom riešenia konfliktov, počnúc od pozície i. .

Reťazová metóda je dominantná stratégia . V tomto prípade i získané z vybranej hašovacej funkcie h(kľúč)=i, sa zaobchádza ako s indexom do hašovacej tabuľky zoznamov, t.j. najprv kľúč kľúčďalší záznam je namapovaný na pozíciu i = h(kľúč) tabuľky. Ak je pozícia voľná, potom je do nej umiestnený prvok s kľúčom. kľúč, ak je zaneprázdnený, potom sa vypracuje algoritmus riešenia konfliktov, v dôsledku čoho sa takéto kľúče umiestnia do zoznamu začínajúceho na i- tá bunka hašovacej tabuľky. Napríklad

Výsledkom je tabuľka radu prepojených zoznamov alebo stromov.

Proces vypĺňania (čítania) hašovacej tabuľky je jednoduchý, ale prístup k prvkom vyžaduje nasledujúce operácie:

Výpočet indexu i;

Vyhľadajte v príslušnom reťazci.

Na zlepšenie vyhľadávania pri pridávaní nového prvku môžete použiť algoritmus vkladania nie na koniec zoznamu, ale s usporiadaním, t.j. pridať prvok do Správne miesto.

Príklad implementácie metódy priameho adresovania s lineárnym sondovaním . Počiatočnými údajmi je 7 záznamov (pre zjednodušenie informačná časť pozostáva len z celočíselných údajov), deklarovaného štrukturálneho typu:

intkey; // Kľúč

intinfo; // Informácie

(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9); veľkosť hash tabuľky m=10.

hašovacia funkcia i=h(údajov) =údajov.kľúč% desať; tie. zvyšok po vydelení 10 - i.

Na základe počiatočných údajov postupne vyplníme hašovaciu tabuľku.

Hašovanie prvých piatich kľúčov poskytuje rôzne indexy (hash adresy):

K prvej kolízii dochádza medzi kľúčmi 81 a 41 - miesto s indexom 1 je obsadené. Preto sa pozrieme cez hašovaciu tabuľku, aby sme našli najbližšie voľné miesto, v tomto prípade to tak je i = 2.

Ďalší kľúč 79 tiež generuje kolíziu: pozícia 9 je už obsadená. Účinnosť algoritmu prudko klesá, pretože na nájdenie voľného miesta bolo potrebných 6 pokusov (porovnaní), index sa ukázal ako voľný i= 4.

Celkový počet vzoriek tejto metódy je od 1 do n-1 vzoriek na prvok, kde n je veľkosť hašovacej tabuľky.

Implementácia metódy reťazenia pre predchádzajúci príklad. Deklarujeme štrukturálny typ pre prvok zoznamu (jednosmerný):

intkey; // Kľúč

intinfo; // Informácie

zap*Ďalej; // Ukazovateľ na ďalší prvok na zozname

Na základe počiatočných údajov sekvenčne vypĺňame hašovaciu tabuľku pridávaním nový prvok na koniec zoznamu, ak je miesto už obsadené.

Hašovanie prvých piatich kľúčov, ako v predchádzajúcom prípade, poskytuje rôzne indexy (hash adresy): 9, 0, 6, 1 a 3.

Keď dôjde ku kolízii, nový prvok sa pridá na koniec zoznamu. Preto je prvok s kľúčom 41 umiestnený za prvkom s kľúčom 81 a prvok s kľúčom 79 je umiestnený za prvkom s kľúčom 59.

Jednotlivé úlohy

1. Binárne stromy. Pomocou programu generátora náhodných čísel získajte 10 hodnôt od 1 do 99 a vytvorte binárny strom.

Urobte si obchádzku:

1.a Prechod zľava doprava: Ľavý-koreň-vpravo: najprv navštívte ľavý podstrom, potom koreň a nakoniec pravý podstrom.

(Alebo naopak, sprava doľava: pravá-koreň-ľavá)

1.b Prechod zhora nadol: Root-Left-Right: navštívte koreň k podstromom.

1. V prechode zdola nahor: Ľavý-Vpravo-Koeň: prejdite na koreň po podstromoch

V širokej škále priemyselných odvetví informačných technológií nájsť ich využitie hašovacích funkcií. Sú navrhnuté tak, aby na jednej strane výrazne zjednodušili výmenu údajov medzi používateľmi a spracovanie súborov používaných na určité účely, na druhej strane aby optimalizovali algoritmy na zabezpečenie kontroly prístupu k príslušným zdrojom. Hašovacia funkcia je jednou z kľúčové nástroje zabezpečenie ochrany údajov heslom, ako aj organizovanie výmeny dokumentov podpísaných pomocou EDS. Existuje veľké množstvo štandardov, podľa ktorých je možné ukladať súbory do vyrovnávacej pamäte. Mnohé z nich sú vyvinuté ruskými špecialistami. Aké sú typy hašovacích funkcií? Aké sú hlavné mechanizmy ich praktického uplatnenia?

Čo to je?

Najprv preskúmame koncept hašovacej funkcie. Tento termín sa bežne chápe ako algoritmus na konverziu určitého množstva informácií na kratší sled znakov pomocou matematických metód. Praktický význam hašovacej funkcie možno vysledovať v rôznych oblastiach. Môžu sa teda použiť pri kontrole integrity súborov a programov. V šifrovacích algoritmoch sa používajú aj kryptografické hašovacie funkcie.

Charakteristika

Pozrime sa na kľúčové charakteristiky skúmaných algoritmov. Medzi týmito:

• prítomnosť interných algoritmov na konverziu údajov pôvodnej dĺžky na kratšiu sekvenciu znakov;
• otvorenosť pre kryptografické overenie;
• prítomnosť algoritmov, ktoré vám umožňujú bezpečne šifrovať pôvodné údaje;
• prispôsobivosť na dešifrovanie pomocou malých výpočtový výkon.

Medzi ďalšie dôležité vlastnosti hašovacej funkcie patria:

• schopnosť spracovať počiatočné dátové polia ľubovoľnej dĺžky;
• generovať hashované bloky pevnej dĺžky;
• rovnomerne distribuovať funkčné hodnoty na výstupe.

Uvažované algoritmy tiež predpokladajú citlivosť na vstupné dáta na 1-bitovej úrovni. To znamená, že aj keď sa relatívne vzaté zmení aspoň 1 písmeno v zdrojovom dokumente, hašovacia funkcia bude vyzerať inak.

Požiadavky na hašovacie funkcie

Existuje množstvo požiadaviek na hašovacie funkcie určené na praktické využitie v určitej oblasti. Po prvé, zodpovedajúci algoritmus musí byť citlivý na zmeny vo vnútornej štruktúre hašovaných dokumentov. To znamená, že hašovacia funkcia by mala byť rozpoznaná textový súbor, permutácia odsekov, delenie slov. Na jednej strane sa obsah dokumentu nemení, na druhej strane je opravená jeho štruktúra a tento proces je potrebné rozpoznať pri hashovaní. Po druhé, uvažovaný algoritmus musí transformovať údaje takým spôsobom, aby spätná operácia (premena hashu na pôvodný dokument) bola v praxi nemožná. Po tretie, hashovacia funkcia by mala zahŕňať použitie takých algoritmov, ktoré prakticky vylučujú možnosť vytvorenia rovnakej postupnosti znakov vo forme hashu, inými slovami, výskyt takzvaných kolízií. Ich podstatu zvážime o niečo neskôr.

Uvedené požiadavky, ktoré musí spĺňať algoritmus hašovacej funkcie, je možné dosiahnuť najmä použitím komplexných matematických prístupov.

Štruktúra

Pozrime sa, aká môže byť štruktúra uvažovaných funkcií. Ako sme uviedli vyššie, medzi hlavné požiadavky na uvažované algoritmy patrí zabezpečenie jednosmerného šifrovania. Človek, ktorý má k dispozícii len hash, by sa na základe neho k pôvodnému dokumentu prakticky nemal dostať.

V akej štruktúre môže byť zastúpená hašovacia funkcia používaná na takéto účely? Príklad jeho zostavenia môže byť nasledovný: H (hash, teda hash) = f (T (text), H1), kde H1 je algoritmus spracovania textu T. Táto funkcia hashuje T tak, že bez znalosti H1 bude prakticky nemožné ho otvoriť ako plnohodnotný súbor.

Používanie hashovacích funkcií v praxi: Sťahovanie súborov

Poďme si teraz podrobnejšie preštudovať možnosti využitia hašovacích funkcií v praxi. Pri písaní skriptov na sťahovanie súborov z internetových serverov je možné použiť vhodné algoritmy.

Vo väčšine prípadov je pre každý súbor určený určitý kontrolný súčet - to je hash. Musí byť rovnaký pre objekt umiestnený na serveri a stiahnutý do počítača používateľa. Ak tomu tak nie je, súbor sa nemusí otvoriť alebo spustiť nesprávne.

Hash funkcia a digitálny podpis

Používanie hašovacích funkcií je bežné pri organizovaní výmeny dokumentov obsahujúcich digitálny podpis. V tomto prípade je podpísaný súbor hašovaný, aby si jeho príjemca mohol overiť, že je pravý. Hoci hašovacia funkcia nie je formálne zahrnutá v štruktúre elektronický kľúč, dá sa opraviť vo flash pamäti hardvéru, ktorým sa podpisujú dokumenty, ako je napríklad eToken.

Elektronický podpis je šifrovanie súboru pomocou verejných a súkromných kľúčov. To znamená, že k zdrojovému súboru sa pripojí správa zašifrovaná súkromným kľúčom a digitálny podpis sa overí pomocou verejný kľúč. Ak sa hašovacia funkcia oboch dokumentov zhoduje, súbor príjemcu sa rozpozná ako autentický a podpis odosielateľa sa rozpozná ako správny.

Hašovanie, ako sme uviedli vyššie, nie je priamo súčasťou EDS, umožňuje vám však veľmi efektívne optimalizovať algoritmy na používanie elektronický podpis. Šifrovať je teda možné iba hash, nie samotný dokument. V dôsledku toho sa výrazne zvyšuje rýchlosť spracovania súborov a zároveň je možné poskytnúť efektívnejšie mechanizmy ochrany EDS, pretože dôraz vo výpočtových operáciách v tomto prípade nebude kladený na spracovanie počiatočných údajov, ale na zabezpečenie kryptografická sila podpisu. Hašovacia funkcia tiež umožňuje podpisovať rôzne typy údajov, nielen text.

Kontrola hesiel

Ďalšou možnou oblasťou použitia pre hashovanie je organizácia algoritmov overovania hesla vytvorených na rozlíšenie prístupu k určitým zdrojom súborov. Ako môžu byť určité typy hašovacích funkcií zapojené do riešenia takýchto problémov? Veľmi jednoduché.

Faktom je, že na väčšine serverov, ku ktorým sa rozlišuje prístup, sú heslá uložené vo forme hashovaných hodnôt. Je to celkom logické – ak by boli heslá prezentované v pôvodnej textovej podobe, hackeri, ktorí k nim získali prístup, by mohli tajné údaje ľahko prečítať. Na druhej strane, na základe hashu nie je ľahké vypočítať heslo.

Ako sa kontroluje prístup používateľa pri použití uvažovaných algoritmov? Heslo zadané používateľom sa porovná s tým, čo je pevne stanovené v hašovacej funkcii, ktorá je uložená na serveri. Ak sa hodnoty textových blokov zhodujú, používateľ získa potrebný prístup k zdrojom.

Najjednoduchšiu hashovaciu funkciu možno použiť ako nástroj na kontrolu hesla. V praxi však IT odborníci najčastejšie používajú zložité viacstupňové kryptografické algoritmy. Typicky sú doplnené o používanie štandardov prenosu dát cez bezpečný kanál, takže hackeri nemôžu zistiť alebo zistiť heslo prenášané z počítača používateľa na servery skôr, ako sa overí pomocou blokov hashovaného textu.

Kolízie hašovacích funkcií

V teórii hašovacích funkcií existuje taký jav, ako je kolízia. Čo je jej podstatou? Hašovacia kolízia je situácia, v ktorej dva rôzne súbory majú rovnaký hašovací kód. Je to možné, ak je dĺžka cieľovej sekvencie znakov malá. V tomto prípade bude pravdepodobnosť zhody hash vyššia.

Aby sa predišlo kolízii, odporúča sa najmä použiť dvojitý algoritmus nazývaný „hašovanie hašovacej funkcie“. Zahŕňa vytvorenie otvoreného a uzavretého kódu. Mnoho programátorov pri riešení kritických problémov odporúča nepoužívať hašovacie funkcie v prípadoch, keď to nie je potrebné a vždy otestovať zodpovedajúce algoritmy na najlepšiu kompatibilitu s určitými kľúčmi.

História vzhľadu

Za zakladateľov teórie hašovacích funkcií možno považovať výskumníkov Cartera, Wegmana, Simonsona, Bierbrouera. V prvých verziách boli príslušné algoritmy použité ako nástroje na generovanie jedinečných obrazov sekvencií znakov ľubovoľnej dĺžky s následným účelom ich identifikácie a overenia pravosti. Na druhej strane, hash by mal mať v súlade so špecifikovanými kritériami dĺžku 30-512 bitov. Ako špeciál užitočný majetok vhodné funkcie, zvažovala sa jeho vhodnosť použitia ako zdroja na rýchle vyhľadávanie súborov alebo ich triedenie.

Populárne hašovacie štandardy

Uvažujme teraz, v akých populárnych štandardoch môžu byť zastúpené hašovacie funkcie. Jedným z nich je CRC. Tento algoritmus je cyklický kód, nazývaný aj kontrolný súčet. Tento štandard sa vyznačuje jednoduchosťou a zároveň všestrannosťou – prostredníctvom neho môžete hashovať najširšie spektrum dát. CRC je jedným z najbežnejších nekryptografických algoritmov.

Na druhej strane, štandardy MD4 a MD5 sú široko používané v šifrovaní. Ďalším populárnym kryptografickým algoritmom je SHA-1. Vyznačuje sa najmä veľkosťou hashu 160 bitov, ktorá je väčšia ako u MD5 – tento štandard podporuje 128 bitov. Existujú ruské normy, ktoré upravujú používanie hašovacích funkcií - GOST R 34.11-94, ako aj GOST R 34.11-2012, ktoré ho nahradili. Je možné poznamenať, že hodnota hash, ktorú poskytujú algoritmy prijaté v Ruskej federácii, je 256 bitov.

Príslušné normy možno klasifikovať rôznymi spôsobmi. Napríklad existujú tie, ktoré používajú blokové a špecializované algoritmy. Jednoduchosť výpočtov na základe noriem prvého typu je často sprevádzaná ich nízkou rýchlosťou. Preto sa ako alternatíva k blokovým algoritmom môžu použiť tie, ktoré zahŕňajú menšie množstvo potrebných výpočtových operácií. Je obvyklé odvolávať sa na vysokorýchlostné štandardy, najmä na vyššie uvedené MD4, MD5 a SHA. Pozrime sa podrobnejšie na špecifiká špeciálnych hashovacích algoritmov na príklade SHA.

Vlastnosti algoritmu SHA

Používanie hašovacích funkcií založených na štandarde SHA sa najčastejšie realizuje v oblasti vývoja nástrojov digitálny podpis dokumenty DSA. Ako sme uviedli vyššie, Algoritmus SHA podporuje hash 160 bitov (poskytuje tzv. "výber" sekvencie znakov). Uvažovaný štandard na začiatku rozdeľuje dátové pole na bloky po 512 bitoch. Ak je to potrebné, ak dĺžka posledného bloku nedosiahne špecifikovanú hodnotu, štruktúra súboru sa doplní 1 a požadovaným počtom núl. Na konci príslušného bloku je tiež zadaný kód, ktorý určuje dĺžku správy. Uvažovaný algoritmus zahŕňa 80 logických funkcií, prostredníctvom ktorých sa spracúvajú 3 slová reprezentované 32 bitmi. Štandard SHA tiež umožňuje použitie 4 konštánt.

Porovnanie hashovacích algoritmov

Pozrime sa, ako korelujú vlastnosti hašovacích funkcií súvisiacich s rôznymi štandardmi, na príklade porovnania charakteristík ruskej normy GOST R 34.11-94 a americkej SHA, o ktorej sme hovorili vyššie. V prvom rade treba poznamenať, že algoritmus vyvinutý v Ruskej federácii zahŕňa implementáciu 4 šifrovacích operácií na 1 cyklus. To zodpovedá 128 nábojom. Na druhej strane, počas 1 kola sa pri použití SHA očakáva výpočet asi 20 príkazov, pričom kôl je celkovo 80. Použitie SHA teda umožňuje spracovať 512 bitov počiatočných dát v rámci 1 cyklu. Zatiaľ čo ruský štandard je schopný vykonávať operácie v cykle 256 bitov dát.

Špecifiká najnovšieho ruského algoritmu

Vyššie sme poznamenali, že norma GOST R 34.11-94 bola nahradená novšou normou - GOST R 34.11-2012 Stribog. Pozrime sa na jeho špecifiká podrobnejšie.

Cez tento štandard môžu byť implementované, ako v prípade vyššie diskutovaných algoritmov, kryptografické hašovacie funkcie. Možno poznamenať, že najnovší ruský štandard podporuje blok vstupných údajov vo výške 512 bitov. Hlavné výhody GOST R 34.11-2012:

• vysoká úroveň ochrany proti prelomeniu šifier;
• spoľahlivosť, podporená použitím osvedčených dizajnov;
• rýchly výpočet hašovacej funkcie, absencia transformácií v algoritme, ktoré komplikujú konštrukciu funkcie a spomaľujú výpočet.

Zaznamenané výhody nového ruského štandardu kryptografické šifrovanie vám umožní používať ho pri organizácii pracovného toku, ktorý spĺňa najprísnejšie kritériá, ktoré sú predpísané v ustanoveniach regulačnej legislatívy.

Špecifickosť kryptografických hašovacích funkcií

Pozrime sa podrobnejšie na to, ako sa dajú typy algoritmov, ktoré študujeme, použiť v oblasti kryptografie. Kľúčovou požiadavkou na zodpovedajúce funkcie je odolnosť voči kolíziám, o ktorej sme sa zmienili vyššie. To znamená, že duplicitné hodnoty hash by sa nemali generovať, ak sú tieto hodnoty už prítomné v štruktúre susedného algoritmu. Kryptografické funkcie musia spĺňať aj ostatné kritériá uvedené vyššie. Je jasné, že vždy existuje nejaká teoretická možnosť zotavenia zdrojový súbor na základe hashu, najmä ak je k dispozícii výkonný výpočtový nástroj. Predpokladá sa však, že tento scenár bude minimalizovaný vďaka silným šifrovacím algoritmom. Preto bude veľmi ťažké vypočítať hašovaciu funkciu, ak jej výpočtová sila zodpovedá vzorcu 2^(n/2).

Ďalším dôležitým kritériom pre kryptografický algoritmus je zmena hashu v prípade, že je pôvodné dátové pole opravené. Vyššie sme si všimli, že šifrovacie štandardy by mali mať citlivosť na úrovni 1 bit. Táto vlastnosť je teda kľúčovým faktorom pri zabezpečení spoľahlivej ochrany prístupu k súborom heslom.

Iteračné schémy

Pozrime sa teraz na to, ako možno vytvoriť kryptografické hašovacie algoritmy. Medzi najbežnejšie schémy riešenia tohto problému patrí použitie iteračného sekvenčného modelu. Je založená na použití takzvanej kontrakčnej funkcie, pri ktorej je počet vstupných bitov podstatne väčší ako tie, ktoré sú pevne dané na výstupe.

Samozrejme, kompresná funkcia musí spĺňať potrebné kritériá kryptografickej pevnosti. V interaktívnej schéme je prvá operácia spracovania vstupného dátového toku rozdelená do blokov, ktorých veľkosť je vypočítaná v bitoch. Zodpovedajúci algoritmus tiež používa dočasné premenné daného počtu bitov. Ako prvá hodnota sa používa dobre známe číslo, zatiaľ čo nasledujúce bloky údajov sa kombinujú s hodnotou príslušnej funkcie na výstupe. Hodnota hash sa stane bitovým výstupom pre poslednú iteráciu, ktorá berie do úvahy celý vstupný tok vrátane prvej hodnoty. Poskytuje sa takzvaný „lavínový efekt“ hashovania.

Hlavným problémom, ktorý charakterizuje hašovanie implementované ako iteratívna schéma, je to, že hašovacie funkcie sa niekedy ťažko zostavujú, ak vstupný tok nie je identický s veľkosťou bloku, na ktorý je rozdelené počiatočné dátové pole. Ale v tomto prípade môžu byť algoritmy napísané v hašovacom štandarde, pomocou ktorého môže byť pôvodný tok tak či onak rozšírený.

V niektorých prípadoch môžu byť do procesu spracovania údajov v rámci iteratívnej schémy zahrnuté takzvané viacpriechodové algoritmy. Naznačujú vznik ešte intenzívnejšieho „lavínového efektu“. Takýto scenár zahŕňa vytváranie opakovaných dátových polí a až na druhom mieste je rozširovanie.

Blokový algoritmus

Kompresná funkcia môže byť tiež založená na blokovom algoritme, pomocou ktorého sa vykonáva šifrovanie. Aby ste zvýšili úroveň bezpečnosti, môžete použiť bloky údajov, ktoré sú predmetom hashovania v aktuálnej iterácii, ako kľúč a výsledok operácií získaných počas vykonávania funkcie kompresie pred tým ako vstup . Výsledkom je, že posledná iterácia poskytne výstup algoritmu. Bezpečnosť hashu bude korelovať s robustnosťou použitého algoritmu.

Ako sme však uviedli vyššie, vzhľadom na rôzne druhy hašovacie funkcie, sú blokové algoritmy často sprevádzané potrebou využívať veľký výpočtový výkon. Ak nie sú k dispozícii, rýchlosť spracovania súborov nemusí byť dostatočná na vyriešenie praktických problémov súvisiacich s používaním hašovacích funkcií. Požadovanú kryptografickú silu možno zároveň realizovať aj s malým počtom operácií so zdrojovými dátovými tokmi, najmä algoritmy, ktoré sme uvažovali - MD5, SHA a ruské kryptografické šifrovacie štandardy - sú prispôsobené na riešenie takýchto problémov.

čo je hash? Hašovacia funkcia je matematická transformácia informácií na krátky reťazec určitej dĺžky.

Prečo je to potrebné? Analýza hašovacej funkcie sa často používa na kontrolu integrity dôležitých súborov operačný systém, dôležité programy, dôležité údaje. Monitorovanie sa môže vykonávať podľa potreby aj pravidelne.

Ako sa to robí? Najprv určite integritu súborov, ktoré je potrebné monitorovať. Pre každý súbor sa podľa špeciálneho algoritmu vypočíta hodnota jeho hashu a výsledok sa uloží. Po potrebnom čase sa vykoná podobný výpočet a výsledky sa porovnajú. Ak sú hodnoty odlišné, informácie obsiahnuté v súbore boli zmenené.

Aké vlastnosti by mala mať hašovacia funkcia?

• musí byť schopný vykonávať transformácie údajov ľubovoľnej dĺžky na pevnú;
• musí mať otvorený algoritmus, aby bolo možné preskúmať jeho kryptografickú silu;
• mala by byť jednostranná, to znamená, že by nemala existovať matematická možnosť určiť počiatočné údaje z výsledku;
• mali by „odolať“ kolíziám, to znamená, že by nemali produkovať rovnaké hodnoty pre rôzne vstupné údaje;
• nemal by vyžadovať veľké výpočtové zdroje;
• pri najmenšej zmene vstupných údajov by sa mal výsledok výrazne zmeniť.

Aké sú populárne hašovacie algoritmy? V súčasnosti sa používajú nasledujúce hašovacie funkcie:

• CRC znamená kód cyklickej redundancie alebo kontrolný súčet. Algoritmus je veľmi jednoduchý, má veľké množstvo variácií v závislosti od požadovanej dĺžky výstupu. Nie je kryptografický!
• MD 5 je veľmi populárny algoritmus. Mať ho rád predošlá verzia MD 4 je kryptografická funkcia. Veľkosť hash je 128 bitov.
• SHA -1 je tiež veľmi populárna kryptografická funkcia. Veľkosť hashu je 160 bitov.
• GOST R 34.11-94 je ruský kryptografický štandard pre výpočet hašovacej funkcie. Veľkosť hashu je 256 bitov.

Kedy môže správca systému použiť tieto algoritmy?Často pri sťahovaní akéhokoľvek obsahu, ako sú programy z webovej stránky výrobcu, hudba, filmy alebo iné informácie, existuje hodnota kontrolného súčtu vypočítaná pomocou určitého algoritmu. Z bezpečnostných dôvodov musíte po stiahnutí nezávisle vypočítať hašovaciu funkciu a porovnať hodnotu s tým, čo je uvedené na stránke alebo v prílohe k súboru. Robili ste to niekedy?

Čo je pohodlnejšie na výpočet hash? Teraz existuje veľké množstvo takýchto nástrojov, platených aj bezplatných. Osobne sa mi páčil HashTab. Po prvé, počas inštalácie je pomôcka vložená ako karta vo vlastnostiach súboru, po druhé, umožňuje vám vybrať veľké množstvo hashovacích algoritmov a po tretie je zadarmo na súkromné ​​nekomerčné použitie.

čo je ruština? Ako už bolo spomenuté vyššie, v Rusku existuje hašovací štandard GOST R 34.11-94, ktorý je široko používaný mnohými výrobcami nástrojov informačnej bezpečnosti. Jedným z týchto nástrojov je fixačný a kontrolný program. počiatočný stav softvérový balík"OPRAVIŤ". Tento program je prostriedkom na monitorovanie efektívnosti využívania zariadení informačnej bezpečnosti.

OPRAVA (verzia 2.0.1) pre Windows 9x/NT/2000/XP

• Výpočet kontrolných súčtov daných súborov pomocou jedného z 5 implementovaných algoritmov.
• Fixácia a následná kontrola počiatočného stavu softvérového balíka.
• Porovnanie verzií softvérových balíkov.
• Oprava a kontrola adresárov.
• Kontrola zmien v zadaných súboroch (adresároch).
• Generovanie reportov vo formátoch TXT, HTML, SV.
• Výrobok má do 01.06.2013 certifikát FSTEC podľa NDV 3 č.913.

A čo ECP? Výsledok výpočtu hašovacej funkcie spolu s tajným kľúčom používateľa vstupuje na vstup kryptografického algoritmu, kde sa vypočítava digitálny podpis. Presne povedané, hašovacia funkcia nie je súčasťou algoritmu EDS, ale často sa to robí zámerne, aby sa vylúčil útok na verejný kľúč.

V súčasnosti vám veľa aplikácií elektronického obchodu umožňuje ukladať Tajný kľúč používateľ v súkromnej oblasti tokenu (ruToken, eToken) bez technická realizovateľnosť extrahovať to odtiaľ. Samotný token má veľmi obmedzenú pamäťovú oblasť, meranú v kilobajtoch. Na podpísanie dokumentu neexistuje spôsob, ako preniesť dokument do samotného tokenu, ale je veľmi jednoduché preniesť hash dokumentu do tokenu a získať EDS na výstupe.

Hash tabuľky

Tabuľka hash(zamiešaná tabuľka, tabuľka s vypočítanými adresami) je dynamické množiny podporujúce operácie pridávanie, vyhľadávanie a mazanie prvku a pomocou špeciálnych metód adresovanie.

Hlavný rozdiel medzi tabuľkami a inými dynamickými sadami je výpočet adresy prvku podľa hodnoty kľúča.

Myšlienka implementácie hash je taká, že práca s jedným veľkým poľom sa redukuje na prácu s množstvom malých sád.

Napríklad zápisník. Strany knihy sú označené písmenami. Strana označená písmenom obsahuje priezviská začínajúce týmto písmenom. Veľká množina priezvisk je rozdelená do 28 podmnožín. Pri hľadaní sa kniha okamžite otvorí na požadovanom písmene a vyhľadávanie sa urýchli.

V programovacej hašovacej tabuľke- toto je štruktúru dáta, ktoré uchovávajú páry (kľúč alebo index + hodnota) a s ktorými sa vykonávajú tri operácie: pridanie nového páru, vyhľadávanie a vymazanie páru podľa kľúča.

Hľadajte v hašovacích tabuľkách realizované v dvoch etapách:

prvý krok - výpočet hašovacej funkcie, ktorá konvertuje kľúč hľadať v tabuľke adresu:

druhý krok je proces riešenia konfliktov pri spracovaní takýchto kľúčov.

Ak rôzne hodnoty Tabuľkové kľúče generuje hašovacia funkcia rovnaký adresy, vraj vzniká Zrážka(konflikt, stret).

Hashovacie funkcie

Hlavným účelom hašovacej funkcie je porovnávanie rôznych kľúče Ak je to možné rôzne nie negatívne celýčísla.

Funkcia hashovania tém lepšie, ako menej identické generuje hodnoty.

Hašovacia funkcia musí byť zvolená tak, aby boli splnené nasledujúce vlastnosti:

hašovacia funkcia je definovaná na prvkoch množiny a berie celé číslo nezáporné hodnoty;

hašovacia funkcia ľahko vypočítať;

hašovacia funkcia môže trvať rôzne hodnoty od cca rovnako pravdepodobné(minimalizácia kolízií);

na príbuzných hodnoty argumentov hašovacia funkcia zaberá vzdialený hodnoty od seba navzájom.

Ak chcete vytvoriť dobrú hašovaciu funkciu, musíte poznať distribúciu kľúčov. Ak je známe rozloženie kľúča, potom by v ideálnom prípade mala byť hustota kľúča a rozloženie hustoty hash hodnoty identické.

Nechaj p ( kľúč ) - hustota distribúcie kľúčových požiadaviek. Potom je v ideálnom prípade hustota distribúcie požiadaviek na vstup do tabuľky g ( H ( kľúč )) byť také, aby v priemere počet prvkov, kat. bolo treba prejsť v reťaziach dvojčiat, bolo to minimálne.

Príklad.

Nech je súbor kľúče

{0, 1, 4, 5, 6, 7, 8, 9, 15, 20, 30, 40}

a nech stôl dovolí 4 vchod.

Môžete vytvoriť hašovaciu funkciu:

h(kľúč) = kľúč % 4 .

Potom dostanete nasledovné adresy pre vstupy

{0, 1, 2, 3} tabuľky:

h(kľúč)

Vstupné číslo
Maximálna dĺžka reťaze
% zásahov

3 0,5+1,5 0,25+0,5 0,08+1 0,17 ≈ 2,1 prvok zoznamu.

Príklad s inou hash funkciou.

h(kľúč)

Vstupné číslo
% zásahov

V priemere to zaberie 4 1,5 0,25 = 1,5 prvok zoznamu.

Ak ide o systém na vyhľadávanie informácií, jeho výkonnosť pri vyhľadávaní sa zvýši približne o 25 %.

Metódy konštrukcie hašovacích funkcií

Modulárne hashovanie

Jednoduchá, efektívna a bežne používaná hašovacia metóda.

Veľkosť tabuľky je vybraná ako jednoduchéčísla m a hašovacia funkcia sa vypočíta ako zvyšok divízie:

h(kľúč) = kľúč % m

kľúč– celočíselná číselná hodnota kľúča,

m- počet hodnôt hash (záznamy v tabuľke hash).

Takáto funkcia sa nazýva modulárny a zmeny z 0 predtým ( m - 1 ).

Modulárna hašovacia funkcia v C++:

typedefintHashIndexType;

HashIndexTypeHash(intkľúč)

{ vrátiťkľúč % m; }

Príklad

kľúč = {1, 3, 56, 4, 32, 40, 23, 7, 41,13, 6,7}

Nechaj m = 5

h(kľúč) = {1, 3, 1, 4, 2, 0, 3, 2, 1, 3, 1, 2}

Na výbere záleží m.Ak chcete získať náhodné rozdelenie kľúčov, musíte si vziať jednoduchéčíslo.

Multiplikatívna metóda

Hash funkcia:

h(kľúč) =

0 < A < 1 je konštanta.

12 mod5 = 2 (zvyšok po vydelení 12 5).

5,04 mod1= 0,04 (vyčnieva zlomková časť)

Príklad

kľúč = 123456

m = 10000

A = 0,6180339887499 = 0,618…

h(kľúč) = =

aditívna metóda

Používa sa na linky variabilná dĺžka (veľkosť tabuľky m rovná sa 256).

{ HashIndexType h = 0;

zatiaľ čo (*str)

h += (*str)++;

vrátiťh;

Nevýhodou aditívnej metódy je, že sa nerozlišujú podobné slová a anagramy, t.j. h(XY ) = h(YX )

aditívna metóda, kde kľúčom je reťazec znakov. V hašovacej funkcii sa reťazec prevedie na celé číslo sčítaním všetkých znakov a vrátením zvyšku po delení m (zvyčajne veľkosť tabuľky m = 256).int h(char *kľúč, int m) (int s = 0;pričom(*kľúč)s += *kľúč++;návrat s % m;) abc a taxík.Túto metódu je možné mierne upraviť, pričom výsledok získate sčítaním iba prvých a posledných znakov kľúčového reťazca. int h(char *kľúč, int m) (int len ​​​​= strlen(kľúč), s = 0;ak (len< 2) // Если длина ключа равна 0 или 1,s = key; // возвратить keyelse s = key + key;return s % m;}В этом случае коллизии будут возникать только в строках, например, abc a amc.

hašovacia funkcia vezme kľúč a vypočíta z neho adresu v tabuľke (adresa môže byť index v poli, ku ktorému sú reťazce pripojené), to znamená, že napríklad môže získať číslo 3 z reťazca „abcd “ a z reťazca „efgh“ môže dostať číslo 7 a potom sa cez hash preberie prvá štruktúra reťazca, alebo cez hash hľadanie pokračuje pozdĺž reťazca, kým sa „abcd“ nenájde v reťazci štruktúr z hashu , alebo "efgh" sa nachádza v reťazci štruktúr z hash, keď sa nájde štruktúra s "abcd ", zvyšok jej údajov sa vezme a vráti, alebo sa vrátia všetky vo všeobecnosti (jej adresa), takže môže z neho vziať zvyšok údajov a reťazec štruktúr je vytvorený, pretože mnoho rôzne kľúče, majú rovnakú adresu v tabuľke, to znamená, že napríklad hašovacia funkcia pre "abcd" môže vrátiť 3 a pre "zxf9" môže vrátiť aj 3, takže sú spojené do reťazca, ktorý visí na treťom indexe pole ... ...

Pole H ukladá samotné páry kľúč – hodnota. Algoritmus vkladania prvkov kontroluje bunky poľa H v určitom poradí, kým sa nenájde prvá voľná bunka, do ktorej bude zapísaný nový prvok.

Vyhľadávací algoritmus prehľadáva bunky hašovacej tabuľky v rovnakom poradí ako pri vkladaní, kým nenájde prvok s požadovaným kľúčom alebo voľnú bunku (čo znamená, že v hašovacej tabuľke nie je žiadny prvok).

XOR

Používa sa pre reťazce s premenlivou dĺžkou. Metóda je podobná aditívnej metóde, ale rozlišuje podobné slová. Spočíva v tom, že operácia "exkluzívne OR" sa postupne aplikuje na prvky reťazca

typedef unsigned char HashIndexType;

nepodpísaný znak Rand8;

HashIndexType Hash(char *str)

( znak bez znamienka h = 0;

zatiaľ čo (*str) h = Rand8;

vrátiťh; }

Tu Rand8 – tabuľku 256 osembitových náhodných čísel.

veľkosť tabuľky<= 65536

typedef unsigned short int HashIndexType;

nepodpísaný znak Rand8;

HashIndexType Hash(char *str)

( HashIndexType h; unsigned char h1, h2;

if (*str == 0) vráti 0;

h1 = *str; h2 = *str + 1; str++;

zatiaľ čo (*str)

(h1 = Rand8; h2 = Rand8;

str++; )

h = ((HashIndexType)h1<< 8) | (HashIndexType)h2;

návrat h % HashTableSize )

Univerzálny hašovanie

Implikuje náhodný výber hašovacej funkcie z nejakej množiny počas plnenie programy.

Ak v multiplikatívnej metóde použiť ako ALE podsekvencia náhodný hodnoty namiesto pevného čísla získate univerzálnu hašovaciu funkciu.

Čas na generovanie náhodných čísel však bude príliš dlhý veľký.

Môže byť použité pseudonáhodnýčísla.

// generátor pseudonáhodných čísel

typedefintHashIndexType;

HashIndexTypeHash(char*v, intm)

(int h, a = 31415, b = 27183;

for(h = 0;*v != 0; v++, a = a*b % (m – l))

h = (a*h + *v) % m;

vrátiť (h< 0) ? (h + m) : h;