Výpočet hashovací funkce. Hash - co to je? Definice, význam, překlad. Hašovací funkce založené na dělení

12. května 2010 v 01:28

Hashovací algoritmy

• Informační bezpečnost

Domnívám se, že mnoho lidí ví, že od roku 2007 pořádá americký Národní institut pro standardy a technologie (NIST) soutěž o vývoj hašovacího algoritmu, který nahradí SHA-1, a rodiny algoritmů SHA-2. Však toto téma, byl z nějakého důvodu na webu zanedbaný. To je vlastně to, co mě k vám přivedlo. Upozorňuji na sérii článků věnovaných hašovacím algoritmům. V této sérii 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í, a určitě je otestujeme. Pokud to bude možné, budeme také uvažovat Ruské standardy hašování.

O mně

Student katedry informační bezpečnosti.

O hašování

V dnešní době se prakticky žádná kryptografická aplikace neobejde 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 určitého bitového vzoru s pevnou délkou nazývaného konvoluce. Hashovací funkce mají různé aplikace při provádění statistických experimentů, při testování logická zařízení při konstrukci algoritmů rychlé vyhledávání a kontrola integrity záznamů v databázích. Hlavním požadavkem na hashovací funkce je rovnoměrné rozložení jejich hodnot, když jsou hodnoty argumentů náhodně vybrány.
Kryptografická hašovací funkce je jakákoli hašovací funkce, která je kryptograficky stabilní, 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ů monitorování integrity dat během jejich přenosu nebo ukládání,
- ověřování zdroje dat.

Libovolná funkce se nazývá hashovací 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 kompresních funkcí y = f(x 1, x 2) dvě proměnné, kde x 1, x 2 A y- binární vektory délky m, n A n podle toho 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ásobek mŽe poslední blok se nějakým speciálním způsobem doplňuje až do úplného dokončení) a poté do výsledných bloků M 1, M 2,.., M N použijte následující postupný postup pro výpočet konvoluce:

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

Zde proti- nějaká konstanta, často nazývaná 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 vzorek data a času).
S tímto přístupem jsou vlastnosti hašovací funkce zcela určeny vlastnostmi jednokrokové kompresní funkce.

Jsou dva důležité typy kryptografické hašovací funkce – klíčové a bezklíčové. Klíčové hašovací funkce se nazývají ověřovací kódy zpráv. Poskytují příležitost bez dodatečné finanční prostředky 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. Umožňují zaručit integritu dat pomocí dalších prostředků (například šifrování). Tyto hashovací funkce lze použít v systémech s důvěřivými i nedůvěřivými uživateli.

O statistických vlastnostech a požadavcích

Jak jsem již řekl, hlavním požadavkem na hashovací funkce je rovnoměrné rozložení jejich hodnot, když jsou hodnoty argumentů náhodně vybrány. Pro kryptografické hašovací funkce 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 úpravy.

První požadavek znamená vysokou složitost výběru zprávy s správná hodnota konvoluce. Za druhé, vysoká složitost výběru pro daná zpráva S známá hodnota shrnout další zprávu se správnou hodnotou srolování.

Požadavky na bezklíčové funkce jsou:
- jednosměrnost,
- odolnost proti nárazům,
- odolnost vůči nalezení druhého předobrazu.

Jednosměrnost odkazuje na vysokou obtížnost nalezení zprávy nastavená hodnota konvoluce. Nutno podotknout, že na momentálně Nepoužívají se žádné osvědčené jednosměrné hashovací funkce.
Odolnost proti kolizi se týká obtížnosti nalezení dvojice zpráv se stejnými hodnotami konvoluce. Obvykle je to objev způsobu, jak kryptoanalytici konstruovat kolize, který slouží jako první signál, že algoritmus zastarává a že je třeba jej rychle nahradit.
Odolnost proti nalezení druhého předobrazu se týká obtížnosti nalezení druhé zprávy se stejnou hodnotou konvoluce pro danou zprávu se známou hodnotou konvoluce.

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 kdysi měl velká popularita, ale první předpoklady pro hacking se objevily na konci devadesátých let a nyní jeho obliba rapidně klesá.
Algoritmus MD6 je z konstrukčního hlediska velmi zajímavý algoritmus. Byl nominován do soutěže SHA-3, ale bohužel jej autoři nestihli uvést do standardu a tento algoritmus není na 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 s vybavením starších modelů.

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.

