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

Z Wikipedie, otevřené encyklopedie
(Přesměrováno z Diffie-Hellman)
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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 společnost 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).
Diffieho-Hellmanův protokol
Alice Bob Veřejnost
Kalkulace Tajné Kalkulace 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, konečnou grupu G=(Z_{p}^*; \cdot) a generátor g této grupy.
  • 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 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, B = g^b \mod p.
  • Své veřejné klíče zveřejní
  • Nyní první účastník může spočítat s \equiv B^a \mod p, druhý účastník může spočítat s' \equiv A^b \mod p.
  • Čísla s, s' jsou totožná, neboť s' = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p = (g^b)^a \mod p = B^a \mod p = s.

Toto číslo s nemůže nikdo zjistit, třetí strana by musela tipovat čísla a, b a doufat, že správné číslo uhodne.

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 mezi-vý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.

Související články[editovat | editovat zdroj]