Коротко — в чем угроза и почему это важно
- Квантовый алгоритм Шора решает задачи факторизации и дискретного логарифма за полиномиальное время, тогда как лучшие классические алгоритмы для тех же задач имеют субэкспоненциальную сложность. Формально: классическое факторирование числа $N$ (двухтысячебитные и т.д.) наилучшим образом делается за время порядка $\exp ((c+o(1))(\log N{)}^{1/3}(\log \log N{)}^{2/3})$ (GNFS), а Шор работает за время $\text{poly}(n)$, где $n=\log N$. В практическом смысле это делает уязвимыми широко используемые схемы с открытым ключом: RSA и протоколы на эллиптических кривых (ECDSA, ECDH и т.п.).
Главные направления пост‑квантовой криптографии (PQC) — суть и плюсы/минусы
- Решётки (Lattice-based): LWE, Ring‑LWE, NTRU (примеры: CRYSTALS‑Kyber — KEM, CRYSTALS‑Dilithium — подписи). Плюсы: хорошие скорости, сравнительно небольшие ключи/подписи, успешны в стандартизации. Минусы: новые, базируются на предположениях с меньшей историей, возможны осторожности в выборе параметров.
- Кодовые схемы (Code-based): McEliece и производные. Плюсы: долгую устойчивость к атакам, простота. Минусы: очень большие публичные ключи (мегабайты) — проблемы для ограниченных устройств.
- Мультивариантные уравнения (Multivariate): быстрые подписи, низкие вычисления. Минусы: многие схемы были сломаны; осторожно выбирать проверенные варианты.
- Хеш‑основанные подписи (Hash-based): Lamport, XMSS, SPHINCS+. Плюсы: основаны на безопасности хешей (надёжно), постквантовая стойкость. Минусы: большие подписи, у некоторых — состояние (stateful) управления.
- Изогении эллиптических кривых (Isogeny-based): маленькие ключи (были перспективны — пример SIKE). Минусы: недавно показаны эффективные классические атаки против некоторых схем (падение уверенности), общая стабильность пока сомнительна.
- Прочие гибриды и вариации (комбинации выше).
Практические проблемы внедрения
- Размеры ключей/сообщений и производительность: некоторые схемы требуют существенно больших публичных ключей/подписей/шумовых буферов, что удлиняет протоколы и нагружает сеть и устройства.
- Совместимость и стандарты: протоколы (TLS, SSH, VPN, PKI, HSM, TPM) нужно обновлять; сертификатная инфраструктура и форматы должны поддерживать новые алгоритмы и гибридные режимы.
- Аппаратная/программная поддержка: ускорители, аппаратные модули безопасности и прошивки часто не готовы; необходимость оптимизаций и защищённых реализаций.
- Надёжность предположений: новые схемы опираются на другие математические проблемы (LWE, SIS, кодовые, MQ и т.д.), с меньшим историческим временем анализа, возможны неожиданные атаки.
- Побочные каналы и реализация: даже «пост‑квантовые» алгоритмы уязвимы к утечкам по времени/питанию/кэш‑каналам; нужно безопасное внедрение.
- Операционная миграция: обнаружение и замена всех точек, где используются уязвимые ключи; управление ключами, обратная совместимость, план миграции и тестирование.
- Долгосрочная секретность: данные, которые нужно сохранять конфиденциальными десятилетиями, требуют ускоренной миграции (атаки будущих квантовых компьютеров могут дешифровать перехваченные сегодня сообщения).
- Патенты и лицензирование: некоторые схемы могут быть покрыты патентами — юридические/лицензионные сложности.
Конкретные числовые ориентиры и рекомендации
- Grover даёт квадратичный выигрыш против симметричных ключей: сложность $2^k$ становится примерно $2^{k/2}$. Поэтому для симметрической криптографии разумно применять ключи вдвое длиннее (например, вместо AES‑128 использовать AES‑256 для сохранения ~$2^{128}$ безопасности).
- Оценки реального квантового ресурса для взлома RSA/ECC варьируются; практические оценки говорят о потребности в сотнях тысяч — миллионах физических кубитов с коррекцией ошибок и существенном времени выполнения. Точные цифры зависят от модели и допущений, но угрозу нельзя игнорировать для ключей с долгим сроком хранения.
Коротко о путях миграции
- Начинать инвентаризацию и классификацию критичных ключей (особенно долгоживущих и конфиденциальных данных).
- Применять гибридные схемы (классический алгоритм + постквантовый KEM) в протоколах, где это возможно.
- Следить за стандартизацией (NIST: CRYSTALS‑Kyber и CRYSTALS‑Dilithium — ключевые результаты) и обновлять стеки по мере принятия.
- Приоритет — защищать критичные и долгоживущие активы в первую очередь.
Если нужно, могу коротко перечислить плюсы/минусы конкретных алгоритмов (Kyber, Dilithium, McEliece, SPHINCS+, и т.д.) или помочь составить план миграции для вашей инфраструктуры.