Пост-квантовая криптография | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Python Developer. Professional
-3%
Разработчик на Spring Framework
-5%
iOS Developer. Professional
-8%
Golang Developer. Professional
-6%
Базы данных
-12%
Agile Project Manager
-5%
Android Developer. Professional
-11%
Microservice Architecture
-5%
C++ Developer. Professional
-5%
Highload Architect
-6%
JavaScript Developer. Basic
-8%
Backend-разработчик на PHP
-9%
Архитектура и шаблоны проектирования C# Developer. Professional
-9%
Team Lead
-6%
Kotlin Backend Developer
-9%
Разработчик программных роботов (RPA) на базе UiPath и PIX Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов Node.js Developer Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes iOS Developer. Basic Супер-интенсив «СУБД в высоконагруженных системах» Супер-интенсив "Tarantool"
Инфраструктура
DevOps практики и инструменты
-12%
Базы данных
-12%
Network engineer. Basic
-10%
Network engineer
-4%
Инфраструктурная платформа на основе Kubernetes
-6%
Экспресс-курс по управлению миграциями (DBVC)
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Administrator Linux. Professional
-6%
Разработчик IoT
-13%
Основы Windows Server Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP NoSQL Супер-практикум по использованию и настройке GIT Супер-интенсив «СУБД в высоконагруженных системах» Экспресс-курс «IaC Ansible»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

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 комментариев
Для комментирования необходимо авторизоваться