Всероссийский сборник статей и публикаций института развития образования, повышения квалификации и переподготовки.

ВВЕДЕНИЕ

Современная цифровая инфраструктура — банковские транзакции, электронная подпись, блокчейн-сети — опирается на криптографию с открытым ключом. Её стойкость основана на сложности факторизации больших чисел и дискретного логарифмирования. Для классических компьютеров эти задачи практически неразрешимы при достаточной длине ключа, что и обеспечивает безопасность RSA, Диффи — Хеллмана и криптографии на эллиптических кривых (ECC).

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

Угроза носит не только будущий, но и текущий характер. Стратегия «harvest now, decrypt later» предполагает, что злоумышленник перехватывает зашифрованный трафик сегодня, рассчитывая расшифровать его позже. Это делает переход на квантовоустойчивые методы актуальной задачей настоящего момента.

1 ОСНОВЫ КВАНТОВЫХ ВЫЧИСЛЕНИЙ

Базовая единица квантовой информации — кубит. В отличие от классического бита, кубит может находиться в суперпозиции состояний 0 и 1. Система из n кубитов описывается суперпозицией 2ⁿ базисных состояний, что позволяет обрабатывать экспоненциально большое пространство параллельно. Квантовые алгоритмы строятся так, чтобы за счёт интерференции усиливать вероятность правильного ответа.

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

Главным практическим препятствием является декогеренция — разрушение квантового состояния из-за взаимодействия с окружением. Реальные устройства NISQ-эпохи содержат от десятков до нескольких сотен физических кубитов с заметным уровнем ошибок. Для взлома 2048-битного RSA необходимы тысячи логических и миллионы физических кубитов — порог, который пока не достигнут, но активно приближается.

2 КВАНТОВЫЕ АЛГОРИТМЫ КАК УГРОЗА КРИПТОГРАФИИ

2.1 Алгоритм Шора и взлом асимметричной криптографии

Алгоритм Шора решает задачу факторизации и дискретного логарифмирования за полиномиальное время — порядка куба от числа битов. Наилучший классический алгоритм факторизации работает за субэкспоненциальное время, что делает факторизацию больших чисел практически невыполнимой.

Идея алгоритма состоит в сведении факторизации к задаче нахождения периода функции. Период эффективно вычисляется с помощью квантового преобразования Фурье. Зная период, классическая постобработка позволяет найти нетривиальный делитель числа.

Последствия прямые: стойкость RSA основана на сложности факторизации, стойкость Диффи — Хеллмана и ECC — на сложности дискретного логарифмирования. Алгоритм Шора подрывает обе основы. При наличии криптографически значимого квантового компьютера все три семейства будут взломаны независимо от длины ключа. Увеличение длины ключа не спасает, поскольку полиномиальный рост затрат квантового компьютера несопоставим с экспоненциальным выигрышем.

2.2 Алгоритм Гровера и симметричная криптография

Алгоритм Гровера обеспечивает квадратичное ускорение неструктурированного поиска: задачу, требующую в среднем N/2 проверок классически, он решает за √N шагов. Применительно к симметричным шифрам стойкость алгоритма с ключом длины k бит снижается эквивалентно до k/2 бит.

Практическое следствие умеренное: для сохранения прежнего уровня безопасности достаточно удвоить длину ключа. AES-128 обеспечивает безопасность, эквивалентную примерно 64 битам, что недостаточно, тогда как AES-256 сохраняет около 128 бит стойкости и признаётся квантовоустойчивым. Таким образом, симметричная криптография переживает квантовую угрозу с количественной, а не качественной коррекцией.

Принципиальное различие: алгоритм Шора даёт экспоненциальное ускорение и полностью разрушает асимметричную криптографию, тогда как алгоритм Гровера даёт лишь квадратичное ускорение и только ослабляет симметричную. Именно поэтому основные усилия по переходу сосредоточены на замене асимметричных примитивов.

3 КВАНТОВОУСТОЙЧИВАЯ (ПОСТКВАНТОВАЯ) КРИПТОГРАФИЯ

Постквантовая криптография (PQC) — алгоритмы, выполняемые на классических компьютерах, но устойчивые к атакам квантовых противников. Их стойкость опирается на математические задачи, для которых не известно эффективного квантового алгоритма. PQC следует отличать от квантового распределения ключей, которое использует физические принципы и требует специального оборудования.

Криптография на решётках опирается на сложность задач о кратчайшем и ближайшем векторе в решётках высокой размерности. Это наиболее зрелое направление, обеспечивающее как шифрование, так и подпись при умеренных размерах ключей. Криптография на хеш-функциях используется для цифровых подписей и опирается только на стойкость хеш-функций — наиболее консервативный вариант. Криптография на кодах, основанная на сложности декодирования случайных линейных кодов, существует с 1970-х годов, но характеризуется большими открытыми ключами.

С 2016 года NIST проводит открытый конкурс по стандартизации постквантовых алгоритмов. В августе 2024 года опубликованы первые три финальных стандарта: FIPS 203 (ML-KEM на основе CRYSTALS-Kyber) — механизм инкапсуляции ключей на решётках; FIPS 204 (ML-DSA на основе CRYSTALS-Dilithium) — основной стандарт цифровой подписи; FIPS 205 (SLH-DSA на основе SPHINCS+) — подпись на хеш-функциях как консервативная альтернатива. В марте 2025 года для стандартизации выбран алгоритм HQC на кодах как резервный механизм инкапсуляции.

Переход на PQC — масштабная инженерная задача, охватывающая протоколы TLS, IKE, инфраструктуру открытых ключей и встроенные системы. На переходном этапе применяются гибридные схемы, в которых классический и постквантовый алгоритмы используются совместно: итоговый ключ остаётся защищённым, даже если один из компонентов будет скомпрометирован.

4 БЛОКЧЕЙН И КРИПТОВАЛЮТЫ ПЕРЕД ЛИЦОМ КВАНТОВОЙ УГРОЗЫ

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

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

Защита предполагает переход на постквантовые схемы подписи, отказ от повторного использования адресов и сокращение времени раскрытия открытого ключа. Сложность состоит в децентрализованной природе сетей: обновление протокола требует согласия сообщества и переноса средств, что является длительным организационным процессом.

ЗАКЛЮЧЕНИЕ

Алгоритм Шора полностью подрывает асимметричную криптографию — RSA, Диффи — Хеллмана и ECC, — на которой держится защита подавляющего большинства цифровых сервисов. Алгоритм Гровера ослабляет симметричные шифры и хеш-функции, однако эта угроза парируется увеличением длины ключей.

Ответом криптографического сообщества стала постквантовая криптография. Публикация стандартов NIST в 2024 году знаменует начало практического перехода. Ключевую роль играет диверсификация математических оснований и применение гибридных схем на переходном этапе. Особую уязвимость демонстрируют блокчейн и криптовалюты, защита которых требует не только технических, но и организационных решений.

Главный вывод: угроза носит упреждающий характер. Стратегия «собери сейчас, расшифруй потом» делает миграцию на квантовоустойчивые алгоритмы актуальной задачей уже сегодня, задолго до появления полноценного квантового компьютера.