Domnívám se, že mnozí vědí, že od roku 2007 pořádá americký Národní institut pro standardy a technologie (NIST) soutěž o vývoj hashovacího algoritmu, který nahradí SHA-1, a rodiny algoritmů SHA-2. Toto téma je však z nějakého důvodu na webu zbaveno pozornosti. To je vlastně to, co mě k vám přivedlo. Upozorňuji na sérii článků o hašovacích algoritmech. V tomto cyklu společně prostudujeme základy hašovacích funkcí, zvážíme nejznámější hašovací algoritmy, ponoříme se do atmosféry soutěže SHA-3 a zvážíme algoritmy, které tvrdí, že ji vyhrají, určitě je otestujeme. Pokud je to možné, budou zváženy také ruské hašovací standardy.

O sobě

Student katedry informační bezpečnosti.

O hašování

V současné době není téměř žádná kryptografická aplikace kompletní bez použití hashování.
Hashovací funkce jsou funkce navržené ke „komprimaci“ libovolné zprávy nebo souboru dat, obvykle zapsaných v binární abecedě, do nějaké kombinace bitů s pevnou délkou nazývané konvoluce. Hashovací funkce mají různé aplikace ve statistických experimentech, při testování logických zařízení, při vytváření algoritmů pro rychlé vyhledávání a kontrolu integrity záznamů v databázích. Hlavním požadavkem na hashovací funkce je jednotnost distribuce jejich hodnot s náhodným výběrem hodnot argumentů.
Kryptografická hašovací funkce je jakákoli hašovací funkce, která je kryptograficky bezpečná, to znamená, že splňuje řadu požadavků specifických pro kryptografické aplikace. V kryptografii se hashovací funkce používají k řešení následujících problémů:
- budování systémů kontroly integrity dat během jejich přenosu nebo ukládání,
- ověřování zdroje dat.

Hašovací funkce je jakákoli funkce h:X -> Y, snadno vyčíslitelné a takové, že pro jakoukoli zprávu M význam h(M) = H (konvoluce) má pevnou délku bitu. X- sada všech zpráv, Y- množina binárních vektorů pevné délky.

Hašovací funkce jsou zpravidla budovány na základě tzv. jednokrokových kontrakčních funkcí y \u003d f (x 1, x 2) dvě proměnné, kde x 1, x2 a y- binární délkové vektory m, n a n respektive a n je délka konvoluce a m- délka bloku zpráv.
Chcete-li získat hodnotu h(M) zpráva je nejprve rozdělena na bloky délky m(zároveň, pokud délka zprávy není násobkem m pak se poslední blok nějakým speciálním způsobem doplní k úplnému bloku) a poté k blokům přijatým M 1, M 2,.., M N použijte následující postupný postup pro výpočet konvoluce:

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

Tady proti- nějaká konstanta, často se jí říká inicializační vektor. Ona se dostane ven
z různých důvodů a může to být tajná konstanta nebo soubor náhodných dat (například výběr data a času).
S tímto přístupem jsou vlastnosti hašovací funkce zcela určeny vlastnostmi funkce jednokrokové kontrakce.

Existují dva důležité typy kryptografických hašovacích funkcí – klíčované a bezklíčové. Klíčové hašovací funkce se nazývají ověřovací kódy zpráv. Umožňují bez dalších prostředků zaručit jak správnost zdroje dat, tak integritu dat v systémech se vzájemně důvěřivými uživateli.
Bezklíčové hašovací funkce se nazývají kódy detekce chyb. Pomocí dalších prostředků (například šifrování) umožňují zaručit integritu dat. Tyto hashovací funkce lze použít v systémech s důvěřivými i nedůvěřujícími uživateli.

O statistických vlastnostech a požadavcích

Jak jsem řekl, hlavním požadavkem na hashovací funkce je rovnoměrné rozložení jejich hodnot s náhodným výběrem hodnot argumentů. U kryptografických hashovacích funkcí je také důležité, že při sebemenší změně argumentu se hodnota funkce velmi změní. Tomu se říká lavinový efekt.

Na klíčové funkce hash má následující požadavky:
- nemožnost výroby,
- nemožnost modifikace.

První požadavek znamená, že je velmi obtížné přiřadit zprávu se správnou hodnotou skládání. Druhým je vysoká složitost přiřazování dané zprávy se známou hodnotou skládání jiné zprávy se správnou hodnotou skládání.

Požadavky na bezklíčové funkce jsou:
- jednosměrný,
- odolnost proti nárazům,
- odolnost proti nalezení druhého prototypu.

Jednosměrnost je chápána jako vysoká složitost nalezení zprávy danou konvoluční hodnotou. Nutno podotknout, že na tento moment nepoužívají se žádné hashovací funkce s osvědčeným jednosměrným přístupem.
Odolnost proti kolizi je chápána jako obtížnost nalezení dvojice zpráv se stejnými násobnými hodnotami. Obvykle je to právě nalezení způsobu, jak konstruovat kolize kryptoanalytiky, co slouží jako první signál zastaralosti algoritmu a nutnosti jeho rychlé výměny.
Odolnost vůči nalezení druhého předobrazu je chápána jako obtížnost nalezení druhé zprávy se stejnou hodnotou skládání pro danou zprávu se známou hodnotou skládání.

Toto byla teoretická část, která se nám bude hodit v budoucnu...

O populárních hashovacích algoritmech

Algoritmy CRC16/32- kontrolní součet (ne kryptografická konverze).

