Diffieho–Hellmanova výměna klíčů

Diffieho-Hellmanova výměna klíčů (zkráceně D-H) je kryptografický protokol, který umožňuje přes nezabezpečený kanál vytvořit mezi komunikujícími stranami šifrované spojení, bez předchozího dohodnutí šifrovacího klíče. Výsledkem tohoto protokolu je vytvoření symetrického šifrovacího klíče, který může být následně použit pro šifrovaní zbytku komunikace. Výhodou je, že případný útočník odposlouchávající komunikaci 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ů. Tento protokol bez kombinace s jinými metodami je tedy vhodný pouze tam, kde útočník nemůže aktivně zasahovat do komunikace.

Historie

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. Jako první tento protokol vymyslel Malcolm Williamson z Government Communications Headquarters z Velké Británie o několik let dříve, ale GCHQ se vzhledem ke své podstatě tajné vládní instituce rozhodla objev utajit až do roku 1997, kdy už to nemělo žádný vliv.

Princip dohody klíče mezi dvěma účastníky

Diffie-Hellman protokol
Alice			Bob			Veřejnost
Výpočty	Tajné		Výpočty	Tajné		Veřejné
	a			b		p, g
$A\equiv g^{a}\mod p$		→			→	A
			$B\equiv g^{b}\mod p$		→	B
$s\equiv B^{a}\mod p$	→ s	=	$s\equiv A^{b}\mod p$	→ s

Principiálně se problém opírá o složitost výpočtu diskrétního logaritmu.

Jeden z účastníků komunikace zveřejní prvočíslo p, tj. konečnou grupu $G=(Z_{p}^{*};\cdot )$ a generátor g této grupy, kde g je vybraný primitivní kořen modulo p (pro dané p může být více g)
První účastník si zvolí číslo a, které bude sloužit jako jeho soukromý klíč a spočte svůj veřejný klíč A jako ${\textstyle A=g^{a}\mod p}$ . Ten zveřejní.
Druhý účastník si zvolí číslo b jako soukromý klíč a spočítá veřejný klíč B, ${\textstyle B=g^{b}\mod p}$ .
Své veřejné klíče zveřejní
Nyní první účastník může spočítat ${\textstyle s\equiv B^{a}\mod p}$ , druhý účastník může spočítat ${\textstyle s'\equiv A^{b}\mod p}$ .
Čísla s, s' jsou totožná, neboť ${\textstyle s'=A^{b}\mod p=(g^{a})^{b}\mod p=g^{ab}\mod p=(g^{b})^{a}\mod p=B^{a}\mod p=s}$ .

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. Čísla p a g jsou zde zvolena tak, že sdílené tajemství může být kterákoliv hodnota z rozsahu od 1 do p−1.

Příklad dohody klíče

Nejjednodušší a původní implementace DH protokolu,^[1] později vydaná jako Finite Field Diffie-Hellman v RFC 7919,^[2] která používá multiplikativní skupinu 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. Následuje příklad vyjednávání pomocí DH protokolu, kde veřejné hodnoty jsou označené modře a tajné hodnoty červeně.

Alice a Bob veřejně souhlasí s použitím modulu p = 23 a základu g = 5 (g je primitivní kořen modulo 23).
Alice vybere tajné celé číslo a = 4, pak pošle Bobovi A = g^a mod p
- A = 5⁴ mod 23 = 4 (v tomto příkladu mají A i a stejnou hodnotu 4, ale obvykle tomu tak není)
Bob vybere tajné celé číslo b = 3, pak pošle Alici B = g^b mod p
- B = 5³ mod 23 = 10
Alice vypočítá s = B^a mod p
- s = 10⁴ mod 23 = 18
Bob vypočítá s = A^b mod p
- s = 4³ mod 23 = 18
Alice a Bob nyní sdílejí tajemství (číslo 18).

Alice i Bob došli ke stejné hodnotě tajemství, protože pod mod p:

{\color {Blue}A}^{\color {Red}b}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}ab}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}ba}{\bmod {\color {Blue}p}}={\color {Blue}B}^{\color {Red}a}{\bmod {\color {Blue}p}}

Konkrétněji:

({\color {Blue}g}^{\color {Red}a}{\bmod {\color {Blue}p}})^{\color {Red}b}{\bmod {\color {Blue}p}}=({\color {Blue}g}^{\color {Red}b}{\bmod {\color {Blue}p}})^{\color {Red}a}{\bmod {\color {Blue}p}}

