Kryptoměna Bitcoin
Přihlásit se
Kryptoměna Bitcoin (3/7) · 10:14

Bitcoin - Kryptografická hašovací funkce Co jsou kryptografické hašovací funkce a jaké mají požadované vlastnosti. Autor videa: Zulfikar Ramzan

Navazuje na Peníze a bankovnictví.
Kryptografické hašovací funkce jsou základní stavební kameny, využívané v mnoha kryptografických algoritmech a protokolech. Mají celou řadu významných aplikací v oboru informační bezpečnosti jako celku. Mezi známější algoritmy v kategorii kryptografických hašovacích funkcí patří... například algoritmus MD5. MD5 má několik starších verzí např. MD4. Známým příkladem je také algoritmus SHA-256. Také u SHA-256 existují starší verze jako je SHA-1. Existuje také mnoho o něco méně známých algoritmů: jsou to např. RIPEMD, BLAKE, Skein a další. Kryptografické hašovací funkce jsou nezbytnou součástí mnoha aplikací, a poprvé se naplno uplatnily v oblasti, která je známá jako digitální podepisování. Digitální podpisy mají dnes opravdu velké množství použití. Jsou v základech protokolů dnešního elektronického obchodování a využívají se také při generování nových bitcoinů. Kryptografické hašovací funkce se dále využívají při ověřování autenticity a integrity zpráv, při generování náhodných čísel, pro zajištění bezpečnosti hesel, do určité míry také při šifrování. A vlastně, kromě použití v rámci digitálních podpisů se hašovací funkce objevují i na dalších místech v bitcoinovém protokolu. Nejdříve vysvětlím, co vlastně je "kryptografická hašovací funkce". Je samozřejmě logické začít samotným pojmem "hašovací funkce". Hašovací funkcí míníme následující: Je to matematická funkce nebo také transformace, do které vkládáme určitý parametr, označovaný jako "zpráva" (message). Tato zpráva může mít zcela libovolnou délku. Hašovací funkce s touto zprávou provede... celou řadu matematických operací, jejichž výsledkem je určitý výstup. Ten se běžně nazývá "otisk" (digest), ačkoli někdy se užívá také označení "štítek" (tag) nebo "haš" (hash). Nicméně označení "otisk" se využívá nejvíce. Zde je vhodné uvést, že označení zmíněného algoritmu MD5... je zkratkou pro Message Digest 5 (otisk zprávy 5), podobně MD4 je zkratkou pro Message Digest 4. Jak bylo řečeno dříve, zpráva může mít libovolnou velikost. Může být velice dlouhá, nebo mít jen pár znaků. Na druhou stranu, výsledný otisk bude mít velikost vždy pevně určenou (fixed length), a to pro každý typ hašovací funkce. Například algoritmus SHA-256 bude produkovat pouze otisky délky 256 bitů. To znamená, že pro každou, libovolně velkou zprávu bude výsledkem otisk stejné velikosti. Dále je potřeba zdůraznit, že hašovací funkce jsou zcela deterministické, což vlastně platí pro všechny matematické funkce. Tedy pro pevně zvolenou zprávu hašovací funkce vyprodukuje vždy stejný otisk. Nikdy tedy nenastane situace, že bychom dostali dva otisky pro jednu zprávu. Tradiční hašovací funkce se používají v informatice už docela dlouhou dobu a používají se v noha aplikacích. Možná jste již o některých slyšeli, příkladem jsou tzv. hašovací tabulky. Zde je potřeba zdůraznit, že hašovací funkce využívané v hašovacích tabulkách nemusí být nutně stejného typu jako jsou kryptografické hašovací funkce. Označení, že jde "kryptografickou" funkci, zde hraje důležitou roli. V praxi to znamená, že na kryptografickou hašovací funkci je kladeno několik speciálních požadavků, které jsou nutné pro jejich využití v kryptografických oborech a aplikacích jako je zabezpečení, ochrana soukromých údajů, utajování informací a ověřování totožnosti. Prvním důležitým požadavkem, který klademe na kryptografické hašovacích funkce, je požadavek výpočetní efektivity (computationally efficient). Tím myslíme, že by doba nutná k výpočtu otisku zprávy měla být co nejkratší. Pro zvolenou zprávu prostě chceme, aby výpočetní operace netrvaly příliš dlouho. Samozřejmě, že na počítačích bude tento proces vždy relativně rychlý. Nicméně i tak je tento požadavek nutno zdůraznit, neboť se lze setkat s návrhy algoritmů, díky nimž jsou dané hašovací funkce výpočetně neefektivní. Takové algoritmy ale nejsou považovány za vhodné v oblasti, kde se nejčastěji používají vlastní kryptografické hašovací funkce. Druhým zásadním požadavkem na kryptografické hašovací funkce, který hraje důležitou roli v oblasti digitálních podpisů, je požadavek, aby bylo těžké nalézt dvě různé zprávy, které mají identický otisk. V případě, že algoritmus tuto vlastnost splňuje, říkáme, že se jedná o hašovací funkci odolnou vůči kolizím. To znamená, že je těžké nalézt kolidující pár vstupních parametrů. Jinak řečeno, pro dvě zvolené zprávy M1 a M2 by otisk vyprodukovaný hašovací funkcí neměl být shodný. Přesněji, nikdy by nemělo stát, že pro dvě různé zprávy M1, M2 dostaneme stejný otisk. Otisk by měl vždy být odlišný. Zde udělejme odbočku a řekněme, že je to vlastně nesplnitelný požadavek. Je jasné, že pokud může být velikost zprávy libovolná, zatímco velikost otisku je pevně daná, není teoreticky možné garantovat, že otisk bude různý pro všechny možné zprávy. Pro praktické aplikace není důležité, aby byl otisk odlišný pro všechny zprávy, ale aby bylo výpočetně obtížné takové dvě zprávy nalézt. Víme ale, že takové dvě zprávy existují. Víme to proto, že všechny zprávy mohou vyprodukovat pouze omezené množství různých otisků, které je vzhledem k neomezenému množství různých zpráv zanedbatelné. Bez ohledu na tento teoretický fakt, by nalezení kolize mělo být opravdu těžké. Tedy pokus o nalezení dvou kolizních zpráv by měl zabrat astronomicky dlouhou dobu, Třetím důležitým požadavkem na kryptografické hašovací funkce je, aby hašovací funkce ukrývala informaci, která je obsažena ve vstupní zprávě. Jinak řečeno, žádný otisk určité zprávy by neměl umožňovat zjistit cokoli o obsahu dané zprávy. Tím není myšleno pouze zjištění obsahu celé zprávy, ale i například to, zda je ve zprávě sudé nebo liché číslo. Tento typ zjištění byl mělo být těžký odvodit z pouhé znalosti otisku. A to i v případě, že se jedná o tak jednoduchou informaci, jestli zadaný vstup je sudý nebo lichý. Čtvrtým požadavkem, který je potřeba zmínit, je, že typicky chceme, aby výsledné otisky byly rovnoměrně distribuované. Jinak řečeno požadujeme, aby hodnoty otisků vypadaly pro různé zprávy náhodně, jako bychom je získali pomocí série hodu mincí. Důležitý princip, který byste si z tohoto měli odnést, je, že na první pohled by nemělo být možné rozlišit mezi hašovací a náhodnou funkcí. To, co jsme si doposud řekli o kryptografických hašovacích funkcích, bychom mohli shrnnout tak, že si je lze představovat jako nějaký zvláštní druh matematického mlýnku na maso. Nasypeme do něj zprávu a mlýnek jí semele pomocí matematických operací tak, že výsledný otisk vypadá z praktického hlediska úplně náhodně a není možné vysledovat souvislost s původním vstupem. Nyní udělám pár závěrečných poznámek o vlastnostech hašovacích funkcí. Zaprvé, všechny ty vlastnosti spolu vzájemně souvisí. Například, pokud nelze mezi vstupními zprávami a výslednými otisky vysledovat žádnou souvislost a výsledné otisky se jeví jako náhodné, pak z toho také do velké míry vyplývá vlastnost kolizní odolnosti. Pokud totiž nelze odhadnout výsledný otisk a platí, že z otisku nelze vyčíst o zprávě žádnou informaci, vyplývá z toho také, že bude obtížné nalézt dvě různé zprávy se stejným otiskem. Vidíme tedy, že někdy můžeme získat jednu vlastnost z ostatních. Druhou poznámku, kterou jsem chtěl udělat je, že v praxi je potřeba spoléhat na to, že uvedené vlastnosti opravdu platí. Ve skutečnosti však nemáme absolutní jistotu, že tomu tak bude. Můžeme např. vytvořit hašovací funkci, o níž předpokládáte odolnost vůči kolizím, nicméně třeba za rok někdo nalezne lepší způsob hledání kolizí. Jde především o urychlující metody, bez použití hrubé síly (tj. zkoušení všech možných kombinací). V současnosti platí, že pro aktuální verze kryptografických algoritmů zatím nikdo nenašel urychlující matematické metody pro prolomení jejich vlastnosti. A tak na základě toho, že doposud spolehlivě sloužily, prostě předpokládáme, že jsou z praktického hlediska bezpečné. Poslední věcí, která je potřeba říct, že tuto lekci nelze nijak považovat za matematicky důslednou v jakémkoli smyslu. Existují způsoby, kterými lze popsat uvedené základní vlastnosti mnohem přesněji. Cílem této lekce bylo především podat základní přehled o tom, jaké vlastnosti mají kryptografické hašovací funkce, aniž bychom zabředli do složitých matematických vzorečků a formalismů.
video