РАЗРАБОТКА МОДИФИЦИРОВАННОГО АЛГОРИТМА ЦИФРОВОЙ ПОДПИСИ НА ОСНОВЕ СХЕМЫ ДИФФИ–ХЕЛЛМАНА И ИССЛЕДОВАНИЕ ЕГО СВОЙСТВ

​DEVELOPMENT OF A MODIFIED DIGITAL SIGNATURE ALGORITHM BASED ON THE DIFFIE-HELLMAN SCHEME AND AN ANALYSIS OF ITS PROPERTIES

Sokolova Alyona Dmitrievna

Student, Samara National Research University named after Academician S.P. Korolev,

Russia, Samara

Dodonova Natalya Leonidovna

Scientific supervisor, Ph.D (Phys.-Math.), Associate Professor, Samara National Research University named after Academician S.P. Korolev,

Russian, Samara

АННОТАЦИЯ

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

ABSTRACT

In this paper, the author analyzes the problem of protecting the authorship of electronic documents. A modification of the scheme is proposed and justified, based on the use of two independent random parameters and the inclusion of the author’s identifier in the signature hash function. A description of the developed software tool implementing the proposed method is provided. It is shown that the modified scheme eliminates both vulnerabilities with a moderate increase in computational cost.

Ключевые слова: защита информации; программное средство; электронная цифровая подпись; протокол Диффи-Хеллмана; схема Шнорра; идентификатор автора; атака «человек посередине».

Keywords: information security; software tool; digital signature; Diffie-Hellman protocol; Schnorr scheme; author identifier; man-in-the-middle attack.

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

Защита авторства электронных документов остается одной из практических задач информационной безопасности. Средством ее решения служит электронная цифровая подпись, подтверждающая целостность документа и принадлежность подписи владельцу ключа [1]. Большинство применяемых схем хорошо изучены, однако при использовании за пределами идеальных условий ряд их свойств требует уточнения. В частности, классические схемы надежно подтверждают неизменность документа, но слабо гарантируют, что подпись поставлена именно заявленным лицом.

Настоящая работа посвящена разработке программного средства защиты авторства документов, в основу которого положена схема Шнорра [2], построенная над ключевой парой протокола Диффи-Хеллмана [3; 4, с. 229]. Эта комбинация отличается простотой формирования и проверки подписи и строгим математическим обоснованием. В отличие от жёстко стандартизированных DSA и ElGamal, эта основа допускает введение дополнительных параметров без нарушения математической корректности, что делает её удобной для исследовательской модификации.

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

Генерация ключа и базовая схема подписи

Стойкость средства опирается на вычислительную сложность задачи дискретного логарифма [2; 3]. Открытыми параметрами системы служат:

• большое простое число порядка 2048 бит;
• простое число , являющееся делителем ;
• генератор порядка .

Закрытый ключ x выбирается случайно из интервала и хранится в секрете. Открытый ключ вычисляется как:

.                                     (1)

При известных y, g, и p восстановление x вычислительно неразрешимо. Подпись документа M в базовой схеме Шнорра формируется в четыре шага:

1) выбирается случайное число ;

2) вычисляется обязательство ;

3) вычисляется значение ;

4) вычисляется число .

Подписью служит пара [1]. Проверка состоит в восстановлении

и повторном вычислении хеша с последующим сравнением его с .

Первая уязвимость вытекает из формулы:

.                       (2)

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

Вторая уязвимость носит протокольный характер. Базовая подпись подтверждает принадлежность ключу , но не указывает, кому этот ключ принадлежит. При перехвате канала противник заменяет открытый ключ на собственный , и проверка получателя завершается успешно. Этот сценарий соответствует так называемой «атаке посредника» (man-in-the-middle), при которой, как отмечают Фергюсон и Шнайер, злоумышленник «может вклиниться в протокол, имитируя пользователя Б при общении с пользователем А, а также имитируя пользователя А при общении с пользователем Б» [4, с. 233].

