CRYSTALS-Dilithium

CRYSTALS-Dilithium — это криптографический алгоритм цифровой подписи на основе решёток, один из трёх финалистов конкурса постквантовой криптографии, проведённого Национальным институтом стандартов и технологий США (NIST). Алгоритм предназначен для обеспечения аутентичности и целостности данных в условиях, когда квантовые компьютеры станут достаточно мощными, чтобы взломать традиционные криптосистемы, основанные на факторизации целых чисел или дискретном логарифмировании.

История и контекст

Разработка CRYSTALS-Dilithium началась в рамках проекта CRYSTALS (Cryptographic Suite for Algebraic Lattices), который также включал алгоритм шифрования Kyber. Основными авторами являются исследователи из нескольких университетов и компаний, включая IBM Research, ETH Zurich, Калифорнийский университет в Лос-Анджелесе и другие.

Алгоритм был впервые представлен в 2017 году как кандидат на конкурс постквантовой криптографии NIST, объявленный в 2016 году. Целью конкурса было создание стандартов для криптографических алгоритмов, устойчивых к атакам с использованием квантовых компьютеров. После нескольких раундов оценки, в 2022 году NIST объявил CRYSTALS-Dilithium одним из трёх финалистов для стандартизации цифровых подписей, наряду с FALCON и SPHINCS+. В августе 2024 года NIST официально опубликовал стандарт FIPS 204, основанный на CRYSTALS-Dilithium, под названием ML-DSA (Module-Lattice-Based Digital Signature Algorithm).

Принцип работы

CRYSTALS-Dilithium основан на сложности задач, связанных с решётками, в частности на задаче Learning With Errors (LWE) и её модульном варианте Module-LWE. Безопасность алгоритма опирается на вычислительную сложность нахождения короткого вектора в решётке (Shortest Vector Problem, SVP) и решения задачи обучения с ошибками.

Генерация ключей

Процесс генерации ключей включает создание секретного ключа (закрытого ключа), который представляет собой случайный вектор с малыми коэффициентами, и соответствующего открытого ключа, который вычисляется как произведение матрицы и секретного вектора с добавлением небольшой ошибки. Открытый ключ является матрицей или вектором, а закрытый ключ — коротким секретным вектором.

Создание подписи

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

1. Генерацию случайного маскирующего вектора.
2. Вычисление «вызова» (challenge) как хеша сообщения и части маскирующего вектора.
3. Формирование ответа, который объединяет секретный ключ и маскирующий вектор, с учётом вызова.
4. Применение процедуры rejection sampling (отбраковки): если ответ выходит за допустимые границы, процесс повторяется с новым маскирующим вектором. Это гарантирует, что подпись не раскрывает информацию о закрытом ключе.

Проверка подписи

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

Характеристики и параметры

CRYSTALS-Dilithium имеет несколько уровней безопасности, соответствующих стандартам NIST:

Ключевые особенности алгоритма:

• Относительно малый размер подписи по сравнению с другими постквантовыми схемами, такими как SPHINCS+.
• Высокая скорость верификации — проверка подписи выполняется быстрее, чем её создание.
• Детерминированность (опционально) — подпись может быть детерминированной, что упрощает реализацию.
• Устойчивость к побочным каналам — алгоритм спроектирован с учётом защиты от атак по времени и энергопотреблению.

Применение

CRYSTALS-Dilithium (ML-DSA) предназначен для широкого круга приложений, где требуется долгосрочная безопасность цифровых подписей:

• Инфраструктура открытых ключей (PKI) — замена RSA и ECDSA в сертификатах X.509.
• Протоколы TLS — обеспечение аутентификации в интернет-соединениях.
• Цифровые подписи документов — электронные подписи, устойчивые к квантовым атакам.
• Блокчейн и криптовалюты — защита транзакций и смарт-контрактов.
• Обновления программного обеспечения — аутентификация кода и обновлений.

В России, в рамках национальной программы по постквантовой криптографии, также рассматриваются аналогичные алгоритмы на основе решёток, но CRYSTALS-Dilithium не входит в официальные российские стандарты (ГОСТ Р 34.10 и разрабатываемые постквантовые стандарты). Тем не менее, он может использоваться в международных проектах и продуктах, работающих на российском рынке, при условии соответствия требованиям законодательства о криптографии.

Сравнение с другими алгоритмами

CRYSTALS-Dilithium сравнивают с двумя другими финалистами NIST:

• FALCON — также основан на решётках, но использует более сложную математику (NTRU-решётки). FALCON обеспечивает меньший размер подписи (до 666 байт для уровня 5), но его реализация сложнее и требует операций с плавающей запятой.
• SPHINCS+ — основан на хеш-функциях, не требует сложной математики, но имеет значительно больший размер подписи (до 49 856 байт для уровня 5) и более медленную верификацию.

CRYSTALS-Dilithium занимает промежуточное положение: он быстрее FALCON в верификации, проще в реализации и имеет меньший размер подписи, чем SPHINCS+. Это делает его предпочтительным для большинства практических приложений.

Критика и ограничения

Несмотря на широкое признание, у CRYSTALS-Dilithium есть ограничения:

• Размер подписи — хотя он меньше, чем у SPHINCS+, он всё же больше, чем у традиционных схем (RSA: 256 байт, ECDSA: 64 байта). Это может быть проблемой для приложений с жёсткими ограничениями по пропускной способности.
• Сложность реализации — хотя алгоритм проще FALCON, его корректная и безопасная реализация требует глубокого понимания алгебраических решёток.
• Зависимость от стандарта — алгоритм оптимизирован под рекомендации NIST, что может не совпадать с национальными требованиями других стран.

Интересные факты

• Название «Dilithium» отсылает к вымышленному элементу из вселенной «Звёздного пути», используемому для управления варп-двигателями. Это подчёркивает ориентацию алгоритма на «квантовую эру».
• CRYSTALS-Dilithium стал первым постквантовым алгоритмом цифровой подписи, который был реализован в открытом исходном коде и включён в библиотеки OpenSSL и BoringSSL.
• В 2023 году исследователи из IBM и других организаций продемонстрировали реализацию CRYSTALS-Dilithium на смарт-картах и устройствах IoT, подтвердив его пригодность для встраиваемых систем.

Источники

1. NIST FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA). National Institute of Standards and Technology, 2024.
2. Ducas, L., et al. "CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme." IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018.
3. Post-Quantum Cryptography: NIST's Plan for the Future. National Institute of Standards and Technology, 2022.
4. Bernstein, D. J., et al. "Post-Quantum Cryptography: State of the Art." Springer, 2020.