Nebo Hašovací funkce je funkce, přemění vstup libovolné (obvykle velké) velikosti na data pevná velikost. Hašování(Někdy G Yeshuvanya, angličtina hašování)— transformace pole vstupních dat libovolné délky na výstupní bitový řetězec pevné délky. Takové transformace se také nazývají hashovací funkce nebo konvoluční funkce, a jejich výsledky se nazývají hash, hash kód hash sum, nebo přehled zpráv(Angličtina) Přehled zpráv).

Hašovací funkce se používá zejména v datových strukturách - hašovacích tabulkách a je široce používána v software pro rychlé načtení dat. Hashovací funkce se používají k optimalizaci tabulek a databází identické záznamy identické hodnoty hashovací funkce. Tento přístup k hledání duplikátů je účinný v souborech velká velikost. Příkladem toho je nalezení podobných oblastí v sekvencích DNA. Kryptografická hašovací funkce usnadňuje ověření, že některý vstup odpovídá dané hašovací hodnotě, ale pokud je vstup neznámý, je záměrně obtížné rekonstruovat vstupní hodnotu (nebo ekvivalentní alternativu) se znalostí uložené hašovací hodnoty. To se používá k zajištění integrity přenášených dat a je stavebním kamenem pro HMAC, které poskytují autentizaci zpráv.

Hashovací funkce souvisí (a často se s nimi zaměňují) součty, kontrolní číslice, otisky prstů, randomizační funkce, kódy pro opravu chyb a šifry. Přestože se tyto koncepty do určité míry překrývají, každý má svůj vlastní rozsah a požadavky a je navržen a optimalizován odlišně.

Příběh

Donald Knuth připisuje první systematický nápad hashování zaměstnanci IBM Hansi Peteru Luhnovi, který hash navrhl v lednu 1953.

V roce 1956 Arnold Duma ve své práci Computers and Automation jako první představil koncept hashování, jak jej dnes většina programátorů zná. Duma považovala hašování za řešení „problému se slovníkem“ a také navrhla použít zbytek dělení prvočíslem jako hašovací adresu.

První významné dílo, které bylo spojeno s hledáním v velké soubory, tam byl článek od Wesleyho Petersona v IBM Journal of Research and Development 1957, ve kterém definoval otevřené adresování a také poukázal na degradaci výkonu vzdáleného adresování. O šest let později vyšla práce Wernera Buchholze, která z velké části zkoumala hašovací funkce. Během několika příštích let bylo hašování široce používáno, ale žádná významná práce nebyla publikována.

V roce 1967 bylo hašování v moderním smyslu zmíněno v knize Herberta Hellermana Principles of Digital výpočetní systémy" V roce 1968 publikoval Robert Morris v Komunikace ACM skvělá recenze o hašování. Tato práce je považována za publikaci, která zavádí pojem hašování do vědeckého oběhu a konečně upevňuje pojem „hash“ mezi odborníky.