Algoritmy MD2/4/5/6. Jsou výtvorem Rona Rivesta, jednoho z autorů algoritmu RSA.
Algoritmus MD5 byl kdysi velmi populární, ale první předpoklady pro hacking se objevily na konci devadesátých let a nyní jeho popularita rychle klesá.
Algoritmus MD6 je z konstruktivního hlediska velmi zajímavý algoritmus. Byl nominován do soutěže SHA-3, ale bohužel se jej autorům nepodařilo uvést do standardu a tento algoritmus není v seznamu kandidátů, kteří postoupili do druhého kola.

Algoritmy pravítka SHA Algoritmy, které jsou dnes široce používány. Dochází k aktivnímu přechodu ze standardů verze SHA-1 na SHA-2. SHA-2 je souhrnný název pro algoritmy SHA224, SHA256, SHA384 a SHA512. SHA224 a SHA384 jsou v podstatě analogy SHA256 a SHA512, pouze po výpočtu konvoluce jsou některé informace v ní zahozeny. Měly by být používány pouze pro zajištění kompatibility se staršími modely zařízení.

ruský standard - GOST 34.11-94.

V dalším článku

Přehled MD algoritmů (MD4, MD5, MD6).

Literatura

A. P. Alferov, Základy kryptografie.

Bruce Schneier, aplikovaná kryptografie.

Hašování je speciální metoda adresování dat (nějaký druh mezerového algoritmu) svými jedinečnými klíči ( klíč ) abyste rychle našli potřebné informace.

Základní pojmy

Hash tabulka

Hashovací tabulka je pravidelné pole se speciální adresou danou nějakou funkcí (Hash function).

hashovací funkce

Funkce, která převádí klíč datové položky na nějaký index v tabulce ( hashovací tabulka), je nazýván hashovací funkce nebo hashovací funkce :

i = h (klíč );

kde klíč- konvertibilní klíč, i- výsledný index tabulky, tzn. klíč je zobrazen v sadě například celých čísel ( hash adresy ), které jsou později použity pro přístup k datům.

Hašování tímto způsobem je technika, která zahrnuje použití hodnoty klíče k určení jeho pozice ve speciální tabulce.

Funkce šíření však může několik jedinečné hodnoty klíče dávají stejnou hodnotu pozice i v hašovací tabulce. Zavolá se situace, kdy dva nebo více klíčů obdrží stejný index (hash adresu). kolize (kolizi) v hašování. Proto musí hašovací schéma zahrnovat algoritmus řešení konfliktů , definující pořadí akcí, pokud je pozice i=h(klíč) je již obsazen záznamem s jiným klíčem.

Existuje mnoho hašovacích schémat, která se liší použitou hašovací funkcí. h(klíč) a algoritmy řešení konfliktů.

Nejběžnější metoda pro určení hashovací funkce je: metoda dělení.

Počáteční data jsou: - nějaký celočíselný klíč klíč a velikost stolu m. Výsledkem této funkce je zbytek dělení tohoto klíče velikostí tabulky. Obecná podoba takové funkce v programovacím jazyce C/C++:

