Современная криптография строится на вычислительной сложности ряда математических задач, описываемых в теории чисел. В частности, в асимметричных схемах электронной подписи к таким задачам относятся факторизация (разложение больших чисел на простые сомножители) и дискретное логарифмирование (обратная операция возведению целого числа в степень по модулю простого числа).
Для решения этих задач на сегодня неизвестны быстрые алгоритмы — то есть такие, у которых сложность решения полиномиально зависит от длины входных данных. Напротив, все существующие подходы обладают экспоненциальной зависимостью. Это значит, что при использовании достаточно больших простых чисел подбор ключа потребует выполнения экспоненциально растущего (по мере увеличения размера входных данных) количества битовых операций и/или объёмов памяти. Иными словами, такие алгоритмы невозможно выполнить за разумное время даже на мощных компьютерах классической архитектуры.
Однако сейчас ведутся интенсивные разработки квантовых процессоров, которые смогли бы задействовать принципиально другие алгоритмы. Их появление может сделать нестойкими многие криптографические системы, что ещё в 1994 году показал Питер Шор.
В девяностые это была лишь гипотетическая угроза, поскольку квантовые компьютеры тогда существовали только на бумаге. Ситуация изменилась в 2001 году, когда IBM создала прототип квантового процессора на семи кубитах и выполнила на нём экспериментальную проверку алгоритма Шора.
Сегодня более десятка крупных компаний представили свои варианты квантовых процессоров, а число кубитов растёт с каждым годом. Назрела реальная необходимость готовить почву для перехода к постквантовой криптографии, то есть разрабатывать протоколы, атаки на которые останутся вычислительно сложными даже для квантовых компьютеров.
Проблема стойкости ЭЦП
Постквантовыми электронными цифровыми подписями (ЭЦП) считаются криптографические схемы на решетках, многомерных полиномах, хэш-функциях и кодах, исправляющих ошибки. Тем не менее доказательства стойкости большой части описанных схем опираются на математические задачи, которые не являются доказанно сложными.
Первая схема электронной подписи, чья стойкость базируется на сложности задачи декодирования кода, исправляющего ошибки, появилась в самом начале девяностых годов прошлого века. Однако она оказалась уязвимой. На протяжении десятилетия появлялся целый ряд модификаций этой схемы, но все они также были атакованы в течение нескольких месяцев с момента появления. В какой-то момент в криптографическом сообществе зародилось сомнение, что построение ЭЦП на кодах, исправляющих ошибки, вообще возможно.
В 2001 году для построения подписи на кодах удалось применить универсальный подход, который в том числе используется для построения классической подписи RSA. Идея заключается в шифровании хэш-значения открытого сообщения на секретном ключе отправителя. Для проверки получатель расшифровывает полученное значение при помощи открытого ключа отправителя и сравнивает результат с самостоятельно вычисленным хэшем.
Такой подход породил большое количество схем на кодах. Однако доказательство их стойкости основывается на предположении о неотличимости базового кода от случайного, что на практике часто оказывается неверным. В этом случае использование структуры кода и позволяет строить эффективные атаки.
Еще один успешный метод синтеза ЭЦП, который удалось применить к кодам, исправляющим ошибки, заключается в применении преобразования Фиата-Шамира к схеме идентификации. Если схема обладает свойством нулевого разглашения, то результирующая подпись будет стойкой к подделке. Подписи такого типа строятся на случайном линейном коде, что позволяет не делать при обосновании их стойкости никаких дополнительных предположений.
Перспективные схемы цифровой подписи
30 ноября 2017 года закончился прием заявок конкурса на новые постквантовые алгоритмы, проводимый Национальным институтом стандартов и технологий США (NIST). Все схемы на конкурсе были представлены по двум направлениям: алгоритмы шифрования и инкапсуляции ключа и алгоритмы цифровой подписи. С тех пор идут активный анализ и сравнение поданных схем. По состоянию на осень 2021 года идёт третий раунд конкурса.
Параллельно с NIST собственную разработку алгоритмов криптографии будущего проводит рабочая группа по постквантовым механизмам Технического комитета по стандартизации «Криптографическая защита информации» (ТК26). В рамках работы группы разрабатывается схема электронной подписи «Шиповник», построенная методом применения преобразования Фиата-Шамира к протоколу идентификации Штерна (с нулевым разглашением). Алгоритм выбора параметров подписи базируется на использовании теории доказуемой стойкости.
Подробнее рассказывает Виктория Высоцкая — специалист-исследователь лаборатории криптографии НПК «Криптонит» и один из соавторов этой схемы ЭЦП.
— Почему ваша схема цифровой подписи называется «Шиповник» и с какой целью она создавалась?
— Наша схема была написана в рамках деятельности рабочей группы по постквантовым механизмам ТК26. Эта группа работает на перспективу: разрабатывает криптографические схемы, которые будут стойкими даже при условии существования достаточно мощного квантового компьютера. Мы дали нашей схеме название – «Шиповник», так как хотели подчеркнуть связь со схемой Штерна (отсюда буква «Ш» в начале). Ну, а дальше просто последовали традиции нашей рабочей группы, в которой схемы имеют «растительные» названия – «Крыжовник», «Форзиция» и т.д.
— Подобные схемы рассматривались на конкурсе NIST?
— Близких аналогов нашей схеме в NIST не было представлено. Однако NIST планирует объявить новый конкурс на схемы ЭЦП, среди которых, вполне вероятно, будут схемы, построенные на основе подхода Фиата-Шамира, как и наша.
— Какой уровень стойкости обеспечивает «Шиповник»?
— В текущем варианте проекта стандарта мы предлагаем набор параметров, позволяющих получить доказуемую стойкость, равную 80 битам (это означает, что на такую схему не может существовать атаки со сложностью менее чем 280 битовых операций). Однако мы полагаем, что реальная стойкость сильно превышает это значение, поскольку текущая оценка дает достаточно большую погрешность. Так, лучшая классическая атака на «Шиповник», известная на данный момент, требует 2256 битовых операций, а лучшая квантовая атака – 2170.
— Каковы шансы, что «Шиповник» станет российским стандартом?
— Сейчас мы на финальной стадии подготовки проекта стандарта. В ТК26 пакет документов по «Шиповнику» планируем отправлять в начале декабря. Дальше будем смотреть на комментарии. Пока мы не знаем, что будет стандартизовано: наша схема или ещё какая-то, предложенная в рамках рабочей группы. Возможно также, что стандартизуют сразу несколько вариантов. На данный момент вместе с «Шиповником» на финальной стадии находится «Крыжовник» — схема подписи на решетках. Кроме того, ведутся разработки подписи на хэш-функциях.
— В чём преимущества «Шиповника» перед «Крыжовником»?
— Решётки являются одним из самых перспективных направлений, что прослеживается даже по составу третьего раунда конкурса NIST, где представлено две такие схемы. Однако если сравнивать «Шиповник» и «Крыжовник», то мы выигрываем по размеру ключей и скорости их генерации. Кроме того, стойкость нашей схемы к подделке основана на сложности задачи синдромного декодирования случайного кода, которая является доказанно NP-трудной, в то время как стойкость схемы на решетках сводится в том числе к задаче обучения с округлением, для которой подобный результат отсутствует.
Надо отметить, что соревнование между схемами не совсем уместно, поскольку на данный момент у российского криптографического сообщества нет планов оставить исключительно какую-то одну постквантовую схему ЭЦП. Основной интерес сейчас направлен на развитие максимально большого числа направлений, которые могли бы друг друга подстраховать в случае появления новых атак. Дело в том, что постквантовое направление в криптографии относительно молодо, и пока неизвестно, какая из схем пройдёт проверку временем, а какая нет.
Источник информации: НПК «Криптонит»
Источник фото: ru.123rf.com
