// 03 · Post-kvantová kryptografie · Zápočet ZKR 2026

CRYSTALS-
Kyber

Standard: NIST FIPS 203 (ML-KEM)
Vznik: 2017 (standard 2024)
Základ: Mřížky (lattices) · MLWE
Status: Kvantově odolný

První post-kvantový standard NIST pro výměnu klíčů. Odolný vůči útokům kvantových počítačů (Shorův algoritmus). Bezpečnost stojí na výpočetní složitosti problému mřížek — Module Learning With Errors (MLWE).

// Motivace

Proč potřebujeme
post-kvantovou kryptografii?

Klasické asymetrické šifry (RSA, ECC) stojí na problémech, které jsou pro klasické počítače výpočetně náročné — faktorizace velkých čísel nebo diskrétní logaritmus. Shorův algoritmus (1994) tyto problémy řeší na kvantovém počítači v polynomiálním čase — tedy exponenciálně rychleji.

AlgoritmusTypKlasický počítačKvantový počítač
RSA-2048AsymetrickýBezpečný✗ Prolomen (Shorův alg.)
ECC-256AsymetrickýBezpečný✗ Prolomen (Shorův alg.)
AES-128SymetrickýBezpečný△ Oslaben (Groverův alg. → AES-64)
AES-256SymetrickýBezpečný✓ Bezpečný (Grover → AES-128)
ML-KEM (Kyber)Post-kvantový KEMBezpečný✓ Bezpečný (MLWE)
„Harvest now, decrypt later": Útočníci dnes sbírají zašifrovaná data s cílem je dešifrovat až budou mít k dispozici dostatečně výkonný kvantový počítač. Proto je migrace na post-kvantové algoritmy naléhavá i bez existujícího kvantového počítače.
// Historie

Od soutěže NIST
ke globálnímu standardu

2016
NIST vyhlašuje soutěž o post-kvantové kryptografické standardy. Přihlásilo se 69 kandidátů z celého světa.
2017
Tým vědců (Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John Schanck, Gregor Seiler, Damien Stehlé) podává návrh CRYSTALS-Kyber.
2022
NIST vybírá Kyber jako primárního kandidáta pro výměnu klíčů po třech kolech intenzivní kryptoanalýzy.
Srpen 2024
NIST publikuje FIPS 203 — ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism). První finální post-kvantový standard v historii.
Dnes
Google Chrome, Apple, Cloudflare a AWS již nasazují ML-KEM v TLS handshake. Hybridní režim: klasické + post-kvantové šifrování zároveň.
// Teorie

LWE problém a mřížky

Kyber stojí na Module Learning With Errors (MLWE) problému. Jde o generalizaci LWE problému, který formuloval Oded Regev v roce 2005. Myšlenka je jednoduchá: je těžké rozlišit náhodná data od dat s malou chybou.

LWE problém — základní princip
Dáno: matice A (veřejná, náhodná) a vektor b = A·s + e
Tajné: vektor s (secret) a malý chybový vektor e (error)
Problém: najdi s znaje pouze A a b
Bez znalosti e je nalezení s výpočetně ekvivalentní problému nejkratšího vektoru v mřížce (SVP) — pro který neexistuje efektivní kvantový algoritmus.

Kyber je KEM — Key Encapsulation Mechanism, ne klasická šifra. Slouží k bezpečné výměně symetrického klíče (shared secret) mezi dvěma stranami. Tento klíč pak použijí pro symetrické šifrování (např. AES).

1
Generování klíčů — Alice
Alice vygeneruje dvojici klíčů: veřejný klíč (pk) a soukromý klíč (sk). Veřejný klíč obsahuje matici A a vektor b = A·s + e.
pk = (A, b = A·s + e)  |  sk = s
2
Zapouzdření klíče — Bob
Bob použije Alicin veřejný klíč k zapouzdření náhodného sdíleného tajemství. Výsledkem je ciphertext (c) a shared secret (K).
(c, K) = Encapsulate(pk)
3
Rozbalení klíče — Alice
Alice použije svůj soukromý klíč k rozbalení stejného sdíleného tajemství z ciphertextu. Obě strany teď mají stejný K — bez přenosu K po síti!
K = Decapsulate(sk, c)  |  K = K_Bob ✓
4
Symetrické šifrování
Sdílené tajemství K použijí obě strany jako klíč pro AES nebo ChaCha20. Kyber sám o sobě data nešifruje — jen bezpečně dohodne klíč.
AES-256-GCM(key=K, plaintext=data)
// Vizualizace

