Квантово-устойчивые алгоритмы

Квантово-устойчивые алгоритмы (также постквантовая криптография) — класс криптографических алгоритмов, предназначенных для обеспечения безопасности информации в условиях существования достаточно мощного квантового компьютера. В отличие от традиционных криптосистем с открытым ключом (RSA, ECDSA, Diffie-Hellman), чья стойкость основана на сложности задач факторизации больших чисел и дискретного логарифмирования, которые могут быть эффективно решены с помощью квантового алгоритма Шора, квантово-устойчивые алгоритмы опираются на математические задачи, для которых не известны эффективные квантовые алгоритмы решения.

Предпосылки появления

Угроза квантовых компьютеров

В 1994 году американский математик Питер Шор разработал алгоритм, позволяющий разложить целое число на простые множители за полиномиальное время на гипотетическом квантовом компьютере. Этот алгоритм, а также алгоритм Гровера для поиска в неструктурированных базах данных, поставили под сомнение стойкость всей современной асимметричной криптографии, включая протоколы TLS, SSH, PGP, а также цифровые подписи, используемые в блокчейне и электронном документообороте.

Хронология развития

• 1994 год — публикация алгоритма Шора (Shor's algorithm).
• 2003–2006 годы — первые академические конференции, посвящённые постквантовой криптографии (PQCrypto).
• 2016 год — Национальный институт стандартов и технологий США (NIST) объявил конкурс на стандартизацию квантово-устойчивых криптоалгоритмов.
• 2022 год — NIST объявил первых победителей конкурса: алгоритм CRYSTALS-Kyber для шифрования и обмена ключами, а также CRYSTALS-Dilithium, FALCON и SPHINCS+ для цифровых подписей.
• 2024 год — NIST опубликовал финальные версии стандартов FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) и FIPS 205 (SLH-DSA), основанных на этих алгоритмах.
• 2025 год — Агентство национальной безопасности США (NSA) рекомендовало переход на квантово-устойчивые алгоритмы для систем национальной безопасности к 2035 году.

Классификация квантово-устойчивых алгоритмов

Криптосистемы на основе решёток (Lattice-based cryptography)

Самый популярный и активно стандартизируемый класс. Безопасность основана на сложности задач обучения с ошибками (LWE — Learning With Errors) и кольцевого обучения с ошибками (Ring-LWE). Ключевые преимущества — высокая скорость, относительно небольшие размеры ключей (по сравнению с другими постквантовыми схемами) и наличие доказательств безопасности.

Примеры:

• CRYSTALS-Kyber (ML-KEM) — механизм инкапсуляции ключей (KEM), стандартизирован NIST в 2024 году.
• CRYSTALS-Dilithium (ML-DSA) — схема цифровой подписи.
• FALCON — компактная схема подписи, основанная на решётках NTRU.

Криптосистемы на основе хэш-функций (Hash-based signatures)

Используют только криптографические хэш-функции, что делает их устойчивыми к квантовым атакам. Основной недостаток — подписи имеют большой размер и требуют ведения состояния (stateful). Примеры: схемы Меркла (Merkle tree), SPHINCS+ (без состояния, SLH-DSA).

Криптосистемы на основе кодов, исправляющих ошибки (Code-based cryptography)

Стойкость основана на сложности декодирования случайного линейного кода (NP-полная задача). Классический пример — криптосистема Мак-Элиса (1978). Недостаток — очень большие открытые ключи (сотни килобайт).

Криптосистемы на основе многомерных квадратичных уравнений (Multivariate cryptography)

Стойкость основана на сложности решения системы многомерных квадратичных уравнений над конечным полем (MQ-задача, NP-полная). Примеры: Rainbow, GeMSS. Однако многие схемы этого класса были взломаны (например, Rainbow в 2022 году).

Криптосистемы на основе изогений эллиптических кривых (Isogeny-based cryptography)

Используют отображения между эллиптическими кривыми (изогении). Наиболее известный протокол — CSIDH. Относительно новый класс, активно исследуется, но медленнее решёточных аналогов.

Применение и стандартизация

Международная стандартизация

