Теория чисел
Post-Quantum Cryptography
Harvest-now-decrypt-later: спецслужбы уже сейчас записывают зашифрованный интернет-трафик, ожидая квантовых компьютеров. Зашифрованные сегодня государственные секреты, медицинские данные, финансовые транзакции - всё это может быть дешифровано через 10-15 лет. Именно поэтому NIST начал конкурс PQC в 2016 году и стандартизировал Kyber в 2022 году. Миграция уже идёт - Chrome, Firefox, Cloudflare.
- **Google Chrome 116+ (2023):** X25519Kyber768 по умолчанию для TLS 1.3; защищает от harvest-now атак
- **Cloudflare:** развернул Kyber768 в production 2023; обслуживает ~20% интернет-трафика
- **NIST FIPS 203/204/205 (2024):** Kyber (ML-KEM), Dilithium (ML-DSA), SPHINCS+ (SLH-DSA) - официальные стандарты
Предварительные знания
Алгоритм Шора: конец RSA и DH
В 1994 году Питер Шор показал: квантовый компьютер факторизует n = p·q за полиномиальное время. Это разрушает RSA, DH и ECDH одним ударом. Не «через 50 лет» - теоретически, сейчас, при достаточно мощном квантовом компьютере.
**Алгоритм Шора:** Факторизует n за O(log³ n) квантовых операций, используя квантовое преобразование Фурье для поиска периода функции f(x) = aˣ mod n. **Что ломает:** - RSA: факторизует n = p·q → вычисляет d - DH в ℤₚ*: решает DLP за O(log³ p) - ECDH/ECDSA: решает ECDLP за O(log³ p) **Что НЕ ломает:** - AES-256: алгоритм Гровера снижает стойкость с 2²⁵⁶ до 2¹²⁸ - достаточно - SHA-256/SHA-3: Гровер удваивает требуемую длину - Решёточная криптография: нет квантового ускорения для LWE/SVP **Текущее состояние:** IBM Eagle (2021) - 127 кубит; для атаки RSA-2048 нужно ~4000 «стабильных» кубит.
Harvest-now-decrypt-later атака: злоумышленники уже сейчас сохраняют зашифрованный трафик, чтобы дешифровать его когда квантовые компьютеры станут достаточно мощными. Данные с длительным сроком хранения (гос. тайны, медкарты, юр. документы) нужно защищать PQC уже сейчас.
Алгоритм Гровера ускоряет перебор с O(2ⁿ) до O(2^(n/2)). Как это влияет на AES-128?
Задачи на решётках: SVP и LWE
Решётки - дискретные подгруппы ℝⁿ. Кратчайший вектор в решётке вычислить сложно - и классически, и квантово. Именно эта сложность лежит в основе post-quantum криптографии.
**Решётка (lattice) в ℝⁿ:** L = {Σ aᵢ·bᵢ : aᵢ ∈ ℤ} - целочисленные комбинации базисных векторов b₁,...,bₙ. **SVP (Shortest Vector Problem):** найти кратчайший ненулевой вектор в решётке. - Сложность: NP-hard в общем случае - Квантовое ускорение: минимальное (не более квадратного корня) **LWE (Learning With Errors):** по матрице A ∈ ℤqⁿˣᵐ и вектору b = As + e (s - секрет, e - малый шум) - найти s. - Сложность: эквивалентна SVP в наихудшем случае (теорема Регева) - Ring-LWE: та же задача в кольце R_q = ℤq[x]/(xⁿ+1) **Module-LWE:** «промежуточный» вариант - используется в Kyber.
Теорема Регева (2005): LWE так же сложна, как SVP в наихудшем случае. Это означает: если кто-то взломает LWE, он взломает и SVP. Поскольку SVP считается действительно сложной задачей (и классически, и квантово), безопасность LWE-криптосистем теоретически обоснована.
В чём принципиальное отличие LWE от обычного решения системы линейных уравнений?
CRYSTALS-Kyber и CRYSTALS-Dilithium
В 2022 году NIST завершил конкурс post-quantum стандартов (начат в 2016 году). Победители: CRYSTALS-Kyber (шифрование/KEM) и CRYSTALS-Dilithium (подписи). Оба основаны на Module-LWE в кольце ℤq[x]/(xⁿ+1).
**CRYSTALS-Kyber (FIPS 203):** - Тип: KEM (Key Encapsulation Mechanism) - Задача: Module-LWE в R_q = ℤ_3329[x]/(x^256+1) - Уровни: Kyber-512 (128 бит), Kyber-768 (192 бит), Kyber-1024 (256 бит) - Публичный ключ: ~800 байт (Kyber-512); шифротекст: ~768 байт **CRYSTALS-Dilithium (FIPS 204):** - Тип: цифровая подпись - Задача: Module-LWE + Module-SIS - Подпись: ~2420 байт (Dilithium2) **Гибридное развёртывание:** - TLS 1.3: X25519Kyber768 = ECDH + Kyber768 - Уже в Chrome 116+ (2023), Firefox 119+
| Схема | Тип | Задача | Квантовая стойкость | Размер ключа |
|---|---|---|---|---|
| RSA-2048 | Шифрование | Факторизация | Нет (Шор) | 256 байт |
| ECDH P-256 | KEM | ECDLP | Нет (Шор) | 64 байта |
| Kyber-768 | KEM | Module-LWE | Да (~178 бит) | 1184 байта |
| Dilithium3 | Подпись | Module-LWE+SIS | Да (~128 бит) | 1952 байта |
| SPHINCS+ | Подпись | Хеш-функции | Да (консервативно) | ~8 КБ |
Почему в TLS 1.3 используют X25519Kyber768 (гибрид), а не только Kyber768?
Ключевые идеи
- **Алгоритм Шора:** факторизует n за O(log³ n) квантовых операций; ломает RSA, DH, ECDH
- **SVP/LWE:** сложные задачи на решётках; квантовое ускорение минимально; основа PQC
- **Kyber (FIPS 203):** KEM на Module-LWE; ключи ~1-2 КБ; уже в Chrome/Firefox
- **Миграция:** harvest-now-decrypt-later требует начала перехода немедленно; рекомендуется гибрид X25519+Kyber
Связанные темы
Post-quantum криптография строится на алгебраической теории чисел:
- Алгебраическая теория чисел — Kyber работает в кольце целых ℤq[x]/(xⁿ+1) - кольцо целых циклотомического поля
- Числа в криптографии — RSA и DH - схемы, которые заменяют post-quantum алгоритмы
- Number Theory в CS — NTT (Number Theoretic Transform) - ключевая оптимизация умножения полиномов в Kyber
Вопросы для размышления
- Алгоритм Шора требует ~4000 «идеальных» кубит для атаки RSA-2048. Сколько физических кубит нужно при текущем уровне ошибок (~0.1% на ворота) с кодом коррекции ошибок?
- LWE с шумом e=0 просто решается. Как ровно наличие малого шума переводит задачу из P в предположительно экспоненциальную?
- Hybrid TLS: X25519+Kyber768. Как именно объединяются два общих секрета в один ключ? Почему этот «комбинированный» подход безопасен, даже если одна из схем сломана?