Модифицированная схема подписи

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

                           (3)

Подпись содержит два значения и . Использование двух случайных параметров вместо одного усложняет атаки, при которых ключ вычисляют из-за повтора или утечки случайного числа. Чтобы раскрыть закрытый ключ, противнику теперь нужно узнать оба параметра, а не один, поэтому схема менее чувствительна к сбоям генератора случайных чисел.

Во-вторых, вводится идентификатор автора:

                                     (4)

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

Идея привязки подписи к идентификатору подписанта восходит к концепции идентификационной криптографии, предложенной Шамиром [5]; в отличие от неё, здесь идентификатор не заменяет открытый ключ, а включается дополнительным аргументом хеш-функции.

Корректность проверки сохраняется, что подтверждается формулой (5):

.    (5)

Программное средство

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

Функциональные возможности средства разделены на пять режимов:

• подписание документа: пользователь указывает файл, вводит фамилию и организацию и получает файл подписи;
• проверка подписи по исходному документу и файлу подписи с выводом результата;
• сравнение базовой и модифицированной схем на одинаковых входных данных;
• моделирование атаки «человек посередине» для обеих схем;
• справочный режим с пояснением используемых понятий.

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

Рисунок 1. Основное окно средства в режиме подписания документа

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

В окне проверки подписи при нажатии кнопки «Проверить» система загружает параметры из файла подписи, вычисляет хеш файла и выполняет верификацию (рисунок 2).

Рисунок 2. Окно проверки подписи с отображением результата

Результат отображается в виде сообщения: «Подпись верна» при совпадении хеш-значений или «Подпись отклонена» с указанием причины отклонения, а также дополнительной информации.

Сопоставление базовой и модифицированной схем, реализованных в средстве на одинаковых параметрах, приведено в таблице 1.

Таблица 1.

Сравнение базовой и модифицированной схем

Сравнение базового и модифицированного алгоритма показывает, что усиление защиты достигается без значимых потерь в производительности: для каждой операции время в базовой и модифицированной схемах практически совпадает (различия лежат в пределах погрешности измерений). Платой за повышенную стойкость к MitM-атаке и привязку к автору становится увеличение размера подписи примерно вдвое со 154 до 307 символов, что является приемлемым компромиссом для большинства практических задач защиты авторства электронных документов.

Заключение

В настоящей работе предложена модификация алгоритма цифровой подписи на основе схемы Шнорра над ключевой парой протокола Диффи-Хеллмана. Модификация включает два независимых изменения: использование двух случайных параметров вместо одного и включение идентификатора автора в хеш-функцию подписи. Аналитически обосновано, что первое изменение повышает устойчивость к раскрытию закрытого ключа при компрометации одного случайного параметра, а второе обеспечивает обнаружение подмены открытого ключа и тем самым противодействует атаке «человек посередине».

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

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

Список литературы:

1. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography / A. Menezes, P. van Oorschot, S. Vanstone. – Boca Raton : CRC Press, 1996. – 780 p.
2. Schnorr C. P. Efficient signature generation by smart cards / C. P. Schnorr // Journal of Cryptology. 1991. Vol. 4, № 3. P. 161–174.
3. Diffie W., Hellman M. New directions in cryptography / W. Diffie, M. Hellman // IEEE Transactions on Information Theory. 1976. Vol. 22, № 6. P. 644–654.
4. Фергюсон Н., Шнайер Б. Практическая криптография : пер. с англ. / Н. Фергюсон, Б. Шнайер. – М. : Издательский дом «Вильямс», 2004. – 432 с.
5. Shamir A. Identity-Based Cryptosystems and Signature Schemes / A. Shamir // Advances in Cryptology – CRYPTO '84 : Lect. Notes in Computer Science, vol. 196. – Berlin ; New York : Springer, 1984. P. 47–53.