Diffie Hellmanův algoritmus výměny klíčů

Nejprve zvažme proces teoreticky. Na obrázku 1 vidíme idealizované rozložení věcí: Alice a Bob spolu chtějí komunikovat bezpečně, ale musí předpokládat, že ke komunikačnímu kanálu má přístup i zlomyslný šmírák a odposloucháváč Eve . (Mimochodem, tato konvenční jména, která jsou vidět v mnoha diskusích o kryptografii, byla představena právě dokumentem popisujícím algoritmus Diffie-Hellmana.)

Otázkou tedy je, dokážou spolu Alice a Bob komunikovat způsobem, který jim umožní vyloučit Evu, aniž by nejprve vytvořili tajný klíč, který znají jen oni? Pamatujte, že jakmile Alice a Bob znají tajný klíč, ale Eva ne, tak může být k šifrování a dešifrování dat použita symetrická šifra.

Odpověď byla po několik tisíc let: ne.

Whitfield Diffie s pomocí Martina Hellmana, byl posedlý touto myšlenkou: Co kdybychom našli matematickou funkci, která by Alici a Bobovi umožnila vypočítat klíč, na který by Eva nemohla přijít, i když by Eva viděla veškerou komunikaci mezi Alicí a Bobem?

Toho by se mohlo dosáhnout výměnou některých informací, u kterých je jedno, že je svět vidí, včetně útočnice Eve. Tato informace je známá jako veřejný klíč. Použití veřejné i tajné složky je důvodem, proč se Diffie-Hellman nazývá asymetrické šifrování.

Matematika, jak toho dosáhnout, není příliš složitá, ale je také vážně nesrozumitelná. Jak k tomu Diffie přišel? No, o té myšlence přemýšlel roky, než mu geniální tah dal níže popsanou odpověď.

První část výměny začíná dohodnutou funkcí tvaru \$\mathbf{g^t mod p}\$ (zapisuje se to také jako: g^t mod p). Tento vzorec je všem stranám znám. Čísla g a t jsou přirozená, p je prvočíslo. Funkce mod p je zbytek po dělení číslem p.

V praxi jsou tato čísla vybírána pomocí pseudonáhodného generátoru.

Ukažme si to na příkladu. Jako základ g použijeme 15. Toto číslo je známé jako generátor. Pro naše prvočíslo p použijeme 1217.

Takže veřejná funkce bude \$\mathbf{11^t mod 1217}\$. Je známá všem. Situaci můžete nyní vidět na obrázku 2.

Co to je t? Odpověď je, že t je exponent a je součástí tajného klíče, u Alice ho označíme a a u Boba b. Alice a Bob si každý soukromě vyberou tajný klíč (exponent) a spustí funkci, na které se předtím dohodli. Výsledky jsou poté sdíleny, čímž se stanou součástí veřejného klíče.

Řekněme, že Alice si vybere tajné číslo 46 a Bob vybere si vybere tajné číslo 94 (opět by to byla větší náhodná čísla v reálném životě). Novou situaci můžete vidět na obrázku 3.

Eva neví, jaká čísla si Alice a Bob vybrali.

Nyní Alice a Bob provozují své příslušné funkce se svými tajnými čísly. Alice vypočítá číslo \$\mathbf{A=15^46 mod 1217=853}\$ a pošle Bobovi. Bob vypočítá číslo \$\mathbf{B=15^94 mod 1217==1185}\$ a pošle Alici.

Nyní Alice a Bob sdílejí tato čísla mezi sebou a musíme předpokládat že je sdílejí také s naší útočnicí Evou. Tato scéna je znázorněna na obrázku 4.

I když Eva zná rovnici a zná výsledky, nemůže snadno objevit chybějící čísla. To je podstata jednosměrné funkce: je proveditelná jenom jedním směrem a je prakticky nemožné ji obrátit.

Například, pokud chce Eva najít Alicino skryté číslo, bude muset vyřešit \$15^t mod 1217 = 853\$ nebo rovnici \$15^t mod 1217=1185\$. Jak těžké to je? Podívejte se. Problém spočívá v řešení diskrétního logaritmu, známého obtížného problému. Je to mnohem obtížnější než odmocňování, se známými matematickými postupy.

Tady přichází ten magický kousek. Alice a Bob spustí každý novou funkci pomocí výsledku, který získali od druhého, spolu se svým vlastním tajným číslem a původním primárním modulem, a dospějí ke společnému sdílenému tajnému číslu, které Eva nemůže určit (musela by řešila rovnici diskrétního logaritmu).

V našem případě, jako na obrázku 5, Alice vypočítá \$\mathbf{1185^46 mod 1217=1213}\$ a Bob vypočítá \$\mathbf{853^94 mod 1217=1213}\$. Oba mají sdílený klíč 1213.

S tímto soukromým klíčem v ruce mohou Alice a Bob vyjednat výměnu symetrického šifrování pomocí něčeho jako AES (Advanced Encryption Standard), zatímco Eva může pracovat na útoku hrubou silou za přibližně 100 milionů dolarů za klíč.

Všimněte si, že většina moderních systémů používá šifrování 2048 – exponenciálně stejně silné. Odhad pro rozluštění znamená vyzkoušet \$2^2048\$ čísel. Jakákoli kalkulačka vám řekne, že je to hodně velké číslo.

Že algoritmus funguje spolehlivě se můžeme přesvědčit i kalkulačkou, trocha počítání je zde.

Ačkoli se Diffie-Hellman ukázal jako vysoce odolný vůči útokům, když je správně implementován (to není špatné pro algoritmus vytvořený téměř před 50 lety), existuje jedna pokroková technologie, která ji může nakonec porazit: kvantové počítače. Kromě hrubé síly nebo průlomu v diskrétních logaritmech nebo kvantových výpočtech mohou být uživatelé Diffie-Hellman zranitelní vůči několika útokům, které závisí na využití výpočetního prostředí, známým jako útoky postranním kanálem.

Překlad: https://www.infoworld.com/article/3647751/understand-diffie-hellman-key-exchange.html

Pochopit Diffie-Hellmanův algoritmus se dá také pomocí barviček, jak je na české Wikipedii

Prvočísla: https://en.wikipedia.org/wiki/List_of_prime_numbers

Vypočítejte sdílený klíč v Diffie Hellmanově protokolu, čísla volte \$g > 100, p > 10000, A>100, B>100\$, p musí být prvočíslo. Prvočísla můžete ověřit třeba zde: Prime Numbers Chart and Calculator Jak se to dělá je podrobně popsáno zde: Diffie Hellman - praktické výpočty. Kdo bude z této stránky doslova opisovat, dostane kuli. Vymyslete si jiná čísla, než já. Výsledky pošlete emailem na adresu jirka@lixis.cz, do předmětu zprávy napište Diffie-Hellman výpočet a do těla zprávy napište čísla g=zvolené něco, p=nějaké prvočíslo, A=vypočítané něco, B=vypočítané něco a sdílený klíč s=váš výsledek. Za domácí úkol dostanete známku.