Криптография

Квантовая угроза криптографии

В 1994 году Питер Шор опубликовал алгоритм, теоретически ломающий RSA за полиномиальное время. Весь интернет использует RSA. Квантовые компьютеры становятся реальностью.

Google Willow 2024: 105 кубитов, квантовое превосходство в специализированных задачах - прогресс экспоненциальный
NIST 2024: три финальных post-quantum стандарта (ML-KEM, ML-DSA, SLH-DSA) - эра PQC началась
China Quantum Backbone: 2000 км QKD-сети между городами - квантовая криптография в продакшне
Harvest Now Decrypt Later: АНБ и другие спецслужбы предположительно собирают зашифрованный трафик уже сегодня

Алгоритм Шора

Алгоритм Шора 1994 года решает задачу факторизации за полиномиальное время O((log N)^3) на квантовом компьютере. Классически лучший алгоритм (GNFS) работает за субэкспоненциальное время - разрыв экспоненциальный. RSA-2048 классически требует ~2^112 операций, квантово - порядка (2048)^3 ≈ 8 миллиардов. Ключевая идея: задача факторизации сводится к задаче нахождения периода функции f(x) = a^x mod N, которую квантовый компьютер решает через QFT (Quantum Fourier Transform).

Алгоритм Шора ломает RSA, DH на конечных полях, и ECDH/ECDSA - все системы основанные на факторизации или дискретном логарифме. Google Willow (2024) продемонстрировал квантовое превосходство в специализированных задачах, но RSA-2048 пока недостижим. NIST запустил конкурс post-quantum стандартизации в 2016, завершил в 2024 - первые стандарты: CRYSTALS-Kyber (ML-KEM), CRYSTALS-Dilithium (ML-DSA), FALCON, SPHINCS+.

Почему алгоритм Шора разрушителен именно для RSA и ECC?

Алгоритм Гровера

Алгоритм Гровера 1996 ускоряет перебор квадратично: классический перебор N элементов за O(N), квантовый - за O(sqrt(N)). Для симметричной криптографии это означает: AES-128 эффективно сводится к AES-64 (2^64 вместо 2^128 операций), AES-256 - к AES-128. Хэш-функции: SHA-256 (256-битное пространство) становится equivalent 128-битному. Выводы NIST: симметричные ключи нужно удвоить, хэши - тоже.

Важно: алгоритм Гровера не так страшен как Шор. Удвоение ключа AES-256 уже существует и достаточно. Реальная угроза квантовых компьютеров - именно асимметричная криптография через алгоритм Шора. Harvest Now, Decrypt Later (HNDL): противники уже сейчас собирают зашифрованный трафик с расчётом расшифровать его когда квантовые компьютеры станут доступны. Данные с долгим сроком конфиденциальности (гос. тайны, медицина) уже под угрозой.

Почему AES-256 считается квантово-устойчивым, а AES-128 - нет?

Квантовое распределение ключей (QKD)

QKD (Quantum Key Distribution) - технология распределения ключей с информационно-теоретической стойкостью: безопасность гарантируется законами физики, не вычислительной сложностью. Протокол BB84 (Bennett & Brassard 1984): квантовые биты (фотоны) передаются в случайных базисах. Если перехватчик измеряет фотоны, он вносит обнаруживаемые ошибки. Ключ используется только если ошибки ниже порогового значения (~11%).

Ограничения QKD: максимальное расстояние ~500 км (потери фотонов в оптоволокне), требует выделенного квантового канала, уязвим к атакам на оборудование (не на протокол). QKD-сети развёрнуты в Китае (2000 км, включая Пекин-Шанхай), Японии, Европе (OpenQKD). Россия имеет экспериментальные линии. Однако post-quantum криптография (математическая) - более практичное решение для массового применения.

Чем QKD принципиально отличается от post-quantum криптографии?

Практическое влияние квантовых компьютеров

Crypto-agility - способность системы быстро сменить криптографический алгоритм без полного переписывания. Это ключевое требование к современным системам. TLS 1.3 уже поддерживает гибридные режимы: X25519+Kyber768 одновременно (классический + post-quantum). Google Chrome с 2023 года включает Kyber для соединений с серверами Google. Cloudflare аналогично. NIST 2024: три финальных стандарта - FIPS 203 (ML-KEM/Kyber), FIPS 204 (ML-DSA/Dilithium), FIPS 205 (SLH-DSA/SPHINCS+).

Harvest Now, Decrypt Later реален: спецслужбы и крупные противники уже собирают зашифрованный трафик. Шифрование LoRA и медицинские записи сроком хранения 30+ лет критически уязвимы. Первые пострадавшие - правительства, оборонная промышленность, фармацевтика. Переход на PQC - не 'если', а 'когда'. NIST рекомендует начать миграцию прямо сейчас.

Что такое Harvest Now, Decrypt Later и почему это угроза уже сегодня?