Protokol výmeny kľúčov Diffie-Hellman je základná kryptografická technika, ktorá umožňuje dvom stranám bezpečne vytvoriť zdieľané tajomstvo cez nezabezpečený komunikačný kanál. Tento protokol zaviedli Whitfield Diffie a Martin Hellman v roku 1976 a je pozoruhodný tým, že na zaistenie bezpečnosti používa problém diskrétneho logaritmu.
Ako funguje Diffieho-Hellmanova výmena kľúčov
Diffieho-Hellmanova výmena kľúčov (skrátene D-H) je kryptografický protokol, ktorý umožňuje cez nezabezpečený kanál vytvoriť medzi komunikujúcimi stranami šifrované spojenie, bez predchádzajúceho dohodnutia šifrovacieho klúča. Výsledkom tohto protokolu je vytvorenie symetrického šifrovacieho klúča, ktorý môže byť následne použitý pre šifrovaní zbytku komunikácie. Výhodou je, že prípadný útočník odposlouchávající komunikáciu tento klíč nezachytí. Klíč je zkonstruován všemi účastníky komunikace a nikdy není poslán v otevřené formě. Nevýhodou tohoto protokolu je bezbrannost proti útoku Man in the middle, protože neumožňuje autentizaci účastníků.
Protokol výmeny kľúčov Diffie-Hellman funguje na princípoch modulárnej aritmetiky a umocňovania. Protokol možno zhrnúť do niekoľkých krokov:
- Výber verejných parametrov:
- Dve veľké prvočísla, p (primárny modul) a g (generátor alebo primitívny koreňový modul p), sú vybrané. Tieto čísla sú verejné a môžu ich poznať všetci účastníci.
- Prvočíslo p by mali byť dostatočne veľké, aby boli útoky hrubou silou výpočtovo neuskutočniteľné.
- Generovanie súkromných a verejných kľúčov:
- Každá strana si vyberie súkromný kľúč. Označme dve strany ako Alice a Bob.
- Alica vyberie súkromný kľúč a, čo je náhodné celé číslo také, že 0 < a < p.
- Bob vyberie súkromný kľúč b, čo je tiež náhodné celé číslo také, že 0 < b < p.
- Výpočet verejných kľúčov:
- Alica vypočíta svoj verejný kľúč A pomocou vzorca A = ga mod p.
- Bob vypočíta svoj verejný kľúč B pomocou vzorca B = gb mod p.
- Výmena verejných kľúčov:
- Alice a Bob si vymieňajú svoje verejné kľúče cez nezabezpečený kanál. Alice posiela Bobovi A a Bob posiela k Alici B.
- Výpočet zdieľaného tajomstva:
- Alica vypočíta spoločné tajomstvo pomocou Bobovho verejného kľúča a jej súkromný kľúč: s = Ba mod p.
- Bob vypočíta spoločné tajomstvo pomocou Alicinho verejného kľúča a jeho súkromný kľúč: s = Ab mod p.
Vďaka vlastnostiam modulárnej aritmetiky bude zdieľané tajomstvo vypočítané Alicou aj Bobom rovnaké: gab mod p = gba mod p.
Úloha problému diskrétneho logaritmu
Bezpečnosť protokolu výmeny kľúčov Diffie-Hellman v zásade závisí od náročnosti riešenia problému diskrétneho logaritmu (DLP). DLP možno uviesť nasledovne: pridelené prvočíslu p, generátor g a hodnota A takýmto spôsobom A = ga mod p, je výpočtovo nemožné určiť celé číslo a (diskrétny logaritmus A na základňu g).
Prečítajte si tiež: Návod na výmenu spojky pre Octaviu 2
V kontexte protokolu Diffie-Hellman:
- Alicin verejný kľúč A je odvodený od jej súkromného kľúča a pomocou exponenciálnej funkcie ga mod p.
- Bobov verejný kľúč B je odvodený od jeho súkromného kľúča b pomocou exponenciálnej funkcie gb mod p.
Protivník, ktorý zachytáva verejné kľúče A a B, bude musieť vyriešiť problém diskrétneho logaritmu na určenie súkromných kľúčov a or b. Bez znalosti týchto súkromných kľúčov nemôže protivník vypočítať zdieľané tajomstvo s.
Príklad
Na ilustráciu výmeny kľúčov Diffie-Hellman na konkrétnom príklade zvážte nasledujúci zjednodušený scenár s malými prvočíslami kvôli prehľadnosti:
- Výber verejných parametrov:
- Primárny modul: p = 23
- Generátor: g = 5
- Súkromné kľúče:
- Alicin súkromný kľúč: a = 6
- Bobov súkromný kľúč: b = 15
- Verejné kľúče:
- Alice vypočíta svoj verejný kľúč: A = 56 mod 23 = 8
- Bob vypočíta svoj verejný kľúč: B = 515 mod 23 = 19
- Výmena verejných kľúčov:
- A = 8 posiela Alice k Bobovi.
- B = 19 posiela Bob k Alici.
- Zdieľaný tajný výpočet:
- Alice vypočíta zdieľané tajomstvo: s = 196 mod 23 = 2
- Bob vypočíta zdieľané tajomstvo: s = 815 mod 23 = 2
Alice aj Bob nezávisle vypočítali rovnaké spoločné tajomstvo s = 2.
Bezpečnostné hľadiská
Bezpečnosť protokolu Diffie-Hellman závisí od výberu hlavného modulu p a generátor g. Prvotriedne p musia byť dostatočne veľké, aby zmarili pokusy o vyriešenie problému diskrétneho logaritmu pomocou hrubej sily alebo iných kryptografických útokov. Pre silné zabezpečenie sa zvyčajne odporúčajú prvočísla aspoň 2048 bitov.
Prečítajte si tiež: Postup výmeny hlavne
Navyše generátor g by mal byť vybraný tak, aby bol primitívnym koreňovým modulom p, zabezpečujúc, že hodnoty gi mod p vytvárajú veľkú cyklickú skupinu. Táto vlastnosť maximalizuje náročnosť riešenia problému diskrétneho logaritmu.
Útoky a zmierňovanie
Za zmienku stojí niekoľko potenciálnych útokov na protokol Diffie-Hellman a ich zmiernenie:
- Stredný útok muža (Man-in-the-middle):
- Pri útoku typu man-in-the-middle protivník zachytí verejné kľúče, ktoré si vymenili Alice a Bob, a nahradí ich vlastnými. Protivník potom môže vytvoriť samostatné zdieľané tajomstvá s každou stranou a dešifrovať a znova zašifrovať správy.
- Zmiernenie: Použite overenú výmenu kľúčov Diffie-Hellman, ako je napríklad protokol Station-to-Station (STS), ktorý zahŕňa digitálne podpisy alebo infraštruktúru verejného kľúča (PKI) na overenie zainteresovaných strán.
- Logjamský útok:
- Útok Logjam využíva slabé parametre Diffie-Hellman (napr. malé prvočísla) na vykonanie predvýpočtových útokov na bežné prvočísla.
- Zmiernenie: Používajte dostatočne veľké prvočísla (najmenej 2048 bitov) a vyhnite sa opätovnému používaniu spoločných prvočísel v rôznych implementáciách.
- Útoky cez bočný kanál:
- Útoky na bočný kanál využívajú únik informácií z fyzických implementácií protokolu, ako sú informácie o načasovaní alebo spotrebe energie.
- Zmiernenie: Implementujte algoritmy s konštantným časom a hardvér odolný voči postranným kanálom, aby ste zabránili úniku citlivých informácií.
Tabuľka: Kto čo vie
Níže uvedený tabuľka znázorňuje kto čo vie, pričom verejné hodnoty sú zvýraznené modře a tajné hodnoty červeně. V príkladu je s tajný sdílený klíč, který je známý Alici a Bobovi, ale nikoliv Evě.
| Hodnota | Kto vie | Poznámka |
|---|---|---|
| p | Alice, Bob, Eva | Verejný (prvočíselný) modul |
| g | Alice, Bob, Eva | Verejný (primitívny koreň) základ |
| a | Alice | Súkromný kľúč Alice |
| b | Bob | Súkromný kľúč Boba |
| A = ga mod p | Alice, Bob, Eva | Verejný kľúč Alice |
| B = gb mod p | Alice, Bob, Eva | Verejný kľúč Boba |
| s = gab mod p | Alice, Bob | Zdieľané tajomstvo |
Poznámka: Pre Alici by malo byť obtížné zjistit Bobův soukromý klíč nebo pro Boba zjistit soukromý klíč Alice. Pokud pro Alici není těžké najít Bobův soukromý klíč (nebo naopak), pak může odposlouchávající Eva jednoduše nahradit svůj vlastní pár soukromého a veřejného klíče, zapojit Bobův veřejný klíč do svého soukromého klíče a vytvořit falešný sdílený klíč a nalézt Bobův soukromý klíč (a použít to pro vyřešení sdíleného tajného klíče).
Diffie-Hellman pre viac účastníkov
Diffieho-Hellmanova výměna klíčů není omezena jen na dva účastníky. Jakýkoliv mezi-výpočet (s až n-1 použitými exponenty, kde n je počet účastníků) může být zveřejněný, ale finální hodnota (kde je aplikováno všech n exponentů) představuje tajemství, které nesmí být zveřejněno. Tyto zásady nechávají otevřené možnosti, v jakém pořadí všichni účastníci přispějí svým privátním exponentem k vytvoření kopií finálního klíče. Nejjednodušším řešením je uspořádat n účastníků do kruhu a nechat kolovat n klíčů, dokud se každému z účastníků nevrátí jeho vlastní klíč (aplikováno všech n exponentů). Optimalizací pořadí, a uvážením faktu, že klíče mohou být reprodukovány, je možné snížit počet modulárních umocnění provedených každého účastníka na log2(n) + 1 za použití přístupu rozděl a panuj.
Prečítajte si tiež: Návod: Upgrade hlavne airsoftovej zbrane
Protokol výmeny kľúčov Diffie-Hellman zostáva základným kameňom moderných kryptografických systémov vďaka elegantnému použitiu matematických princípov a schopnosti nadviazať bezpečnú komunikáciu cez nezabezpečené kanály. Problém diskrétneho logaritmu zohráva dôležitú úlohu pri zaisťovaní bezpečnosti protokolu tým, že je pre protivníkov výpočtovo nemožné odvodiť súkromné kľúče z verejných kľúčov. Po pochopení základných mechanizmov a potenciálnych zraniteľností môžu odborníci efektívne implementovať a zabezpečiť výmenu kľúčov Diffie-Hellman v rôznych kryptografických aplikáciách.
Diffie-Hellman (DH) key exchange is a mathematical method of securely generating a symmetric cryptographic key over a public channel and was one of the first protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. The Diffie-Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. Diffie-Hellman is used to secure a variety of Internet services.
Diffieho-Hellmanův protokol distribuce klíčů byl vynalezen v roce 1976 Whitfieldem Diffiem a Martinem Hellmanem, svou roli zde ovšem sehrál i Ralph Merkle, John Gill navrhl aplikování problému diskrétního logaritmu. Jednalo se o první praktické využití metody vytvoření tajných sdílených informací na nechráněném komunikačním kanálu.
Moderný digitálny svet je plný tajomstiev, ktoré potrebujeme chrániť. Každý deň posielame citlivé informácie cez internet - od bankových údajov až po osobné správy. Ale ako sa môžu dvaja ľudia, ktorí sa nikdy nestretli, dohodnúť na spoločnom tajomstve cez nezabezpečený kanál? Diffie-Hellman Key Exchange predstavuje jeden z najdôležitejších prelomov v histórii kryptografie. Táto metóda umožňuje dvom stranám vytvoriť spoločný šifrovací kľúč bez toho, aby ho museli priamo prenášať cez komunikačný kanál. Pripravte sa na fascinujúcu cestu do sveta asymetrickej kryptografie. Dozviete sa, ako táto metóda funguje, prečo je taká dôležitá a kde všade ju denne využívate, možno ani o tom neviete.
Diffie-Hellmanova výměna klíčů znázorněna pomocí míchání barev (Předpokládá se, že oddělení smíchaných barev je nemožné). Sdílené tajemství s nemůže zjisti nikdo, kdo sleduje vzájemnou komunikaci, protože by musel tipovat čísla a, b a doufat tak, že správné číslo uhodne.
Nejjednodušší a původní implementace DH protokolu, později vydaná jako Finite Field Diffie-Hellman v RFC 7919, která používá multiplikativní grupu celých čísel modulo p, kde p je prvočíslo a g je primitivní kořen modulo p. Tyto dvě hodnoty jsou zvoleny tak, aby výsledný sdílený tajný klíč mohl nabývat jakékoli hodnoty od 1 do p−1. Pouze hodnoty a a b jsou drženy v tajnosti. Všechny ostatní hodnoty (p, g, ga mod p a gb mod p) se odesílají veřejně.
Jakmile Alice a Bob vypočítají sdílené tajemství, mohou jej použít jako tajný šifrovací klíč pro odesílání zpráv přes otevřený komunikační kanál. Odolnost výměny proti odposlechnutí vychází ze skutečnosti, že výpočet gab mod p = gba mod p trvá extrémně dlouho, než se libovolným známým algoritmem nalezne pouze na základě znalosti p, g, ga mod p a gb mod p. Aby byl příklad bezpečný, byly by samozřejmě potřeba mnohem větší hodnoty a, b a p, protože ve výše uvedeném příkladu existuje pouze 23 možných výsledků n mod 23. Pokud je však p prvočíslo s alespoň 600 číslicemi, pak ani nejrychlejší moderní počítače používající nejrychlejší známé algoritmy nemohou najít utajené a na základě veřejných g, p a ga mod p. Obtížnost tohoto řešení se nazývá problém diskrétního logaritmu. Výpočet ga mod p je známý jako modulární umocňování a lze jej efektivně provádět i pro velká čísla.
Diffie-Hellman key agreement is not limited to negotiating a key shared by only two participants. Any number of users can take part in an agreement by performing iterations of the agreement protocol and exchanging intermediate data (which does not itself need to be kept secret). Any intermediate value (having up to N−1 exponents applied, where N is the number of participants in the group) may be revealed publicly, but the final value (having had all N exponents applied) constitutes the shared secret and hence must never be revealed publicly. These principles leave open various options for choosing in which order participants contribute to keys. The simplest and most obvious solution is to arrange the N participants in a circle and have N keys rotate around the circle, until eventually every key has been contributed to by all N participants (ending with its owner) and each participant has contributed to N keys (ending with their own).