Na počátku 90. let bylo ekvivalentem termínu „hašování“ díky práci Andreje Ershova slovo „uspořádání“ (ruština) a pro kolize se používal termín „konflikt“ (ruština) (Ershov používal "uspořádání" od roku 1956, stejně jako v ruském vydání knihy Niklause Wirtha "Algorithms and Data Structures" (1989) se tento termín nepoužívá, ale v literatuře se používá termín "). používá se hlavně hašování.

Popis

Hašování se používá k sestavení asociativní pole, hledání duplikátů v řadě datových sad, konstrukce jedinečné identifikátory pro datové sady kontrolní součty za účelem identifikace náhodných nebo záměrných chyb během ukládání nebo přenosu, pro ukládání hesel v bezpečnostních systémech (v tomto případě přístup do paměťové oblasti "paměť, kde jsou hesla umístěna, neumožňuje obnovit heslo samotné ), při generování elektronický podpis(v praxi se často nepodepisuje samotná zpráva, ale její hash obrázek).

V obecný případ Neexistuje žádná individuální korespondence mezi zdrojovými daty a kódem hash kvůli skutečnosti, že počet hodnot hashovací funkce je menší než počet variant hodnot vstupního pole. Existuje mnoho polí s různým obsahem, ale dávají stejné hash kódy – tzv. kolize. Roli hraje pravděpodobnost kolizí důležitou roli při posuzování kvality hašovacích funkcí.

Existuje mnoho hashovacích algoritmů různé vlastnosti(bitová hloubka, výpočetní náročnost, kryptografická síla atd.). Volba té či oné hashovací funkce je dána specifiky řešeného problému. Nejjednoduššími příklady hašovacích funkcí jsou kontrolní součet nebo CRC.

Typy hašovacích funkcí

Dobrá hašovací funkce musí splňovat dvě vlastnosti:

• rychle vypočítat;
• Minimalizujte počet kolizí

Pro jistotu předpokládejme, že počet klíčů a hashovací funkce mají pouze různé hodnoty:

Příkladem „špatné“ hašovací funkce je funkce c, která má deset číslic přirozené číslo odpovídá třem číslicím vybraným ze středu dvacetimístného čtvercového čísla. Zdálo by se, že hodnoty hash kódu by měly být rovnoměrně rozloženy mezi „000“ a „999“, ale pro skutečná data je tato metoda vhodná pouze v případě, že klíče nemají velký počet nul vlevo nebo vpravo.

Existuje však několik dalších jednoduchých a spolehlivých metod, na kterých je mnoho hashovacích funkcí založeno.

Hašovací funkce založené na dělení

První metoda spočívá v tom, že jako hash použijeme zbytek dělení, kde je počet všech možných hashů:

Přitom je zřejmé, že u páru je úsporný režim spárován, s párem. A liché – když liché, což může vést k výraznému posunu dat v souborech. Také byste neměli jako základ používat číselný systém počítače, protože hash bude záviset pouze na několika číslicích čísla umístěného vpravo, což povede k velkému počtu kolizí. V praxi většinou volí ten jednoduchý – ve většině případů je tento výběr vcelku uspokojivý.

Něco jiného je třeba říci o metodě hašování, která je založena na dělení logem modulo dva. V tato metoda musí být také mocninou dvou a binární klíče () jsou ve tvaru polynomů. V tomto případě se hash kód bere jako hodnoty koeficientů polynomu získaného jako zbytek dělení předem vybraným polynomem stupně:

Na udělat správnou volbu Tato metoda zaručuje absenci kolizí mezi téměř identickými klíči.

Multiplikativní hashovací schéma

Druhá metoda je zvolit nějakou celočíselnou konstantu coprime, kde je číslo možné možnosti hodnoty ve formě strojového slova (in Počítače IBM PC). Pak můžeme vzít hashovací funkci formuláře:

V tomto případě na počítači s binární soustava zápis, představuje mocninu dvou a skládá se z nejvýznamnějších bitů pravé poloviny součinu.

Mezi výhody těchto dvou metod stojí za zmínku, že využívají skutečnosti, že skutečné klíče nejsou náhodné. Pokud například klíče představují aritmetickou progresi (řekněme posloupnost jmen „jméno1“, „jméno2“, „jméno3“). Multiplikativní metoda bude mapovat aritmetický průběh na přibližný aritmetický průběh různých hashových hodnot, snižuje počet kolizí ve srovnání s náhodnou situací.

Jednou z variant této metody je Fibonacciho hašování, založené na vlastnostech zlatého řezu. Zde vybraná hodnota je ta, která se nejvíce blíží celému číslu, které je coprime

Hodnota hash řetězců s proměnnou délkou

Výše uvedené metody se také používají v případě, kdy potřebujeme uvažovat klíče skládající se z několika slov nebo klíčů s variabilní délka. Slova můžete například spojit do jednoho pomocí sčítání modulo nebo sčítání modulo 2. Jedním z algoritmů, který pracuje na tomto principu, je Pearsonova hašovací funkce.

Pearsonovo hašování je algoritmus navržený Peterem Pearsonem. Peter Pearson) pro procesory s 8bitovými registry, jejichž úkolem je rychle vypočítat hash kód pro řetězec libovolné délky. Funkce přijímá jako vstup slovo sestávající ze znaků, každý o velikosti 1 bajtu, a vrací hodnotu v rozsahu od 0 do 255. Hodnota hash kódu závisí na každém znaku vstupního slova.

Algoritmus lze popsat následujícím pseudokódem, který bere řetězec jako vstup a používá permutační tabulku

h:=0 Pro každého C v W smyčka index:=h xor ch:=T Konec smyčky Návrat h

Mezi výhody algoritmu je třeba poznamenat:

• snadnost výpočtu;
• neexistují žádná vstupní data, u kterých je pravděpodobnost kolize nejvyšší;
• možnost modifikace na ideální hašovací funkci.

Jak alternativní způsob hash klíče sestávající ze symbolů () mohou nabízet výpočty

Použití hashovacích funkcí

Hashovací funkce jsou široce používány v kryptografii, stejně jako v mnoha datových strukturách – hashovacích tabulkách, Bloomových filtrech a kartézských stromech.

Kryptografické hašovací funkce

Mezi mnoha existujícími hashovacími funkcemi je obvyklé rozlišovat kryptograficky silné, používané v kryptografii, protože jsou superponované dodatečné požadavky. Aby byla hašovací funkce považována za kryptograficky silnou, musí splňovat tři základní požadavky, které jsou základem pro většinu použití hašovacích funkcí v kryptografii:

• Nevratnost: pro danou hash hodnotu m Musí být výpočetně nemožné najít datový blok, pro který.
• Udržitelnost srážky prvního druhu: pro danou zprávu M musí být výpočetně nemožné najít jinou zpráva N, pro které.
• Udržitelnost Na kolize druhý druh: Mělo by být výpočetně nemožné najít dvojice zpráv, které mají stejný hash.

Tyto požadavky na sobě závisí:

• Inverzní funkce je nestabilní vůči srážkám prvního a druhého druhu.
• Funkce, která je nestabilní vůči srážkám prvního druhu, nestabilní vůči srážkám druhého druhu; obráceně to není pravda.

Nutno podotknout, že nebyla prokázána existence nevratných hašovacích funkcí, pro které je výpočet jakéhokoli inverzního obrazu dané hašovací hodnoty teoreticky nemožný. Obvykle je nalezení převrácené hodnoty pouze výpočetně obtížný úkol.

Narozeninový útok umožňuje najít kolize hashovací funkce s délkou hodnot n bitů v průměru na přibližně výpočet hashovací funkce. Proto n — Bitová hašovací funkce je považována za kryptoměnu, pokud se její výpočetní složitost při hledání kolizí blíží.

U kryptografických hashovacích funkcí je také důležité, že při sebemenší změně argumentu se hodnota funkce velmi změní (lavinový efekt). Zejména hodnota hash nesmí unikat informace, a to ani o jednotlivých bitech argumentu. Tento požadavek je klíčem ke kryptografické síle hashovacích algoritmů, které hashují heslo uživatele za účelem získání klíče.

Hašování se často používá v algoritmech digitálního podpisu, kde není zašifrována samotná zpráva, ale její hash, což zkracuje dobu výpočtu a také zvyšuje šifrovací sílu. Ve většině případů se také místo hesel ukládají hodnoty jejich hash kódů.

Geometrické hašování

Geometrické hašování geometrické hašování)- široce používané v počítačová grafika a metoda výpočetní geometrie pro řešení problémů v rovině nebo v trojrozměrném prostoru, například k nalezení nejbližších dvojic v sadě bodů nebo k vyhledávání identické obrázky. Hašovací funkce v této metodě obvykle přijímá jako vstup metrický prostor a rozdělí ji, čímž vznikne mřížka buněk. Stůl v v tomto případě je pole se dvěma nebo více indexy a nazývá se soubor mřížky. Soubor mřížky). Geometrické hašování se také používá v telekomunikacích při práci s vícerozměrnými signály.

