Kryptografická hašovací funkce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. května 2019; kontroly vyžadují 58 úprav .

Kryptografické hašovací funkce jsou odlišnou třídou hašovacích funkcí , které mají určité vlastnosti, díky nimž jsou vhodné pro použití v kryptografii .

Konstrukční principy

Iterativní sekvenční obvod

V obecném případě je konstrukce hashovací funkce založena na iterativním sekvenčním schématu. Jádrem algoritmu je kompresní funkce – převádějící k vstupu na n výstupních bitů, kde n je délka hashovací funkce a k je libovolné číslo větší než n . V tomto případě musí funkce komprese splňovat všechny podmínky šifrovací síly .

Vstupní tok je rozdělen do bloků ( k − n ) bitů. Algoritmus používá dočasnou proměnnou velikosti n bitů, jejíž počáteční hodnota je nějaké dobře známé číslo. Každý další blok dat je kombinován s výstupní hodnotou funkce zmenšování v předchozí iteraci. Hodnota hashovací funkce je výstupní n bitů poslední iterace. Každý bit výstupní hodnoty hashovací funkce závisí na celém vstupním datovém toku a počáteční hodnotě. Tím je dosaženo lavinového efektu .

Při návrhu hašovacích funkcí na základě iterativního schématu nastává problém s velikostí vstupního datového toku. Velikost vstupního datového toku musí být násobkem ( k − n ) . Zpravidla se před spuštěním algoritmu data rozšíří nějakým předem známým způsobem.

Kromě jednoprůchodových algoritmů existují víceprůchodové algoritmy, ve kterých je lavinový efekt dále zesílen. V tomto případě se data nejprve opakují a poté rozšíří na požadovanou velikost.

Funkce kontrakce založená na symetrickém blokovém algoritmu

Algoritmus symetrické blokové šifry lze použít jako kompresní funkci . Pro zajištění větší bezpečnosti můžete jako klíč použít blok dat určený k hašování v této iteraci a jako vstup výsledek předchozí kompresní funkce. Výsledkem poslední iterace pak bude výstup algoritmu. V takovém případě je zabezpečení hašovací funkce založeno na zabezpečení použitého algoritmu.

Obvykle se při vytváření hashovací funkce používá složitější systém. Zobecněné schéma symetrického blokového šifrovacího algoritmu je znázorněno na Obr. 2.

Dostaneme tedy 64 možností pro konstrukci kontrakční funkce. Většina z nich je buď triviální, nebo nebezpečná. Níže jsou uvedena čtyři nejbezpečnější schémata pro všechny typy útoků.

Hlavní nevýhodou hashovacích funkcí navržených na základě blokových algoritmů je jejich nízká rychlost. Potřebné kryptografické síly lze dosáhnout i menším počtem operací na vstupních datech. Existují rychlejší hashovací algoritmy, které jste navrhli sami, od začátku, na základě požadavků na šifrovací sílu. Nejběžnější z nich jsou MD5 , SHA-1 , SHA-2 .

Požadavky

Požadavky na kryptografické hašovací funkce jsou:

1. Odolnost při vyhledávání prvního předobrazu : Vzhledem k hash by mělo být obtížné najít takovou zprávu , že tato vlastnost souvisí s pojmem jednosměrná funkce . Funkce, které tuto vlastnost postrádají, jsou zranitelné vůči prvním útokům preimage . $h$ $m$ $h=hash(m)$

2. Odolnost vůči hledání druhého předobrazu : vzhledem ke zprávě by mělo být obtížné najít jinou zprávu (ne rovnou ) tak, aby . Tato vlastnost je někdy označována jako slabá odolnost proti kolizi. Funkce, které tuto vlastnost postrádají, jsou zranitelné vůči druhým útokům vyhledávání preimage. $m_1$ $m_2$ $m_1$ $hash(m_{1})=hash(m_{2})$

3. Odolnost proti srážkám