int h (int klíč , int m ) {

Pro m= 10 hašovací funkce vrací nejméně významnou číslici klíče.

Pro m=100 vrací hašovací funkce dvě nejméně významné číslice klíče.

V uvažovaných příkladech hashovací funkce i=h(klíč) pouze definuje pozici, ze které se má hledat (nebo zpočátku umístit do tabulky) záznam s klíčem klíč. Dále musíte použít nějaký druh hashovacího schématu (algoritmu).

Hašovací schémata

Ve většině problémů jsou dva nebo více klíčů hashovány stejným způsobem, ale nemohou zabírat stejnou buňku v tabulce hash. Existují dva možné možnosti: buď najděte jinou pozici pro nový klíč, nebo vytvořte samostatný seznam pro každý index hashovací tabulky, ve kterém jsou umístěny všechny klíče namapované na tento index.

Tyto varianty jsou dvě klasická hashovací schémata:

hašování otevřeným adresováním s lineárním sondováním - lineární sonda OTEVŘENO oslovování.

řetězové hašování (se seznamy), neboli tzv. multidimenzionální hašování - řetězení s samostatný seznamy;

Otevřená metoda adresování s lineárním snímáním . Zpočátku jsou všechny buňky hashovací tabulky, což je normální jednorozměrné pole, označeny jako neobsazené. Při přidávání nového klíče se tedy kontroluje, zda je daná buňka obsazená. Pokud je buňka obsazená, algoritmus hledá v kruhu, dokud nezůstane prázdné místo („otevřená adresa“).

Tito. prvky s homogenními klíči jsou umístěny blízko výsledného indexu.

V budoucnu při vyhledávání nejprve najděte pozici pomocí klíče i v tabulce, a pokud se klíč neshoduje, provede se následné vyhledávání v souladu s algoritmem řešení konfliktu, počínaje pozicí i. .

Řetězová metoda je dominantní strategie . V tomto případě i získané z vybrané hashovací funkce h(klíč)=i, se zachází jako s indexem do hash tabulky seznamů, tzn. nejprve klíč klíč další záznam je namapován na pozici i = h(klíč) tabulky. Pokud je pozice volná, pak se do ní umístí prvek s klíčem. klíč, pokud je zaneprázdněn, je vypracován algoritmus řešení konfliktů, v důsledku čehož jsou takové klíče umístěny do seznamu začínajícího na i-tu buňku hash tabulky. Například

Výsledkem je tabulka řady propojených seznamů nebo stromů.

Proces naplnění (čtení) hash tabulky je jednoduchý, ale přístup k prvkům vyžaduje následující operace:

Výpočet indexu i;

Hledejte v odpovídajícím řetězci.

Pro zlepšení vyhledávání při přidávání nového prvku můžete použít algoritmus vkládání nikoli na konec seznamu, ale s řazením, tzn. přidat prvek do Správné místo.

Příklad implementace metody přímého adresování s lineárním sondováním . Výchozími daty je 7 záznamů (pro zjednodušení se informační část skládá pouze z celočíselných dat), deklarovaného strukturálního typu:

intkey; // Klíč

intinfo; // Informace

(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9); velikost hash tabulky m=10.

hashovací funkce i=h(data) =data.klíč%deset; těch. zbytek po dělení 10 - i.

Na základě počátečních dat postupně vyplníme hashovací tabulku.

Hašování prvních pěti klíčů poskytuje různé indexy (hash adresy):

První kolize nastává mezi klíči 81 a 41 - místo s indexem 1 je obsazeno. Proto se podíváme do hashovací tabulky, abychom našli nejbližší volné místo, v tomto případě je i = 2.

Další klíč 79 také generuje kolizi: pozice 9 je již obsazena. Účinnost algoritmu prudce klesá, protože k nalezení volného místa bylo potřeba 6 pokusů (porovnání), index se ukázal jako volný i= 4.

Celkový počet vzorků této metody je od 1 do n-1 vzorků na prvek, kde n je velikost hashovací tabulky.

Implementace metody řetězení pro předchozí příklad. Pro prvek seznamu deklarujeme strukturální typ (jednosměrný):

intkey; // Klíč

intinfo; // Informace

zap*Další; // Ukazatel na další prvek na seznamu

Na základě počátečních dat postupně plníme hashovací tabulku přidáváním nový prvek na konec seznamu, pokud je místo již obsazeno.

Hašování prvních pěti klíčů, jako v předchozím případě, poskytuje různé indexy (hash adresy): 9, 0, 6, 1 a 3.

Když dojde ke kolizi, nový prvek se přidá na konec seznamu. Proto je prvek s klíčem 41 umístěn za prvkem s klíčem 81 a prvek s klíčem 79 je umístěn za prvkem s klíčem 59.

Jednotlivé úkoly

1. Binární stromy. Pomocí programu generátoru náhodných čísel získejte 10 hodnot od 1 do 99 a vytvořte binární strom.

Udělejte si objížďku:

1.a Procházení zleva doprava: Left-Root-Right: nejprve navštivte levý podstrom, pak kořen a nakonec pravý podstrom.

(Nebo naopak, zprava doleva: zprava-odmocnina-doleva)

1.b Procházení shora dolů: Root-Left-Right: přejděte do kořene k podstromům.

1.V Traversal from bottom to top: Left-Right-Root: návštěva kořene po podstromech

V celé řadě průmyslových odvětví informační technologie najít jejich použití hashovací funkce. Jsou navrženy tak, aby na jedné straně výrazně zjednodušily výměnu dat mezi uživateli a zpracování souborů používaných pro určité účely, na straně druhé optimalizovaly algoritmy pro zajištění řízení přístupu k odpovídajícím zdrojům. Hašovací funkce je jednou z klíčové nástroje zajištění ochrany dat heslem, stejně jako organizace výměny dokumentů podepsaných pomocí EDS. Existuje velké množství standardů, podle kterých lze soubory ukládat do mezipaměti. Mnohé z nich jsou vyvinuty ruskými specialisty. Jaké jsou typy hashovacích funkcí? Jaké jsou hlavní mechanismy jejich praktické aplikace?

co to je?

Nejprve prozkoumáme koncept hashovací funkce. Tento termín je běžně chápán jako algoritmus pro převod určitého množství informací na kratší sekvenci znaků pomocí matematických metod. Praktický význam hashovací funkce lze vysledovat v různých oblastech. Lze je tedy použít při kontrole integrity souborů a programů. V šifrovacích algoritmech se také používají kryptografické hašovací funkce.

Charakteristika

Podívejme se na klíčové vlastnosti studovaných algoritmů. Mezi těmito:

• přítomnost vnitřních algoritmů pro převod dat původní délky na kratší sekvenci znaků;
• otevřenost pro kryptografické ověření;
• přítomnost algoritmů, které umožňují bezpečně šifrovat původní data;
• přizpůsobivost k dešifrování pomocí malých výpočetní výkon.

Mezi další důležité vlastnosti hashovací funkce patří:

• schopnost zpracovávat počáteční pole dat libovolné délky;
• generovat hashované bloky pevné délky;
• rovnoměrně distribuovat funkční hodnoty na výstupu.

Uvažované algoritmy rovněž předpokládají citlivost na vstupní data na úrovni 1 bitu. To znamená, že i když se relativně vzato změní alespoň 1 písmeno ve zdrojovém dokumentu, hashovací funkce bude vypadat jinak.

Požadavky na hashovací funkce

Na hashovací funkce určené pro praktické použití v konkrétní oblasti existuje řada požadavků. Za prvé, odpovídající algoritmus musí být citlivý na změny ve vnitřní struktuře hašovaných dokumentů. To znamená, že hashovací funkce by měla být rozpoznána, když na to přijde textový soubor, permutace odstavců, dělení slov. Jednak se nemění obsah dokumentu, jednak je opravena jeho struktura a tento proces je třeba při hašování rozpoznat. Za druhé, uvažovaný algoritmus musí transformovat data takovým způsobem, aby zpětná operace (přeměna hashe na původní dokument) byla v praxi nemožná. Za třetí, hashovací funkce by měla zahrnovat použití takových algoritmů, které prakticky vylučují možnost vytvoření stejné sekvence znaků ve formě hashe, jinými slovy výskyt takzvaných kolizí. O jejich podstatě se budeme zabývat o něco později.

Uvedené požadavky, které musí algoritmus hashovací funkce splňovat, lze dosáhnout především použitím komplexních matematických přístupů.

Struktura

Podívejme se, jaká může být struktura uvažovaných funkcí. Jak jsme uvedli výše, mezi hlavní požadavky na uvažované algoritmy patří zajištění jednosměrného šifrování. Člověk, který má k dispozici pouze hash, by se na jeho základě k původnímu dokumentu prakticky neměl dostat.

V jaké struktuře může být reprezentována hashovací funkce používaná pro takové účely? Příklad jeho sestavení může být následující: H (hash, tedy hash) = f (T (text), H1), kde H1 je algoritmus T zpracování textu. Tato funkce hashuje T tak, že bez znalosti H1 jej prakticky nebude možné otevřít jako plnohodnotný soubor.

Použití hashovacích funkcí v praxi: Stahování souborů

Pojďme si nyní podrobněji prostudovat možnosti využití hašovacích funkcí v praxi. Použití vhodných algoritmů lze využít při psaní skriptů pro stahování souborů z internetových serverů.

Ve většině případů je pro každý soubor určen určitý kontrolní součet - to je hash. Musí být stejný pro objekt umístěný na serveru a stažený do počítače uživatele. Pokud tomu tak není, soubor se nemusí otevřít nebo se nespustí správně.

Hash funkce a digitální podpis

Použití hašovacích funkcí je běžné při organizování výměny dokumentů obsahujících digitální podpis. V tomto případě je podepsaný soubor hašován, aby jeho příjemce mohl ověřit, že je pravý. Přestože hashovací funkce není ve struktuře formálně zahrnuta elektronický klíč, lze jej opravit ve flash paměti hardwaru, kterým se dokumenty podepisují, jako je například eToken.

Elektronický podpis je šifrování souboru pomocí veřejných a soukromých klíčů. To znamená, že ke zdrojovému souboru je připojena zpráva zašifrovaná soukromým klíčem a digitální podpis je ověřen pomocí veřejný klíč. Pokud se hašovací funkce obou dokumentů shoduje, je soubor příjemce rozpoznán jako autentický a podpis odesílatele je rozpoznán jako správný.

Hashování, jak jsme uvedli výše, není přímo součástí EDS, umožňuje však velmi efektivně optimalizovat algoritmy pro použití elektronický podpis. Šifrovat lze tedy pouze hash, nikoli samotný dokument. V důsledku toho se výrazně zvyšuje rychlost zpracování souborů a zároveň je možné poskytnout efektivnější mechanismy ochrany EDS, protože důraz ve výpočetních operacích v tomto případě nebude kladen na zpracování počátečních dat, ale na zajištění kryptografická síla podpisu. Hašovací funkce také umožňuje podepisovat různé typy dat, nejen text.

Kontrola hesel

Další možnou oblastí použití pro hašování je organizace algoritmů pro ověřování hesel vytvořených pro rozlišení přístupu k určitým zdrojům souborů. Jak mohou být určité typy hashovacích funkcí zapojeny do řešení takových problémů? Velmi jednoduché.

Faktem je, že na většině serverů, k nimž přístup podléhá diferenciaci, jsou hesla uložena ve formě hashovaných hodnot. To je celkem logické – pokud by byla hesla prezentována v původní textové podobě, hackeři, kteří k nim získali přístup, mohli tajná data snadno přečíst. Na druhé straně, na základě hashe, není snadné vypočítat heslo.

Jak se kontroluje uživatelský přístup, když jsou použity uvažované algoritmy? Heslo zadané uživatelem je porovnáno s tím, co je pevně stanoveno v hashovací funkci, která je uložena na serveru. Pokud se hodnoty textových bloků shodují, uživatel získá potřebný přístup ke zdrojům.

Nejjednodušší hashovací funkci lze použít jako nástroj pro kontrolu hesla. V praxi však IT profesionálové nejčastěji používají složité vícestupňové kryptografické algoritmy. Obvykle jsou doplněny o použití standardů pro přenos dat zabezpečeným kanálem, takže hackeři nemohou zjistit nebo zjistit heslo přenášené z počítače uživatele na servery před tím, než je ověřeno pomocí hašovaných textových bloků.

Kolize hashovací funkce

V teorii hašovacích funkcí je poskytnut takový jev, jako je kolize. Jaká je její podstata? Hašovací kolize je situace, kdy dva různé soubory mají stejný hašovací kód. To je možné, pokud je délka cílové sekvence znaků malá. V tomto případě bude pravděpodobnost shody hash vyšší.

Aby se předešlo kolizi, doporučuje se zejména použít dvojitý algoritmus nazvaný „hashovací funkce hash“. Zahrnuje tvorbu otevřeného a uzavřeného kódu. Mnoho programátorů při řešení kritických problémů doporučuje nepoužívat hashovací funkce v případech, kdy to není nutné, a vždy otestovat odpovídající algoritmy pro nejlepší kompatibilitu s určitými klíči.

Historie vzhledu

Za zakladatele teorie hašovacích funkcí lze považovat badatele Cartera, Wegmana, Simonsona, Bierbrouera. V prvních verzích byly odpovídající algoritmy použity jako nástroje pro generování jedinečných obrazů sekvencí znaků libovolné délky s následným účelem jejich identifikace a ověření pravosti. Na druhé straně by hash v souladu se stanovenými kritérii měl mít délku 30-512 bitů. Jako speciál užitečná vlastnost odpovídající funkce, byla zvážena jeho vhodnost použití jako zdroje pro rychlé vyhledávání souborů nebo jejich třídění.

Populární hashovací standardy

Podívejme se nyní, v jakých populárních standardech mohou být hashovací funkce zastoupeny. Jedním z nich je CRC. Tento algoritmus je cyklický kód, nazývaný také kontrolní součet. Tento standard se vyznačuje jednoduchostí a zároveň všestranností – jeho prostřednictvím můžete hashovat nejširší spektrum dat. CRC je jedním z nejběžnějších nekryptografických algoritmů.

Standardy MD4 a MD5 jsou zase široce používány v šifrování. Dalším populárním kryptografickým algoritmem je SHA-1. Zejména se vyznačuje velikostí hashe 160 bitů, což je větší hodnota než u MD5 – tento standard podporuje 128 bitů. Existují ruské normy, které upravují používání hašovacích funkcí - GOST R 34.11-94, stejně jako GOST R 34.11-2012, které je nahradily. Lze poznamenat, že hodnota hash poskytovaná algoritmy přijatými v Ruské federaci je 256 bitů.

Dotyčné normy lze klasifikovat různými způsoby. Existují například ty, které používají blokové a specializované algoritmy. Jednoduchost výpočtů na základě standardů prvního typu je často doprovázena jejich nízkou rychlostí. Proto lze jako alternativu k blokovým algoritmům použít ty, které zahrnují menší množství nutných výpočetních operací. Je obvyklé odvolávat se na vysokorychlostní standardy, zejména výše uvedené MD4, MD5 a SHA. Podívejme se podrobněji na specifika speciálních hashovacích algoritmů na příkladu SHA.

Vlastnosti algoritmu SHA

Využití hašovacích funkcí založených na standardu SHA se nejčastěji realizuje v oblasti vývoje nástrojů digitální podpis dokumenty DSA. Jak jsme uvedli výše, Algoritmus SHA podporuje hash 160 bitů (poskytuje tzv. „digest“ sekvence znaků). Zpočátku uvažovaný standard rozděluje datové pole do bloků po 512 bitech. V případě potřeby, pokud délka posledního bloku nedosahuje zadané hodnoty, je struktura souboru doplněna o 1 a požadovaný počet nul. Na konci odpovídajícího bloku je také zadán kód, který určuje délku zprávy. Uvažovaný algoritmus zahrnuje 80 logických funkcí, jejichž prostřednictvím jsou zpracovávána 3 slova, reprezentovaná ve 32 bitech. Standard SHA také umožňuje použití 4 konstant.

Porovnání hashovacích algoritmů

Pojďme si na příkladu srovnání charakteristik ruské normy GOST R 34.11-94 a amerického SHA, o kterých jsme diskutovali výše, prostudovat, jak korelují vlastnosti hašovacích funkcí souvisejících s různými standardy. Nejprve je třeba poznamenat, že algoritmus vyvinutý v Ruské federaci zahrnuje implementaci 4 šifrovacích operací za 1 cyklus. To odpovídá 128 ranám. Na druhé straně se během 1 kola při použití SHA očekává výpočet asi 20 příkazů, přičemž kol je celkem 80. Použití SHA tedy umožňuje zpracovat 512 bitů počátečních dat během 1 cyklu. Zatímco ruský standard je schopen provádět operace v cyklu 256 bitů dat.

Specifika nejnovějšího ruského algoritmu

Výše jsme poznamenali, že norma GOST R 34.11-94 byla nahrazena novější - GOST R 34.11-2012 Stribog. Pojďme prozkoumat jeho specifika podrobněji.

Přes tento standard mohou být implementovány, jako v případě výše diskutovaných algoritmů, kryptografické hashovací funkce. Lze poznamenat, že nejnovější ruský standard podporuje blok vstupních dat ve výši 512 bitů. Hlavní výhody GOST R 34.11-2012:

• vysoká úroveň ochrany proti prolomení šifer;
• spolehlivost, podpořená použitím osvědčených konstrukcí;
• rychlý výpočet hašovací funkce, absence transformací v algoritmu, které komplikují konstrukci funkce a zpomalují výpočet.

Významné výhody nového ruského standardu kryptografické šifrování vám umožní používat jej v organizaci pracovního postupu, který splňuje nejpřísnější kritéria, která jsou předepsána v ustanoveních regulačních právních předpisů.

Specifičnost kryptografických hašovacích funkcí

Podívejme se podrobněji na to, jak lze typy algoritmů, které studujeme, použít v oblasti kryptografie. Klíčovým požadavkem na odpovídající funkce je odolnost proti kolizím, kterou jsme zmínili výše. To znamená, že by se neměly generovat duplicitní hodnoty hash, pokud jsou tyto hodnoty již přítomny ve struktuře sousedního algoritmu. Ostatní kritéria uvedená výše musí také splňovat kryptografické funkce. Je jasné, že vždy existuje nějaká teoretická možnost nápravy zdrojový soubor založené na hash, zvláště pokud je k dispozici výkonný výpočetní nástroj. Tento scénář by však měl být minimalizován díky silným šifrovacím algoritmům. Bude tedy velmi obtížné vypočítat hašovací funkci, pokud její výpočetní síla odpovídá vzorci 2^(n/2).

Dalším důležitým kritériem pro kryptografický algoritmus je změna hashe v případě, že je opraveno počáteční pole dat. Výše jsme si všimli, že šifrovací standardy by měly mít citlivost na úrovni 1 bit. Tato vlastnost je tedy klíčovým faktorem pro zajištění spolehlivé ochrany přístupu k souborům heslem.

Iterativní schémata

Podívejme se nyní na to, jak lze sestavit kryptografické hashovací algoritmy. Mezi nejběžnější schémata řešení tohoto problému patří použití iterativního sekvenčního modelu. Je založena na použití tzv. kontrakční funkce, při které je počet vstupních bitů výrazně větší než ty, které jsou pevně dané na výstupu.

Kompresní funkce samozřejmě musí splňovat nezbytná kritéria kryptografické pevnosti. V interaktivním schématu je první operace pro zpracování vstupního datového toku rozdělena do bloků, jejichž velikost se počítá v bitech. Odpovídající algoritmus také používá dočasné proměnné daného počtu bitů. Jako první hodnota je použito dobře známé číslo, zatímco následující bloky dat jsou na výstupu kombinovány s hodnotou příslušné funkce. Hodnota hash se stane bitovým výstupem pro poslední iteraci, která bere v úvahu celý vstupní tok, včetně první hodnoty. Je zajištěn takzvaný „lavinový efekt“ hašování.

Hlavním problémem, který charakterizuje hašování implementované jako iterativní schéma, je to, že hašovací funkce se někdy obtížně konstruují, pokud vstupní proud není identický s velikostí bloku, do kterého je počáteční pole dat rozděleno. Ale v tomto případě mohou být algoritmy zapsány v hašovacím standardu, pomocí kterého lze původní stream tak či onak rozšířit.

V některých případech mohou být do procesu zpracování dat v rámci iterativního schématu zapojeny tzv. víceprůchodové algoritmy. Naznačují vznik ještě intenzivnějšího „lavinový efekt“. Takový scénář zahrnuje vytváření opakovaných datových polí a až na druhém místě je rozšiřování.

Blokový algoritmus

Kompresní funkce může být také založena na blokovém algoritmu, kterým se provádí šifrování. Aby se zvýšila úroveň zabezpečení, můžete jako klíč použít bloky dat, které jsou předmětem hašování v aktuální iteraci, a jako vstup výsledek operací získaných během provádění komprimační funkce před tím. . Výsledkem je, že poslední iterace poskytne výstup algoritmu. Bezpečnost hashe bude korelovat s robustností použitého algoritmu.

Nicméně, jak jsme uvedli výše, uvažovat různé druhy hashovací funkce, blokové algoritmy jsou často doprovázeny nutností použití velkého výpočetního výkonu. Pokud nejsou k dispozici, rychlost zpracování souborů nemusí být dostatečná k vyřešení praktických problémů souvisejících s používáním hashovacích funkcí. Požadovanou kryptografickou sílu lze zároveň realizovat pomocí malého počtu operací se zdrojovými datovými toky, zejména námi zvažované algoritmy - MD5, SHA a ruské kryptografické šifrovací standardy - jsou přizpůsobeny řešení takových problémů.

Co je to hash? Hašovací funkce je matematická transformace informace do krátkého řetězce určité délky.

Proč je to potřeba? Analýza hashovací funkce se často používá ke kontrole integrity důležitých souborů operační systém, důležité programy, důležité údaje. Monitorování lze provádět jak podle potřeby, tak i pravidelně.

Jak se to dělá? Nejprve určete integritu souborů, které je třeba monitorovat. Pro každý soubor se podle speciálního algoritmu vypočítá hodnota jeho hashe a výsledek se uloží. Po nezbytné době se provede podobný výpočet a výsledky se porovnají. Pokud se hodnoty liší, informace obsažené v souboru byly změněny.

Jaké vlastnosti by měla mít hashovací funkce?

• musí být schopen provádět transformace dat libovolné délky na fixní;
• musí mít otevřený algoritmus, aby bylo možné prozkoumat jeho kryptografickou sílu;
• měla by být jednostranná, to znamená, že by neměla existovat matematická možnost určit výchozí data z výsledku;
• měly by „odolat“ kolizím, to znamená, že by neměly produkovat stejné hodnoty pro různá vstupní data;
• by nemělo vyžadovat velké výpočetní zdroje;
• při sebemenší změně vstupních dat by se měl výsledek výrazně změnit.

Jaké jsou oblíbené hashovací algoritmy? V současné době se používají následující hashovací funkce:

• CRC je zkratka pro kód cyklické redundance nebo kontrolní součet. Algoritmus je velmi jednoduchý, má velké množství variací v závislosti na požadované délce výstupu. Není kryptografický!
• MD 5 je velmi populární algoritmus. Jako on předchozí verze MD 4 je kryptografická funkce. Velikost hashe je 128 bitů.
• SHA -1 je také velmi oblíbená kryptografická funkce. Velikost hashe je 160 bitů.
• GOST R 34.11-94 je ruský kryptografický standard pro výpočet hashovací funkce. Velikost hashe je 256 bitů.

Kdy může správce systému použít tyto algoritmy?Často se při stahování jakéhokoli obsahu, jako jsou programy z webových stránek výrobce, hudba, filmy nebo jiné informace, vyskytuje hodnota kontrolního součtu vypočítaná pomocí určitého algoritmu. Z bezpečnostních důvodů musíte po stažení nezávisle vypočítat hashovací funkci a porovnat hodnotu s tím, co je uvedeno na webu nebo v příloze k souboru. Už jsi to někdy dělal?

Co je pro výpočet hashe pohodlnější? Nyní existuje velké množství takových nástrojů, placených i bezplatných. Osobně se mi líbil HashTab. Za prvé, během instalace je nástroj vložen jako karta ve vlastnostech souboru, za druhé vám umožňuje vybrat velké množství hashovacích algoritmů a za třetí je zdarma pro soukromé nekomerční použití.

co je to ruština? Jak bylo uvedeno výše, v Rusku existuje hashovací standard GOST R 34.11-94, který je široce používán mnoha výrobci nástrojů pro bezpečnost informací. Jedním z těchto nástrojů je fixační a kontrolní program. výchozí stav softwarový balík"OPRAVIT". Tento program je prostředkem ke sledování efektivity využívání zařízení informační bezpečnosti.

OPRAVA (verze 2.0.1) pro Windows 9x/NT/2000/XP

• Výpočet kontrolních součtů daných souborů pomocí jednoho z 5 implementovaných algoritmů.
• Fixace a následná kontrola výchozího stavu softwarového balíku.
• Porovnání verzí softwarových balíků.
• Oprava a kontrola adresářů.
• Řízení změn v zadaných souborech (adresářích).
• Generování reportů ve formátech TXT, HTML, SV.
• Výrobek má do 01.06.2013 certifikát FSTEC dle NDV 3 č. 913.

A co ECP? Výsledek výpočtu hashovací funkce spolu s tajným klíčem uživatele vstupuje na vstup kryptografického algoritmu, kde je vypočítán digitální podpis. Přesně řečeno, hashovací funkce není součástí algoritmu EDS, ale často se tak děje záměrně, aby se vyloučil útok na veřejný klíč.

V dnešní době mnoho aplikací pro e-commerce umožňuje ukládání Tajný klíč uživatel v soukromé oblasti tokenu (ruToken, eToken) bez technická proveditelnost extrahovat to odtud. Samotný token má velmi omezenou paměťovou oblast, měřenou v kilobajtech. Pro podepsání dokumentu neexistuje způsob, jak přenést dokument do samotného tokenu, ale je velmi snadné přenést hash dokumentu do tokenu a získat EDS na výstupu.

Hash tabulky

Hash tabulka(zamíchaná tabulka, tabulka s vypočtenými adresami) je dynamickou sadu podporující operace přidávání, vyhledávání a mazání prvku a pomocí speciálních metod oslovování.

Hlavní rozdíl mezi tabulkami a jinými dynamickými sadami je výpočet adresy prvku podle hodnoty klíče.

Myšlenka implementace hash spočívá v tom, že práce s jedním velkým polem se redukuje na práci s řadou malých sad.

Například notebook. Stránky knihy jsou označeny písmeny. Stránka označená písmenem obsahuje příjmení začínající tímto písmenem. Velká množina příjmení je rozdělena do 28 podmnožin. Při hledání se kniha okamžitě otevře na požadované písmeno a hledání se zrychlí.

V programovací hashovací tabulce- tohle je struktura data, která ukládají páry (klíč nebo index + hodnota) a se kterými se provádějí tři operace: přidání nového páru, vyhledání a odstranění páru podle klíče.

Vyhledávání v hash tabulkách se provádí ve dvou fázích:

první krok - výpočet hashovací funkce, která převádí klíč hledat v tabulce adresa:

druhý krok je proces řešení konfliktů při zpracování takových klíčů.

Pokud různé hodnoty generuje hashovací funkce klíčů tabulky stejný adresy, prý vzniká kolize(konflikt, střet).

Hashovací funkce

Hlavním účelem hašovací funkce je spárování různých klíče Pokud možno rozličný ne negativní Celýčísla.

Funkce hash pro témata lepší, jak méně identické generuje hodnoty.

Hashovací funkce musí být zvolena tak, aby byly splněny následující vlastnosti:

hashovací funkce je definována na prvcích množiny a bere celé číslo nezáporné hodnoty;

hashovací funkce snadné spočítat;

hash funkce může trvat rozličný hodnoty od cca stejně pravděpodobné(minimalizace kolize);

na příbuzní hodnoty argumentů hašovací funkce přebírá vzdálený hodnoty od sebe navzájem.

Chcete-li vytvořit dobrou hashovací funkci, musíte znát rozložení klíčů. Pokud je známo rozložení klíčů, pak by v ideálním případě měly být hustota klíče a rozložení hustoty hash hodnot identické.

Nechat p ( klíč ) - hustota distribuce klíčových požadavků. Potom je v ideálním případě hustota distribuce vstupních požadavků tabulky G ( H ( klíč )) být takové, aby v průměru počet prvků, kat. bylo nutné procházet v řetězech dvojčat, bylo to minimální.

Příklad.

Nechť je soubor klíče

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

a nechte stůl dovolit 4 vchod.

Můžete vytvořit hashovací funkci:

h(klíč) = klíč % 4 .

Pak získáte následující adresy pro vstupy

{0, 1, 2, 3} tabulky:

h(klíč)

Vstupní číslo
Maximální délka řetězu
% zásahů

3 0,5+1,5 0,25+0,5 0,08+1 0,17 ≈ 2,1 prvek seznamu.

Příklad s jinou hashovací funkcí.

h(klíč)

Vstupní číslo
% zásahů

V průměru to zabere 4 1,5 0,25 = 1,5 prvek seznamu.

Pokud se jedná o systém pro vyhledávání informací, pak se jeho vyhledávací výkon zvýší asi o 25 %.

Metody pro konstrukci hašovacích funkcí

Modulární hashování

Jednoduchá, efektivní a běžně používaná hašovací metoda.

Velikost tabulky je vybrána jako jednoduchýčísla m a hashovací funkce se vypočítá jako zbytek divize:

h(klíč) = klíč % m

klíč– celočíselná číselná hodnota klíče,

m- počet hodnot hash (položky v tabulce hash).

Taková funkce se nazývá modulární a mění se z 0 před ( m - 1 ).

Modulární hashovací funkce v C++:

typedefintHashIndexType;

HashIndexTypehash(intklíč)

{ vrátit seklíč % m; }

Příklad

klíč = {1, 3, 56, 4, 32, 40, 23, 7, 41,13, 6,7}

Nechat m = 5

h(klíč) = {1, 3, 1, 4, 2, 0, 3, 2, 1, 3, 1, 2}

Na výběru záleží m.Chcete-li získat náhodné rozdělení klíčů, musíte vzít jednoduchýčíslo.

Multiplikativní metoda

Hash funkce:

h(klíč) =

0 < A < 1 je konstanta.

12 mod5 = 2 (zbytek po dělení 12 5).

5,04 mod1= 0,04 (vyčnívá zlomková část)

Příklad

klíč = 123456

m = 10000

A = 0,6180339887499 = 0,618…

h(klíč) = =

aditivní metoda

Používá se pro linky variabilní délka (velikost stolu m rovná se 256).

{ HashIndexType h = 0;

zatímco (*str)

h += (*str)++;

vrátit seh;

Nevýhodou aditivní metody je, že se nerozlišují podobná slova a anagramy, tzn. h(XY ) = h(YX )

aditivní metoda, kde klíč je znakový řetězec. V hashovací funkci je řetězec převeden na celé číslo sečtením všech znaků a vrácením zbytku po dělení m (obvykle velikost tabulky m = 256).int h(char *klíč, int m) (int s = 0; while(*key)s += *key++;návrat s % m;) abc a kabina.Tuto metodu lze mírně upravit a získat výsledek sečtením pouze prvních a posledních znaků řetězce klíče. int h(char *klíč, int m) (int len ​​​​= strlen(klíč), s = 0;if (len< 2) // Если длина ключа равна 0 или 1,s = key; // возвратить keyelse s = key + key;return s % m;}В этом случае коллизии будут возникать только в строках, например, abc a amc.

hashovací funkce vezme klíč a vypočítá z něj adresu v tabulce (adresa může být index v poli, ke kterému jsou připojeny řetězce), to znamená, že například může získat číslo 3 z řetězce "abcd ", a z řetězce "efgh" může získat číslo 7 a pak se první struktura řetězce vezme přes hash, nebo přes hash pokračuje hledání podél řetězce, dokud se v řetězci struktur z hashe nenajde "abcd" , nebo "efgh" se nachází v řetězci struktur z hash, když je nalezena struktura s "abcd ", zbytek jejích dat je převzat a vrácen nebo je obecně vrácena všechna (její adresa), takže může z něj vzít zbytek dat a řetězec struktur je vytvořen, protože mnoho různé klíče, mají v tabulce stejnou adresu, to znamená, že například hashovací funkce pro "abcd" může vrátit 3 a pro "zxf9" může také vrátit 3, takže jsou spojeny do řetězce, který visí na třetím indexu pole ... ...

Pole H ukládá samotné páry klíč–hodnota. Algoritmus vkládání prvků kontroluje buňky pole H v určitém pořadí, dokud není nalezena první volná buňka, do které bude nový prvek zapsán.

Algoritmus hledání prohledává buňky hašovací tabulky ve stejném pořadí jako při vkládání, dokud nenajde buď prvek s požadovaným klíčem, nebo volnou buňku (což znamená, že v hašovací tabulce není žádný prvek).

XOR

Používá se pro struny s proměnnou délkou. Metoda je podobná aditivní metodě, ale rozlišuje podobná slova. Spočívá v tom, že operace "exclusive OR" je postupně aplikována na prvky řetězce

typedef unsigned char HashIndexType;

nepodepsaný znak Rand8;

HashIndexType Hash(char *str)

( znak bez znaménka h = 0;

zatímco (*str) h = Rand8;

vrátit seh; }

Tady Rand8 – tabulka 256 osmibitových náhodných čísel.

velikost stolu<= 65536

typedef unsigned short int HashIndexType;

nepodepsaný znak Rand8;

HashIndexType Hash(char *str)

( HashIndexType h; unsigned char h1, h2;

if (*str == 0) vrátí 0;

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

zatímco (*str)

(hl = Rand8; h2 = Rand8;

str++; )

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

návrat h % HashTableSize )

Univerzální hašování

Naznačuje náhodný výběr hašovací funkce z nějaké množiny během splnění programy.

Pokud v multiplikativní metodě použít jako ALE subsekvence náhodný hodnoty namísto pevného čísla získáte univerzální hashovací funkci.

Čas na generování náhodných čísel však bude příliš dlouhý velký.

Může být použito pseudonáhodnéčísla.

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

typedefintHashIndexType;

HashIndexTypeHash(znak*v, int m)

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

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

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

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