Zrychlete načítání dat

Hashovací tabulka je datová struktura, která umožňuje ukládat dvojice formuláře (klíč, hash kód) a podporuje vyhledávací operace, vkládání a mazání prvků. Hashovací tabulky mají za úkol urychlit vyhledávání, např. u záznamů v textových polích v databázi lze vypočítat jejich hash kód a data umístit do sekce odpovídající tomuto hash kódu. Při hledání dat si pak budete muset nejdříve spočítat hash textu a hned budete vědět, ve které sekci je máte hledat, tedy hledat ne v celé databázi, ale pouze v jednu z jeho sekcí (to velmi urychluje vyhledávání).

Domácím analogem hašování může být v tomto případě umístění slov ve slovníku v abecedním pořadí. První písmeno slova je jeho hash kód a při vyhledávání neprohlížíme celý slovník, ale pouze požadované písmeno.

Například můžeme zadat 128bitovou hašovací funkci s románem Lva Tolstého v hexadecimálním tvaru nebo číslem 1. Výsledkem je, že v obou případech obdržíme různé sady pseudonáhodných hexadecimálních číslic ve tvaru: „c4ca4238a0b923820dcc509a6f75849b“ .

Při změně zdrojový text i o jednu číslici se výsledek hašovací funkce úplně změní.