• NIST (США) — ведущий орган по стандартизации постквантовой криптографии. В 2024 году опубликованы стандарты FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA). Продолжается работа над дополнительными алгоритмами (например, на основе изогений).
• ETSI (Европейский институт телекоммуникационных стандартов) — выпускает технические отчёты по внедрению постквантовой криптографии.
• IETF (Internet Engineering Task Force) — разрабатывает протоколы гибридного обмена ключами (Hybrid Key Exchange), в которых квантово-устойчивый алгоритм комбинируется с классическим (например, X25519Kyber768).

Ситуация в России

В Российской Федерации работы по квантово-устойчивым алгоритмам ведутся в рамках программы «Цифровая экономика» и национального проекта «Наука и университеты». В 2023 году Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26) начал разработку национальных стандартов (ГОСТ Р) на постквантовые криптоалгоритмы. Предполагается, что российские стандарты будут основаны на алгоритмах на решётках и кодах, исправляющих ошибки, с учётом требований к импортозамещению. В 2024 году опубликован проект ГОСТ Р «Криптографическая защита информации. Алгоритмы постквантовой криптографии». Внедрение планируется в системах электронной подписи, защищённого документооборота и государственных информационных системах.

Практическое внедрение

• Google — в 2016 году провёл эксперимент с алгоритмом NewHope в браузере Chrome.
• Cloudflare — с 2022 года внедрил поддержку гибридного обмена ключами X25519Kyber768 в CDN.
• Signal — в 2023 году добавил поддержку постквантового протокола PQXDH для обмена ключами.
• Apple — в iMessage с 2024 года используется постквантовый протокол PQ3.
• Российские разработки — компания «Крипто-Про» и другие вендоры разрабатывают экспериментальные реализации постквантовых алгоритмов для СКЗИ (средств криптографической защиты информации).

Критика и проблемы

Размер ключей и подписей

Квантово-устойчивые алгоритмы, как правило, имеют значительно большие размеры ключей и подписей по сравнению с классическими. Например, открытый ключ в схеме Мак-Элиса может достигать 1 МБ, а подпись SPHINCS+ — до 50 КБ. Это создаёт проблемы для устройств с ограниченными ресурсами (IoT, смарт-карты) и для сетей с низкой пропускной способностью.

Производительность

Некоторые алгоритмы (особенно на основе изогений и многомерных квадратичных уравнений) требуют значительно больше вычислительных ресурсов. Для массового внедрения требуется оптимизация аппаратного обеспечения (чипы, поддерживающие постквантовую криптографию).

Неизвестные атаки

Хотя математические задачи, лежащие в основе постквантовой криптографии, считаются сложными, не исключено, что в будущем будут найдены эффективные алгоритмы их решения (как классические, так и квантовые). Поэтому многие эксперты рекомендуют гибридные схемы, где квантово-устойчивый алгоритм комбинируется с классическим.

Угроза «собери сейчас, расшифруй позже» (Harvest Now, Decrypt Later)

Даже если квантовый компьютер будет создан через 10–20 лет, злоумышленники могут уже сейчас собирать зашифрованный трафик, чтобы расшифровать его в будущем. Это делает переход на постквантовую криптологию актуальным уже сегодня, особенно для данных с длительным сроком жизни (государственные тайны, медицинские записи, интеллектуальная собственность).

Перспективы

Ожидается, что к 2030–2035 годам большинство критически важных информационных систем перейдут на квантово-устойчивые алгоритмы. В первую очередь это коснётся:

• Систем электронной подписи и удостоверяющих центров.
• Протоколов защищённой передачи данных (TLS, VPN).
• Блокчейн-систем и криптовалют (например, Bitcoin и Ethereum рассматривают переход на постквантовые подписи).
• Государственных информационных систем и систем «Электронное правительство».

В России разработка и внедрение квантово-устойчивых алгоритмов включены в дорожную карту развития квантовых технологий до 2030 года.

Источники

• Bernstein, D. J., Buchmann, J., & Dahmen, E. (Eds.). (2009). Post-Quantum Cryptography. Springer.
• National Institute of Standards and Technology (NIST). (2024). FIPS 203, 204, 205: Post-Quantum Cryptography Standards.
• Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science.
• Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26). (2024). Проект ГОСТ Р «Алгоритмы постквантовой криптографии».
• Cloudflare. (2022). Post-Quantum Cryptography: The Path to a Secure Internet.
• Signal. (2023). PQXDH: Post-Quantum Extended Diffie-Hellman.