# Diffie-Hellman: výměna klíčů

Máš linku, kterou někdo odposlouchává. Vidí každý bajt, který po ní pošleš, oběma směry. Nikdy předtím jsi s protistranou nemluvil, nemáte žádné společné heslo.

**Domluvte se na tajném klíči.**

Zní to jako trik s podmínkou, která se nedá splnit. Whitfield Diffie a Martin Hellman ji v roce 1976 splnili a je to pravděpodobně nejdůležitější jednotlivý nápad v celé praktické kryptografii. Bez něj by HTTPS nemohlo existovat v podobě, jakou znáš — každý web by s tebou musel předem sdílet heslo.

Předpokládá to [stavební kameny](Sifrovani-zaklady) a navazuje na [veřejný a soukromý klíč](Verejny-a-soukromy-klic).

## Nejdřív intuice: míchání barev

Klasické přirovnání, které funguje překvapivě přesně:

1. Alice a Bob se veřejně dohodnou na společné barvě — třeba **žluté**. Odposlouchávající ji vidí.
2. Každý si potají vybere **tajnou barvu**. Alice červenou, Bob modrou. Nikomu je neřeknou.
3. Každý smíchá žlutou se svou tajnou a **výsledek pošle veřejně**. Alice pošle oranžovou, Bob zelenou. Odposlouchávající vidí obě.
4. Alice přimíchá do Bobovy zelené svou červenou. Bob přimíchá do Aliciny oranžové svou modrou. **Oba dostanou stejnou hnědou** — žlutá + červená + modrá.

Odposlouchávající zná žlutou, oranžovou a zelenou. Hnědou z toho nedostane, protože **z namíchané barvy nejde vytáhnout, co v ní bylo**. Mixování je snadné, rozmixování ne.

Tohle přirovnání zachycuje úplně všechno podstatné. Zbytek stránky jen ukazuje, co je tou barvou doopravdy.

## Ta samá věc s čísly

Míchání barev je ve skutečnosti **umocňování ve zbytkové aritmetice**. Klíčová vlastnost, na které to celé stojí:

```
(g^a)^b  =  g^(a·b)  =  (g^b)^a
```

Nezáleží na pořadí. Když Alice umocní Bobovo číslo na svůj tajný exponent a Bob Alicino na svůj, **dostanou totéž**. A veřejnou část přitom nikdo nemusí umět rozložit zpátky.

Zbytek po dělení (`mod p`) je tam proto, aby se čísla nerozrostla do nekonečna a hlavně aby zmizela jakákoliv souvislost mezi velikostí vstupu a výstupu.

### Postup

Alice a Bob se veřejně dohodnou na dvou číslech: **prvočíslu `p`** a **generátoru `g`**. Ani jedno není tajné, obojí bývá pevně dané standardem.

```mermaid
sequenceDiagram
    participant A as Alice
    participant E as Odposlech
    participant B as Bob
    Note over A,B: veřejně známé: p, g
    A->>A: zvolí tajné a
    B->>B: zvolí tajné b
    A->>B: A = g^a mod p
    Note over E: vidí A
    B->>A: B = g^b mod p
    Note over E: vidí B
    A->>A: s = B^a mod p
    B->>B: s = A^b mod p
    Note over A,B: obě strany mají totéž s
    Note over E: zná p, g, A, B — a nic z toho nepomůže
```

### Spočítej si to

S malými čísly, aby to šlo na papír. `p = 23`, `g = 5`.

**Alice** si vybere tajné `a = 6`:

```
A = 5^6 mod 23 = 15625 mod 23 = 8
```

**Bob** si vybere tajné `b = 15`:

```
B = 5^15 mod 23 = 30517578125 mod 23 = 19
```

Vymění si `8` a `19`. Odposlouchávající je vidí.

**Alice** spočítá:

```
s = 19^6 mod 23 = 2
```

**Bob** spočítá:

```
s = 8^15 mod 23 = 2
```

Oba mají **2**, aniž by to číslo kdokoliv poslal po drátě.

Ověř si to sám:

```bash
python3 -c "p=23; g=5; a=6; b=15;
A=pow(g,a,p); B=pow(g,b,p);
print(A, B, pow(B,a,p), pow(A,b,p))"
# 8 19 2 2
```