Tato vlastnost hashovacích funkcí umožňuje jejich použití v následujících případech:

• při konstrukci asociativních polí;
• při hledání duplikátů v řadě souborů dat;
• při vytváření jedinečných identifikátorů pro datové sady;
• při výpočtu kontrolních součtů z dat (signálů) pro následnou detekci chyb v nich (náhodně nebo úmyslně zanesených), ke kterým dochází při ukládání a/nebo přenosu dat;
• při ukládání hesel v ochranných systémech ve formě hash kódu (pro obnovení hesla pomocí hash kódu je nutná funkce, která je inverzní k použité hash funkci);
• při vývoji elektronického podpisu (v praxi se často nepodepisuje samotná zpráva, ale její „hash image“);
• atd.

Typy hašovacích funkcí

"Dobrá" hashovací funkce musí splňovat dvě vlastnosti:

• rychlý výpočet;
• minimální počet „kolizí“.

Představme si následující zápis:

∀ k ∈ (0 ; K): h (k)< M {\displaystyle \forall k\in (0;\,K):h(k).

Příkladem „špatné“ hashovací funkce je funkce s M = 1000 (\displaystyle M=1000), což je desetimístné přirozené číslo K (\displaystyle K) srovnává třičíslice vybrané ze středu dvacetimístného čtverce čísla K (\displaystyle K). Zdálo by se, že hodnoty „hash code“ by měly být rovnoměrně distribuováno mezi " 000 "A" 999 ", ale pro" nemovitý"údaje to platí pouze tehdy, když" klíče" nemají "velký" počet nul vlevo nebo vpravo.

Podívejme se na několik jednoduchých a spolehlivých implementací hašovacích funkcí.

"Hashovací funkce" založené na dělení

1. „Hash kód“ jako zbytek dělení počtem všech možných „hash“

Hašovací funkce může vypočítat "hash" jako zbytek dělení vstupních dat M (\displaystyle M):

h (k) = k mod M (\displaystyle h(k)=k\mod M),

Kde M (\displaystyle M)- počet všech možných „hashe“ (výstupních dat).

Navíc je zřejmé, že pro dokonce M (\displaystyle M) hodnota funkce bude i když sudá k (\displaystyle k) a liché - když liché k (\displaystyle k). Také by se nemělo používat jako M (\displaystyle M) základ číselného systému počítače, protože "hash kód" bude záviset pouze na několikčíslice čísla k (\displaystyle k), umístěný vpravo, což povede k velkému počtu kolizí. V praxi většinou volí jednoduché M (\displaystyle M); ve většině případů je tato volba docela uspokojivá.

2. „Hash kód“ jako množina koeficientů výsledného polynomu

Hašovací funkce může provádět modulo dvě dělení vstupních dat polynomem. V této metodě M (\displaystyle M) musí být mocnina dvou a binární klíče ( K = k n − 1 k n − 2 .. . k 0 (\displaystyle K=k_(n-1)k_(n-2)...k_(0)) ) jsou zastoupeny ve tvaru polynomy K (\displaystyle K), hodnoty koeficientů jsou brány jako „hash kód“ polynom, získaný jako zbytek dělení vstupních dat na předem vybraný polynom:

P (\displaystyle P) stupně

m (\displaystyle m) K (x) mod P (x) = h m − 1 x m − 1 + ⋯ + h 1 x + h 0 (\displaystyle K(x)\mod P(x)=h_(m-1)x^(m- 1)+\tečky +h_(1)x+h_(0)) h (x) = h m - 1 .

.

. h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0)) Se správnou volbou P(x) (\displaystyle P(x)).

