Квантово-устойчивая криптография: схемы против Шора

Квантово-устойчивая криптография - это набор криптографических схем, стойкость которых не нарушается даже при наличии большого универсального квантового компьютера. Её также называют постквантовой криптографией (PQC), и важно сразу развести два понятия: речь идёт об обычных алгоритмах, исполняемых на классических процессорах, но опирающихся на математические задачи, для которых не известно эффективного квантового алгоритма. Это не квантовая криптография (QKD), где ключи распределяются через физику фотонов. Толчком к развитию направления стал алгоритм Шора: он показал, что факторизация и дискретный логарифм решаются на квантовом компьютере за полиномиальное время, а значит, фундамент классической асимметрики рушится. Ниже разберём, почему именно эти задачи уязвимы, на каких новых проблемах строят защиту и какие стандарты уже приняты.

Почему классические схемы уязвимы к Шору

Современная асимметричная криптография держится на двух вычислительно сложных задачах: факторизации большого числа $N = pq$ (это RSA) и дискретном логарифме в конечной группе (это протокол Диффи-Хеллмана и эллиптические кривые ECC). Для классического компьютера лучшие методы - решето числового поля и $\rho$-метод Полларда - работают субэкспоненциально, поэтому ключ в $2048$ бит считается надёжным на десятилетия.

Алгоритм Шора ломает эту картину. Он сводит факторизацию к поиску периода функции $f(x) = a^x \bmod N$ и находит этот период квантовым преобразованием Фурье за время, полиномиальное от $\log N$. Тот же приём с минимальными изменениями решает и задачу дискретного логарифма, поэтому под удар попадают RSA, классический Диффи-Хеллман и ECC одновременно. Симметричные шифры (AES) и хэши страдают меньше: алгоритм Гровера даёт лишь квадратичное ускорение, и удвоение длины ключа его компенсирует. Прежде чем читать дальше, полезно прикинуть, какая из ваших схем падает первой и какой запас прочности у её ключа.

Модель угрозы «harvest now, decrypt later»

Главная причина спешки - атака «собери сейчас, расшифруй потом». Противник перехватывает и складывает зашифрованный трафик уже сегодня, не имея возможности его прочитать, и ждёт появления криптографически значимого квантового компьютера (CRQC). Когда тот появится, накопленный архив будет расшифрован задним числом. Для данных с длинным сроком конфиденциальности - медицинские записи, гостайна, банковские архивы - это означает, что мигрировать на квантово-устойчивую криптографию нужно задолго до того, как реальный квантовый компьютер заработает.

Отсюда практическое правило оценки риска: сложить срок, в течение которого данные должны оставаться секретными ($X$ лет), время на саму миграцию инфраструктуры ($Y$ лет) и сравнить с прогнозом появления CRQC ($Z$ лет). Если $X + Y > Z$, вы уже опоздали с началом перехода. Это так называемое неравенство Мошки, и оно объясняет, почему стандартизация PQC идёт с опережением реальной угрозы.

На каких задачах строят постквантовую стойкость

Постквантовая криптография опирается на математические проблемы, для которых квантового ускорения уровня Шора пока не найдено. Основных семейств пять.

• Решётчатая криптография. Стойкость задач Learning With Errors (LWE) и Shortest Vector Problem (SVP) на целочисленных решётках в пространстве высокой размерности. Самое практичное и универсальное семейство - даёт и шифрование, и подписи.
• Криптография на кодах. Сложность декодирования случайного линейного кода (задача синдромного декодирования). Старейший подход, McEliece известен с 1978 года и до сих пор не взломан.
• Криптография на хэш-функциях. Подписи строятся только из стойкости хэша к прообразу; самая консервативная гарантия, но подписи громоздкие.
• Многомерная криптография. Системы квадратичных уравнений над конечным полем; компактные подписи, но история взломов настораживает.
• Изогении эллиптических кривых. Очень короткие ключи, однако ключевая схема SIKE была взломана классически в 2022 году, что отрезвило всё семейство.

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

Решётки и задача LWE

Рассмотрим LWE подробнее, потому что это математическое ядро современных квантово-устойчивых схем. Берём секретный вектор $\mathbf{s} \in \mathbb{Z}_q^n$, случайную матрицу $A$ и малый шум $\mathbf{e}$, после чего публикуем

$\mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q.$

