Курс «Квантовые вычисления». Глава 12. Криптографические следствия: инвентаризация угрозы

Курс «Квантовые вычисления»

Цели главы. Перевести алгоритмические результаты частей II–III на язык информационной безопасности: точно отделить развёрнутые схемы, уязвимые для Шора, от примитивов, которые Гровер лишь ускоряет, и от постквантовых семейств; ввести понятия CRQC и HNDL; применить неравенство Моски к срокам миграции. Формул в главе почти нет, но оговорки о модели атаки здесь не менее важны, чем оценки степеней двойки.

12.1. Карта современной криптографии

Чтобы оценить ущерб, вспомним, из чего состоит криптографическая инфраструктура.

• Симметричная криптография: общий секретный ключ у обеих сторон. Шифры (AES, ChaCha20, отечественный «Кузнечик») защищают объём данных; хеш-функции (SHA-2, SHA-3, «Стрибог») дают целостность; MAC — аутентичность. Быстро, компактно — но требует, чтобы ключ уже был у обеих сторон.
• Асимметричная криптография использует пару открытого и закрытого ключей. Механизмы установления ключей (Diffie–Hellman, ECDH, KEM) создают общий секрет через открытый канал; цифровые подписи (RSA, ECDSA, EdDSA, ГОСТ 34.10 и постквантовые схемы) аутентифицируют данные; на подписях строится PKI — иерархия сертификатов, используемая, в частности, TLS.

Типичное TLS 1.3-соединение уже гибридно в широком смысле: (EC)DHE или KEM участвует в выработке сеансовых ключей, сертификатная подпись удостоверяет сервер, а AEAD вроде AES-GCM или ChaCha20-Poly1305 защищает дальнейший трафик. Конкретные алгоритмы зависят от конфигурации. Квантовая угроза различна для этих частей: широко развёрнутые классические обмен и подпись уязвимы для Шора, а симметрическая защита испытывает лишь квадратичное ускорение общего перебора.

12.2. Что ломает Шор: факторизация и дискретный логарифм

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

• RSA — шифрование и подписи (факторизация модуля);
• Diffie–Hellman и DSA (дискретный логарифм в конечном поле);
• ECDH, ECDSA и EdDSA — эллиптические обмены и подписи в TLS, SSH и многих криптовалютах (дискретный логарифм на кривой); короткая запись эллиптического ключа не означает стойкость против Шора;
• национальные стандарты той же математической природы — включая ГОСТ 34.10 (эллиптические кривые): смена флага математику не меняет.

Это не «стойкость просела, удлиним ключи». Рост размера RSA или эллиптической группы повышает стоимость квантовой атаки лишь полиномиально вместе с размером входа и не возвращает прежнюю асимптотику; практичные размеры ключей не лечат уязвимое основание. Но формулировка «Шор ломает всю асимметрию» неверна: решёточные, хешевые и кодовые постквантовые схемы тоже асимметричны и на факторизации или дискретном логарифме не основаны. Заменить надо именно уязвимые семейства, а не саму идею открытого ключа.

12.3. Что делает Гровер: посильный урон симметрике

Для идеализированного симметричного примитива общий квантовый инструмент — ускоренный поиск; специальные атаки на конкретную конструкцию надо оценивать отдельно. Картина принципиально мягче, чем у Шора:

• Шифры: в модели оракула поиск одного k-битного ключа требует порядка 2^k/2 последовательных квантовых запросов. Поэтому для AES-128 получается абстрактная оценка 2⁶⁴, для AES-256 — 2¹²⁸. Один запрос означает дорогую обратимую реализацию шифра, а параллельные машины дают отдельный компромисс «число машин — время», поэтому эту степень нельзя прямо переводить в часы. Консервативный рецепт для новых долгоживущих систем — 256-битный ключ.
• Хеш-функции: для n-битного выхода общий поиск прообраза требует порядка 2^n/2 квантовых запросов, а общий поиск коллизии алгоритмом BHT — порядка 2^n/3 запросов с существенной квантовой памятью. Память и обратимая схема делают такую атаку крайне дорогой, но не возвращают математически классическую границу 2^n/2. Для SHA-256 это около 128 бит по прообразу и 85 бит в абстрактной модели коллизий; нужен ли более длинный хеш, зависит от требуемого свойства и профиля, а SHA-384 даёт примерно 128-битную общую квантовую оценку коллизий.
• Особняком — информационно-стойкие схемы. Одноразовый блокнот сохраняет совершенную секретность только при действительно случайном секретном ключе длиной с сообщение, использованном ровно один раз; квантовое вычисление это доказательство не меняет. Ограничения распределения и хранения такого ключа делают схему нишевой.

Итоговая асимметрия угрозы, определяющая всю стратегию перехода: симметрику — удлинить, асимметрику — заменить.

12.4. CRQC и неравенство Моски

Криптографически значимый квантовый компьютер (CRQC) — отказоустойчивая машина, способная исполнить Шора на практически используемом ключе в полезное для атакующего время. Это не фиксированное число кубитов: оценки для RSA-2048 зависят от кода, связности, скорости цикла, физической ошибки, допустимого времени и алгоритма и уже расходятся от сотен тысяч до миллионов физических кубитов. Современные эксперименты демонстрируют отдельные логические памяти и операции, но не такой расчёт. Достоверной даты CRQC нет, поэтому управлять риском по единственному прогнозу нельзя; полезный инструмент — неравенство Моски. Обозначим:

• x — срок, в течение которого ваши данные должны оставаться конфиденциальными (shelf life);
• y — время, которое займёт миграция вашей инфраструктуры на постквантовую криптографию;
• z — время до появления CRQC.

Если x + y > z — вы уже опоздали.

Пример: медицинские данные должны быть тайной 25 лет (x = 25), миграция крупной организации займёт 7 лет (y = 7); если z < 32 лет, ждать появления машины для начала перехода поздно. При рабочем сценарии z = 20 запас уже отрицателен на 12 лет. Неравенство не предсказывает z и не доказывает неизбежность CRQC: оно показывает, при каких допустимых сценариях риск требует действия, и заставляет явно записать сроки данных и миграции.

12.5. «Собрать сейчас — расшифровать потом»

Неравенство Моски материализуется в конкретной атаке — harvest now, decrypt later: противник записывает зашифрованный трафик сегодня, чтобы расшифровать после появления CRQC. Записанное TLS-рукопожатие содержит всё необходимое: будущий Шор восстановит из него эфемерный секрет ECDH, а с ним — сеансовый ключ и весь трафик. Три свойства делают атаку особенно неприятной:

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

Отсюда одна из осей приоритизации: обмен ключами для данных с длинным x защищают рано, потому что будущая атака может раскрыть уже записанный трафик. Подпись нельзя «расшифровать потом», но у неё своя экспозиция: прошивка, документ, журнал или корневой сертификат могут проверяться десятилетиями, а после появления CRQC уязвимой схемой можно будет подписать новую подделку. Реальная очередь учитывает обе оси вместе с критичностью, доступностью обновления и зависимостями системы.

12.6. Сводная таблица

Итоги главы

• Шор полиномиально ломает развёрнутые схемы на факторизации и дискретном логарифме, но не всю асимметричную криптографию.
• Гровер даёт квадратичное ускорение общего поиска; у хешей надо различать прообразы (~2^n/2) и коллизии (~2^n/3 квантовых запросов).
• Дата CRQC неизвестна; неравенство Моски x + y > z не предсказывает её, а проверяет, при каких сценариях ждать уже нельзя.
• HNDL делает защиту каналов с долгоживущими данными срочной до появления CRQC; долгоживущие подписи требуют отдельной ранней программы миграции.

Упражнения

1. Примените неравенство Моски: (а) телеметрия умного счётчика, x ≈ 0; (б) коммерческая тайна, x = 10; (в) государственная тайна, x = 30. Возьмите y = 5 и оцените, при каких z каждая категория «уже опоздала». Какая из них оправдывает миграцию даже при скептическом z = 25?
2. Почему увеличение RSA-ключа с 2048 до 8192 бит — не защита от Шора, хотя от классического GNFS оно помогает радикально? Сформулируйте через классы сложности главы 9.
3. Биткойн использует ECDSA/Schnorr на secp256k1 и SHA-256. Разложите угрозу: что ломается Шором, что лишь получает общий поиск, и почему выход P2PKH/P2WPKH скрывает открытый ключ до траты, тогда как P2TR содержит открытый ключ уже в выходе. Почему повторное использование адресов — отдельный риск?
4. Составьте для гипотетической организации (интернет-банк) список из пяти криптозависимых подсистем и расставьте их в порядке очерёдности миграции, обосновывая через HNDL и сроки жизни подписей.
5. Правда ли, что «квантовые компьютеры сломают все пароли»? Разберите: как хранятся пароли (хеши с солью), что даёт Гровер для перебора, и как длина пароля соотносится с длиной ключа в оценках главы 8.
6. Протокол Signal ещё в 2023 году добавил постквантовый компонент в установление ключей (PQXDH), не тронув остальное. Объясните этот выбор приоритета языком разделов 12.5 (какая часть протокола под HNDL?).

Ответы и указания. 1: опоздание при z < 5, z < 15, z < 35 соответственно; категория (в) требует действий даже во многих далёких сценариях. 2: GNFS имеет субэкспоненциальную, но сверхполиномиальную сложность по длине модуля; Шор — полиномиальную. Увеличение ключа заметно тормозит обе стороны, но не устраняет качественное преимущество квантовой атаки. 3: Шор позволяет по открытому ключу получить секрет подписи; P2PKH/P2WPKH до первой траты показывают лишь хеш, но P2TR сразу публикует ключ, а повторно используемый адрес оставляет раскрытый ключ и после подтверждения. Гровер даёт только квадратичный общий поиск по пространству nonce/прообразов, причём майнинг — гонка с ограниченным временем и дорогим последовательным квантовым вычислением. 5: нет. Соль исключает общие заранее вычисленные таблицы, но не офлайн-проверку кандидатов для одной записи. Гровер квадратично ускоряет идеализированный равномерный поиск; реальные пароли неравномерны, а стоимость обратимого KDF, память, параллелизм и скорость перебора меняют оценку. Длинная случайная парольная фраза и параметризованный memory-hard KDF остаются нужными, но это не сводится буквально к «половине длины пароля».

Литература к главе

1. M. Mosca, "Cybersecurity in an era with quantum computers: will we be ready?", IEEE Security & Privacy 16, 2018 (препринт 2015). eprint.iacr.org/2015/1075
2. NIST IR 8105, "Report on Post-Quantum Cryptography," 2016. csrc.nist.gov/pubs/ir/8105/final
3. NCSC, "Timelines for migration to post-quantum cryptography," 2025. ncsc.gov.uk/guidance/pqc-migration-timelines
4. ETSI, "Quantum-Safe Cryptography and Security," White Paper. etsi.org/technologies/quantum-safe-cryptography

Предыдущая глава || Содержание курса || Следующая глава