je zaručena absence kolizí mezi téměř identickými klíči. "Hashovací funkce" založené na násobení Označme symbolem "Hashovací funkce" založené na násobení w (\displaystyle w) h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0)) počet čísel, která mohou být reprezentována strojovým slovem. Například pro 32bitové počítače kompatibilní s IBM PC

w = 2 32 (\displaystyle w=2^(32))

Zvolme nějakou konstantu M (\displaystyle M) A (\displaystyle A) aby byl coprime s . Pak by hashovací funkce pomocí násobení mohla vypadat takto:.

h (K) = [ M ⌊ A w ∗ K ⌋ ] (\displaystyle h(K)=\left)

V tomto případě na počítači s binární číselnou soustavou "Hashovací funkce" založené na násobení je mocnina dvou a h (K) (\displaystyle h(K)) se bude skládat z nejvýznamnějších bitů pravé poloviny produktu h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0)) A ∗ K (\displaystyle A*K) Mezi výhody hašovacích funkcí založených na dělení a násobení stojí za zmínku přínosné využití nenáhodnosti reálných klíčů. Pokud jsou například klíče aritmetický postup (například posloupnost jmen "Jméno 1", "Jméno 2", "Jméno 3"), hashovací funkce, která používá násobení, mapuje aritmetický postup na přibližně aritmetický postup. různých hodnot hash, což sníží počet kolizí ve srovnání s náhodnou situací. Jednou hašovací funkcí, která používá násobení, je hašovací funkce, která používá Fibonacciho hašování. Fibonacciho hašování je založeno na vlastnostech zlatého řezu. Jako konstanta

zde je celé číslo nejbližší

φ − 1 ∗ w (\displaystyle \varphi ^(-1)*w)

a spojit se s h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0)) nebo operace „exclusive or“. Jedním z algoritmů, který pracuje na tomto principu, je Pearsonova hašovací funkce.

Univerzální hashování

Metody řešení kolizí

Kolize (někdy konflikt nebo kolize) je případ, kdy jedna hashovací funkce pro různé vstupní bloky vrací stejné hashovací kódy.

Metody řešení kolizí v hašovacích tabulkách

Většina raných prací popisujících hašování byla věnována metodám pro řešení kolizí v hašovacích tabulkách. Tehdy se k vyhledávání textu ve velkých souborech používaly hashovací funkce. Existují dva hlavní způsoby řešení kolizí v hašovacích tabulkách:

1. řetězová metoda (metoda přímého spojování);
2. otevřená metoda adresování.

