Zobrazení zdroje stránky Diffieho–Hellmanova výměna klíčů

'''Diffieho-Hellmanova výměna klíčů''' (zkráceně '''D-H''') je [[Kryptografie|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á kryptografie|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 [[Autentizace|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]] [[Whitfield Diffie|Whitfieldem Diffiem]] a [[Martin Hellman|Martinem Hellmanem]], svou roli zde ovšem sehrál i Ralph Merkle, John Gill navrhl aplikování [[Diskrétní logaritmus|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 [[Government Communications Headquarters|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 ==
[[Soubor:Diffie-Hellman Key Exchange (cs).svg|rám|207x207px|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).]]
{| class="wikitable"
|+Diffie-Hellman protokol
! colspan="2" | Alice
! 
! colspan="2" | Bob
!
! Veřejnost

|-
! Výpočty
! Tajné
! 
! Výpočty
! Tajné
!
! Veřejné

|-
|
| align="center" | '''a'''
|
|
| align="center" | '''b'''
|
| align="center" | p, g

|-
| align="center" | <math>A \equiv g^a \mod p</math>
|  
| align="center" | →
| 
| 
| align="center" | →
| align="center" | A

|-
|
|
| align="center" | 
| align="center" | <math>B \equiv g^b \mod p</math>
|
| align="center" | →
| align="center" | B

|-
| align="center" | <math>s \equiv B^a \mod p</math>
| align="center" | → '''s'''
| align="center" | =
| align="center" | <math>s \equiv A^b \mod p</math>
| align="center" | → '''s'''
|
|
|}

Principiálně se problém opírá o složitost [[diskrétní logaritmus|výpočtu diskrétního logaritmu]].
* Jeden z účastníků komunikace zveřejní [[prvočíslo]] ''p'', tj. konečnou [[grupa|grupu]] <math>G=(Z_{p}^*; \cdot)</math> a generátor ''g'' této grupy, kde ''g'' je vybraný [[Primitivní kořen|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 <math display="inline">A = g^a \mod p</math>. Ten zveřejní.
* Druhý účastník si zvolí číslo b jako soukromý klíč a spočítá veřejný klíč B, <math display="inline">B = g^b \mod p</math>.
* Své veřejné klíče zveřejní
* Nyní první účastník může spočítat <math display="inline">s \equiv B^a \mod p</math>, druhý účastník může spočítat <math display="inline">s' \equiv A^b \mod p</math>.
* Čísla ''s'', ''s''' jsou totožná, neboť <math display="inline">s' = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p = (g^b)^a \mod p = B^a \mod p = s</math>.

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,<ref name="Diffie 1976">{{Cite journal|last1=Diffie|first1=Whitfield|last2=Hellman|first2=Martin E.|author-link2=Martin Hellman|date=November 1976|title=New Directions in Cryptography|url=http://ee.stanford.edu/%7Ehellman/publications/24.pdf|url-status=live|journal=[[IEEE Transactions on Information Theory]]|volume=22|issue=6|pages=644–654|doi=10.1109/TIT.1976.1055638|archive-url=https://web.archive.org/web/20141129035850/https://ee.stanford.edu/%7Ehellman/publications/24.pdf|archive-date=2014-11-29|author-link1=Whitfield Diffie|citeseerx=10.1.1.37.9720}}</ref> později vydaná jako ''Finite Field Diffie-Hellman'' v [[rfc:7919|RFC 7919]],<ref>{{cite book|title=Real World Cryptography|url=https://books.google.com/books?id=Qd5CEAAAQBAJ|chapter=Key exchange standards|last=Wong|first=David|publisher=Manning|year=2021|isbn=9781617296710|chapter-url=https://archive.today/20200921005545/https://freecontent.manning.com/key-exchange-standards/|via=Google Books}}</ref> 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é <span style="color:blue">modře</span> a tajné hodnoty <span style="color:red">červeně</span>.

# [[Alice a Bob]] veřejně souhlasí s použitím modulu ''<span style="color:blue">p</span>'' = 23 a základu ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span> (''g'' je [[primitivní kořen]] modulo 23).
# Alice vybere tajné celé číslo ''<span style="color:red">a</span>'' = 4, pak pošle Bobovi ''<span style="color:blue">A</span>'' = ''<span style="color:blue">g</span><sup><span style="color:red">a</span></sup>'' mod ''<span style="color:blue">p</span>''
#* ''<span style="color:blue">A</span>'' = <span style="color:blue">5</span><sup><span style="color:red">4</span></sup> mod <span style="color:blue">23</span> = <span style="color:blue">4</span> (v tomto příkladu mají ''<span style="color:blue">A</span>'' i ''<span style="color:red">a</span>'' stejnou hodnotu 4, ale obvykle tomu tak není)
# Bob vybere tajné celé číslo ''<span style="color:red">b</span>'' = 3, pak pošle Alici ''<span style="color:blue">B</span>'' = ''<span style="color:blue">g</span><sup><span style="color:red">b</span></sup>'' mod ''<span style="color:blue">p</span>''
#* ''<span style="color:blue">B</span>'' = <span style="color:blue">5</span><sup><span style="color:red">3</span></sup> mod <span style="color:blue">23</span> = <span style="color:blue">10</span>
# Alice vypočítá ''<span style="color:red">s</span>'' = ''<span style="color:blue">B</span><sup><span style="color:red">a</span></sup>'' mod ''<span style="color:blue">p</span>''
#* ''<span style="color:red">s</span>'' = <span style="color:blue">10</span><sup><span style="color:red">4</span></sup> mod <span style="color:blue">23</span> = <span style="color:red">18</span>
# Bob vypočítá ''<span style="color:red">s</span>'' = ''<span style="color:blue">A</span><sup><span style="color:red">b</span></sup>'' mod ''<span style="color:blue">p</span>''
#* ''<span style="color:red">s</span>'' = <span style="color:blue">4</span><sup><span style="color:red">3</span></sup> mod <span style="color:blue">23</span> = <span style="color:red">18</span>
# Alice a Bob nyní sdílejí tajemství (číslo 18).

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

:<math>{\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}</math>

Konkrétněji:

:<math>({\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}</math>

Pouze hodnoty ''a'' a ''b'' jsou drženy v tajnosti. Všechny ostatní hodnoty (''p'', ''g'', ''g<sup>a</sup>'' mod ''p'' a ''g<sup>b</sup>'' 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<sup>ab</sup>'' mod ''p'' = ''g<sup>ba</sup>'' mod ''p'' trvá extrémně dlouho, než se libovolným známým algoritmem nalezne pouze na základě znalosti ''p'', ''g'', ''g<sup>a</sup>'' mod ''p'' a ''g<sup>b</sup>'' 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<sup>a</sup>'' mod ''p''. Obtížnost tohoto řešení se nazývá [[Diskrétní logaritmus|problém diskrétního logaritmu]]. Výpočet ''g<sup>a</sup>'' 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 <span style="color:blue">modře</span> a tajné hodnoty <span style="color:red">červeně</span>. Eva zde odposlouchává – sleduje, co se posílá mezi [[Alice a Bob|Alicí a Bobem]], ale nemění obsah jejich komunikace.

* ''<span style="color:blue">g</span>'', veřejný základ (primitivní kořen) známý Alici, Bobovi a Evě: ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
* ''<span style="color:blue">p</span>'', veřejný modulus (prvočíslo) známý Alici, Bobovi a Evě: ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
* '''''<span style="color:red">a</span>''''', privátní klíč Alice, známý jen Alici: '''''<span style="color:red">a</span>''''' = '''<span style="color:red">6</span>'''
* '''''<span style="color:red">b</span>''''', privátní klíč Boba, známý jen Bobovi: '''''<span style="color:red">b</span>''''' = '''<span style="color:red">15</span>'''
* ''<span style="color:blue">A</span>'', veřejný klíč Alice, známý Alici, Bobovi a Evě: ''<span style="color:blue">A</span>'' = ''<span style="color:blue">g</span><sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>'' = <span style="color:blue">8</span>
* ''<span style="color:blue">B</span>'', veřejný klíč Boba, známý Alici, Bobovi a Evě: ''<span style="color:blue">B</span>'' = ''<span style="color:blue">g</span><sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>'' = <span style="color:blue">19</span>

{| border="0" cellspacing="0" cellpadding="2"
|-
| valign="top" |
{| class="wikitable"
|+ Alice
|- style="text-align:center;" 
! Známé
! Neznámé
|-
| ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
|
|-
| '''''<span style="color:red">a</span>''''' = '''<span style="color:red">6</span>'''
| '''''<span style="color:red">b</span>'''''
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">5</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span>
|
|-
| '''''<span style="color:blue">B</span>''''' = '''<span style="color:blue">19</span>'''
| 
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">B</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">19</span><sup>'''''<span style="color:red">6</span>'''''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|}
| valign="top" | 
{| class="wikitable"
|+ Bob
|- style="text-align:center;" 
! Známé
! Neznámé
|-
| ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
|
|-
| '''''<span style="color:red">b</span>''''' = '''<span style="color:red">15</span>'''
| '''''<span style="color:red">a</span>'''''
|-
| ''<span style="color:blue">B</span>'' = <span style="color:blue">5</span><sup>'''''<span style="color:red">b</span>'''''</sup> mod <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">B</span>'' = <span style="color:blue">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">19</span>
|
|-
| '''''<span style="color:blue">A</span>''''' = '''<span style="color:blue">8</span>'''
| 
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">A</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">8</span><sup>'''''<span style="color:red">15</span>'''''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|}
| valign="top" | 
{| class="wikitable"
|+ Eva
|- style="text-align:center;" 
! Známé
! Neznámé
|-
| ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
|
|-
|
| '''''<span style="color:red">a</span>''''', '''''<span style="color:red">b</span>'''''
|-
| &nbsp;
| &nbsp;
|-
| &nbsp;
| &nbsp;
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">8</span>, ''<span style="color:blue">B</span>'' = <span style="color:blue">19</span>
| 
|-
| &nbsp;
| &nbsp;
|-
|
| '''''<span style="color:red">s</span>'''''
|}
|}

V příkladu je '''''<span style="color:red">s</span>''''' tajný sdílený klíč, který je známý Alici a Bobovi, ale ''nikoliv'' Evě. Všimněte si, že Evě nepomůže spočítat ''<span style="color:blue">AB</span>'', což je rovno ''<span style="color:blue">g</span>''<sup>'''''<span style="color:red">a</span>''''' + '''''<span style="color:red">b</span>'''''</sup> mod <span style="color:blue">p</span>.

''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<sup>a</sup> mod p''' a zašle Bobovi
# Bob vypočítá '''(g<sup>a</sup>)<sup>b</sup> mod p = g<sup>ab</sup> mod p''' a zašle Carol
# Carol vypočítá '''(g<sup>ab</sup>)<sup>c </sup>mod p = g<sup>abc </sup>mod p''' a nechá skryté
# Bob vypočítá '''g<sup>b </sup>mod p''' a zašle Carol
# Carol vypočítá '''(g<sup>b</sup>)<sup>c </sup>mod p = g<sup>bc</sup> mod p''' a zašle Alici
# Alice vypočítá '''(g<sup>bc</sup>)<sup>a</sup> mod p = g<sup>bca</sup> mod p = g<sup>abc</sup> mod p''' a nechá skryté
# Carol vypočítá '''g<sup>c</sup> mod p''' a zašle Alici
# Alice vypočítá '''(g<sup>c</sup>)<sup>a</sup> mod p = g<sup>ca</sup> mod p''' a zašle Bobovi
# Bob vypočítá '''(g<sup>ca</sup>)<sup>b</sup> mod p = g<sup>cab</sup> mod p = g<sup>abc</sup> 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<sup>abc</sup> 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<sub>2</sub>(n) + 1''' za použití přístupu [[Rozděl a panuj (algoritmus)|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<sup>abcd</sup>''', které zašle E, F, G a H od nichž získají '''g<sup>efgh</sup>'''.
# Účastníci A a B každý jedním modulárním umocněním získají '''g<sup>efghab</sup>''', které zašle C a D od nichž získají '''g<sup>efghcd</sup>''' (stejný postup proběhne i ve skupině EFGH).
# Účastník A jedním modulárním umocněním získá '''g<sup>efghcda</sup>''', které zašle B a od něj získá '''g<sup>efghcdb</sup>''' (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<sup>efghcdba</sup> = g<sup>abcdefgh</sup>''' (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<sup>abcdefgh</sup>''', ale každý účastník provede jen čtyři modulární umocnění místo osmi v kruhovém uspořádání.

{{Překlad|en|Diffie–Hellman key exchange|638761349}}

== Reference ==
<references />

== Související články ==
* [[Secure Sockets Layer|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 ==
* {{Commonscat}}

{{Autoritní data}}

[[Kategorie:Kryptografie s veřejným klíčem]]