Přeskočit na obsah

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

Z Wikipedie, otevřené encyklopedie

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.

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

[editovat | editovat zdroj]
Diffieho-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é). Vždy vznikne stejná výsledná barva, protože je do výchozí barvy přimícháno pokaždé stejné množství barev, které případný útočník nezná (tudíž nezná ani výslednou barvu).
Diffie-Hellman protokol
Alice Bob Veřejnost
Výpočty Tajné Výpočty Tajné Veřejné
a b p, g
A
B
s = 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 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 . Ten zveřejní.
  • Druhý účastník si zvolí číslo b jako soukromý klíč a spočítá veřejný klíč B, .
  • Své veřejné klíče zveřejní
  • Nyní první účastník může spočítat , druhý účastník může spočítat .
  • Čísla s, s' jsou totožná, neboť .

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

[editovat | editovat zdroj]

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ě.

  1. 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).
  2. Alice vybere tajné celé číslo a = 4, pak pošle Bobovi A = ga mod p
    • A = 54 mod 23 = 4 (v tomto příkladu mají A i a stejnou hodnotu 4, ale obvykle tomu tak není)
  3. Bob vybere tajné celé číslo b = 3, pak pošle Alici B = gb mod p
    • B = 53 mod 23 = 10
  4. Alice vypočítá s = Ba mod p
    • s = 104 mod 23 = 18
  5. Bob vypočítá s = Ab mod p
    • s = 43 mod 23 = 18
  6. Alice a Bob nyní sdílejí tajemství (číslo 18).

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

Konkrétněji:

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. 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í

[editovat | editovat zdroj]

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 = ga mod p = 8
  • B, veřejný klíč Boba, známý Alici, Bobovi a Evě: B = gb mod p = 19
Alice
Známé Neznámé
p = 23
g = 5
a = 6 b
A = 5a mod 23
A = 56 mod 23 = 8
B = 19
s = Ba mod 23
s = 196 mod 23 = 2
Bob
Známé Neznámé
p = 23
g = 5
b = 15 a
B = 5b mod 23
B = 515 mod 23 = 19
A = 8
s = Ab mod 23
s = 815 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 ga + 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

[editovat | editovat zdroj]

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.

  1. zveřejní se parametry p a g
  2. každá ze stran si vypočítá své privátní klíče a, b a c
  3. Alice vypočítá ga mod p a zašle Bobovi
  4. Bob vypočítá (ga)b mod p = gab mod p a zašle Carol
  5. Carol vypočítá (gab)c mod p = gabc mod p a nechá skryté
  6. Bob vypočítá gb mod p a zašle Carol
  7. Carol vypočítá (gb)c mod p = gbc mod p a zašle Alici
  8. Alice vypočítá (gbc)a mod p = gbca mod p = gabc mod p a nechá skryté
  9. Carol vypočítá gc mod p a zašle Alici
  10. Alice vypočítá (gc)a mod p = gca mod p a zašle Bobovi
  11. Bob vypočítá (gca)b mod p = gcab mod p = gabc 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 gabc 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 log2(n) + 1 za použití přístupu rozděl a panuj. zde je příklad s osmi účastníky:

  1. Účastníci A, B, C a D, každý jedním modulárním umocněním získají gabcd, které zašle E, F, G a H od nichž získají gefgh.
  2. Účastníci A a B každý jedním modulárním umocněním získají gefghab, které zašle C a D od nichž získají gefghcd (stejný postup proběhne i ve skupině EFGH).
  3. Účastník A jedním modulárním umocněním získá gefghcda, které zašle B a od něj získá gefghcdb (stejný postup proběhne i ve skupině CD, EF a GH).
  4. Účastník A jedním modulárním umocněním získá gefghcdba = gabcdefgh (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ý gabcdefgh, 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.

  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. 

Související články

[editovat | editovat zdroj]

Externí odkazy

[editovat | editovat zdroj]