Při použití metody řetězení jsou v hashovací tabulce uloženy dvojice „propojený seznam klíčů“ a „hash kód“. Pro každý klíč vypočítá hašovací funkce hašovací kód; pokud byl hash kód získán dříve (pro jiný klíč), klíč je přidán do existujícího seznamu klíčů spárovaných s hash kódem; jinak se vytvoří nový pár „seznam klíčů“ - „hash kód“ a klíč se přidá do vytvořeného seznamu. Obecně, pokud existuje N (\displaystyle N) klíče a M (\displaystyle M) seznamů, bude průměrná velikost hash tabulky N M (\displaystyle (\frac (N)(M))). V tomto případě se při prohledávání tabulky ve srovnání s případem, kdy je vyhledávání prováděno postupně, průměrné množství práce sníží přibližně o M (\displaystyle M) jednou.

Při použití metody otevřeného adresování ukládá hashovací tabulka páry klíč-hash kód. Pro každý klíč vypočítá hašovací funkce hašovací kód; Pár „klíč“ - „hash kód“ je uložen v tabulce. V tomto případě se při prohledávání tabulky ve srovnání s případem, kdy se používají propojené seznamy, nepoužívají odkazy, provádí se sekvenční vyhledávání párů „klíč“ - „hash kód“, vyhledávání se zastaví po zadání požadovaného klíče. nalezeno. Sekvence, ve které jsou skenovány buňky tabulky, se nazývá sekvence sondy.

Kryptografická sůl

Použití hashovacích funkcí

Hashovací funkce jsou široce používány v kryptografii.

Hash se používá jako klíč v mnoha datových strukturách – hašovacích tabulkách, Bloomových filtrech a kartézských stromech.

Kryptografické hašovací funkce

Mezi mnoha existujícími hashovacími funkcemi je obvyklé rozlišovat kryptograficky silné hashovací funkce používané v kryptografii, protože jsou na ně kladeny další požadavky. Aby byla hašovací funkce H (\displaystyle H) považován za kryptograficky silný, musí splňovat tři základní požadavky, na kterých je založena většina použití hašovacích funkcí v kryptografii:

Tyto požadavky nejsou nezávislé.

Domnívám se, že mnoho lidí ví, že od roku 2007 pořádá americký Národní institut pro standardy a technologie (NIST) soutěž o vývoj hašovacího algoritmu, který nahradí SHA-1, a rodiny algoritmů SHA-2. Toto téma však bylo z nějakého důvodu na webu opomíjeno. To je vlastně to, co mě k vám přivedlo. Upozorňuji na sérii článků věnovaných hašovacím algoritmům. V této sérii 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í, a určitě je otestujeme. Pokud je to možné, budou zváženy také ruské hašovací standardy.

O mně

Student katedry informační bezpečnosti.

O hašování

V dnešní době se prakticky žádná kryptografická aplikace neobejde 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 určitého bitového vzoru s pevnou délkou nazývaného konvoluce. Hashovací funkce mají různé aplikace při provádění statistických experimentů, testování logických zařízení a 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 rovnoměrné rozložení jejich hodnot, když jsou hodnoty argumentů náhodně vybrány.
Kryptografická hašovací funkce je jakákoli hašovací funkce, která je kryptograficky stabilní, 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ů monitorování integrity dat během jejich přenosu nebo ukládání,
- ověřování zdroje dat.

Libovolná funkce se nazývá hashovací 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 kompresních funkcí y = f(x 1, x 2) dvě proměnné, kde x 1, x 2 A y- binární vektory délky m, n A n podle toho 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ásobek m pak se nějakým zvláštním způsobem doplňuje poslední blok, dokud není kompletní) a poté k výsledným blokům M 1, M 2,.., M N použijte následující postupný postup pro výpočet konvoluce:

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

Zde proti- nějaká konstanta, často nazývaná 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 vzorek data a času).
S tímto přístupem jsou vlastnosti hašovací funkce zcela určeny vlastnostmi jednokrokové kompresní funkce.

Existují dva důležité typy kryptografických hašovacích funkcí – klíčové 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 s uživateli, kteří si navzájem důvěřují.
Bezklíčové hašovací funkce se nazývají kódy detekce chyb. Umožňují zaručit integritu dat pomocí dalších prostředků (například šifrování). Tyto hashovací funkce lze použít v systémech s důvěřivými i nedůvěřivými uživateli.

O statistických vlastnostech a požadavcích

