Постквантовые криптографические алгоритмы цифровой подписи: сравнительный анализ и главные проблемы

Выполнил: Качмазов Руслан Александрович

После открытия алгоритма Шора стало понятно, что большинство из используемых сегодня ассиметричных криптографических схем могут быть скомпрометированы при появлении достаточно мощного квантового компьютера, так как они основаны на проблеме дискретного логарифмирования и факторизации чисел, например, RSA и ECDSA. Учитывая то, что сфера квантовых вычислений активно развивается, криптографическое сообщество начало думать о внедрении новых алгоритмов, способных противостоять такого рода атакам — эта сфера была названа постквантовой криптографией. В основном, постквантовые алгоритмы строятся на задачах теории целочисленных решеток, кодов исправления ошибок, хэш-функций, систем многочленов от многих переменных, изогении элиптических кривых, теории кос и других.

В 2016 году NIST учредил конкурс, в котором отбирал алгоритмы инкапсуляции ключа (KEM) и цифровой подписи, результатом которого стали 3 финалиста в рамках цифровой подписи: CRYSTALS-Dilithium (решетки), SPHINCS+ (хэш-функции) и Falcon (решетки). Отечественная криптография не осталась в стороне, и в рамках ТК26 была создана рабочая группа 2.5, занимающаяся постквантовой криптографией. Одними из представленных алгоритмов стали Гиперикум (хэш-функции) и Шиповник (коды ошибок).

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

Презентация (Качмазов) (PDF, 924 Кб)

Ссылка на репозиторий на GitLab