Квантовая атака

Квантовая атака — это класс методов криптоанализа, использующих эффекты квантовой механики для взлома криптографических систем. В отличие от классических атак, которые полагаются на вычислительную сложность математических задач, квантовые атаки применяют принципы суперпозиции, запутанности и квантового параллелизма. Основная цель таких атак — подрыв безопасности криптосистем с открытым ключом (например, RSA, ECC) и симметричных шифров (например, AES) при помощи квантового компьютера достаточной мощности. Несмотря на то, что полноценный квантовый компьютер, способный демонстрировать практическое превосходство над классическими ЭВМ, пока не создан, развитие квантовых атак активно изучается, особенно в контексте перехода к постквантовой криптографии.

История

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

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

В 1996 году Лов Гровер (США) разработал квантовый алгоритм для поиска в неструктурированной базе данных (алгоритм Гровера). Хотя он не ломает криптографию так же радикально, как алгоритм Шора, он ускоряет перебор ключей симметричных шифров, сводя эффективную длину ключа к квадратному корню от исходной. Например, для 128-битного ключа AES атака Гровера требует около 2^64 операций, а не 2^128.

С начала 2000-х годов, по мере развития квантовых компьютеров, начались экспериментальные реализации квантовых атак. В 2001 году группа исследователей из IBM и Стэнфордского университета впервые реализовала алгоритм Шора на 7-кубитном ядерном магнитном резонансном (ЯМР) квантовом компьютере, разложив число 15 на множители 3 и 5.

К 2010-м годам прогресс в области квантовых вычислений привел к созданию прототипов, способных решать задачи, недоступные для классических суперкомпьютеров (квантовое превосходство), но пока не представляющих прямую угрозу для современных криптосистем. Однако разработки компаний Google, IBM, российских научных коллективов (например, в Российском квантовом центре) показывают, что создание полноценного квантового компьютера — вопрос времени.

Типы квантовых атак

Квантовые атаки можно классифицировать в зависимости от используемого алгоритма и объекта атаки.

### Алгоритм Шора (Shor’s algorithm)

Цель: Взлом криптосистем с открытым ключом, основанных на задачах факторизации и дискретного логарифмирования.

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

Уязвимые системы:

• RSA: Полностью ломается при наличии достаточно мощного квантового компьютера (несколько тысяч логических кубитов).
• DSA (Digital Signature Algorithm) и ElGamal — на основе дискретного логарифмирования.
• ECC (Elliptic Curve Cryptography): Алгоритм Шора адаптируется для атак на эллиптические кривые. Квантовый компьютер способен вычислить секретный ключ из открытого, сведя кривую к дискретному логарифму.

### Алгоритм Гровера (Grover’s algorithm)

Цель: Ускорение полного перебора ключей для симметричных шифров (AES, ChaCha20) и хэш-функций.

Принцип работы: Алгоритм Гровера — это квантовый поиск, который находит нужное значение (например, секретный ключ) в неструктурированной базе данных за O(√N) операций, где N — общее количество вариантов. Для симметричного шифрования с ключом длиной n бит классическая атака требует 2^n попыток, квантовая — 2^(n/2).

Последствия:

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

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

Парадокс: Квантовые атаки могут быть направлены и против самих систем квантовой криптографии.

Виды атак на QKD:

• Атака с перехватом и повторной посылкой (intercept-resend): Простейшая атака, где злоумышленник (Ева) перехватывает фотоны, измеряет их состояние и отправляет таковые же Алисе. Однако из-за неопределенности измерения эта атака вносит ошибки, которые обычно обнаруживаются.
• Атака с разделением фотона (photon-number splitting): Если источник не является однофотонным (испускает несколько фотонов), Ева может взять один фотон себе, а пропустить остальные. Это незаметно, если разница в числах фотонов в импульсах не регистрируется.
• Атака на уязвимости реализации: Например, атаки на детекторы (blinding detectors), когда злоумышленник ослепляет лавинный фотодиод мощным лазером и заставляет его выдавать сигнал только при определенном поляризационном состоянии.

### Квантовая атака на генерацию случайных чисел

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

Уязвимость существующих криптосистем

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

• Открытые ключи (RSA, ECC): Считаются практически незащищенными. Стандарты (например, от NIST) уже начали переход к постквантовым алгоритмам.
• Симметричные шифры (AES, ChaCha20): Устойчивы на практике, если использовать ключи достаточной длины (256 бит). Атака Гровера требует экспоненциального времени по длине ключа — 2^128 операций для AES-256 нереализуемо даже с квантовым компьютером.
• Хэш-функции (SHA-2, SHA-3): Уязвимы, но запас прочности сохраняется при удвоенной выходной длине (SHA-512 безопаснее против квантовых коллизий, чем SHA-256).
• Квантовое распределение ключей (QKD): В идеальной реализации обеспечивает абсолютно защищенную передачу ключа, но в реальных системах уязвимости могут быть использованы до усовершенствования технологии.

Меры противодействия и перспективы

Основным способом защиты от квантовых атак является постквантовая криптография — криптографические алгоритмы, устойчивые как к классическим, так и к квантовым атакам.

• Криптография на решетках (Lattice-based): Основана на сложности задач Learning With Errors (LWE) и Shortest Vector Problem (SVP). Примеры — CRYSTALS-Kyber и CRYSTALS-Dilithium (рекомендованы NIST в 2022 году, поддерживаются в России).
• Криптография на изогениях (Isogeny-based): Использует математику эллиптических кривых, но для квантовых атак известных уязвимостей пока нет. Пример — CSIDH.
• Криптография с использованием кодов исправления ошибок (Code-based): Основана на сложности декодирования случайного линейного кода. Пример — McEliece.
• Многомерная криптография (Multivariate): Основана на сложности решения системы нелинейных уравнений над конечным полем (MQ-проблема).

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

Источники:

1. Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. IEEE Computer Society.
2. Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. ACM STOC.
3. NIST. (2022). Post-Quantum Cryptography: Selected Algorithms 2022.
4. РЖД, Минцифры РФ. (2021–2023). Материалы о постквантовой криптографии и квантовых коммуникациях в России.