Jak jsem již řekl, hlavním požadavkem na hashovací funkce je rovnoměrné rozložení jejich hodnot, když jsou hodnoty argumentů náhodně vybrány. 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.

Klíčové hashovací funkce mají následující požadavky:
- nemožnost výroby,
- nemožnost úpravy.

První požadavek znamená, že je velmi obtížné najít zprávu se správnou hodnotou sbalení. Druhým je vysoká složitost výběru pro danou zprávu se známou hodnotou konvoluce jiné zprávy se správnou hodnotou konvoluce.

Požadavky na bezklíčové funkce jsou:
- jednosměrnost,
- odolnost proti nárazům,
- odolnost vůči nalezení druhého předobrazu.

Jednosměrnost označuje vysokou obtížnost nalezení zprávy na základě dané konvoluční hodnoty. Je třeba poznamenat, že v současné době nejsou používány žádné hashovací funkce s osvědčenou jednosměrností.
Odolnost proti kolizi se týká obtížnosti nalezení dvojice zpráv se stejnými hodnotami konvoluce. Obvykle je to objev způsobu, jak kryptoanalytici konstruovat kolize, který slouží jako první signál, že algoritmus zastarává a že je třeba jej rychle nahradit.
Odolnost proti nalezení druhého předobrazu se týká obtížnosti nalezení druhé zprávy se stejnou hodnotou konvoluce pro danou zprávu se známou hodnotou konvoluce.

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 konstrukčního hlediska velmi zajímavý algoritmus. Byl nominován do soutěže SHA-3, ale bohužel jej autoři nestihli uvést do standardu a tento algoritmus není na 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 s vybavením starších modelů.

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.

Co je to hash? Hašovací funkce je matematická transformace informace do krátkého, definovaného řetězce.

Proč je to nutné? K ověření integrity se často používá analýza pomocí hašovacích funkcí důležité soubory operační systém, důležité programy, důležité údaje. Kontrolu lze provádět podle potřeby nebo pravidelně.

Jak se to dělá? Nejprve určete integritu souborů, které je třeba monitorovat. Pro každý soubor je jeho hash hodnota vypočtena pomocí speciální algoritmus uložit výsledek. Po požadované 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 libovolnou konverzi dat na pevnou délku;
• musí mít otevřený algoritmus aby bylo možné prozkoumat jeho kryptografickou sílu;
• musí být jednostranné, to znamená, že by nemělo být matematická možnost na základě výsledku určit počáteční údaje;
• musí „odolat“ kolizím, to znamená, že nesmí 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 – kód cyklické redundance nebo kontrolní součet. Algoritmus je velmi jednoduchý, to ano velký počet variace v závislosti na požadované délce výstupu. Ne 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čty hašovacích funkcí. Velikost hashe je 256 bitů.

Kdy může správce systému použít tyto algoritmy?Často při stahování jakéhokoli obsahu, jako jsou programy z webových stránek výrobce, hudba, filmy nebo jiné informace, hodnota kontrolní součty, vypočítané pomocí specifické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í je jich velké množství podobné utility placené i bezplatné použití. Osobně se mi líbil HashTab. Za prvé, během instalace je nástroj zabudován 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í 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é sledování výchozího stavu softwarového balíku.
• Porovnání verzí softwarových balíků.
• Fixace a kontrola adresářů.
• Kontrola změn v zadané soubory(katalogy).
• Generování přehledů v TXT formáty, HTML, SV.
• Výrobek má certifikát FSTEC dle NDV 3 č. 913 do 1.6.2013

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

V současné době mnoho aplikací e-commerce vám umožní uložit tajný klíč uživatel v uzavřené oblasti tokenů (ruToken, eToken) bez technická proveditelnost dostat to odtamtud. Samotný token má velmi omezenou paměťovou oblast, měřenou v kilobajtech. Chcete-li podepsat dokument, neexistuje způsob, jak přenést dokument do samotného tokenu, ale je velmi jednoduché přenést hash dokumentu do tokenu a jako výsledek získat elektronický digitální podpis.