Jak to funguje v praxi

Dvě vizualizace: animovaný KEM protokol s reálnými daty která letí po síti, a interaktivní ukázka proč je LWE problém těžký.

KEM protokol — Pat & Mat
Sleduj co přesně letí po síti mezi Patem a Matem — a co z toho vidí Eva (útočník uprostřed). Klikni Spustit a sleduj krok po kroku.
Rychlost:
🧑
Pat
Příjemce
Ví:
→
pk
🕵️
Eva
Útočník
←
ct
👨‍🦱
Mat
Odesílatel
Ví:
Krok:
LWE — zkus prolomit
Tohle je přesně ten problém na kterém stojí Kyber. Máš veřejnou matici A a vektor b = A·s + e. Tajné jsou s (soukromý klíč) a e (malý šum). Zkus uhádnout s.
// Implementace

Interaktivní LWE demo

Kyber pracuje s polynomy v okruhu Zq[x]/(xn+1), kde q=3329 a n=256. Pro přehlednost demonstrujeme LWE princip na malých číslech — zmenšená verze která zachovává všechny matematické vlastnosti originálu.

LWE — generování klíčů (zjednodušené)
Modul q = 17 (malé prvočíslo pro přehlednost, Kyber používá q = 3329). Matice A je veřejná, vektor s je soukromý klíč, e je malá náhodná chyba.
KEM simulace — výměna klíče
Simulace celého Kyber KEM protokolu se zjednodušenými parametry. Ukazuje jak Bob zapouzdří shared secret a Alice ho rozbalí.
// Zápočtová ukázka

Šifrování textu pomocí Kyber + AES

Kyber samotný je KEM — nevyprodukuje ciphertext zprávy, ale sdílený klíč. Ten předáme AES-256-GCM pro skutečné šifrování. Toto je přesně to co dělá TLS 1.3 s ML-KEM v praxi.

Hybridní šifrování: ML-KEM + AES-256-GCM
Simulace hybridního schématu. Kyber KEM dohodne sdílený klíč, AES-GCM text zašifruje. Při špatném soukromém klíči dešifrování selže — sdílený klíč se nebude shodovat.
Proč špatný klíč selže úplně jinak než u Vigenèra?
U Vigenèra špatný klíč produkuje nečitelný ale deterministický text. U Kyber + AES-GCM špatný soukromý klíč způsobí jiný shared secret → jiný AES klíč → GCM autentizační tag nesedí → dešifrování je odmítnuto celé, žádný výstup. AES-GCM garantuje integritu — buď vše správně, nebo nic.
// Bezpečnost

Proč kvantové počítače
Kyber neprolomí

Shorův algoritmus funguje na problémech s periodickou strukturou (faktorizace, diskrétní logaritmus). Problém nejkratšího vektoru v mřížce (SVP) žádnou takovou strukturu nemá — nejlepší kvantové algoritmy pro SVP jsou jen kvadraticky rychlejší než klasické, ne exponenciálně.

Bezpečnostní parametry ML-KEM
ML-KEM-512:   n=256, k=2, q=3329   → NIST úroveň 1 (≈ AES-128)
ML-KEM-768:   n=256, k=3, q=3329   → NIST úroveň 3 (≈ AES-192)
ML-KEM-1024: n=256, k=4, q=3329   → NIST úroveň 5 (≈ AES-256)
k = počet modulů (rozměr), n = stupeň polynomu, q = modul okruhu
Pravidla bezpečného použití ML-KEM:
1. Nikdy nepoužívej stejný klíčový pár pro více než jednu výměnu (forward secrecy).
2. Kombinuj s klasickým algoritmem (hybridní režim: X25519 + ML-KEM-768) — obrana proti chybám v implementaci.
3. Shared secret musí projít KDF (Key Derivation Function) před použitím jako AES klíč.
4. Používej prověřené knihovny — liboqs (Open Quantum Safe), BoringSSL, libsodium (brzy).
Kde se ML-KEM nasazuje dnes (2024–2026):
Google Chrome 124+ (hybridní X25519+ML-KEM-768 v TLS) · Apple iOS 17.4+ (iMessage PQ3) · Cloudflare (post-quantum TLS) · AWS KMS · Signal Protocol (PQXDH) · SSH OpenSSH 9.0+