Задача восстановить $\mathbf{s}$ по паре $(A, \mathbf{b})$ выглядит как обычная система линейных уравнений, но добавленный шум $\mathbf{e}$ превращает её в задачу поиска ближайшего вектора в решётке - а та считается трудной и для классического, и для квантового компьютера. Уберите шум - и обычное гауссово исключение мгновенно вскроет секрет; именно ошибка делает задачу стойкой. На практике используют структурированный вариант Module-LWE: он сокращает размер ключей за счёт работы с многочленами в кольце $\mathbb{Z}_q[x]/(x^n+1)$, сохраняя ту же стойкость. Параметр $q$ берут небольшим простым, размерность $n$ задаёт уровень безопасности, а распределение шума $\mathbf{e}$ подбирают так, чтобы легитимная сторона расшифровывала сообщение с подавляющей вероятностью, а атакующий без секрета сталкивался с экспоненциально трудной решёточной задачей. Именно эта асимметрия между «знающим секрет» и «угадывающим» лежит в основе схемы инкапсуляции ключей ML-KEM.

Стандарты NIST: ML-KEM, ML-DSA, SLH-DSA

В августе 2024 года NIST выпустил первые финальные стандарты постквантовой криптографии после восьмилетнего открытого конкурса.

• FIPS 203 - ML-KEM (бывший CRYSTALS-Kyber): механизм инкапсуляции ключей на Module-LWE. Это замена Диффи-Хеллмана и RSA-обмена ключами. Уровни ML-KEM-512/768/1024.
• FIPS 204 - ML-DSA (бывший CRYSTALS-Dilithium): схема цифровой подписи на решётках, основная рекомендация для подписей.
• FIPS 205 - SLH-DSA (бывший SPHINCS+): подпись на хэш-функциях как консервативный запасной вариант с другим математическим основанием.

Позже к ним добавили FIPS 206 (FN-DSA на базе Falcon) для случаев, где критичен компактный размер подписи. Разнообразие семейств здесь намеренное: если решётки однажды поддадутся, хэш-подписи останутся стоять.

Криптографическая гибкость и гибридный режим

Переход на квантово-устойчивую криптографию - это не разовая замена библиотеки. Принцип криптографической гибкости (crypto-agility) требует, чтобы система умела менять алгоритм без переписывания протокола. На практике сейчас доминирует гибридный режим: общий секрет вычисляют одновременно классическим X25519 и постквантовым ML-KEM, а затем смешивают через KDF. Такая комбинация остаётся стойкой, пока цел хотя бы один из двух механизмов, и страхует от того, что новая постквантовая схема окажется уязвимой к ещё не найденной классической атаке. Именно гибридный X25519+ML-KEM-768 уже включён в TLS 1.3 в браузерах и серверах.

Частые ошибки

• Путать PQC и квантовую криптографию (QKD). Постквантовые алгоритмы работают на обычных процессорах; QKD - это распределение ключей по оптоволокну через физику фотонов. Это разные вещи.
• Считать, что симметрика тоже под угрозой Шора. AES и SHA уязвимы только к Гроверу с квадратичным ускорением - удвоения длины ключа достаточно, переход на новые шифры не нужен.
• Откладывать миграцию «до появления квантового компьютера». Атака «harvest now, decrypt later» делает уже перехваченный трафик уязвимым задним числом, поэтому ждать нельзя.
• Внедрять чисто постквантовую схему без гибрида. Молодые алгоритмы ещё проходят проверку временем (история SIKE и Rainbow это показала); гибрид с классикой страхует от внезапного взлома.
• Игнорировать рост размеров ключей и подписей. ML-KEM и особенно SLH-DSA заметно крупнее RSA/ECC - это бьёт по embedded-устройствам и размеру TLS-рукопожатия.

FAQ

Существует ли уже квантовый компьютер, ломающий RSA-2048? Нет. По оценкам, для этого нужны миллионы стабильных физических кубитов с коррекцией ошибок, тогда как сегодняшние устройства оперируют сотнями шумных кубитов. Но угроза «собери сейчас - расшифруй потом» делает миграцию актуальной уже сегодня.

Нужно ли менять симметричное шифрование AES? Нет, достаточно перейти на длину ключа $256$ бит. Алгоритм Гровера ускоряет перебор лишь квадратично, поэтому стойкость AES-256 против кванта эквивалентна AES-128 против классики - этого хватает.

Можно ли использовать ML-KEM вместо RSA прямо сейчас? Да, стандарт FIPS 203 финализирован, и рекомендуемый путь - гибридный режим: одновременно классический X25519 и ML-KEM. Так система остаётся защищённой, даже если одна из двух схем окажется уязвимой.

Коротко

Квантово-устойчивая (постквантовая) криптография - это классические алгоритмы на математических задачах, недоступных алгоритму Шора: решётках (LWE), кодах, хэшах. Шор ломает RSA, ECC и Диффи-Хеллмана через факторизацию и дискретный логарифм, поэтому NIST уже стандартизовал ML-KEM, ML-DSA и SLH-DSA. Из-за атаки «harvest now, decrypt later» мигрировать нужно заранее, и безопаснее всего делать это в гибридном режиме классической и постквантовой схемы.