Пост-квантовая криптография
2026-03-10 16:46 Diff

Теги: tls, ssh, криптографическая защита информации, rsa, пост-квантовая криптография, квантовый компьютер, агенство стандартизации nist, ipsec, signal, тотальный взлом, задачи на евклидовых решетках, задачи из теории кодирования, задачи на многомерных полиномах, задача вычисления изогении между абелевыми многообразиями, задача нахождения коллизий хэш-функции

Наверняка, многие, кто так или иначе связан с IT, слышали о том, что квантовый компьютер легко взламывает современные методы криптографии с открытым ключом. Существует множество разрозненных мнений о том, насколько скоро появится квантовый компьютер, способный «взломать» ключи той длины, которой мы пользуемся сегодня — 4096 бит RSA модуль или 256 бит подгруппа для Диффи-Хэллмана.

И всё же Агенство стандартизации NIST решило готовить сани летом и в 2018 году запустило конкурс на лучшие пост-квантовые примитивы. С предложенными кандидатами на пост-квантовую эру мы и познакомимся.

Предисловие

Современная криптография с открытым ключом (TLS, SSH, IpSec, Signal) основана на сложности факторизации больших чисел (RSA) и/или сложности вычисления дискретного логарифма (Диффи-Хэллман). В 1994 году Шор предложил квантовый алгоритм, решающий обе задачи за полиномиальное (от длины входных данных) время.

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

Сложно предсказать, когда мы получим квантовый компьютер, который сможет проводить вычисления с несколькими тысячами кубит. На всякий случай криптографы подготовили альтернативные криптографические примитивы, (предположительно) стойкие к атакам на квантовый компьютер.

Пост-квантовые решения

А именно, место теоретико-числовых задач (таких как факторизация, дискретный логарифм) могут занять:

I. Сложные задачи на евклидовых решетках

А именно, задача нахождения короткого вектора: по данному базису найти кратчайший ненулевой элемент решетки, определенной как

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

Примеры: Frodo, New Hope, Crystals-Kyber, NTRU (для шифрования), Crypstals-Dilithium, Falcon (для цифровой подписи)

II. Сложные задачи из теории кодирования

Задача декодирования спрашивает, по данной матрице вектору и весовому значению найти вектор e, т.ч. He = s и

Плюсы задач теории кодирования: простота понимания, реализации; несколько десятилетий криптоанализа Недостатки: большие размеры ключа и, следовательно, более медленные операции. Отсутствие алгоритма подписи

Примеры: McEliece

III. Сложные задачи на многомерных полиномах

Найти решение (как правило, разряженное) системы уравнений от многих переменных над

Рисунок взят из презентации Albrecht Petzoldt, PQCrypto 2018

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

IV. Задача вычисления изогении между абелевыми многообразиями

По двум (эллиптическим) кривым найти изогению определённой степени Рисунок сделан W.Castryk в этом посте

Плюсы: малые размеры ключей Недостатки: сравнительно мало изученная задача, длительные алгоритмы обмена ключами, подписи еще более неэффективные Примеры: SIKE, CSIDH

V. Задача нахождения коллизий хэш-функции

По сути, усложнение одноразовой подписи Лампорта

Рисунок взят из презентации Andreas Huelsing

Плюсы: небольшие ключи Недостатки: только подпись, сравнительно большой размер подписи

Примеры: SHINCS

Есть вопросы? Пишите в комментариях!