Постквантовая криптография

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

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

Квантовая угроза

В 1994 году американский математик Питер Шор предложил квантовый алгоритм, который теоретически может за полиномиальное время разложить число на простые множители и вычислить дискретный логарифм. Это ставит под удар все асимметричные криптосистемы, основанные на сложности этих задач, включая RSA, DSA, ECDSA и протокол Диффи-Хеллмана. Симметричные алгоритмы (например, AES) также уязвимы, но в меньшей степени: алгоритм Гровера позволяет ускорить перебор ключей, однако удвоение длины ключа восстанавливает стойкость до приемлемого уровня.

Развитие квантовых вычислений

Хотя полноценный квантовый компьютер, способный взломать RSA-2048, пока не создан, прогресс в этой области ускоряется. Крупные корпорации (Google, IBM, Microsoft) и государственные лаборатории (например, в Китае и США) активно инвестируют в квантовые технологии. По оценкам экспертов, появление криптографически значимого квантового компьютера возможно в течение 10–20 лет. Это создаёт угрозу «собрать сейчас — расшифровать позже» (англ. harvest now, decrypt later), когда злоумышленники накапливают зашифрованные данные в расчёте на будущую расшифровку.

Основные подходы постквантовой криптографии

Все известные на сегодняшний день постквантовые криптосистемы можно разделить на несколько семейств, основанных на различных математических задачах.

Криптография на решётках (Lattice-based cryptography)

Наиболее перспективное и активно изучаемое направление. Безопасность основана на сложности задач теории решёток, таких как Learning With Errors (LWE) и Shortest Vector Problem (SVP). Квантовые алгоритмы не дают значительного преимущества в решении этих задач. К достоинствам относится высокая производительность и возможность построения как схем шифрования, так и цифровых подписей. Примеры: CRYSTALS-Kyber (шифрование), CRYSTALS-Dilithium (подпись), FALCON (подпись). В 2022 году NIST выбрал Kyber и Dilithium в качестве стандартов.

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

Использует только стойкость криптографических хэш-функций (например, SHA-256). Цифровые подписи на основе хэшей (например, схемы Меркла, XMSS, LMS) считаются одними из самых надёжных, так как их безопасность хорошо изучена. Основной недостаток — ограниченное количество подписей на один ключ и относительно большой размер подписи. Применяются в основном для долговременного архивирования и в системах с низкими требованиями к скорости.

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

Безопасность основана на сложности декодирования случайного линейного кода (задача синдромного декодирования, NP-полная). Классический пример — криптосистема Мак-Элиса (1978 год). Преимущество — очень высокая скорость шифрования и дешифрования, недостаток — огромные размеры открытого ключа (сотни килобайт). Современные варианты (например, Classic McEliece) проходят стандартизацию NIST.

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

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

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

Использует отображения между суперсингулярными эллиптическими кривыми. Протокол SIDH (Supersingular Isogeny Diffie-Hellman) был предложен в 2011 году, но в 2022 году взломан с помощью классического компьютера. Тем не менее, другие схемы (например, CSIDH) продолжают изучаться. Отличаются очень малыми размерами ключей, но низкой производительностью.

Стандартизация

NIST

Национальный институт стандартов и технологий США (NIST) в 2016 году начал процесс стандартизации постквантовых криптоалгоритмов. В 2022 году были объявлены первые победители:

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

В 2024 году NIST также опубликовал проекты стандартов для дополнительных алгоритмов, включая Classic McEliece и HQC.

Россия

В России работы по постквантовой криптографии ведутся в рамках деятельности Технического комитета по стандартизации «Криптографическая защита информации» (ТК 26). Разрабатываются национальные стандарты (ГОСТ Р), основанные на отечественных математических разработках. В 2023 году были утверждены первые проекты:

• ГОСТ Р 34.10-202x (проект) — алгоритм цифровой подписи на основе решёток.
• ГОСТ Р 34.11-202x (проект) — схема шифрования на основе решёток.

Российские учёные (в частности, из Академии криптографии РФ, МГУ, ИСП РАН) активно участвуют в международных конференциях и разработке алгоритмов, однако конкретные сроки внедрения национальных стандартов пока не определены.

Другие страны

Китай, Евросоюз, Япония и Южная Корея также ведут собственные программы стандартизации. Например, Китай в 2024 году опубликовал набор национальных стандартов PQC, основанных на решётках и кодах.

Применение

Переход существующих систем

Основные области внедрения постквантовой криптографии включают:

• Инфраструктура открытых ключей (PKI): замена сертификатов X.509 на постквантовые.
• Протоколы TLS/SSL: гибридные схемы (например, X25519 + Kyber) уже тестируются в браузерах Chrome и Firefox.
• Электронная подпись: в государственных и корпоративных системах документооборота.
• Блокчейн и криптовалюты: защита от квантовых атак на цифровые подписи (например, в проекте Ethereum рассматривается переход на решёточные подписи).
• Военная и государственная связь: системы с длительным сроком секретности (до 30–50 лет) требуют немедленного перехода.

Гибридные схемы

На этапе перехода широко применяются гибридные криптосистемы, объединяющие классический и постквантовый алгоритмы. Например, в протоколе TLS 1.3 используется комбинация X25519 (классический) и Kyber-768 (постквантовый). Это обеспечивает защиту даже в случае, если один из алгоритмов будет взломан.

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

Размер ключей и шифротекстов

Постквантовые алгоритмы, особенно на основе кодов и многомерных уравнений, имеют значительно большие размеры ключей и шифротекстов по сравнению с RSA и ECC. Например, открытый ключ Classic McEliece может занимать более 1 МБ, что неприемлемо для многих встраиваемых систем.

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

Хотя решёточные алгоритмы (Kyber, Dilithium) демонстрируют приемлемую скорость, некоторые схемы (например, SPHINCS+) требуют значительных вычислительных ресурсов для генерации подписи. Это может быть критично для устройств с ограниченной вычислительной мощностью (IoT, смарт-карты).

Доверие к математическим задачам

Все постквантовые схемы основаны на задачах, которые пока не доказаны как NP-трудные. Существует риск, что в будущем будет найден эффективный классический или квантовый алгоритм для их решения. Например, взлом SIDH в 2022 году показал, что даже хорошо изученные схемы могут быть уязвимы.

Стандартизация и интероперабельность

Разные страны и организации разрабатывают собственные стандарты, что может привести к фрагментации и проблемам совместимости. Международное сообщество (IETF, ISO) работает над унификацией, но процесс идёт медленно.

Перспективы

Постквантовая криптография рассматривается как критически важная технология для обеспечения информационной безопасности в эпоху квантовых вычислений. Крупные технологические компании (Google, IBM, Microsoft, Amazon) уже начали внедрение PQC в свои продукты. Ожидается, что к 2030–2035 годам большинство критически важных систем будет переведено на постквантовые алгоритмы. В России переход планируется синхронизировать с утверждением национальных стандартов, что, по оценкам экспертов, произойдёт в 2025–2027 годах.

Источники

• NIST Post-Quantum Cryptography Standardization Process (2022–2024).
• Peter W. Shor, «Algorithms for Quantum Computation: Discrete Logarithms and Factoring» (1994).
• Технический комитет по стандартизации ТК 26 «Криптографическая защита информации», проекты ГОСТ Р (2023).
• Daniel J. Bernstein, «Introduction to Post-Quantum Cryptography» (2009).
• «Post-Quantum Cryptography: Current State and Future Directions» — отчет Европейского агентства по кибербезопасности (ENISA, 2021).