КВАНТОВЫЕ КОМПЬЮТЕРЫ И УГРОЗА КЛАССИЧЕСКОЙ КРИПТОГРАФИИ: КАК КВАНТОВЫЕ АЛГОРИТМЫ МОГУТ ВЗЛОМАТЬ СОВРЕМЕННЫЕ КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ

АННОТАЦИЯ

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

Ключевые слова: квантовый компьютер, криптография, алгоритм Шора, алгоритм Гровера, RSA, ECC, постквантовая криптография.

Введение

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

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

1. Алгоритм Шора и уязвимость криптографии с открытым ключом

Асимметричная криптография использует открытый и закрытый ключи. Безопасность RSA основана на сложности факторизации числа N = pq, где p и q — большие простые числа. Перемножить их легко, но восстановить по произведению классическому компьютеру крайне трудно. Схемы Diffie-Hellman и ECC аналогично опираются на сложность дискретного логарифмирования.

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

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

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

Симметричная криптография устроена иначе: один секретный ключ используется для шифрования и расшифрования. Если ключ неизвестен, базовая атака сводится к перебору всех вариантов. Для ключа длиной k бит пространство поиска равно 2^k. Например, AES-128 имеет 2^128 возможных ключей, что делает полный перебор практически невозможным в классической модели.

Алгоритм Гровера ускоряет неструктурированный поиск: если классический перебор требует порядка N проверок, то квантовый поиск требует порядка sqrt(N). Для пространства 2^k это дает 2^(k/2). Поэтому AES-128 в идеализированной квантовой модели имеет эффективную стойкость около 64 бит, а AES-256 — около 128 бит. Это серьезное снижение запаса прочности, но не полный взлом симметрической криптографии.

Расчетная модель: N = 2^k; классическая сложность Cclassic ≈ 2^k; квантовая сложность по Гроверу Cquantum ≈ sqrt(2^k) = 2^(k/2). Следовательно, увеличение длины симметричного ключа в два раза компенсирует квадратичное ускорение квантового поиска.

3. Сравнение угроз

Таблица 1.

Сравнение угроз

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

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

В 2024 году NIST утвердил первые стандарты постквантовой криптографии: FIPS 203 для ML-KEM, FIPS 204 для ML-DSA и FIPS 205 для SLH-DSA. Это показывает, что переход к новым алгоритмам уже является практической задачей. Особенно важна проблема «собери сейчас — расшифруй потом»: злоумышленник может сохранять зашифрованный трафик сегодня, чтобы расшифровать его в будущем.

Заключение

Квантовые компьютеры создают реальную угрозу классической криптографии, но она неодинакова для разных методов. Наиболее уязвимы RSA, Diffie-Hellman и ECC, поскольку алгоритм Шора решает лежащие в их основе задачи за полиномиальное время. Симметричные алгоритмы сохраняют применимость, однако алгоритм Гровера снижает их эффективную стойкость, поэтому для долгосрочной защиты предпочтительны увеличенные параметры, например AES-256.

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

Список литературы:

1. Grover L. K. A fast quantum mechanical algorithm for database search. STOC, 1996.
2. Nielsen M. A., Chuang I. L. Quantum Computation and Quantum Information. Cambridge University Press.
3. Лекция 1. Основы квантовых вычислений и квантовых компьютеров. РГУ нефти и газа имени И. М. Губкина, 2026.
4. Лекция 6. Алгоритм Гровера. РГУ нефти и газа имени И. М. Губкина, 2026.
5. Лекция 7. Алгоритмы квантовых вычислений. РГУ нефти и газа имени И. М. Губкина, 2026.