V reálu je `p` dlouhé 2048 až 4096 bitů, `a` a `b` jsou náhodná čísla podobné velikosti a výsledek se prožene [KDF](Sifrovani-zaklady#kdf-jak-se-z-jednoho-tajemství-udělá-víc-klíčů), protože surové DH tajemství není rovnoměrně náhodné.

## Proč to odposlech neprolomí

Útočník zná `p`, `g`, `g^a mod p` a `g^b mod p`. Chce `g^(ab) mod p`.

Nejpřímější cesta je z `g^a mod p` dopočítat `a`. Tomu se říká **problém diskrétního logaritmu** a nikdo pro něj nezná rychlý postup. U 2048bitového prvočísla by nejlepší známý algoritmus — síto v číselném tělese — potřeboval zhruba 2¹¹² operací. To není dlouhé čekání, to je mimo možnosti lidstva.

Zajímavý detail: **není dokázáno, že jinak než přes diskrétní logaritmus to nejde.** Předpoklad, že z `g^a` a `g^b` nikdo nedostane `g^ab`, se jmenuje *computational Diffie-Hellman assumption* a je to předpoklad, ne věta. Za padesát let se ho nepodařilo vyvrátit, což je nejsilnější důkaz, jaký máme.

### Proč je to snadné dopředu a těžké zpátky

`5^6 mod 23` spočítáš rychlým umocňováním na pár násobení, i když je exponent obrovský — u 2048bitového exponentu je to nízké tisíce operací.

Opačným směrem ale výsledek **skáče chaoticky**. Mocniny pětky modulo 23 jdou po řadě `5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1`. Žádný trend, žádná blízkost, žádné „přihořívá". Nemůžeš se k odpovědi propracovat postupně, můžeš jen zkoušet. To je celý rozdíl mezi lehkým a těžkým směrem.

## Eliptické křivky: totéž, jen účinněji

Moderní protokoly nepoužívají čísla modulo prvočíslo, ale **body na eliptické křivce**. Princip je identický, jen se místo umocňování opakovaně sčítá bod sám se sebou:

| | Klasický DH | ECDH |
|---|---|---|
| Veřejná dohoda | prvočíslo `p`, generátor `g` | křivka a základní bod `G` |
| Tajné | číslo `a` | číslo `a` |
| Veřejné | `g^a mod p` | bod `a·G` |
| Sdílené | `g^ab mod p` | bod `a·b·G` |
| Velikost pro 128bitovou úroveň | **3072 bitů** | **256 bitů** |

Ten poslední řádek je celý důvod přechodu. Na křivkách nikdo nenašel nic lepšího než obecné metody, které trvají odmocninu z velikosti skupiny — proto stačí dvanáctkrát kratší klíče při stejné bezpečnosti. Podrobněji v [asymetrické kryptografii](Verejny-a-soukromy-klic#proč-jsou-křivky-lepší).

### X25519

Konkrétní podoba ECDH, kterou dnes v drtivé většině potkáš. Křivka Curve25519, veřejný klíč **32 bajtů**, sdílené tajemství 32 bajtů, jedna operace zabere desítky mikrosekund.

Používá ji [TLS 1.3](TLS-handshake), [SSH](SSH), [WireGuard](WireGuard), Signal, `age`, Tor.

Proč zrovna tahle:

**Nemá záludné vstupy.** U křivek NIST musí implementace kontrolovat, jestli přijatý bod na křivce vůbec leží — kdo to zapomene, dostane *invalid curve attack* a útočník mu po částech vytáhne soukromý klíč. X25519 je navržená tak, že jakýchkoliv 32 bajtů je přijatelný vstup a nic se tím nerozbije.

**Sama drží konstantní čas.** Používá Montgomeryho žebřík, který dělá stejnou práci bez ohledu na bity klíče. Nedá se z ní tedy měřením času nic odvodit.

**Ořezává klíč automaticky.** Soukromý klíč si sama upraví (nastaví a zruší konkrétní bity, tzv. *clamping*) tak, aby padl do bezpečné části skupiny. Programátor to nemůže pokazit.

Jediná věc, kterou implementace hlídat musí: **odmítnout sdílené tajemství, které vyjde jako samé nuly**. Toho lze dosáhnout posláním speciálního bodu a TLS i SSH v takovém případě spojení ukončí.

## Dopředné utajení

Tohle je důvod, proč se dnes DH používá i tam, kde by šlo něco jednoduššího.

Do TLS 1.2 se běžně používal jiný postup: klient vymyslel náhodný klíč a **zašifroval ho veřejným klíčem serveru** z certifikátu. Fungovalo to, ale mělo zásadní vadu:

> Kdo si dnes uloží zašifrovaný provoz a za pět let se dostane k soukromému klíči serveru, dešifruje **zpětně všechno, co si uložil**.

Klíč serveru je jeden a dlouhodobý. Uniknout může průnikem, soudním příkazem, ukradenou zálohou nebo chybou typu Heartbleed.

Diffie-Hellman to řeší tím, že si obě strany vygenerují **nová `a` a `b` pro každé spojení** a po jeho skončení je zahodí. Tomu se říká **ephemeral** — v názvech šifer to `E` na konci (`ECDHE`, `DHE`).

Únik dlouhodobého klíče serveru pak umožní **vydávat se za server od té chvíle dál**, ale **nedešifruje ani jedno minulé spojení**. Ta dočasná tajemství už neexistují nikde na světě.

To je dopředné utajení (*forward secrecy*) a **TLS 1.3 ho vyžaduje povinně**. Statické varianty byly z protokolu odstraněny, ne jen odrazovány.

Praktický dopad na tebe: [úložiště session ticketů v nginxu](TLS-a-HTTPS#verze-a-šifry) dopředné utajení dokáže zrušit, když se klíče k ticketům nerotují — proto to `ssl_session_tickets off`.

## Bez ověření je to k ničemu

Nejdůležitější odstavec na téhle stránce.

**Diffie-Hellman neříká, s kým jsi se domluvil.** Domluvíš se s tím, kdo ti odpoví. Když sedí uprostřed útočník, udělá DH zvlášť s tebou a zvlášť se serverem:

```mermaid
sequenceDiagram
    participant K as Klient
    participant M as Útočník
    participant S as Server
    K->>M: g^a
    M->>K: g^m1
    M->>S: g^m2
    S->>M: g^b
    Note over K,M: klíč 1
    Note over M,S: klíč 2
    K->>M: šifrováno klíčem 1
    M->>M: dešifruje, přečte, přešifruje
    M->>S: šifrováno klíčem 2
```

Obě strany mají dokonalé šifrování. Útočník vidí všechno a může to i měnit. Ani jedna strana nic nepozná, protože **z pohledu matematiky proběhlo všechno správně**.

Řešení je vždycky stejné: **jedna strana musí svou část podepsat klíčem, který ta druhá umí ověřit nezávisle.**

| Protokol | Čím se to ověří |
|---|---|
| **TLS** | server podepíše průběh handshake klíčem z [certifikátu](TLS-a-HTTPS), ten ověří [CA](Certifikaty-a-Lets-Encrypt) |
| **SSH** | server podepíše výsledek výměny **host keyem**, ten máš v `known_hosts` |
| **WireGuard** | veřejné klíče peerů jsou napevno v konfiguraci, cizí se ignoruje |
| **Signal** | dlouhodobý identifikační klíč a bezpečnostní kód k porovnání |

**Tady je pak celý smysl certifikátů.** Nešifrují nic. Existují výhradně proto, aby výměna klíčů měla ke komu být připoutaná.

A odtud plyne i to, proč je varování o neplatném certifikátu vážná věc a ne otravný dialog. Znamená přesně: *dohoda na klíči proběhla, ale nemám čím ověřit, s kým.*

## Parametry a jak se to lámalo v praxi

Klasický DH nefunguje s libovolnými čísly a historie na to bohatě doplatila.

**Slabé prvočíslo.** Když má `p−1` jen malé dělitele, dá se úloha rozložit na spoustu malých a vyřešit. Proto se používají *safe primes*, kde je `(p−1)/2` také prvočíslo.

**Logjam (2015).** Servery pořád podporovaly exportní 512bitové DH z devadesátých let. Útočník je uprostřed dokázal donutit ho použít a pak parametry během minut zlomil. Součástí téhož výzkumu bylo zjištění, že **8,4 % z milionu nejnavštěvovanějších HTTPS serverů sdílelo jeden jediný 1024bitový modul** — velká část práce na jeho zlomení se dá udělat jednou dopředu a pak už jednotlivá spojení padají rychle. To je práce pro státní rozpočet, ale ne pro sci-fi.

**Reakce.** RFC 7919 zavedlo pevně pojmenované skupiny (`ffdhe2048` až `ffdhe8192`) a **TLS 1.3 zakázalo vlastní parametry úplně**. Dnes si nemůžeš vybrat špatně, protože si nemůžeš vybrat.

Praktický důsledek pro tebe: pokud v konfiguraci nginxu ještě máš `ssl_dhparam`, je to relikt z doby TLS 1.2. U čistého TLS 1.3 nedělá nic. Když ho tam potřebuješ kvůli starším klientům, ať má aspoň 2048 bitů a **negeneruj si vlastní** — pojmenovaná skupina je stejně bezpečná a nedá se pokazit.

## Kde to uvidíš

### TLS 1.3

Klient **hádá dopředu**. Do prvního paketu rovnou přiloží `key_share` — svou veřejnou část pro skupinu, kterou předpokládá (dnes prakticky vždy X25519). Server odpoví svou částí a tím je výměna hotová během **jednoho kola**.

Kdyby klient hádal špatně, server pošle `HelloRetryRequest` s tím, kterou skupinu chce, a stojí to jedno kolo navíc. Proto je dobré nechat výchozí nastavení.

```bash
openssl s_client -connect example.cz:443 -tls1_3 </dev/null 2>&1 | grep -iE "negotiated|cipher"
# Negotiated TLS1.3 group: X25519MLKEM768
# New, TLSv1.3, Cipher is TLS_AES_256_GCM_SHA384
```

Podrobný rozbor je na [TLS handshake krok za krokem](TLS-handshake).

### SSH

Výměna probíhá hned po pozdravu, ještě před tím, než server ví, jaký uživatel se hlásí. Výsledek se hashuje do **exchange hash** a server ho podepíše svým host keyem.

```bash
ssh -Q kex                       # co tvůj klient umí
ssh -vv server 2>&1 | grep -i "kex:"
# kex: algorithm: mlkem768x25519-sha256
```

Viz [SSH do hloubky](SSH#výměna-klíčů).

### WireGuard

Nejzajímavější případ. WireGuard nedělá jednu výměnu, ale **čtyři DH operace v jednom handshake** (návrh Noise IK). Kombinuje dočasné klíče s dlouhodobými tak, že jedním postupem získá zároveň dopředné utajení **i** vzájemné ověření obou stran — žádné certifikáty, žádné podpisy.

Přidává k tomu vlastnost, kterou TLS nemá: **neznámému odesílateli neodpoví vůbec nic**. Kdo nezná tvůj veřejný klíč, nedostane od WireGuardu ani jeden bajt a z internetu ten port vypadá jako zavřený. Viz [WireGuard](WireGuard).

### Signal a šifrované chaty

Kde se druhá strana nemusí připojit ve stejnou chvíli, se používá **X3DH**: klíče se dopředu nahrají na server a příjemce provede svou půlku výměny až později. Na to navazuje **double ratchet**, který odvozuje nový klíč pro **každou jednotlivou zprávu** — únik jednoho klíče pak neodhalí ani zprávy předchozí, ani ty následující.

## Postkvantový posun

Shorův algoritmus na dostatečně velkém kvantovém počítači řeší diskrétní logaritmus efektivně. **To ukončí Diffie-Hellmana ve všech jeho podobách včetně eliptických křivek.**

Takový počítač neexistuje a nikdo neví, kdy bude. Problém je ale jinde: **provoz odposlechnutý dnes se dá dešifrovat později**. Kdo si dnes ukládá šifrovaná data, počká si. Proto se výměna klíčů migruje jako první, ještě než je hrozba reálná.

Řešením je **hybridní režim**: klasický X25519 se provede zároveň s postkvantovým mechanismem a obě tajemství se sloučí do jednoho klíče. Pro prolomení musí útočník zlomit **obě** části.

```
X25519MLKEM768  =  X25519 (klasické)  +  ML-KEM-768 (postkvantové)
```

Tohle už není budoucnost. Chrome a Firefox to zapnuly ve výchozím nastavení během roku 2024 a OpenSSH má postkvantovou výměnu jako výchozí od verze 9.0. Když se dnes podíváš, co ti server vyjednal, dost pravděpodobně tam uvidíš právě tuhle kombinaci — aniž bys cokoliv nastavoval.

Detaily na [postkvantové kryptografii](Postkvantova-kryptografie).

## Co si odnést

**DH umožní dohodu na tajemství přes veřejný kanál.** To je jeho jediný úkol.

**Neověřuje protistranu.** Bez podpisu z certifikátu nebo host keye je bezcenný.

**Dočasné klíče dávají dopředné utajení.** Proto `ECDHE` a proto TLS 1.3 nic jiného nedovolí.

**Křivky vyhrály.** X25519 se 32 bajty proti 3072bitovému klasickému DH.

**Parametry si nevybíráš a je to dobře.** Vlastní `dhparam` je dnes zbytečnost a v horším případě chyba.

**Postkvantová varianta už běží.** Nemusíš pro to nic dělat kromě aktualizací.

## Kam dál

- **[Veřejný a soukromý klíč](Verejny-a-soukromy-klic)** — druhá polovina asymetrické kryptografie
- **[TLS handshake krok za krokem](TLS-handshake)** — DH zasazený do skutečného protokolu
- **[SSH do hloubky](SSH)** — totéž z druhé strany
- **[WireGuard](WireGuard)** — čtyřnásobný DH bez certifikátů
- **[Postkvantová kryptografie](Postkvantova-kryptografie)** — co přijde po Diffie-Hellmanovi