Kolize hashovací funkce je dvojice hodnot a ′, ′ pro které . Protože počet možných otevřených textů je větší než počet možných hodnot konvoluce, pak pro nějakou konvoluci existuje mnoho předobrazů, a proto nutně existují kolize pro hašovací funkce. Nechť je například délka předobrazu hash 6 bitů, délka konvoluce je 4 bity. Potom je počet různých skladů a počet hashových předobrazů je , tedy 4krát více, což znamená, že alespoň jeden ze všech skladů odpovídá 4 předobrazem. $m$ $m$ $m\neq m$ $H(m)=H(m')$ $2^{4}=16$ $2^6=64$

Odolnost hašovací funkce vůči kolizím znamená, že neexistuje žádný účinný polynomiální algoritmus pro nalezení kolizí.

Tyto vlastnosti nejsou nezávislé:

Invertibilní funkce je nestabilní vůči obnově druhého předobrazu a kolizím.
Funkce, která není odolná vůči obnovení druhého předobrazu, není odolná vůči kolizím; obráceně to není pravda.
Funkce je odolná proti kolizi, odolná proti druhému předobrazu.
Hašovací funkce odolná proti kolizi není nutně jednosměrná.

Pro kryptografii je důležité, aby se hodnoty hash hodně změnily při sebemenší změně argumentu ( lavinový efekt ). Hodnota hash by neměla unikat informace ani o jednotlivých bitech argumentu.

Při vývoji moderního ruského standardu GOST R 34.11-2012 (Stribog) byly pro kryptografické hašovací funkce formulovány následující požadavky:

Obtížnost při výpočtu předobrazu: pokud je známá hodnota funkce, pak by mělo být obtížné najít takovou zprávu, jejíž hashovací funkce je rovna známé;
Zabezpečení výpočtu druhého předobrazu: nechť existuje jedna hodnota a hash kód této hodnoty je znám. Pak by pro útočníka mělo být obtížné najít jinou takovou hodnotu, aby se její hašovací funkce shodovala s hašovací funkcí první hodnoty;
Obtížnost při hledání kolizí: mělo by být obtížné najít dvě takové zprávy, které si nejsou stejné, ale mají stejné hashovací kódy;
Odolnost proti prodlužování preimage: pokud útočník nezná zprávu, ale zná z ní její délku a hash kód, pak by pro něj mělo být obtížné vyzvednout zprávu, která po přidání k originálu dá nějakou známou hashovací funkci . Jinými slovy, útočníkovi by nemělo být možné něco změnit přidáním do zprávy a zároveň se seznámit s výstupem. Dá se to vyjádřit i jinak: hashovací funkce nemusí být dobře „vycpaná“.

4. Pseudonáhodnost : Mělo by být obtížné odlišit generátor pseudonáhodných čísel založený na hash od generátoru náhodných čísel, například projde obvyklými testy náhodnosti .

Prokazatelně bezpečné hashovací funkce

Bezpečnost hašovací funkce může být zajištěna složitostí některého matematického problému, pokud existuje důkaz, že útoky směřující k porušení požadavků na ni jsou stejně obtížné jako řešení tohoto problému. [jeden]

Kryptografická hašovací funkce je prokazatelně odolná proti kolizi, pokud problém hledání kolizí může být zprostředkován v polynomiálním čase z problému , který je v polynomiálním čase považován za neřešitelný . Jinými slovy, pokud by algoritmus umožnil vyřešit problém hledání kolizí v polynomiálním čase, pokud existuje redukční algoritmus , který také funguje v polynomiálním čase, pak by tento algoritmus umožnil vyřešit problém v polynomiálním čase, což je v rozporu s jeho složitostí. , což znamená , že problém hledání kolizí není jednodušší než úkol . $P$ $A$ $R$ $A$ $P$ $P$

Obdobně je definováno prokazatelné zabezpečení proti hledání prvního a druhého předobrazu.

Odolnost při hledání druhého předobrazu vyplývá z prokázané odolnosti proti srážkám, proto se v praxi někdy teoreticky prokazuje pouze odolnost proti nalezení prvního předobrazu a odolnost proti srážkám. [2]

Některé problémy, které mají být neřešitelné v polynomiálním čase, které lze použít ke konstrukci takových funkcí:

Nevýhody přístupu založeného na důkazech

Za přítomnosti teoretických záruk složitosti má přístup založený na důkazech také významné nevýhody:

Současné prokazatelně bezpečné hashovací algoritmy jsou příliš výpočetně složité na to, aby je bylo možné použít v praxi. Oproti běžným hashovacím funkcím jsou dost pomalé.
Vytváření prokazatelně bezpečných hashovacích funkcí je časově mnohem náročnější než klasické přístupy.
Samotný bezpečnostní důkaz je často založen na problému, který má požadovanou průměrnou nebo nejhorší složitost. Složitost nejhoršího případu nejčastěji popisuje patologické situace spíše než ty typické pro daný úkol. Dokonce i redukce na problém se složitostí v průměru poskytuje omezené zabezpečení, protože lze nalézt algoritmus, který problém snadno vyřeší pro určitou podmnožinu problémových dat. Takže se například ukázalo, že pro dva ze tří parametrů navržených v původním článku pro hashovací funkci Fast Syndrome-Based existují optimálnější útoky, než jaké navrhli tvůrci k prokázání bezpečnosti. [3]

SWIFFT je příkladem hashovací funkce, která poněkud obchází popsaný bezpečnostní problém. Lze ukázat, že pro každý algoritmus, který prolomí SWIFFT s pravděpodobností v čase, existuje algoritmus, který řeší určitý matematický problém v nejhorším případě v čase v závislosti na a . [čtyři] $P$ $T$ $T'$ $P$ $T$

Příklady prokazatelně bezpečných hashovacích funkcí

VSH - Very Smooth Hash function - je prokazatelně bezpečná funkce odolná proti kolizi, která spoléhá na obtížnost hledání netriviálních odmocnin modulo složeného čísla n (což je stejně obtížné jako faktoring n ).
MuHASH
ECOH - Elliptic curve only hash - hašovací funkce založená na myšlence eliptických křivek , problému součtu podmnožin a polynomiální sumace. Bezpečnostní důkaz se opíral o předpoklad NP-úplnosti základního matematického problému, ale byla nalezena zranitelnost pro Wagnerův zobecněný „narozeninový“ útok související s hledáním druhého předobrazu. [5]
FSB – Fast Syndrome-Based hash function – Lze ukázat, že prolomení FSB je přinejmenším stejně obtížné jako vyřešení NP-úplného problému známého jako dekódování pravidelného syndromu. [6]
SWIFFT - SWIFFT je založen na FFT a je prokazatelně bezpečný za dosti slabého předpokladu o nejhorším případě obtížnosti nalezení krátkých vektorů v cyklické/ideální mřížce. [7]
Chaum, van Heijst, Pfitzmann hašovací funkce - funkce, ve které je hledání kolizí stejně pracné jako při hledání diskrétního logaritmu v konečné grupě . $F_{2p+1}$
Hašovací funkce založené na batohu jsou skupinou hašovacích funkcí založených na problému batohu .
Existuje obecný přístup k budování prokazatelně bezpečných hashovacích algoritmů založených na jakémkoli vhodném sigma protokolu . Tímto způsobem lze získat rychlejší verzi VSH (nazývanou VSH*).

Ideální kryptografická hašovací funkce

Ideální kryptografická hašovací funkce je kryptografická hašovací funkce, která má pět základních vlastností:

Determinismus . Se stejnými vstupními daty bude výsledek hashovací funkce stejný (stejná zpráva vždy vede ke stejnému hashu);
Vysokorychlostní výpočet hodnoty hash pro danou zprávu;
Neschopnost vygenerovat zprávu z její hash hodnoty, s výjimkou pokusu o vytvoření všech možných zpráv;
Lavinový efekt. Malá změna ve zprávách by měla změnit hodnoty hash tak široce, že nové hodnoty hash neodpovídají starým hodnotám hash;
Neschopnost najít dvě různé zprávy se stejnou hash hodnotou.

Ideální kryptografická hašovací funkce, která má délku n (tj. výstup je n bitů), tedy musí vyžadovat alespoň operace pro výpočet předobrazu. $2^{n}$

Útočník bude hledat předobraz ideální hašovací funkce následujícím způsobem: má číslo h a potřebuje najít m takové, že H(m) = h. Pokud se jedná o ideální hashovací funkci, pak může útočník pouze projít všemi možnými M a zkontrolovat, čemu se hashovací funkce z této zprávy rovná. Pokud je m zcela iterováno, výsledkem výpočtu je ve skutečnosti náhodné číslo. Pokud číslo h leží v rozsahu od 0 do , pak útočník v průměru stráví iterace hledáním požadovaného h. Výpočet předobrazu tedy zabere polovinu iterací než v ideálním případě. $2^{n}$ $2^{{n-1}}$

Výpočet druhého předobrazu zůstává . Při hledání kolizí bude skóre dávat , a to není úplně přesný výsledek. Toto hodnocení vychází z hodnocení takzvaného „ narozeninového paradoxu “. $2^{n}$ $2^{n}$

Pokud chce útočník napsat program na hledání kolizí, bylo by pro něj optimální nejprve si pořídit slovník kolizí. Podle toho pak vypočítá hašovací funkci z další zprávy a zkontroluje, zda tato hašovací funkce patří do další zprávy nebo ne. Pokud ano, pak je kolize nalezena a poté lze ve slovníku nalézt původní zprávu s daným hash kódem. Pokud ne, doplní slovník. V praxi tato metoda není implementována, protože by na takový slovník nebyl dostatek paměti.

Narozeninový útok

Narozeninový útok je název používaný v kryptoanalýze pro metodu detekce kolizí hašovací funkce založenou na narozeninovém paradoxu. Podstatou paradoxu je, že ve skupině 23 a více lidí pravděpodobnost shody narozenin (dne a měsíce) u minimálně dvou osob přesahuje 50 %. Pokud je například ve třídě 23 nebo více studentů, pak je pravděpodobnější, že narozeniny některého ze spolužáků připadnou na stejný den, než že každý bude mít své jedinečné narozeniny.

Lavinový efekt

Podívejme se na tento efekt a jeho roli na příkladu blockchainového hashovacího procesu. Tato vlastnost znamená, že pokud provedeme malé změny ve vstupním řetězci, pak se hashe (tedy výstup kryptografické funkce) budou od sebe drasticky lišit. Pojďme si tuto vlastnost ověřit na jednoduchém příkladu. Vezměme si například výsledek hashovací funkce z rodiny MD – MD5. Na vstupu dodáme hodnoty, které se budou lišit pouze v případě prvních znaků - řetězce jsou téměř totožné. Jejich hash (výsledek hashovací funkce) se však liší.

Příklad toho, jak funguje šifrovací algoritmus MD5
Vstup	Výstup
bitcoin	0xCD5B1E4947E304476C788CD474FB579A
bitcoin	0xD023EC040F79F1A9B2AC960B43785089

"Vysoká entropie"

Dobré hašovací funkce mají vlastnost "Vysoká entropie ". To znamená, že hashe datových polí by měly být během procesu hashování v systému maximálně rozmístěny, to znamená, že by měly mít vysokou entropii ve smyslu informace. Jak víte, entropie ve smyslu informace je mírou nejistoty určitého systému, zejména nepředvídatelnosti vzhledu symbolu.

Vezměme si například rovnici , kde je zřetězení řetězce a řetězce a je kryptografická hašovací funkce. Pokud má hodnota vysoký index entropie, pak bude téměř nemožné najít hodnotu, která by rovnici vyhovovala. $OUTPUT=H(K|INPUT)$ $K|INPUT$ $K$ $INPUT$ $H$ $K$ $INPUT$

Pojmem „Vysoká entropie“ se v kontextu hašovacích funkcí rozumí stav, kdy je hodnota vybrána z tak široké škály možných možností, že pokusy o uhodnutí náhodným výběrem nemají šanci na úspěch. Například číslo, které je mezi 1 a 10, má nízkou entropii, zatímco číslo, které je mezi 1 a , má naopak vysokou entropii. $2^{256}$

Rodina hashovacích funkcí MD a SHA

K dnešnímu dni je naprostá většina aplikací hashovacích funkcí „převzata“ algoritmy MD5 , SHA-1 , SHA-256 a v Rusku také GOST R 34.11-2012 (Stribog) . Samozřejmě existuje mnoho dalších algoritmů, které jsou méně známé nebo běžné pouze v úzkých komunitách (například RIPEMD , TIGER , Panama atd.), nicméně tyto algoritmy nejsou tak běžné. Níže je uvedena analýza hašovacích funkcí MD4 , což byl předchůdce MD5, a také hašovací funkce SHA.

Typ	Popis
MD4	Nejrychlejší, optimalizovaný pro 32bitové stroje z rodiny funkcí MD. Hashovací funkce vyvinutá profesorem University of Massachusetts Ronaldem Rivestem v roce 1990 a poprvé popsaná v RFC 1186. Obsahuje tři smyčky po 16 krocích. V roce 1993 byl popsán algoritmus cracking MD4, takže dnes se tato funkce nedoporučuje pro použití s reálnými aplikacemi.
MD5	Nejběžnější z rodiny funkcí MD. Podobné jako MD4, ale díky vylepšením zabezpečení je o 33 % pomalejší než MD4. Obsahuje čtyři cykly po 16 krocích. Poskytuje kontrolu integrity dat. První úspěšné pokusy o prolomení této hašovací funkce se datují do roku 1993: výzkumníci Bert den Boer a Anton Bossilaris ukázali, že v algoritmu jsou možné pseudokolize. V roce 1996 Hans Dobbertin ukázal možnost kolizí a teoreticky popsal hackerský algoritmus. 24. srpna 2004 čtyři nezávislí výzkumníci - Wang Xiaoyun, Feng Dengguo, Lai Xuejia a Yu Hongbo - objevili zranitelnost algoritmu, která umožňuje najít kolize pomocí analytické metody ve více či méně přijatelném čase. V roce 2005 Vlastimil Klíma publikoval algoritmus pro detekci kolizí během několika hodin. 18. března 2006 publikoval výzkumník algoritmus, který najde kolize za jednu minutu, což bylo později nazváno „tunelování“. Ode dneška se MD5 nedoporučuje používat v aplikacích reálného světa.
SHA-1 (Zajistit hash Algoritmus 1)	V roce 1993 NSA spolupracovala s NIST na vývoji Secure Hash Algorithm (nyní známého jako SHA-0) (zveřejněného ve FIPS PUB 180) pro bezpečný hashovací standard. NSA však tuto verzi brzy stáhla s odvoláním na chybu, kterou objevili a která nebyla nikdy zveřejněna. A nahradil ji revidovanou verzí publikovanou v roce 1995 ve FIPS PUB 180-1. Tato verze je považována za to, co se nazývá SHA-1 . Později, na konferenci CRYPTO v roce 1998, dva francouzští vědci představili útok na algoritmus SHA-0, který nefungoval na algoritmu SHA-1. To mohla být chyba objevená NSA. SHA-1 vytváří 160bitovou hodnotu, nazývanou také výtah zpráv. Obsahuje čtyři stupně. MD5 i SHA-1 jsou v podstatě vylepšená rozšíření MD4. Rozdíly: V SHA-1 používá čtvrtý stupeň stejnou funkci jako druhý stupeň. V MD5 každá akce používá jedinečnou přírůstkovou konstantu. V SHA-1 jsou konstanty znovu použity pro každou ze čtyř skupin. Do SHA-1 byla přidána pátá proměnná. SHA-1 používá cyklický kód opravy chyb. MD5 má čtyři různé základní booleovské funkce, zatímco SHA-1 má tři. V MD5 je délka digestu 128 bitů, v SHA-1 je to 160 bitů. SHA-1 obsahuje více kol (80 místo 64) a běží na 160bitové vyrovnávací paměti ve srovnání se 128bitovou vyrovnávací pamětí MD5 . SHA-1 by tedy měl na stejném hardwaru běžet asi o 25 % pomaleji než MD5.
SHA-2	Rodina kryptografických algoritmů - hashovací funkce, včetně algoritmů SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 a SHA-512/224. V roce 2003 Gilbert a Handschuh provedli studii o SHA-2 , ale nenašli žádné zranitelnosti. V březnu 2008 však indičtí vědci Somitra Kumar Sanadiya a Palash Sarkar zveřejnili srážky, které našli pro 22 iterací SHA-256 a SHA-512. V září téhož roku představili metodu pro konstrukci kolizí pro zkrácené verze SHA-2 (21 iterací). Studie ukázaly [8] , že algoritmy SHA-2 pracují 2-3krát pomaleji než MD5 , SHA-1 hash algoritmy .
SHA-256	Samostatně vyniká algoritmus SHA-256, který se používá v hashovacích algoritmech pro bitcoiny a další kryptoměny. Jak již název kryptografické hashovací funkce napovídá, výstupní hash je dlouhý 256 bitů, odpovídající entropii lze definovat jako množinu hodnot od 1 do 2 až po mocninu 256 – obrovské množství hodnot, které dělají cracking a dešifrování extrémně časově náročný proces založený na sekvenčním výčtu.
SHA-3 ( keccak)	Hashovací funkce SHA-3 (také nazývaná Keccak) je proměnná bitová funkce vyvinutá skupinou autorů vedenou Joan Dymen . 2. října 2012 se Keccak stal vítězem soutěže kryptografických algoritmů pořádané americkým Národním institutem pro standardy a technologie [9] . Dne 5. srpna 2015 byl funkční algoritmus schválen a publikován jako standard FIPS 202 [10] [11] . Algoritmus funkce SHA-3 je postaven na principu kryptografické houby .

Aplikace

Elektronický podpis

Aby bylo jisté, že zprávu odeslal konkrétní odesílatel, je spolu se zprávou předán tzv. elektronický podpis. Příjemce zkontroluje, zda elektronický podpis k dané zprávě skutečně patří.

Vzhledem k tomu, že použití kryptografie s veřejnými klíči (podepisování, ověřování podpisů atd.) je velmi pomalý proces, navíc pokud podepíšete celou zprávu, pak bude velikost tohoto podpisu srovnatelná s velikostí zprávu, nepodepisujte zprávu a hashovací funkci ze zprávy. A pak příjemce při dešifrování podpisu obdrží hashovací funkci. Dále porovná hašovací funkci ze zprávy, kterou obdržel, a hašovací funkci, která byla získána v důsledku dešifrování. Vzhledem k tomu, že hashovací funkce má pevnou délku, je menší než samotná zpráva. To vám umožní rychle vypočítat digitální podpis. Velikost tohoto podpisu bude malá ve srovnání s velikostí zprávy.

Ověření přístupové fráze

Ve většině případů se přístupové fráze neukládají na cíle, ukládají se pouze jejich hodnoty hash. Není vhodné ukládat přístupové fráze, protože v případě neoprávněného přístupu k souboru s frázemi bude útočník znát všechna hesla a bude je moci okamžitě použít a při ukládání hodnot hash se naučí pouze hodnoty hash které nejsou vratné na původní data, v tomto případě - do přístupové fráze. Během autentizační procedury se vypočítá hash hodnota zadané přístupové fráze a porovná se s uloženou.

Příklady jsou v tomto případě GNU/Linux a Microsoft Windows XP . Ukládají pouze hash hodnoty přístupových frází z uživatelských účtů .

Tento systém předpokládá přenos zprávy přes zabezpečený kanál, to znamená kanál, ze kterého není pro kryptoanalytika možné zachytit zprávy nebo poslat své vlastní. V opačném případě může přístupovou frázi zachytit a použít ji k další nelegální autentizaci. Před takovými útoky se můžete chránit pomocí metody výzva-odpověď .

Nechte klienta s názvem name autentizovat server pomocí přístupové fráze pass . Server ukládá hash hodnotu H ( pass , R 2 ) , kde R 2 je pseudonáhodné, předem vybrané číslo. Klient odešle požadavek ( jméno , R 1 ), kde R 1 je pseudonáhodné, pokaždé nové číslo. Jako odpověď server odešle hodnotu R2 . Klient vypočítá hodnotu hash H ( R 1 , H ( pass , R 2 )) a odešle ji na server. Server také vypočítá hodnotu H ( R 1 , H ( pass , R 2 )) a porovná ji s přijatou. Pokud se hodnoty shodují, je ověření správné.

V takové situaci není heslo uloženo otevřeně na serveru a ani po zachycení všech zpráv mezi klientem a serverem nemůže kryptoanalytik heslo obnovit a přenášená hash hodnota je pokaždé jiná.

Bitcoin hash

Transakce bitcoinového platebního systému , které jsou prezentovány jako určité pole dat, jsou kombinovány do bloků (dále se souhrn všech bloků nazývá blockchain ) a procházejí hashovacím algoritmem, to znamená, že data z jejich polí jsou přiváděna na vstup. kryptografické hašovací funkce. Každá transakce uvádí, odkud jsou prostředky odepisovány a kam jdou. Pro specifikaci adresáta slouží jeho veřejný klíč (jedinečný identifikátor v bitcoinové síti). Aby mohl adresát přijaté peníze použít v rámci bitcoinového protokolu (vylučujeme prodej vlastní peněženky - Wallet), musí vytvořit novou transakci, která měnu vezme z té předchozí a přesměruje ji na jinou adresu pomocí veřejný klíč. V souladu s tím bude nová transakce spolu s transakcemi ostatních uživatelů bitcoinové sítě spadat do nového bloku. Počet bloků v blockchainu tak roste. Každá transakce však musí být schválena – systém musí dosáhnout konsensu. Existuje několik způsobů, jak to udělat, ale Bitcoin používá princip Proof-of-Work (PoW). Po přijetí transakce je považována za skutečnou a kryptoměna se přesune z jedné peněženky do druhé.

Bitcoinový systém je decentralizovaný systém bez vyhrazených center pro generování bloků. Každý účastník může vzít sadu transakcí čekajících na zaprotokolování a vytvořit nový blok. Navíc v systémech jako BitCoin dostane takový účastník (těžař) také bonus v podobě určité částky nebo provize z transakcí přijatých do bloku.

Ale nemůžete jen vzít a vytvořit blok v decentralizovaných systémech. Systém musí dosáhnout konsensu, tedy získat souhlas. Existuje několik způsobů, jak to udělat, ale Bitcoin používá princip Proof-of-Work (PoW). Spolehlivost takových systémů je založena právě na tom, že nový blok nelze vytvořit rychleji (v průměru) než za určitý čas. Například za 10 minut (BitCoin).

Bloková struktura bitcoinového blockchainu

pole	Popis	velikost
Magie ne	hodnota vždy 0xD9B4BEF9	4 byty
velikost bloku	počet bajtů následujících do konce bloku	4 byty
blockheader	skládající se ze 6 položek	80 bajtů
počítadlo transakcí	kladné celé číslo	1-4 bajty
transakce	<non empty> seznam transakcí	<Počítadlo transakcí> - mnoho transakcí

Struktura Blockheader v bloku bitcoinového blockchainu

pole	Účel	Aktualizovat, když…	velikost
verze	číslo verze bloku	Upgradujete software a ten určí novou verzi	čtyři
hashPrevBlock	256bitový hash předchozí hlavičky bloku	Přichází nový blok	32
hashMerkelRoot	256bitový hash založený na všech transakcích v bloku	Transakce je přijata	32
Čas	aktuální časové razítko jako sekundy od 01.01.1970 do 00:00 UTC	Každých pár sekund	čtyři
bitů	aktuální cíl v kompaktním formátu	Obtížnost je upravena	čtyři
noce	32bitové číslo (začíná na 0)	Hash je unavený (zvyšuje se)	čtyři

obtížnost je počet nulových bitů, které budou na začátku cílového čísla .

target je číslo, o které musí být hash bloku menší, než aby byl blok považován za platný. Cíl nebo přesněji obtížnost závisí na aktuální síle sítě a je potřeba měnit obtížnost každých n (v BitCoinové síti - 2016) bloků tak, aby se každých 10 minut vygeneroval jeden blok. Předpokládejme, že v síti je vygenerováno 2016 bloků a každý klient kontroluje, jak dlouho byl každý blok vytvořen. Pokud je tato doba delší než vypočítaná, tedy více než 10 minut, pak složitost klesá.

nonce je náhodné číslo, které musí těžaři vyzvednout, aby vytvořili blok.

Struktura bitcoinové datové struktury

Jak bylo uvedeno výše, sada bitcoinových transakcí je reprezentována jako spojené bloky dat - blockchain . Struktura zařízení samotného blockchainu je prezentována jako propojený seznam s ukazateli.

Každý blok má ukazatel, který obsahuje odkaz na předchozí datový blok. Pro přechod na n + 1 bloků je tedy nutné sledovat ukazatele předchozích n bloků. V souladu s tím ukazatele přidávají adresu nového bloku až poté, co původní datový blok prošel bitcoinovým hashovacím algoritmem – to vám umožní učinit spojení spolehlivým a bezpečným.

Takový systém je méně pravděpodobné, že bude napaden vetřelci, kteří se mohou pokusit změnit data v blockchainu, například provést vlastní transakci na zvolené adrese. Jak již bylo zmíněno, hash každého bloku v blockchainu závisí nejen na jeho vlastním obsahu, ale také na obsahu předchozího bloku. Jakákoli změna dat v původním bloku tedy znamená změnu dat v jiných blocích. To zaručuje neměnnost blockchainu a bezpečnost systému, protože je extrémně obtížné blockchain „falšovat“. Je však třeba poznamenat, že hash každého bloku musí být jedinečný, jinak nebude možné sledovat pokusy o útok.

Merkle strom

Všechny transakce jsou reprezentovány jako řetězce v hexadecimálním formátu, které jsou hashovány za účelem získání ID transakcí. Na jejich základě je postaven blokový hash, který je zohledněn následným blokem, zajišťujícím neměnnost a koherenci. Hodnota hash jednoho bloku se shromažďuje pomocí stromu Merkle .

Merkle strom je úplný binární strom , jehož vrcholy listů obsahují hash z transakcí a vnitřní vrcholy obsahují hash z přidávání hodnot v podřízených vrcholech a kořenový uzel stromu (Top Hash) obsahuje hash z celý soubor dat.

Konstrukce Merkleho stromu pro bitcoinový blockchain je následující:

$H(L_{i})$ - výsledek hashovací funkce z transakce $L_{i}$

Vypočítají se hashe transakcí umístěných v blocích: H(L1), H(L2), H(L3) a tak dále.
Hashe se počítají ze součtu hashů transakcí, například H(H(L1) + H(L2)). Protože Merkle strom je binární, počet prvků v každé iteraci musí být sudý. Pokud tedy blok obsahuje lichý počet transakcí, pak je tento duplikován a přidán k sobě: hash (H(L3) + H(L3)).
Dále se hashe počítají opět ze součtu hashů. Proces se opakuje, dokud nezískáte jediný hash - kořen stromu Merkle. Jde o kryptografický důkaz integrity bloku (to znamená, že všechny transakce probíhají v uvedeném pořadí). Hodnota kořene je pevná v hlavičce bloku.

Zároveň, když je například transakce L1 utracena, pak lze data o ní z bloku odstranit a nechat pouze její hash pro ověření bloku. Když jsou transakce L1 a L2 utraceny, pak můžeme smazat jejich hash (Hash 0-0 a Hash 0-1) a ponechat pouze Hash 0, opět pro účely ověření bloku. V okamžiku, kdy jsou všechny transakce využity, pak lze smazat všechny hashe kromě Top Hashe, protože informace o těchto transakcích již nebudou potřeba.

Pro získání hashe pro nový řetězový blok je tedy nutné vzít v úvahu všechny předchozí transakční hashe. Změna hashe alespoň jednoho z předchozích bloků povede ke změně hashe dalšího bloku, respektive takovou transakci lze okamžitě identifikovat jako neplatnou.

Těžba bitcoinů

Těžba je proces hledání konsenzu na principu Proof-Of-Work – získání souhlasu k vytvoření nového bloku. Ve skutečnosti to v bitcoinové síti spočívá v počítání hashe z bloku a jeho porovnání s cílovým číslem : pokud je hash menší než cíl, vygeneruje se nový blok, jinak tomu tak není.

Těžaři zajišťují nepřetržitý růst blockchainu. K tomu se využívá obrovský výpočetní výkon – každý těžař přispívá ke zvýšení celkového bitcoinového hashrate (výpočetního výkonu). Podíl bitcoinové hashovací operace každým těžařem závisí na celkovém hashrate ukazateli – čím vyšší je celkový hashrate sítě, tím více výpočetní práce za kratší dobu musí těžař udělat, aby si udržel průměrnou velikost své těžební odměny.

Proces dosazení nonce do řetězce pokračuje, dokud není nalezeno správné řešení. Někdy může počet pokusů dosáhnout až milionkrát. Těžař, který jako první najde správné řešení, přidá blok do blockchainu a dostane za to odměnu.

Proces výběru nonce je založen na metodě hrubé síly . Proto těžební zařízení nepřetržitě generuje náhodné řetězce, dokud není nalezena požadovaná hodnota nonce .

Příklady kryptoměn, které pro šifrování používají hašovací funkci SHA-256

SHA-256 je klasický algoritmus pro kryptoměny: je na něm postavena hlavní kryptoměna, bitcoin. V souladu s tím se tento algoritmus používá také v bitcoinových forcích: v bitcoinových penězích, bitcoinech SV. Zároveň v Bitcoin Gold těžaři používají kryptofunkci – Equihash

Kromě nich se SHA-256 používá také v:

Steemit;
peercoin ;
NameCoin ;
ocoin;
zetacoin;
emercoin .

Algoritmus SHA-256 se také používá jako podprogram v kryptoměně Litecoin a hlavním algoritmem pro těžbu je Scrypt.

Viz také

Poznámky

↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. Rychlá prokazatelně bezpečná kryptografická hashovací funkce . - 2003. - č. 230 . - str. 3-4 . Archivováno z originálu 8. prosince 2019.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. Rychlá prokazatelně bezpečná kryptografická hashovací funkce . - 2003. - č. 230 . - S. 3 . Archivováno z originálu 8. prosince 2019.
↑ Jean-Sebastien Coron, Antoine Joux. Kryptoanalýza prokazatelně zabezpečené kryptografické hashovací funkce . - 2004. - č. 013 . - S. 1.3 . Archivováno z originálu 7. prosince 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Skromný návrh pro FFT hašování // Rychlé softwarové šifrování. — Springer, Berlín, Heidelberg, 2008-02-10. — S. 65 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Archivováno z originálu 8. dubna 2019.
↑ Michael A. Halcrow, Niels Ferguson. Druhý útok před obrazem proti pouze hash eliptické křivky (ECOH) . - 2009. - č. 168 . Archivováno z originálu 24. prosince 2018.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. Rychlá prokazatelně bezpečná kryptografická hashovací funkce . - 2003. - č. 230 . Archivováno z originálu 8. prosince 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Skromný návrh pro FFT hašování // Rychlé softwarové šifrování. — Springer, Berlín, Heidelberg, 2008-02-10. - str. 54-72 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Archivováno z originálu 8. dubna 2019.
↑ Porovnání rychlosti populárních krypto algoritmů . www.cryptopp.com. Získáno 22. prosince 2017. Archivováno z originálu 2. července 2017.
↑ Swenson, Gayle . NIST vybírá vítěze soutěže Secure Hash Algorithm (SHA-3) Competition (eng.) , NIST (2. října 2012). Archivováno z originálu 5. října 2012. Staženo 23. prosince 2017.
↑ Hernandez, Paul . NIST uvádí SHA-3 Cryptographic Hash Standard , NIST ( 5. srpna 2015). Archivováno z originálu 24. ledna 2018. Staženo 23. prosince 2017.
↑ Morris J. Dworkin. Standard SHA-3: Funkce hash založené na permutaci a funkce rozšiřitelného výstupu // Federal Inf. proces. Stds. (NIST FIPS) - 202. - 04.08.2015. Archivováno z originálu 17. září 2017.

Literatura

Bruce Schneier. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C. - M .: Triumph, 2002. - ISBN 5-89392-055-4 .
Laponina O.R. Kryptografické základy bezpečnosti . - M . : Internetová univerzita informačních technologií - INTUIT.ru, 2004. - S. 320. - ISBN 5-9556-00020 -5.

Odkazy

Informace o elektronickém digitálním podpisu . (neurčitý)
Keccak Hash Function and the Sponge Construction as a Universal Crypto Primitive, pgpru.com, 2010-2013 (přeloženo z noekon.org)
Text oficiální normy GOST R 34.11-2012 ve Wikisource

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA