Theoretical possibilities for combining various mathematical primitives within an electronic digital signature scheme.

Komarova Antonina Vladislavovna Graduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 196244, Russia, Saint Petersburg, ul. Tipanova, d. 29 piter-ton@mail.ru Korobeynikov Anatolii Grigor'evich Doctor of Technical Science Professor, Department of Design and Security of Computer Systems, St. Petersburg National Research University of Information Technologies, Mechanics 196631, Russia, g. Saint Petersburg, ul. Kronverkskii Prospekt, 49 korobeynikov_a_g@mail.ru Menshchikov Aleksandr Alekseevich Graduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, Saint Petersburg, Kronverkskii prospekt, 49 menshikov@corp.ifmo.ru Klyaus Tat'yana Konstantinovna Graduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, g. Saint Petersburg, Kronverskkii prospekt, 49 t_klyaus@corp.ifmo.ru Negol's Aleksandr Valer'evich Graduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, g. Saint Petersburg, ul. Kronverkskii Prospekt, 49 dozory07@yandex.ru

Sergeeva Anastasiya Aleksandrovna Graduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, Saint Petersburg, Kronverkskii prospekt, 49 aasergeeva@corp.ifmo.ru

Введение

Информационные технологии с каждым годом все больше набирают свою значимость в современном мире. Для успешного функционирования любых организаций, будь то коммерческие или государственные структуры, требуется непрерывная защита циркулирующей в них информации. Существуют проблемы обеспечения аутентификации информации, обеспечения аутентичности информации и обеспечения конфиденциальности информации. Как известно, все эти задачи решаются с помощью электронной цифровой подписи (далее - ЭЦП). В связи с этим, постоянная доработка и модернизация существующих алгоритмов и стандартов ЭЦП имеет определяющее значение для функционирования государственных и коммерческих организаций. Стойкость всех криптографических алгоритмов ЭЦП основывается на трудности решения определенной криптографической задачи. Так, известный во всем мире криптографический алгоритм RSA основан на задаче факторизации. А схема Эль-Гамаля, как известно, основана на задаче дискретного логарифмирования в простом конечном поле. Трудоемкими для взлома в настоящий момент считаются алгоритмы и протоколы, основанные на задаче дискретного логарифмирования на эллиптических кривых (далее – ЭК) ^[1].

Также хочется отметить возрастающий интерес к алгоритмам, предположительно стойким к квантовым вычислениям, так называемым алгоритмам «постквантовой криптографии» ^[2]. В частности, к таким протоколам можно отнести протоколы цифровой подписи: Гольдвассера-Гольдштейна-Халеви (GGH) ^[3], Миссиансио-Вадхена ^[4], Миссиансио-Любашевского ^[5], NTRUSign ^[6] и др. Таким образом, для повышения трудоемкости взлома, предлагается использовать алгоритм, основанный одновременно на двух вычислительно сложных задачах, а именно на примитивах теории решеток, относящейся к постквантовой криптографии, и на задаче дискретного логарифмирования на эллиптических кривых (ЭК).

В настоящее время в современной криптографии существуют следующие проблемы:

1. Ограниченное количество основополагающих «трудных» задач, на которых базируются используемые схемы. Данное ограничение ведет к тому, что количество рабочих схем криптографии с открытым ключом весьма невелико.
2. Увеличение необходимого размера для блока данных, а также ключей, связанные с прогрессом математики, а также вычислительной техники.
3. Потенциальная ненадежность базиса. На данный момент рассматривается возможность решение задачи данного типа за полиномиальное время. Теория вычислительной сложности уже доказала связь вычислительно сложных задач между собой. Данное доказательство означает, что если хотя бы на одну из современных криптосистем будет проведена успешная атака, то и большинство остальных систем могут не устоять.
4. Проблема криптографии в эру квантовых компьютеров. Алгоритм Шора утверждает, что после наступления эры квантовых компьютеров, многие криптографические схемы могут потерять свою актуальность в связи со значительным увеличением вычислительной мощи ^[1].

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

Схема ЭЦП общепринято состоит из трех основных этапов ^[7]:

1. Генерация ключей (подписи и проверки);
2. Формирование подписи;
3. Проверка подписи.

Далее представим описание процедур формирования и проверки ЭЦП в общем виде.

Для того чтобы подписать некоторое сообщение M, пользователь должен сгенерировать секретный ключ х и по нему сформировать открытый ключ y, который будет храниться в справочнике открытых ключей в открытом доступе. Эта процедура выполняется один раз при вычислении или смене секретного ключа. Специальный алгоритм Sign, на вход которого подаются подписываемое сообщение М и секретный ключ х, формирует подпись S к сообщению М. Данный процесс проиллюстрирован на рисунке 1.

Рисунок 1. Общая схема процедуры формирования ЭЦП S к сообщению M

Для выполнения процедуры проверки подписи к сообщению М пользователь получает открытый ключ у автора сообщения, находя его в справочнике открытых ключей. Далее он с помощью специального алгоритма проверки подписи Verify, на вход которого подаются сообщение М, подпись S к нему и открытый ключ у подписывающего производит проверку, является ли автор сообщения тем, за кого себя выдает. Если алгоритм Verify возвращает положительный ответ, то владелец открытого ключа у признается автором ЭЦП к сообщению М.

Рисунок 2. Общая схема процедуры проверки подлинности ЭЦП S к сообщению M

Схематично подписанное сообщение, согласно ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» можно представить так, как показано на рисунке 3 ^[7].

Рисунок 3. Схематическое представление подписанного сообщения

ЭЦП относится к условно стойким криптографическим преобразованиям, т.к. их стойкость основывается на высокой вычислительной сложности решения некоторой криптографической задачи.

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

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

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

Криптостойкость алгоритмов с использованием решеток, как и современных алгоритмов асимметричной криптографии, основана на трудной математической задаче ^[2].

Решетка – это совокупность точек в n-мерном пространстве с периодической структурой ^[5]. Более точно решетку L можно определить как абелеву подгруппу, заданную в пространстве Rm.

Пусть базис решетки `B={b_(1)... b_(n)}` задан линейно неза­висимыми векторами, тогда под решеткой будем понимать множество целочисленных линейных комбинаций этих векторов.

К трудным задачам теории решеток можно отнести следующие:

1. Задача поиска наикратчайшего вектора решетки - SVP (Shortest vector problem). По базису решетки B требуется найти кратчайший ненулевой вектор x, принадлежащий этой решетке (Рис.4). SVP-задача является NP-полной задачей, и является наиболее перспективной для использования в протоколах безопасности ^[8].

Рисунок 4. Поиск кратчайшего вектора решетки

2. Задача приближенного поиска кратчайшего вектора решетки - `SVP_(Gamma)` (γ -approximation shortest vector problem). По базису решетки B и вещественному γ>0 требуется найти ненулевой вектор x, принадлежащий этой решетке, с p-нормой (Рис.5).

Рисунок 5. Приближенный поиск кратчайшего вектора решетки

3. Задача поиска ближайшего вектора решетки - CVP (Closest vector problem). По базису решетки B и некоторому векторуy требуется найти ближайший к y вектор x, принадлежащий этой решетке (Рис.6).

Рисунок 6. Поиск ближайшего вектора решетки

4. Задача приближенного поиска ближайшего вектора решетки - `CVP_(Gamma)` (γ - approximate closes vector problem). По базису решетки B, вещественному γ>0 и некоторому векторуy требуется найти ближайший к y вектор x, принадлежащий этой решетке, с p-нормой (Рис.7).

Рисунок 7. Приближенный поиск ближайшего вектора решетки

5. Задача поиска уникального кратчайшего вектора – `uSVP_(gamma)` (γ - approximate unique shortest vector problem). По базису решетки, в которой кратчайший вектор x в k раз меньше другого кратчайшего линейно независимого вектора y, необходимо найти кратчайший вектор (Рис.8).

Рисунок 8. Поиск уникального кратчайшего вектора

6. Задача приближенного поиска кратчайших линейно независимых векторов - `SIVP_(gamma)` (γ - approximate shortest independent vector problem). Для данной n-мерной решетки требуется найти набор линейно-независимых векторов , принадлежащих решетке, с p-нормой (Рис.9).

Рисунок 9. Приближенный поиск кратчайших линейно независимых векторов

В 1985 году Нил Коблиц и Виктор Миллер независимо предложили использовать в криптографии некоторые алгебраические свойства эллиптических кривых (ЭК). С этого момента началось бурное развитие нового направления в криптографии, для которого используется термин криптография на ЭК. В настоящее время лучшие алгоритмы имеют экспоненциальное время работы, в отличие от алгоритмов для решения проблемы простого дискретного логарифма и проблемы факторизации целого числа, которые имеют субэкспоненциальное время работы. Это означает, что в системах на ЭК желаемый уровень безопасности может быть достигнут при значительно меньшей длине ключа, а для современной криптографии актуальна проблема повышения стойкости и уменьшения размера блоков данных ^[9].

В общем случае для нахождения дискретного логарифма на ЭК можно использовать все универсальные методы дискретного логарифмирования, которые не используют специфических свойств структуры группы. Специфических алгоритмов на ЭК пока не придумано, благодаря этому ЭЦП на ЭК является наиболее стойкими при заданном уровне сложности генерации подписи. Наиболее эффективными считаются алгоритмы Сильвера-Полига-Хеллмана ^[10] и p-метод Полларда ^[11]. Сложность первого алгоритма по времени `W(t)=O(logp)^(c)`, а по памяти `W(m)=Osqrt(r)` . p-метод Полларда имеет аналогичную сложность по памяти, но меньшую сложность по времени: `W(m)=Olog(p)`. В обоих случаях r – это наибольший простой делитель порядка мультипликативной группы p-1, с – положительная константа.

Следует отметить, что стойкость действующих государственных стандартов Российской Федерации ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» ^[7], а так же ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хэширования» ^[12] основана именно на задаче дискретного логарифмирования на эллиптических кривых.

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

Анализ представленных выше математических примитивов позволяет сказать, что безопасность алгоритмов ЭЦП зависит от двух факторов:

1. От текущей стойкости алгоритма, зависящей от сложности лучшего из известных методов решения трудной задачи, положенной в основу алгоритма;

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

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

Р (взлом задачи поиска наикратчайшего вектора решетки) `cong10^(-8)` ;

Р (взлом задачи дискретного логарифмирования на ЭК) `~=10^(-8)` .

Вероятность одновременного взлома задачи поиска наикратчайшего вектора решетки и задачи дискретного логарифмирования на ЭК равна произведению вероятностей взлома каждой задачи в отдельности, а именно `cong10^(-16)`.

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

Механизм комбинирования двух вычислительно трудных задач в одной схеме был предложен в работе ^[13], поэтому предложенный авторами подход представляется интересным и возможным в реализации.

В работах ^[14-16] представлены некоторые алгоритмы и протоколы ЭЦП, одновременно опирающиеся на сложность нескольких трудных задач. Это как протоколы коллективной подписи ^[14], так и новые алгоритмы ^{[15, 16]}. Следует отметить, что в данных работах освещаются вопросы комбинирования в одной схеме двух трудных задач, относящихся к асимметричной криптографии.

Авторы данной статьи предлагают использовать задачу постквантовой криптографии для повышения стойкости схем ЭЦП. Данный подход актуален не только в силу возможного появления квантового компьютера, но и для повышения стойкости современных алгоритмов к криптоанализу и к растущим вычислительным мощностям.

В данной работе рассматривается подход к комбинированию двух различных математических примитивов в одной схеме электронной цифровой подписи. Это задача поиска наикратчайшего вектора решетки (Shortest Vector Problem) и задача дискретного логарифмирования на эллиптических кривых. Также в статье освещается актуальность данного вопроса для современной криптографии. В силу важности проблемы, авторы полагают, что данная статья может быть интересна для обсуждения даже на теоретическом уровне. В будущем авторами планируется реализация данного подхода и создание рабочего алгоритма электронной цифровой подписи.