Pouze hodnoty a a b jsou drženy v tajnosti. Všechny ostatní hodnoty (p, g, g^a mod p a g^b 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 g^ab mod p = g^ba mod p trvá extrémně dlouho, než se libovolným známým algoritmem nalezne pouze na základě znalosti p, g, g^a mod p a g^b 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 g^a mod p. Obtížnost tohoto řešení se nazývá problém diskrétního logaritmu. Výpočet g^a mod p je známý jako modulární umocňování a lze jej efektivně provádět i pro velká čísla. Všimněte si, že g nemusí být vůbec velké a v praxi je to obvykle malé celé číslo (například 2, 3, ...).

Tabulka utajení

Níže uvedený tabulka znázorňuje kdo co ví, přičemž veřejné hodnoty jsou zvýrazněny modře a tajné hodnoty červeně. Eva zde odposlouchává – sleduje, co se posílá mezi Alicí a Bobem, ale nemění obsah jejich komunikace.

g, veřejný základ (primitivní kořen) známý Alici, Bobovi a Evě: g = 5
p, veřejný modulus (prvočíslo) známý Alici, Bobovi a Evě: p = 23
a, privátní klíč Alice, známý jen Alici: a = 6
b, privátní klíč Boba, známý jen Bobovi: b = 15
A, veřejný klíč Alice, známý Alici, Bobovi a Evě: A = g^a mod p = 8
B, veřejný klíč Boba, známý Alici, Bobovi a Evě: B = g^b mod p = 19

Alice
Známé	Neznámé
p = 23
g = 5
a = 6	b
A = 5^a mod 23
A = 5⁶ mod 23 = 8
B = 19
s = B^a mod 23
s = 19⁶ mod 23 = 2

Bob
Známé	Neznámé
p = 23
g = 5
b = 15	a
B = 5^b mod 23
B = 5¹⁵ mod 23 = 19
A = 8
s = A^b mod 23
s = 8¹⁵ mod 23 = 2

Eva
Známé	Neznámé
p = 23
g = 5
	a, b


A = 8, B = 19

	s

V příkladu je s tajný sdílený klíč, který je známý Alici a Bobovi, ale nikoliv Evě. Všimněte si, že Evě nepomůže spočítat AB, což je rovno g^{a + b} mod p.

Poznámka: Pro Alici by mělo být 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). Eva se může pokusit vybrat pár soukromého a veřejného klíče, který jí usnadní hledání Bobova soukromého klíče.

Provoz s více než dvěma účastníky

Diffieho-Hellmanova výměna klíčů není omezena jen na dva účastníky. Je tedy možné mít libovolný počet účastníků.

Pro představu mějme 3 komunikující uživatele: Alice, Bob a Carol.

zveřejní se parametry p a g
každá ze stran si vypočítá své privátní klíče a, b a c
Alice vypočítá g^a mod p a zašle Bobovi
Bob vypočítá (g^a)^b mod p = g^ab mod p a zašle Carol
Carol vypočítá (g^ab)^cmod p = g^abcmod p a nechá skryté
Bob vypočítá g^bmod p a zašle Carol
Carol vypočítá (g^b)^cmod p = g^bc mod p a zašle Alici
Alice vypočítá (g^bc)^a mod p = g^bca mod p = g^abc mod p a nechá skryté
Carol vypočítá g^c mod p a zašle Alici
Alice vypočítá (g^c)^a mod p = g^ca mod p a zašle Bobovi
Bob vypočítá (g^ca)^b mod p = g^cab mod p = g^abc mod p a nechá skryté

Případný útočník odposlouchávající komunikaci může zaznamenat všechny mezivýpočty, ale není schopný vypočítat klíče a, b a c a konečné výsledky g^abc mod p.

Pro rozšíření tohoto mechanismu pro větší skupiny, je nutné dodržovat dva základní principy:

Začít výpočet vždy s klíčem g tak, že každý účastník ve výpočtu použije svůj privátní exponent právě jednou (první takové umocňování dává vlastní veřejný klíč účastníka).
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. Tudíž každý uživatel musí znát kopii společného klíče, kterou získá jedině tím, že aplikuje svůj privátní klíč jako poslední.

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ů). Ovšem toto řešení vyžaduje, aby každý účastník provedl n modulárních umocnění.

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 log₂(n) + 1 za použití přístupu rozděl a panuj. zde je příklad s osmi účastníky:

Účastníci A, B, C a D, každý jedním modulárním umocněním získají g^abcd, které zašle E, F, G a H od nichž získají g^efgh.
Účastníci A a B každý jedním modulárním umocněním získají g^efghab, které zašle C a D od nichž získají g^efghcd (stejný postup proběhne i ve skupině EFGH).
Účastník A jedním modulárním umocněním získá g^efghcda, které zašle B a od něj získá g^efghcdb (stejný postup proběhne i ve skupině CD, EF a GH).
Účastník A jedním modulárním umocněním získá g^efghcdba = g^abcdefgh (mezi tím B, C, D, E, F, G a H udělají to samé).

Jakmile je tato operace dokončena všichni účastníci budou mít tajný g^abcdefgh, ale každý účastník provede jen čtyři modulární umocnění místo osmi v kruhovém uspořádání.

V tomto článku byl použit překlad textu z článku Diffie–Hellman key exchange na anglické Wikipedii.

Reference

↑ DIFFIE, Whitfield; HELLMAN, Martin E. New Directions in Cryptography. IEEE Transactions on Information Theory. November 1976, s. 644–654. Dostupné v archivu pořízeném z originálu dne 2014-11-29. DOI 10.1109/TIT.1976.1055638.
↑ WONG, David. Google Books. Real World Cryptography. [s.l.]: Manning, 2021. Dostupné online. ISBN 9781617296710. Kapitola Key exchange standards.

Související články

SSL – Zabezpečené spojení
RSA – Bezpečnost RSA
PKI – Infrastruktura veřejných klíčů
Diffieho-Hellmanův protokol s využitím eliptických křivek

Externí odkazy

Obrázky, zvuky či videa k tématu Diffieho-Hellmanova výměna klíčů na Wikimedia Commons

[Diffie_1976-1] DIFFIE, Whitfield; HELLMAN, Martin E. New Directions in Cryptography. IEEE Transactions on Information Theory. November 1976, s. 644–654. Dostupné v archivu pořízeném z originálu dne 2014-11-29. DOI 10.1109/TIT.1976.1055638.

[2] WONG, David. Google Books. Real World Cryptography. [s.l.]: Manning, 2021. Dostupné online. ISBN 9781617296710. Kapitola Key exchange standards.

[1]

[2]