Пост-квантовая криптография | OTUS

Курсы

Курсы в разработке Подготовительные курсы
Работа в компаниях Компаниям Блог +7 499 110-61-65

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

Crypto_Deep_28.5_site-5020-34ee5f.png

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

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

Предисловие

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

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

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

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

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

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

А именно, задача нахождения короткого вектора: по данному базису CodeCogsEqn-5020-75d183.pngнайти кратчайший ненулевой элемент решетки, определенной как CodeCogsEqn__1-5020-0baf43.png

PostQuantum_Lattice-36085-e32052.png

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

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

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

Задача декодирования спрашивает, по данной матрице CodeCogsEqn__2-5020-d06f0a.pngвектору CodeCogsEqn__3-5020-9c1bc1.pngи весовому значению CodeCogsEqn__4-5020-6df92c.pngнайти вектор e, т.ч. He = s и CodeCogsEqn__5-5020-ab4ab8.png

PostQuantum_ISD-36085-833706.png

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

Примеры: McEliece

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

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

PostQuantum_MVQ-36085-9152d4.pngРисунок взят из презентации Albrecht Petzoldt, PQCrypto 2018

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

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

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

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

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

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

PostQuantum_HashBased-36085-0709f5.png

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

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

Примеры: SHINCS

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

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться